Примеры

1) А v - закон исключения третьего

2) А → А – закон тождественности

3) А → (А→ В)

4) (А→ В)→ (В→ С)→ (А→ С)

5)

Проблема разрешимости:

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

Теорема:

Формула А является тождественно истинной тогда и только тогда, когда в ее конъюнктивной нормальной форме каждая элементарная дизъюнкция содержит некоторую переменную и ее отрицание.

X_i v v D = 1

Формула является тождественно ложной тогда и только тогда, когда в ее дизъюнктивной нормальной форме каждый элемент конъюнкции содержит переменную и ее отрицание.

X_i & & D = 0

Правильные рассуждения

Процесс получения новых знаний представленных из ранее полученных высказываний называется рассуждением.

Исходное высказывание будем обозначаться < P₁…P_n> - посылки.

Новое высказывание будем обозначать D – заключение.

Схема рассуждений:

Пример:

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

Таким образом, для доказательства правильности рассуждения достаточно показать, что формула P₁ & P₂ & … & P_n → D 1.

Замечание: Истинность заключения D не является ни обходимым, ни достаточным условием правильности рассуждения.

Некоторые схемы правильных рассуждений

1. Правило заключений (Modus Ponens)

2. Правило отрицания (Modus Tollens)

3. Правило утверждения отрицания

,

4. Правило отрицания утверждения

, , ,

5. Правило транзитивности

6. Правило противоречия