Макстерм и минтерм.
Алгебраический (аналитический) способ представления логической функции.
Табличный способ представления логической функции.
Способы представления логических функций
В данном случае ЛФ представляется своей таблицей истинности.
Например, представление ЛФ 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 – макстермы (дизъюнктивные термы) любого ранга, включая единичный, Õ – знак логического умножения.
СНДФ (совершенная (стандартные или канонические) нормальная дизъюнктивная форма) – этоминтермы (конъюнктивные термы) только максимального ранга.
СНКФ (совершенная нормальная конъюнктивная форма) – – макстермы (дизъюнктивные термы) только максимального ранга.
Любая совершенная нормальная форма (СНФ) отличаются от нормальной формы тем, что всегда содержит термы только максимального ранга и дает однозначное представление логической функции.