Нормальные формы аналитического представления ЛФ.

Макстерм и минтерм.

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

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

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

В данном случае ЛФ представляется своей таблицей истинности.

Например, представление ЛФ 3-х аргументов f(x1, x2, x3) ее таблицей истинности:

№ набор значение
набора x1 x2 x3 функции

 

Обычно в таблице истинности столбец с номером набора не приводится.

Табличный способ является максимально наглядным, но в случае сложных функций алгебры логики (ФАЛ) он не достаточно компактный.

Аналитический способ представления логической функции – это аналитическая запись функций в виде формул.

Например,

f(x1,x2,x3) = x3 + x1`x2 + x2 x3 +`x1`x2 x3

f(x1,x2,x3) = (x1 +`x2)×(x2 + x3)×(`x1 +`x2 + x3)

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

функция x1x2 аналитическое пред- примечание
  ставление функции  
f0 f0 константа нуля
f1 x1 Ù x2 конъюнкция (пересечение)
f2 x1 Ù`x2 запрет x2 (разность)
f3 x1Ù`x2 Ú x1Ùx2 = x1 переменная x1
f4 `x1 Ù x2 запрет x1
f5 `x1 Ùx2 Ú x1Ùx2 = x2 переменная x2
f6 x1 Å x2 сложение по модулю 2 – неравнозначность (симметричная разность)
f7 x1 Ú x2 дизъюнкция (объединение)
f8 x1 ¯ x2 функция Пирса (ИЛИ-НЕ)
f9 x1 º x2 равнозначность
f10 `x1 Ù`x2 Ú x1Ù`x2 =`x2 инверсия x2
f11 x2 ® x1 x2 – посылка х1 – следствие импликация x2 (=1) если x2 – истинна, то x1=0 и f=0
f12 `x1 Ù`x2 Ú`x1 Ù x2=`x1 инверсия x1
f13 x1 ® x2 импликация x1 (=1)
f14 x1 / x2 функция Шеффера (И-НЕ)
f15 f1 константа единицы

 

Макстерм (H) или дизъюнктивный терм (ИЛИ) – это ЛФ, связывающая все переменные в прямой и инверсной форме (литералы) знаком дизъюнкции. Конституента нуля (K0) тождественна макстерму.

Элементарная сумма – это дизъюнкция нескольких переменных или их отрицаний – макстерм (ИЛИ).

Минтерм (F) или конъюнктивный терм (И) – это ЛФ, связывающая все переменные в прямой и инверсной форме (литералы) знаком конъюнкции. Конституента единицы (K1) тождественна минтерму.

Элементарное произведение – это конъюнкция нескольких переменных или их отрицаний – минтерм (И).

НДФ (нормальная дизъюнктивная форма) –это SFi, где Fi – минтермы (конъюнктивные термы) любого ранга, включая единичный, S – знак логического сложения.

НКФ (нормальная конъюнктивная форма) – это ÕHi, где Hi – макстермы (дизъюнктивные термы) любого ранга, включая единичный, Õ – знак логического умножения.

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

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

Любая совершенная нормальная форма (СНФ) отличаются от нормальной формы тем, что всегда содержит термы только максимального ранга и дает однозначное представление логической функции.