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

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

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

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

Заданную в табл.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	Соответствующий минитерм

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

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

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

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

.

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

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

.

Так как , то

.

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

.

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

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

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

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

7.2. Рассмотрите решение предыдущей задачи для случая трех переключателей.