Аналитическое представление функций алгебры логики

 

Существует много способов задания логических функций. Ранее был рассмотрен табличный способ, при котором каждому набору значений переменных в таблице истинности указывается значение самой логической функции. Этот способ нагляден и может быть применен для записи функций от любого количества переменных. Однако при анализе свойств функций алгебры логики (ФАЛ) такая запись не является компактной. Проще выглядит аналитическая запись в виде формул.

Рассмотрим фиксированный набор переменных { х 1, х 2,..., xn }, на котором задана функция алгебры логики. Так как любая переменная хi ={0,1}, то набор значений переменных фактически представляет собой некоторое двоичное число. Представим, что номером набора будет произвольное двоичное число i, получаемое следующим образом:

i =2 n -1 x 1+2 n -2 x 2+…+ xn.

 

Пусть имеется функция Ф i (х 1, х 2,..., xn):

 

Функцию Ф i называют термом.

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

Например: Ф7=1234; Ф2=12.

Конъюнктивный терм (минтерм) – терм, связывающий переменные, представленные в прямой или инверсной форме, знаком конъюнкции (иногда в литературе используется термин “конституэнта единицы”). Обозначается минтерм следующим образом:

 

Например F 1=1234; F 0=123.

Ранг терма r определяется количеством переменных, входящих в данный терм. Например, для минтерма F 10= 12345 r = 5, и для макстерма Ф2=1+2+3 r = 3.

На основании вышесказанного можно сформулировать следующую теорему.

 

Теорема 1.1. Любая таблично заданная ФАЛ может быть представлена аналитически в виде:

f (x 1, x 2… xn)= F 1 F 2…  Fn = Fi,

 

где i – номера наборов, на которых функция равна 1; — знак дизъюнкции, объединяющий все термы Fi, равные единице. Таким образом, каждому набору i, для которого fi =1, соответствует элемент Fi =1, а наборам i, на которых fi =0, не соответствует ни одного элемента fi =1. Поэтому таблица истинности однозначно отображается приведенной аналитической записью, которую в дальнейшем будем называть объединением термов.

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

Количество всех термов, входящих в состав аналитической записи, равно количеству единичных строк таблицы.

 

Пример. Записать в аналитическом виде функцию, заданную таблицей 1.9.

 

Таблица 1.9

Решение. На основании теоремы эту функцию можно записать в аналитической форме:

f (1,2,3)= F (0,0,0)+ F (0,1,1)+ F (1,0,0)=123+123+123.

Ответ: f (1,2,3)= 123+123+123.

 

Для представления ФАЛ используется совокупность термов, объединенных знаками дизъюнкции ( или +). Можно использовать также другую элементарную логическую операцию. Сформулируем основные требования к этой операции.

 

Требование 1: если какой-либо терм Fi =1, то функция f должна быть равна единице.

 

Требование 2: если какой-либо терм Fi =0, то функция f может быть равна единице.

Необходимо, чтобы при значениях термов Fi = 0 функция f была равна нулю.

Табличное представление искомой логической операции имеет вид таблиц 1.9 и 1.10.

 

Таблица 1.10 Таблица 1.11

Таким образом, получили, что искомой функцией, кроме функции ИЛИ, может быть функция разноименности и при этом справедливым становится такое следствие из теоремы 1.1:

 

Следствие: любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме:

f (x 1, x 2… xn) = F 1 f 2 …  fk,

 

где знак  обозначает операции , .

Требования 1 и 2 можно обобщить и потребовать, чтобы аналитическое представление нулевых и единичных строчек таблицы различалось и чтобы выполнялось взаимно-однозначное соответствие между нулевой единичной строкой и термом.

 

Требование 3: если какой-либо терм Ф i = 0, то функция f должна быть равна нулю.

 

Требование 4: если все термы Ф i = 0, то функция f =1.

Выполняя эти требования, можно прийти к двум другим возможным функциям, конъюнкции и равнозначности (табл. 1.12 и 1.13).

 

Таблица 1.12

Таблица 1.13

Теорема 1.2. Любая таблично заданная ФАЛ может быть задана в аналитической форме:

f (x 1, x 2… xn)=Ф1&Ф2&…&Ф k,

 

где k – количество двоичных наборов, для которых Ф=0.

Нормальная конъюнктивная форма (НКФ) – объединение термов, включающее в себя макстермы разных рангов.

 

Следствие. Любая таблично заданная ФАЛ может быть представлена в аналитической форме:

f (x 1, x 2… xn)=Ф1Ф2…Ф k,

 

где k – количество нулевых значений функции.