2.3.6. Нормальные формы в логике высказываний

Часто необходимо преобразовывать формулы из одной формы в другую, особенно – в «нормальную форму». Нормальная форма – синтаксически однозначный способ задания формулы, реализующий заданную функцию.

Преобразования выполняются путем замены в данной формуле некоторой ее подформулы., на некоторую формулу, эквивалентную заменяемой. Процедура повторяется до тех пор, пока не получится желаемая формула.

2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)

Введем обозначение:

Определение1. Формула , где

- какой-либо двоичный набор, а среди переменных x_i могут быть совпадающие, называется элементарной конъюнкцией.

Определение 2. Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Определение 3. Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее нахождение под знаком отрицания).

Примеры: а) ; б) ;

в) ; г) .

Определение 4. Правильная элементарная конъюнкция называется полной относительно переменных x₁, ...,x_n, если в нее каждая переменная входит один и только один раз (быть может, под знаком отрицания).

В примерах а) конъюнкция полная относительно

х₁, х₂, х₃; г) – относительно х₁, х₂, х₃, х₄.

Теорема (о разложении булевой функции по переменным)

Здесь дизъюнкция берется по всем возможным наборам

Требуется доказать, что данная формула реализует заданную булеву функцию. Для этого возьмем произвольный набор значений аргументов функции и вычислим на нем значение формулы. Если оно окажется равным значению функции на этом наборе аргументов, то из этого следует доказываемое утверждение.

Напомним, что под x^y понимается наибольшая нижняя граница {x,y}, а под xvy – наименьшая верхняя граница.

Доказательство

Следствие1.

f(x₁,...,x_n-1,x_n) =

Следствие 2.

здесь дизъюнкция берется по тем наборам , для которых функция f = 1.

По определению 2: Формула F находится в дизъюнктивной нормальной форме тогда и только тогда, когда она имеет вид:

F = F₁v...vF_n, ≥ 1, где каждая из F₁, F₂, ...,F_n есть конъюнкция переменных ( ).

Пример: F= здесь: и .

x	y	x→y
1	1	1	1
1	0	0	0
0	1	1	1
0	0	1	1

Всякая формула может быть преобразована в нормальную формулу. Это легко достигается с помощью равносильностей алгебры логики. Рассмотрим эскиз процедуры такого преобразования.

Шаг 1. для устранения (элиминирования) логических связок ↔ и → используем законы:

и .

Проверим эквивалентность с помощью истинностной таблицы

Шаг 2. Несколько раз используем законы де Моргана:

, чтобы перенести знак отрицания непосредственно к переменным.

Шаг 3. Несколько раз используем дистрибутивные законы:

av(bvc) = (avb)vc и a^(b^c) = (a^b)^c,

чтобы получить нормальную форму.

Пример: получить дизъюнктивную нормальную форму для формулы:

Так как , то дизъюнктивная нормальная форма для есть