Алгоритм приведения формул к СДНФ и СКНФ.

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

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

3. На основе закона дистрибутивности конъюнкции относительно дизъюнкции (дистрибутивность дизъюнкции относительно конъюнкции) формула сводится к нормальной форме.

4. Полученные формы упрощаются с использованием основных формул равносильности.

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

Á eq (Á&xi)Ú(Á&ùxi)

Á eq (ÁÚxi)&(ÁÚù xi)

Существует еще один метод получения КНФ, использующий понятие двойственности.

Для некоторой формулы Á находится двойственная формула Á*.

Á®Á*.

Для Á* находится ДНФ: ДНФ(Á*)=Â.

Двойственная к найденной ДНФ формула является КНФ исходной формулы: Â* eq КНФ(Á).

Пример 1: Привести к СДНФ формулу ù(xÚy)«x&y.

ù(xÚy)«x&y eq (ù(ù(xÚy))&ù(x&y)Ú(ù(xÚy)&(x&y)) eq ((xÚy)&(ùxÚùy))Ú((ùx&ùy)&(x&y)) eq (x&ùxÚy&ùxÚx&ùyÚy&ùy)Ú(ùx&ùy&x&y) eq (y&ùx)Ú(x&ùy)- ДНФ и СДНФ.

Пример 2: Преобразовать к СКНФ формулу (x&yÚùy&z)&(y®x)

(x&yÚùy&z)&(y®x) eq (x&yÚùy&z)&(ùyÚx) eq ((xÚùy)&(yÚùy)&(xÚz)&(yÚz)&(ùyÚx) eq ((xÚùy)&(xÚz)&(yÚz))&(ùyÚx) eq (xÚùy)&(xÚz)&(yÚz)&(ùyÚx) eq (xÚùy)&(xÚz)&(yÚz)- КНФ.

Преобразуем к СКНФ.

(x&yÚùy&z) & (y®x) eq (xÚùy) & (xÚz) &(yÚz) eq

(xÚùyÚz)&(xÚùyÚùz)&(xÚyÚz)&(xÚùyÚz)& (xÚyÚz)& (ùxÚyÚz) eq (xÚùyÚz)& (xÚùyÚùz)& (xÚyÚz)& (ùxÚyÚz).

1.7 Логическое следование

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

Цель рассуждений представляет собой конечную последовательность высказываний (составных, но, может быть, и простых предложений), приводимых в обоснование некоторого утверждения. Мы должны понять, действительно ли предлагаемый вывод (заключительной утверждение - заключение) можно сделать из указанных предпосылок начальных высказываний. Их называют посылками. Посылки считаются истинными. И, исходя из истинности посылок, мы должны вывести заключение.

Исчисление высказываний дает критерий вместе с практическими формами его использования для ответа на вопрос: «Правильно ли делается вывод о том, что заключение будет выполняться (иметь значение «истина»), если все посылки имеют значение «истина»»?

Высказывание B есть логическое следствие высказываний A1,…,An, что символически записывается в виде A1, …, An ᅣ В, если для всякого распределения истинностных значений, приписываемых каждой из простых формул P1 , …, Pm, входящих в одну или несколько формул A1, …, An, и В, формула В получает значение «истина» всякий раз, когда значение «истина» получают все формулы A1, …, An.

1а) (AᅣB)↔( ᅣA→B)