Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.2. Формы представления булевых функций
Совершенные формы представления
Любую булеву функцию y = f(a, b) можно представить как некоторую комбинацию областей:
C0 = a ∧ b, C1 = a ∧ b, C2 = a ∧ b, C3 = a ∧ b.
Тогда, в зависимости от значения функции и заданных Ci, которые в этом случае называются конституентами, получим 16 логических операций:
y = [a ∧ b ∧ f (0,0)] ∨ [a ∧ b ∧ f (1,0)] ∨
∨ [a ∧ b ∧ f (0,1)] ∨ [a ∧ b ∧ f (1,1)].
Подобная форма представления логических функций называется совершенной дизъюнктивной нормальной формой (СДНФ).
В логике Буля действует принцип двойственности, который гласит: при одновременной замене символов ∧ ⇔ ∨ и 1 ⇔ 0 все логические равенства остаются в силе. Поэтому СДНФ можно представить несколько иначе:
y = [a ∨ b ∨ f (1,1)] ∧ [a ∨ b ∨ f (0,1)] ∧
∧ [a ∨ b ∨ f (1,0)] ∧ [a ∨ b ∨ f (0,0)].
Эта форма представления называется совершенной конъюнктивной нормальной формой (СКНФ). Здесь уже конституенты представлены не в виде конъюнктов, как в СДНФ, а в виде дизъюнктов. Соединены же эти дизъюнкты конъюнкцией, отсюда и название — СКНФ.
Существует еще и третья форма — совершенная полиномиальная нормальная форма (СПНФ). Ее можно получить из СДНФ путем замены:
a ∨ b = a + b + ab, a = 1 + a.
Поскольку конституенты не пересекаются (CiCj = 0), мы можем сразу же записать (в СПНФ символ конъюнкции опускается):
y = [(1 + a)(1 + b) f (0,0)] + [a(1 + b) f (1,0)] +
+ [(1 + a)b f (0,1)] + [ab f (1,1)] =
= f (0,0) + a[f (0,0) + f (1,0)] + b[f(0,0) + f(0,1)] +
+ ab[f (0,0) + f (1,0) + f (0,1) + f (1, 1)].
В табл. 1.9 приведен полный список элементарных логических функций от двух аргументов в трех совершенных формах — СДНФ, СКНФ и СПНФ. Совершенные формы представлений позволяют выразить аналитической формулой любую функцию, если известна ее таблица истинности.
Таблица 1.9
| y = f (a, b) | СДНФ = СКНФ = СПНФ |
| y0 = 0 | = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) = 0 |
| y1 = a ∧ b | = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) = ab |
| y2 = b – a | = a ∧ b = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) = b + ab |
| y3 = b | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = b |
| y4 = a – b | = a ∧ b = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) = a + ab |
| y5 = a | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = a |
| y6 = a + b | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = a + b |
| y7 = a ∨ b | = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) = a ∨ b = a + b + ab |
| y8 = a ↓ b | = a ∧ b = (a ∨ b) ∧ (a ∨ b) ∧ (a ∨ b) = 1+ a + b + ab |
| y9 = a ~ b | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = 1 + a + b |
| y10 = a | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = 1 + a |
| y11 = a → b | = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) = a ∨ b = 1 + a + ab |
| y12 = b | = (a ∧ b) ∨ (a ∧ b) = (a ∨ b) ∧ (a ∨ b) = 1 + b |
| y13 = b → a | = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) = a ∨ b = 1 + b + ab |
| y14 = a | b | = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) = a ∨ b = 1 + ab |
| y15 = 1 | = (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) ∨ (a ∧ b) = 1 |
Пусть задана конкретная таблица истинности (табл. 1.10) для функции, зависящей от трех аргументов.
Таблица 1.10
x1 x2 x3 y 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 Тогда, выписывая соответствующие конъюнкты против единичных значений y, мы получим СДНФ. Если же мы выпишем дизъюнкты против нулевых значений y, то в результате уже получим СКНФ. Наконец, СПНФ образуется путем замены в СДНФ: ∨ на + и х на 1 + х.
yСДНФ = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3),
yСКНФ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3),
yСПНФ = x1(x2 + 1)(x3 + 1) + x1x2 (x3 + 1) + (x1 + 1)(x2 + 1)x3 + x1x2x3.
В последнем случае выражение для yСПНФ легко упростить, если раскрыть скобки и взаимно сократить все одинаковые слагаемые, входящие в формулу четное число раз:
yСПНФ = x1 + x2 + x2x3.
Подобное упрощение, которое называется минимизацией логической функции, можно приминить к СДНФ и СКНФ.
В логике Буля действует закон склеивания:
(a ∧ b) ∨ (a ∧ b) = a, (a ∨ b) ∧ (a ∨ b) = a.
Применение этих законов позволяет найти более компактные аналитические выражения для заданной функции y, т.е. минимальную дизъюнктивную нормальную форму yМДНФ. Приведем соответствующие формы представления функции y, заданной табл. 1. 10:
yМДНФ = (x1 ∧ x3) ∨ (x1 ∧ x2) ∨ (x1 ∧ x2 ∧ x3),
и для СКНФ, т.е. минимальную КНФ:
yМКНФ= (x1 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2).
После того, как найдены минимальные нормальные формы (МНФ), их рекомендуется проверить на всех наборах аргументов xi. Переменные xi или xi часто называют термами. Именно полный набор из n термов образует конституенту. В процессе же минимизации некоторые термы из конституент пропадут. Тогда оставшуюся часть дизъюнкта или конъюнкта называют импликантой.
Как мы только что убедились на примере, импликанты появляются в результате склейки смежных конституент, различающихся одним термом. Однако для функций, зависящих от многих переменных, неконтролируемый процесс склейки неизбежно приводит к лишним импликантам. Требуемое число импликант может оказаться гораздо меньше возможного числа смежных склеек. В таких случаях истинную МНФ получают с помощью специальных методов минимизации, три из которых мы сейчас разберем. При этом следует помнить, что рассматриваемые далее методы минимизации касаются только СДНФ. Но на основании принципа двойственности они могут быть легко распространены и на СКНФ.
|
|
