,
,
,
,
,
,
, 
,
,
,
,
, последние два тождества называются правилами де Моргана.
Эти правила можно обобщить для нескольких аргументов:
, 
.
Правила поглощения: 
,
,
, 
.
Правила склеивания по переменной 
: 
, 
.
Вынесение за скобки: 
, 
.
Свойства функций Шеффера, Пирса, суммы по модулю 2.
,
, 
,
,
, 
.
,
.
Для функций Шеффера и Пирса имеет место переместительный закон:
, 
,
Но сочетательный закон для них НЕ справедлив!
,
,
, 
,
,
,
,
,
,
.
Существуют тождества похожие на правила де Моргана:
,
.
На практике часто возникает необходимость преобразовать функцию, аргументы которой связаны операцией Шеффера или Пирса к выражению, содержащему только операции конъюнкции, дизъюнкции и отрицания. Если символы отрицания расположены над одиночными символами переменных, то такая булева функция называется нормальной. Именно такие представления функций наиболее просто воспринимаются человеком. Для подобного преобразования в литературе обычно используют правила де Моргана, однако существует очень простой прием, позволяющий сразу записать искомый результат:
1) заменить в выражении операции Пирса и Шеффера на операции И-НЕ и ИЛИ-НЕ соответственно;
2) подсчитать число инверсий над каждой буквой, если оно четно, то в преобразуемое выражение эта буква будет входить без отрицания, если нечетно – с отрицанием;
3) подсчитать число инверсий над каждой логической операцией, если число инверсий четно, то операция не меняется, если нечетно, то логическая операция заменяется дуальной логической операцией.
Пример:
Для функций Шеффера и Пирса можно вывести тождества, похожие на правила склеивания и поглощения:
, 
действительно, 
,
,
,
Аналитическая запись булевых функций в булевом базисе.
Определение: конституентой единицы булевой функции называют произведение всех ее аргументов, записанных с отрицанием или без него.
Пример: если рассмотреть функцию трех аргументов 
, то
, 
, 
-конституенты единицы. Напишем несколько
выражений не являющихся конституентами 1: 
(не все
аргументы), 
- используя правило де Моргана, получим: 
, а это противоречит
определению конституенты 1.
Следствие: любая конституента 1 равна 1 только на одном наборе аргументов, на остальных наборах эта конституента равна нулю.
Для того чтобы определить набор на котором
конституента 1 равна 1 следует найти такие значения аргументов, которые дают
значение 1 каждому члену произведения. Пример: 
, если 
, а это возможно только на
наборе 101.
Теорема: Любая булева функция может быть записана в виде дизъюнкции конституент 1, соответствующих тем наборам на которых функция равна 1.
Доказательство. Выберем в таблице истинности произвольный набор. При этом возможны два случая:
Если на данном наборе функция равна 1, то из множества конституент выберем конституенту равную 1 на этом наборе (на остальных наборах она будет равна нулю) и записываем ее в формулу. Учитывая свойство дизъюнкции 1+…=1, мы обеспечиваем единичное значение функции на этом наборе.
Если на этом наборе функция равна нулю, то конституента равная 1 на этом наборе в формулу не вписывается, а значит на этом наборе функция будет равна 0.
После рассмотрения всех наборов мы получим аналитическую запись булевой функции в дизъюнктивной совершенной нормальной форме (ДСНФ).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.