Конъюнктивная и дизъюнктивная нормальные формы

Каждую формулу логики высказываний можно преобразовать в эквивалентную формулу некоторого стандартного вида, в которой используются только связки -л, v и л. Познакомимся с двумя стандартными видами формул: с конъюнктивной нормальной формой (КНФ) и с дизъюнктивной нормальной формой (ДНФ). Под эквивалентностью двух формул здесь подразумевается их синтаксическая эквивалентность, под преобразованием понимается построение вывода одной формулы из другой. Определим точно эти понятия.

Определение. Формула А называется синтаксическим следствием (говорят еще синтаксически выводима из) множества формул Г, что обозначается Г-А, если имеется такая последовательность формул Ah А2, ..., Ап, что Ап есть А и для любого /е{ 1, 2, ..., п} формула А,- есть либо аксиома, либо одна из формул множества Г, либо получается по одному из правил вывода из предыдущих формул AhA2, |. Последовательность формул А12, ...,А„ называется доказательством, или выводом, формулы А из множества Г. Сами формулы, входящие во множество Г, называются посьыками, или гипотезами.

Определение. Если 0 [А, то формула А называется теоремой и обозначается -А.

Определение. Формула А называется синтаксически эквивалентной формуле В, если А [В и В -А справедливо одновременно.

Оказывается, что синтаксическая эквивалентность формул А и В означает У (А = В), т.е. эквивалентность А = В является теоремой. Поэтому понятия синтаксическая эквивалентность и эквивалентность являются синонимами. Это позволяет избегать построения вывода для получения из формулы А ее КНФ или ДНФ. Для того чтобы выполнить преобразование формулы А в КНФ или ДНФ, достаточно использовать законы логики высказываний, строя цепочки эквивалентностей подобно тому, как в алгебре строятся цепочки равенств в ходе алгебраических преобразований. Следующее утверждение по существу является метатеоремой логики высказываний, обосновывающей указанной способ получения КНФ и ДНФ.

Теорема. Формулы Л и В синтаксически эквивалентны, т.е. Л[В и В [А справедливы одновременно тогда и только тогда, когда |- (А = В).

Это утверждение является следствием теоремы дедукции, доказанной Ж. Эрбраном (1930 г.).

Теорема дедукции. Пусть Г— множество формул, А и В — некоторые формулы. Если Г[{А} -В, то Г|- (Л—»#). В частности, если А [В, то |- (А^>В).

Приведение формул к КНФ и ДНФ проводится с использованием законов логики высказываний и следующих теорем:

Здесь awb — произвольные формулы.

Определение. Формула вида я,va2v... vanv-,b[v-ib2v... v-ibm называется дизъюнктом, или предложением, а формула вида я,ля2л... ля„л-1/>,л-1/>2л...л-Д„ называется конъюнктом, где я,, я2,..., ап, Ьи Ьъ Ьт — пропозициональные символы. При этом а,, а2,ап называются положительными, а ->->Ь2, —>Ьт отрицательными членами дизъюнкта или конъюнкта.

У дизъюнктов и конъюнктов могут полностью отсутствовать положительные или отрицательные члены. Это означает, что формулы

в частности, формулы я, и ->/>, тоже являются дизъюнктами. Аналогично формулы

в частности, формулы я, и тоже являются конъюнктами.

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

Другими словами: КНФ — это конъюнкция предложений. В общем виде КНФ можно представить формулой

где Z),, D2,Dk — предложения (дизъюнкты).

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

В общем виде ДНФ можно представить формулой

в которой С,, Съ ..., Ск — конъюнкты. Вполне возможно, что ДНФ состоит из единственного конъюнкта; точно также КНФ может состоять из единственного дизъюнкта.

Теорема. Любая формула логики высказываний эквивалентна некоторой КНФ и некоторой ДНФ.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >