Сделай Сам Свою Работу на 5

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





Логика высказываний.

Высказывание - повествовательное предложение, о котором можно судить, истинное оно или ложное.

Обозначаются высказывания A,B,C,…

Истинностное значение высказывания A обозначается символом l(A) и определяется по формуле:

l(A)=1, если высказывание A истинно, и

l(A)=0, если A ложно.

Определение. Алгеброй высказываний называется множество всех высказываний P с логическими операциями .

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

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

Переменные символы X,Y,Z,…, которые используются для обозначения высказываний и которые называются пропозициональными переменными.

Определение. Формулы алгебры высказываний индуктивно определяются по правилам:

1) каждая пропозициональная переменная является формулой,

2) если F,Y – формулы, то формулами являются также выражения

( ), , , , .

Множество всех формул алгебры высказываний обозначим FАВ .



Если в формулу F входят переменные , то записывают .

Из индуктивного определения формул следует, что если в формулу F вместо переменных подставить произвольные конкретные высказывания , то получится некоторое сложное высказывание .

Истинностное значение высказывания определяется истинностными значениями исходных высказываний согласно таблицам истинностных значений логических операций .

Определение. Формула называется:

- тавтологией (или тождественно истинной формулой) и обозначается , если ее истинностная функция тождественно равна 1;

- противоречием (или тождественно ложной формулой), если ее истинностная функция тождественно равна 0;

- выполнимой, если ее истинностная функция не равна тождественно 0;

- опровержимой, если ее истинностная функция не равна тождественно 1.

- Тавтологии являются общими схемами построения истинных высказываний и в этом смысле выражают некоторые логические законы.

- Примеры таких законов являются:

- – закон исключенного третьего,

- – закон двойного отрицания,



- – закон противоречия,

- – закон контрапозиции.

Новые тавтологии можно получить с помощью следующих правил.

-Правило отделения:

если , , то .

- Правило подстановки:

если , то для любых формул тавтологией является формула .

Логическая равносильность формул.

Определение. Формулы называются логически эквивалентными (или просто равносильными), если .

Для обозначения логически эквивалентных формул используется символическая запись , или просто .

Такие выражения называются логическими эквивалентностями или просто равенствами формул.

Лемма. Справедливы следующие равенства формул:

1) , – свойства ассоциативности дизъюнкции и конъюнкции;

2) , – свойства коммутативности дизъюнкции и конъюнкции;

3) , – свойства идемпотентности дизъюнкции и конъюнкции;

4) , – законы дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции;

5) , – законы де Моргана;

6) , – законы поглощения;

7) – закон двойного отрицания;

8) , – взаимосвязь импликации с дизъюнкцией и конъюнкцией;

9) , – взаимосвязь эквивалентности с импликацией, дизъюнкцией и конъюнкцией.

Лемма (Правило замены). Если формулы равносильны, то для любой формулы ,содержащей переменную X,выполняется равенство: = .

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

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

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

Отношение равносильности является отношением эквивалентности на множестве всех формул FАВ, которое разбивает это множество на классы эквивалентности , определяемые формулами .



Из лемм следует, что для каждой формулы можно указать равносильные ей формулы специального вида, содержащие только символы логических операций .

Определение.Литерой называется пропозициональная переменная X или ее отрицание ØX . Для обозначения литеры используется символ Xa, где aÎ{0,1} и по определению , .

Определение.Конъюнктом (соответственно, дизъюнктом) называется литера или конъюнкция (соответственно, дизъюнкция) литер.

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

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

При этом КНФ (соответственно, ДНФ) называется совершенной, если совершенны все ее дизъюнкты (соответственно, конъюнкты).

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

Теорема 2. Любая выполнимая формула равносильна формуле вида , где дизъюнкция берется по всем упорядоченным наборам {0,1}n, удовлетворяющим условию .

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

Теорема 3. Любая опровержимая формула равносильна формуле вида , где конъюнкция берется по всем упорядоченным наборам {0,1}n, удовлетворяющим условию .

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

Логическое следование формул.

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

Символическое обозначение - называется логическим следованием.

Формулы называются посылками и формула следствием логического следования .

Определение. Множество формул называется противоречивым, если из него логически следует любая (в том числе и тождественно ложная) формула .Символически это записывается .

Лемма (Транзитивность логического следования). Если и для любого значения выполняется , то .

 

Лемма (Критерии логического следования). Условие равносильно каждому из следующих условий:

a) ,

b) ,

c) .

В частности, равносильно . Отсюда также следует, что равносильно тому, что и .

Основные правила логического следования:

1) правило отделения (или правило модус поненс – от латинского modus ponens)

;

2) правило контрапозиции

;

3) правило цепного заключения

;

4) правило перестановки посылок

.

Метод резолюций в алгебре высказываний

Определение. Пусть для некоторой переменной X дизъюнкты представимы в виде , . Тогда дизъюнкт называется резольвентой дизъюнктов по переменной X и обозначается ResX .

Резольвента дизъюнктов по некоторой переменной X называется резольвентой дизъюнктов и обозначается Res . По определению Res =0.

Определение. Резолютивным выводом формулы F из множества дизъюнктов называется такая последовательность формул , что:

1) Fn=F;

2) каждая из формул Fi (i=1,…,n) либо принадлежит множеству S, либо является резольвентой предыдущих формул Fj, Fk при некоторых 1£j,k£i.

Теорема. Множество дизъюнктов противоречиво в том и только том случае, если существует резолютивный вывод значения 0 из множества S.

Так как по критерию логического следования соотношение

|=F

равносильно условию

|=,

то справедлив следующий результат.

Следствие (Проверка логического следования формул).

Пусть для формул формула имеет КНФ .

Тогда логическое следование |= F равносильно существованию резолютивного вывода значения 0 из множествадизъюнктов .

 








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



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