Преобразуем эту формулу, используя соответствующие эквивалентности

U º º

Изобразим схему, соответствующую заключительной формуле

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение. Преобразуем формулу к приведенному виду и затем упростим ее.

( ) º ( ) º ( ) º º ( ) º ( ) º ( )

Полученная формула является КН- и ДН-формой, однако обе формы не являются совершенными. Приведем ее к совершенному виду.

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

( ) º ( )

) – СДН-форма.

Полные системы операций и функций.

Алгебра Жегалкина

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

Так как всякая формула может быть представлена приведенной формулой, то система å₀= {Ù, Ú, } - полна. Полной будет и любая система å, через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.

Если все операции полной системы å^* представимы формулами над системой å, то å полна, в этом случае говорят, что å сводится к å^*.

Алгебра над множеством логических функций с двумя операциями Ù и Å называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

, ,

а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант.

Задание. Доказать полноту системы å₅ = {Ù, Å}.

Решение. Сведем систему å₅ к полной системе å₀.

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

Выводимость

Пусть задано множество формул от высказывательных переменных

( ), ( ), . . . , ( ). (1)

Это множество формул назовем системой посылок.

Определение. Формула ( ) называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . , ú- , тогда и только тогда, когда формула

(2)

является ТИ-высказыванием, т.е.

ú= .

Из определения следует, что если конъюнкция

(3)

тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула.

Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных.

Нетрудно доказать следующие свойства выводимости.

1. Если ú- и ú- то ú- .

2. Если ú- и ~ , то ú- .

Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием.

Теорема 6.1. Формула ( ) тогда и только тогда выводима из системы формул (1), когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) относительно высказывательных переменных .

Так как теорема 1 формулирует необходимое и достаточное условие выводимости формулы, то на основе нее можно сформулировать алгоритм доказательства выводимости формулы.

1. Из системы посылок (1) строится конъюнкция (3).

2. Находим СКН-форму от высказывательных переменных для формулы (3).

3. Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).

Задание 1. Доказать выводимость ú- .

Решение.

1. Обозначим = X, = . Строим их конъюнкцию .

2. Найдем СКН-форму эквивалентную этой конъюнкции.

3. Получим СКН-форму для формулы B .

Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана.

Замечание. Выводимость формулы можно получить и без нахождения ее СКН-формы. Для этого нужно преобразовать с помощью известных эквивалентностей формулу (3) или даже конъюнкцию некоторых полных дизъюнкций из этой СКН-формы. Например, конъюнкция 1-ой и 3-ей полных дизъюнкций формулы из задания 1 преобразуется с помощью формулы склеивания к искомой формуле.

Кроме того, воспользовавшись теоремой 1, можно построить все СКН-формы выводимые из данной системы посылок. Для этого требуется небольшая модификация алгоритма доказательства выводимости формулы. После построения СКН-формы для формулы (3) необходимо

3°. Из полных элементарных дизъюнкций полученной СКН-формы строим различные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из системы посылок (1).

Задание 2. Найти все формулы, выводимые из системы посылок задания 1.

Решение. Построим различные комбинации полных элементарных дизъюнкций формулы .

1.

2.

3.

4.

5.

6.

7.

Как легко видеть, при построении всех СКН-форм, выводимых из данной системы посылок, мы получили, как частный случай, формулу .

Следует заметить, что на понятии выводимости основан способ доказательства утверждений методом приведения к абсурду.

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

является ТИ-высказыванием. В силу определения выводимости, это означает, что формула выводима из формул и .

1 2 345 6

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.