2020-07-12
137
Функции конъюнкции и дизъюнкции обладают рядом свойств, аналогичных свойствам обычных операций умножения и сложения. Для этих функций имеют место следующие законы:
1)сочетательный 
;
;
2)переместительный 
;
3)распределительный 
;
Рассмотрим теперь ряд простых, но весьма важных соотношений:
Как обобщение из формул (1 – 8) и (1 – 9) получаем следующие формулы, обычно называемые формулами де Моргана:
(1 – 14)
(1 – 15)
Свойства сложения по модулю два, импликации и функции Шеффера и Вебба.
Свойства функции сложения по модулю два и функции импликации часто бывают полезными при анализе и синтезе различных дискретных устройств.
(1 – 16)
Имеют место также очевидные соотношения:
(1 – 17)
В отличие от всех ранее рассмотренных функций для импликации не имеют места переместительный и сочетательный законы:
|
|
(1 – 18)
=x 
y 
p 
z 
x/y 
z 
p 
x,
=y x z p/x y z p x,
=p 
y z x y/z p x 
y,
=x y z/p x z y p x,
=z p y p x/z p y x,
=x y z p/x z y p x,
=y p z x y p/x y z,
=x/y z p x z p y z,
=p z y x y z p x/y,
=x y z p x y x z/p,
=y p z x y z/p y x,
=p z/x y z p x y p,
=p 
z y x y z/p x z,
=x z p p y z/p 
z y,
=p x z/y x p z y p,
=z x y p 
x z/x y z,
=x/p y z x y z p x,
=y p/x x z p y p z,
=z y x/p z p x y z,
=p y z x z/p y x y,
=x y z/p x y z p x,
=z p x y x/z y p x,
=y p x/z y x y p z,
=x y p z x y z/p y,
=z p x y x/y z p z,
=x y p z y x/y p z,
=z p y z/y x y p z,
=x y z p x/y x z p,
|
=z p y z p x y/z x,
Пример 1-4. Формулы: 
и 
- дизъюнкты. Формулы 
и 
- конъюнкты, а 
одновременно является и дизъюнктом, и конъюнктом.
Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).
Пример 1-5. Формула 
- ДНФ, формула 
- КНФ, а формула 
является одновременно КНФ и ДНФ.
Теорема 3. 1. Любая формула эквивалента некоторой ДНФ.
2. Любая формула эквивалента некоторой КНФ.
