Похожие презентации:
Решение логических задач
1. Решение логических задач
2.
Задача. Методом резолюций проверьтесправедливость следующих рассуждений.
Допустим, что если руководство вуза
действует по закону высшей школы, то
студент-задолжник не отчисляется, если он
является задолжником не более одного
месяца
или
преподаватель-экзаменатор
уходит в отпуск. Не будет ли отчислен
студент-задолжник, если руководство вуза
действует по закону высшей школы и сессия
только что закончилась?
3.
Решение.Введем
обозначения
для
следующих высказываний:
D = «руководство вуза действует по закону
высшей школы»;
S = «студент-задолжник отчисляется»;
P = «преподаватель-экзаменатор уходит в
отпуск»;
T = «студент является задолжником не более
одного месяца».
Первое утверждение задачи
4.
Сформулированное в вопросе задачиутверждение
выражается
следующим
сложным высказыванием:
По условию задачи требуется определить,
выполняется ли логическое следование
5.
Рассмотрим множество дизъюнктов полученнойКНФ формулы
и построим резолютивный вывод значения 0 из
этого множества S.
6. Алгебра логических значений
7.
Определение. Алгеброй называется непустоемножество A с фиксированным набором операций
f1,f2,…,fk,
имеющих
соответствующие
определенные
арности n1,n2,…,nk. При этом
множество A называется базисным множеством
алгебры и набор символов операций ={f1,f2,…,fk}
соответствующей арности n1,n2,…,nk называется
алгебраическим типом (или сигнатурой) алгебры.
Такая
алгебра
сокращенно
обозначается
(A;f1,f2,…,fk ), или (A; ), или просто буквой A и
называется алгеброй типа , или сокращенно алгеброй.
8.
Пример алгебры дает множество {0,1}истинностных значений высказываний с nарными операциями F , которые являются
функциями истинностных значений формул
X 1 ,..., X n ,
логики
высказываний
образованных с помощью n пропозициональных
переменных X 1 ,..., X n .
X
Формула
определяет
унарную
операцию F F X (x) , которая обозначается
символом x и называется отрицанием или
дополнением переменной x .
9.
Формулы X Y , X Y определяютбинарные операции F FX Y ( x, y) , F FX Y ( x, y ) ,
которые обозначаются соответственно символами
x y,x y
и называются дизъюнкцией и
конъюнкцией переменных x ,y.
Операция x y иногда называется также
объединением или суммой переменных x ,y и
обозначается соответственно через x y или
x y.
Операция x y иногда называется также
пересечением или произведением переменных x ,y
и обозначается соответственно через x y или
x y.
10.
Алгебра B=({0,1}, , , ) впервые была введенав 19-ом веке английским математиком Дж.Булем с
целью применения в логике математических
методов.
Поэтому эта алгебра называется алгеброй Буля
или алгеброй логических значений.
11.
Теорема.Алгебра
Буля
B=({0,1}, , , )
удовлетворяет свойствам:
1) a (b c) (a b) c , a (b c) (a b) c –
ассоциативность дизъюнкции и конъюнкции;
2) a b b a , a b b a – коммутативность
дизъюнкции и конъюнкции;
a a a
3) a a a ,
–
идемпотентность
дизъюнкции и конъюнкции;
4) a (b c) (a b) (a c) , a (b c) (a b) (a c)
– дистрибутивность соответственно конъюнкции
относительно
дизъюнкции
и
дизъюнкции
относительно конъюнкции;
12.
5) (a ) a – идемпотентность дополнения;6) (a b) a b , (a b) a b – законы де
Моргана;
a (a b) a
7) a (a b) a ,
–
законы
поглощения;
8) a a 1 , a a 0
– характеристическое
свойство дополнения,
a 1 a
9) a 1 1 ,
– характеристическое
свойство наибольшего элемента 1,
10) a 0 a , a 0 0 – характеристическое
свойство наименьшего элемента 0.
13. Булевы многочлены и булевы функции
14.
Для описания алгебраических свойств булевыхалгебр
используются
формулы,
которые
называются булевыми многочленами и которые
образованы
из
булевых
переменных
x,y,…(принимающих значения 0,1) и символов
булевых операций +, , по следующим правилам:
1)
все булевы переменные x,y,… и символы 0,1
– булевы многочлены;
2)
если p и q – булевы многочлены, то
таковыми являются выражения
p q , p q , p .
15.
Если p образован с помощью x1 ,..., xn , то онобозначается p( x1,..., xn ) .
Множество всех булевых многочленов от n
переменных обозначим Pn .
Если в p( x1,..., xn ) вместо переменных x1 ,..., xn
подставить произвольные значения a1 ,..., an из
множества B, то в результате вычислений
получится некоторый элемент p(a1,..., an ) алгебры B.
Каждый булев многочлен p( x1,..., xn ) определяет
отображение p : Bn B , которое называется булевой
полиномиальной функцией, определяемой булевым
многочленом p( x1,..., xn ) .
16.
p, q PnОпределение. Булевы многочлены
называются
эквивалентными,
если
они
определяют одну и ту же булеву полиномиальную
функцию, т.е. p q .
Символическая запись: p ~ q или просто p q .
Бинарное
отношение
~
является
эквивалентностью на множестве Pn .
Классы эквивалентности p {q Pn : p ~ q} ,
образуют фактор-множество Pn / ~ { p : p Pn } .
Полные системы представителей этого фактормножества называются системами нормальных
форм булевых многочленов.
17.
Для булевой переменной x и {0,1} положим:x, если 1,
x
x , если 0.
x
называется литерой.
Выражение
Литера или конъюнкция (соответственно,
дизъюнкция) литер называется конъюнктом
(соответственно, дизъюнктом).
Конъюнкт (дизъюнкт) называется совершенным,
если он содержит все булевы переменные
рассматриваемой формулы.
18.
Дизъюнкт или конъюнкция (совершенных)дизъюнктов
называется
(совершенной)
конъюнктивной нормальной формой. Сокращенно
КНФ и СКНФ, соответственно.
Конъюнкт или дизъюнкция (совершенных)
конъюнктов
называется
(совершенной)
дизъюнктивной нормальной формой. Сокращенно
ДНФ и СДНФ, соответственно.
19.
Теорема. Любая булева функция f:Bn Bявляется булевой полиномиальной функцией
следующих булевых многочленов:
pf
f 1,..., n x1
1
1 ,..., n B n
n
...xn
и
qf
( f 1,..., n x1
1
1 ,..., n B
n
n
... xn )
.
20.
Следствие 1. Если булева функция f:Bn B неравна тождественно нулю, то она является
булевой полиномиальной функцией следующей
совершенной дизъюнктивной нормальной формы
pf
1
n
x1 ...xn
1 ,..., n B n ,
f 1 ,..., n 1
,
которая называется совершенной дизъюнктивной
нормальной формой (сокращенно СДНФ)
функции f .
21.
Следствие 2. Если булева функция f:Bn B неравна тождественно единице, то она является
булевой полиномиальной функцией следующей
совершенной конъюнктивной нормальной формы
qf
1
( x1 ... x n n )
1 ,..., n B n ,
f 1 ,..., n 0
,
которая называется совершенной конъюнктивной
нормальной
формой
(сокращенно
СКНФ)
функции f .
22.
Алгоритм нахождения СДНФ и СКНФ функцииf:Bn B:
1. Составить таблицу значений функции f и
добавить к ней два дополнительных столбца с
заголовками «Совершенные конъюнкты» и
«Совершенные дизъюнкты».
2. Если при значениях x1 k1,..., xn kn значение
функции f равно 1, то в соответствующей строке
таблицы в столбце «Совершенные конъюнкты»
k1
x1 ...xnk n
записать
конъюнкт
и в столбце
«Совершенные дизъюнкты» сделать прочерк (при
1
0
x
x
x
x ).
этом
и
23.
3. Если при значениях x1 m1,..., xn mn значениефункции f равно 0, то в соответствующей строке таблицы
в столбце «Совершенные дизъюнкты» записать
дизъюнкт x1m1 ... xnmn и в столбце «Совершенные
конъюнкты» сделать прочерк.
x1
…
xn
...
f x1 ,..., xn
…
…
…
…
…
…
…
...
...
...
...
...
…
1
…
0
…
k1
…
m1
…
kn
…
mn
…
Совершенные Совершенные
конъюнкты
дизъюнкты
…
…
–
x1k1 ...xnk n
…
–
…
x1m1 ... xnmn
…
…
24.
4. Дизъюнкция полученных совершенныхконъюнктов
k1
kn
x1 ...xn
+…
является СДНФ функции f , конъюнкция
полученных совершенных дизъюнктов
( x1m1 ... xnmn ) ...
является СКНФ функции f .
25. Системы булевых функций
26.
Операция отрицания является одной изчетырех булевых функций от одной переменной,
которые перечисляются в следующей таблице:
x
f1 ( x)
f 2 ( x)
f 3 ( x)
f 4 ( x)
0 0
0
1
1
1 0
1
0
1
27.
Операции дизъюнкция + и конъюнкция являютсяпримерами двух из шестнадцати булевых функций от
двух переменных, которые перечисляются в следующей
таблице:
x y
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
f16
0 0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0 1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1 0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1 1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
x
y
+
y
x
1
Функция f15 ( x, y ) f 2 ( x, y )
обозначается x | y .
f 9 ( x, y ) f8 ( x, y )
Функция
обозначается x y .
штрих
-
Шеффера,
стрелка
Пирса,