Примеры

Нормальные формы

Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами.

Элементарной конъюнкцией называется конъюнкция, в которой участвуют высказывательные переменные или их отрицания.

Элементарной дизъюнкцией называется дизъюнкция, в которой участвуют высказывательные переменные или их отрицания.

Терема 5.1. 1) Элементарная конъюнкция тождественно ложна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.

2) Элементарная дизъюнкция тождественно истинна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.

Доказательство. Докажем утверждение 1). Пусть элементарная конъюнкция тождественно ложна. Предположим противное, что она не содержит никакую высказывательную переменную вместе с её отрицанием. Тогда можно построить интерпретацию, на которой эта конъюнкция истинна, придав переменным входящим в неё без отрицаний значение 1, а с отрицанием – 0. Следовательно, получено противоречие с предположением о тождественной ложности элементарной конъюнкции.

Обратное утверждение непосредственно следует из закона противоречия 9 и свойств констант 6.

Утверждение 2) доказывается аналогично.

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

Коньюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.

1. - КНФ.

2. - ДНФ.

3. приведенная формула, но не является ни ДНФ, ни КНФ.

4. является и ДНФ, и КНФ.

Теорема 5.2. Для всякой формулы U существуют эквивалентные ей КН-форма и ДН-форма.

Алгоритм построения нормальных форм.

1. Преобразовать формулу к приведенному виду (см. п. 2).

2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности 5 операций конъюнкции и дизъюнкции.

Например ДНФ формулы примера 1 получим непосредственно по свойству 5 º. Упростив формулу примера 3 по закону обобщенного склеивания º, получим КН- и ДН-форму.

Задание 1. Построить нормальные формы формулы

.

Решение. Преобразуем формулу к приведенному виду и затем упростим ее, используя двойное отрицание и законы Де Моргана.

º º

º º º .

Полученная формула является КН- и ДН-формой.

ДНФ и КНФ не единственны. Существуют формулы, к которым можно привести любую логическую формулу единственным образом с точностью до порядка элементарных дизъюнкций или конъюнкций и элементов в них. Такими формулами являются совершенные нормальные формы.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ в каждой конъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие конъюнкции называются полными.

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ в каждой дизъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие дизъюнкции называются полными.

Теорема 5.3. 1) Всякая элементарная дизъюнкция высказывательных переменных , не являющаяся ТИ-формулой, эквивалентна некоторой СКН-форме от этих высказывательных переменных.

2) Всякая элементарная конъюнкция высказывательных переменных , не являющаяся ТЛ-формулой, эквивалентна некоторой СДН-форме от этих высказывательных переменных.

Доказательство. Докажем утверждение 1) Так как элементарная дизъюнкция не является тождественно истинной, то в силу теоремы 5.1, она не содержит никакую высказывательную переменную вместе с её отрицанием. Если некоторая переменная (или её отрицание ) входит в элементарную дизъюнкцию несколько раз, то в силу идемпотентности операции дизъюнкции, оставим только одно её вхождение. Если же некоторая переменная не содержится в элементарной дизъюнкции, то, воспользовавшись законом склеивания 13

º Ù

Ù , получим КНФ. Если полученная форма не является совершенной, то для каждой её элементарной дизъюнкции повторим данную операцию. Таким образом, за конечное число применений закона склеивания получим СКНФ.

Утверждение 2) доказывается аналогично.

Следствие. Для всякой формулы, образованных из высказывательных переменных не являющейся тождественно истинной и тождественно ложной, существуют эквивалентные им СКН-форма и СДН-форма.

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

Обе нормальные формы, построенные в задании 1, не являются совершенными. Приведем их к совершенному виду.

º – СКН-форма.

º º

ÚÚ

ÚÚº

ºÚÚ– СДН-форма.

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы.

Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.

Сформулируем изложенные выше утверждения для булевых функций. Для этого введем следующие обозначения .

Легко проверить, что , .

Теорема 5.4 (о разложении булевых функций). Любую булеву функцию можно представить в виде

(5.1)

где дизъюнкции берутся по всем возможным наборам ().

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

,

так как, если хотя бы одно из значений отличается от , то , а, следовательно, обращается в 0 и вся конъюнкция. Таким образом, отличной от 0 будет только конъюнкция на наборе () = (), а так как , то . Ч.т.д.

Положив в (5.1) m = n, получим

f (x₁ , …, х_n) = Ú (x₁ ~ s₁) Ù…Ù (x_n ~ s_n) Ù f (s₁ , …, s_n).

s₁,.., s_n

Очевидно, среди всех дизъюнкций нужно оставить только те, в которых f (s₁ , …, s_n) = 1. Окончательно получим

(5.2)

Полученная формула разложения является совершенной дизъюнктивной нормальной формой булевой функции.

Теорема 5.5. Всякая булева функция (кроме 0) имеет единственную СДН-форму

.

С помощью принципа двойственности легко доказать представление функции СКН-формой.

Теорема 5.6. Всякая булева функция (кроме 1) имеет единственную СКН-форму

. (5.3)

Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.

Например, функция f переменных x₁, x₂, x₃, заданная в таблице

x1	x2	x3	f

имеет следующие совершенные нормальные формы:

– СКН-форма;

– СДН-форма.

Упростив любую из этих формул, можно получить простейшую формулу, реализующую данную функцию.

Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Х_i или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее.

В ЭВМ совершенные формы представляются в виде матрицы размера k´n, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f.

Пусть х – массив пропозиционных переменных. Предположим, х_i получили некоторые значения и необходимо вычислить значение нормальной формы f. Предлагаются следующие правила:

Эффективность данного алгоритма проявляется также в том, что цикл можно прервать, как только будет найдено необходимое значение i или j.

Например, вычислим значение функции f(x₁, x₂) = x₁ ~ x₂ при x₁ = 0; x₂ = 1. Запишем таблицу истинности функции f:

x1	x2	f

Тогда F_СДНФ = ; F_СКНФ = . Поскольку ни одна из строк F_СДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями х_j, то f (0, 1) = 0.

Тоже самое можно определить и по СКНФ, так как первая строка F_СКНФ совпадает со значениями х_j, то f (0, 1) = 0.

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

Если функция представлена ДНФ, то любая её элементарная конъюнкция будет её импликантой.

Определение. ДНФ называется минимальной, если она содержит наименьшее число вхождений переменных среди всех ДНФ, эквивалентных ей.

Определение. Длиной ДНФ называют число входящих в неё элементарных конъюнкций. ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

Минимальная ДНФ всегда является кратчайшей, обратное неверно.

Дата добавления: 2014-01-11