Билет 18. «Тождественно-истинные формулы

«Тождественно-истинные формулы. Правильные рассуждения. Косвенные методы доказательства».

Пусть формула А зависит от списка переменных <X_i1, …, X_ik>.

Формула А называется тавтологией (тождественно-истинной формулой), если на любых оценках списка переменных <X_i1, …, X_ik> она принимает значение И.

Формула А называется выполнимой, если на некоторой оценке списка переменных <X_i1, …, X_ik>, она принимает значение И.

Формула А называется тождественно-ложной, если на любых оценках списка переменных <X_i1, …, X_ik>, она принимает значение Л.

Формула А называется опровержимой, если на некоторой оценке списка переменных <X_i1, …, X_ik>, она принимает значение Л.

1. А – тавтология тогда и только тогда, когда А не является опровержимой или А – тождественно-ложная.

2. А ~ В – тавтология тогда и только тогда, когда А и В равносильны.

Основные тавтологии (А, В, С – произвольные формулы)

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

2) А А

3) А (В А)

4) (А В) ((В С) (А С)) (закон цепного рассуждения)

5) (А (В С)) ((А В) (А С))

6) (А В) А, (А В) В

7) А (В (А В))

8) А (А В), В (А В)

9) ( В А) (( В А) В)

10) ((А В) А) А (закон Пирса)

Обосновывается с помощью таблицы истинности.

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

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

Первый способ – доказательство от противного. Мы предполагаем, что данное выражение ложно. В процессе доказательства мы приходим к противоречию, т.е подтверждаем, что некоторое утверждение выполняется и не выполняется одновременно. Этот метод доказывается равносильностью

А В (А В) (С С) (А В) (С С).

Второй способ – доказательство с помощью контрапозиции.

А В В А.

Т.е вместо первой части тождества мы доказываем второе.

Поиск по сайту: