Вопросы и задания

5.1. Докажите с помощью таблицы соответствия справедливость законов ассоциативности и поглощения.

5.2. Путем последовательных преобразований проверьте, какие из следующих выражений являются верными тождествами:

а) ;

б) ;

в) .

Сравните полученные результаты с результатами задания 3.15.

6. Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций)

Дизъюнктивная (конъюнктивная) нормальная форма– это дизъюнкция (конъюнкция) конечного числа различных членов, каждый из которых представляет собой конъюнкцию (дизъюнкцию) отдельных переменных или их отрицаний, входящих в данный член не более одного раза.

Пример

­­– дизъюнктивная нормальная форма

­­– конъюнктивная нормальная форма

Формулы приводятся к нормальной форме следующим путем:

1. с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным;

2. на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций);

3. полученные выражения упрощаются в соответствии с тождествами ()

Пример

Привести к дизъюнктивной и конъюнктивной нормальным формам функцию .

Решение

В соответствии с законом де Моргана преобразуем .

.

На основе законов дистрибутивности раскроем скобки:

.

В соответствии с законом идемпотентности . Откуда

.

Полученное выражение является дизъюнктивной нормальной формой.

Аналогичным образом представим заданную функцию в конъюнктивной нормальной форме:

.

Конъюнктивная нормальная форма получена.

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) kбукв, называютсяминитермами(макситермами)k-го ранга. Так, например,– минитерм третьего ранга, а– макситерм второго ранга.

Совершенной дизъюнктивной (конъюнктивной) нормальной формойназывается дизъюнктивная (конъюнктивная) нормальная форма, каждый минитерм (макситерм) которой содержит все переменные (либо в прямом, либо в инверсном виде).

Например, минитерм функции четырех переменных (х₁,х₂,х₃,х₄) в совершенной дизъюнктивной нормальной форме будет представлен дизъюнкцией двух минитермов:.

Вопросы и задания

6.1. Может ли одной и той же дизъюнктивной нормальной форме соответствовать несколько различных совершенных дизъюнктивных нормальных форм?

6.2. Может ли одной и той же совершенной дизъюнктивной нормальной форме соответствовать несколько различных дизъюнктивных нормальных форм?

6.3. Представьте функцию трех переменных

а) в дизъюнктивной нормальной форме;

б) в совершенной дизъюнктивной нормальной форме;

в) в конъюнктивной нормальной форме;

г) в совершенной конъюнктивной нормальной форме.

6.4. Схема, представленная на рис.4.4 соответствует дизъюнктивной нормальной форме. Каждая ветвь цепи соответствует одному минитерму. Какая цепь соответствует макситерму? Каков общий вид схемы, соответствующей конъюнктивной нормальной форме?

7. Построение аналитического выражения булевой функции по таблице ее значений

Ранее мы рассмотрели возможности описания функции, заданной аналитически, при помощи таблицы соответствий. Широко распространенной является и обратная задача – построение аналитического выражения некоторой логической функции, первоначально заданной таблично.

Пусть, например, таблично (табл.7.1) задана функция y(х₁,х₂,х₃).

Таблица 7.1
y	х1	х2	х3
1	0	0	0
1	0	0	1
0	0	1	0
1	0	1	1
0	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Заданную в табл.7.1 функцию можно описать следующим образом: значение функции уравно 1, когда (х₁≡0 их₂≡0 и х₃≡0) или (х₁≡0 их₂≡0 и х₃≡1) или (х₁≡0 их₂≡1 и х₃≡1) или (х₁≡1 их₂≡0 и х₃≡1) или (х₁≡1 их₂≡1 и х₃≡0) или (х₁≡1 их₂≡1 и х₃≡0). Союзу "или" соответствует операция дизъюнкции, а союзу "и" – операция конъюнкции, выражение "х_i≡1" эквивалентно "х_i", а "х_i≡0" эквивалентно "нех_i". Таким образом, таблично заданную функцию можно описать дизъюнкцией конъюнкций, т.е. дизъюнктивной нормальной формой.

Рассмотрим подробно алгоритм описания в виде дизъюнктивной нормальной формы функции, заданной таблично.

На первом этапе каждому набору аргументов сопоставим минитерм, принимающий на этом наборе аргументов значение, равное единице. Минитерм строится как конъюнкция аргументов (правый столбец табл.7.2). Для равенства минитерма единице необходимо, чтобы переменные, равные нулю, присутствовали в виде инверсии, а переменные, равные единице, присутствовали в исходном виде. Например, в первом наборе все переменные равны нулю. Следовательно, в соответствующем минитерме каждая из них присутствует в виде инверсии. При этом сам минитерм равен единице, что и требовалось при его построении.

Таблица 7.2
Функция		Аргументы
y	х1		х2	х3	Соответствующий минитерм
1	0		0	0
1	0		0	1
0	0		1	0
1	0		1	1
0	1		0	0
1	1		0	1
1	1		1	0
1	1		1	1

Важным для дальнейших рассуждений является тот факт, что при фиксированном наборе значений аргументов единице равен только соответствующий этому набору минитерм, а все остальные минитермы равны нулю.

Следующим этапом получения аналитического описания является построение совершенной дизъюнктивной нормальной формы. Для этого из таблицы выбираются те минитермы, для которых значения функции равны единице. Функция описывается дизъюнкцией этих минитермов. Почему так происходит?

Если значения аргументов соответствуют одному из вошедших в описании функции минитермов, то значение этого минитерма становится равно единице, а значит и вся функция становится равной единице. Если же значения аргументов таковы, что ни один из входящих в описание функции минитермов не равен единице, то вся функция равна нулю. Построение аналитического описания такой функции и было задачей.

Итак, аналитическое описание функции заданной в табл.7.2 выглядит следующим образом:

.

Такая запись является совершенной дизъюнктивной нормальной формой.

К аналитическому описанию функции, заданной таблично, можно подойти и с другой стороны – описывать аргументы соответствующие нулевым значениям функции. Аналитическое описание из приведенного ранее примера будет следующим:

.

Так как , то

.

В соответствии с законами де Моргана преобразуем:

.

Полученная запись является конъюнкцией дизъюнкций, каждый макситерм содержит все переменные, т.е. запись представляет собой совершенную конъюнктивную нормальную форму.

Таким образом, любой таблично заданной логической функции можно сопоставить аналитическое выражение как в виде дизъюнктивной, так и в виде конъюнктивной нормальной формы.