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

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

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

i=2n-1x1+2n-2x2+…+xn.

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

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

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

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

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

Например F1=1234; F0=123.

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

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

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

f(x1, x2…xn)=F1 F2…  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(x1, x2…xn) = F1f2 …  fk,

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

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

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

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

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

Таблица 1.12

Таблица 1.13

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

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

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

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

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

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

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