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