18. Операции разности и импликации.
Разностью множеств A и B, это множество, которое вошло в A, но не вошло в B:
А – В = {1,2,4,6} – {3,4,8,9,2} = {1,6} = C1
Дополнение к разности называется импликацией
-
импликация
A \ B (A - B) A → B
Таблицы истинности:
Разность |
|
Импликация |
||||
X1 |
X2 |
Y = X1 - X2 |
|
X1 |
X2 |
Y = X1→X2 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
Для данных операций можно записать:
19. Операции симметрической разности и эквивалентности.
Симметрическая разность двух множеств А и В – это объединение следующих двух разностей, то есть
А + В = (А - В) v (B - A) = {1,6} v {3,8,9}= {1,3,6,8,9} = C1 v C2
Д ополнительной к данной операции является операция эквивалентности, которая определяется теми же элементами множества А и В, которые являются для них общими, при этом элементы не входящие ни в А ни в В также являются эквивалентными.
Симметричная разность Эквивалентность
A + B A ~ B
Разность |
|
Импликация |
||||
X1 |
X2 |
Y = X1 + X2 |
|
X1 |
X2 |
Y = X1 ~ X2 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
Симметричную разность имеет другие названия: строгая дизъюнкция, исключительная альтернатива, сложение по модулю.
Из определения операции симметричной разности и эквивалентности следует:
20. Формы представления булевых функций (сднф, скнф, спнф).
Любую
булеву функцию y=f(a,b)
можно представить как комбинацию
областей:
Тогда
в зависимости от значения функций и
заданных
,
которые именуются констинтуентами,
получим 16-ть конечных операций, которые
в общем виде можно записать:
Такая форма представления называется СДНФ (совершенно-дизъюнктивная нормальная форма)
В ней констинтуенты – коньюнты соединяются с помощью дизъюнкции.
В логике Буля действует принцип двойственности, который говорит, если одновременно заменить все конъюнкции на дизъюнкции, или наоборот (все ^ на v), замене символов (конъюнкция на дизъюнкцию и 0 на 1), то все логические равенства остаются в силе.
Такая форма представления логических функций называется СКНФ (совершенная коньюктивная нормальная форма). В ней констинтуенты – дизъюнкты, соединяются с помощью конъюнкции.
Существует также третья форма представления логических функций СПНФ – совершенная полиномиальная нормальная форма. Ее можно получить из СДНФ путем следующей замены:
Так как СДНФ все констинтуенты не пересекаются, то можно записать:
