Существует много способов задания логических функций. Ранее был рассмотрен табличный способ, при котором каждому набору значений переменных в таблице истинности указывается значение самой логической функции. Этот способ нагляден и может быть применен для записи функций от любого количества переменных. Однако при анализе свойств функций алгебры логики (ФАЛ) такая запись не является компактной. Проще выглядит аналитическая запись в виде формул.
Рассмотрим фиксированный набор переменных { х 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=1234; Ф2=12.
Конъюнктивный терм (минтерм) – терм, связывающий переменные, представленные в прямой или инверсной форме, знаком конъюнкции (иногда в литературе используется термин “конституэнта единицы”). Обозначается минтерм следующим образом:
Например 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 – количество нулевых значений функции.
