Тождественно истинные и ложные формулы

Пусть формула Л зависит от списка переменных Хх,...,Хп .

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

Пример. X v X .

Формула А называется выполнимой, если на некоторой оценке списка переменных Х| она принимает значение И.

Пример. X a Y.

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

Пример. X аХ .

Формула А называется опровержимой, если на некоторой оценке списка переменных Х{,...,Хп она принимает значение Л.

Пример. X vT.

Утверждение 1.

  • 1. А - тавтология <=> А не является опровержимой.
  • 2. А - тождественно-ложна <=> А не является выполнимой.
  • 3. А - тавтология Я-тождественно-ложна.
  • 4. А - тождественно-ложна А - тавтология.
  • 5. А —В— тавтология А=В.

С точки зрения логики тавтологии суть не что иное, как логические законы, ибо при любой подстановке вместо переменных тавтологии конкретных высказываний в результате получим истинные высказывания. Ниже указаны наиболее важные тавтологии (А, В, С - произвольные формулы).

  • 1) Ах/А (закон исключающего третьего);
  • 2) А^А-,
  • 3) А^(В^А);
  • 4) (АлВ)^А;
  • 5) (Лл5)->?;
  • 6) А -^(В^(АлВ)У,
  • Т) A^(AvB);
  • 8) ?->(Л v?);
  • 9) (В А) ((В А) В);
  • 10) ((Л —> 2?) —> Л) —> Л (закон Пирса);
  • 11) (Л —> 2?) —> ((В —> С) —> (А —> С)) (цепное рассуждение);
  • 12) (А^(В^С))^((А->В)^>(А->С)).

Каждую из этих тавтологий можно обосновать, например, составив таблицу истинности при произвольных значениях А, В, С.

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

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

Пусть Рп - посылки, D - заключение. Тогда для определения пра-вильности рассуждения по схеме -----то есть утверждения о том, что из данных посылок Рп следует заключение D, требуется установить тождественную истинность формулы } Л...Л

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

Пример. Рассмотрим рассуждения.

1. Если число 7 простое, то оно нечетное. Число 7 нечетное. Следовательно, число 7 простое. Заключение истинно, но рассуждение неправильное.

jg jg

Это рассуждение по схеме------—. Но формула F (А, В) = ((А -> В) л В) —> А

А

не является тождественно-истинной

Таблица 5

Формула F}(A.B)

А

в

А^>В

(А—>В)/В

((А^В)лВУ^А

Л

л

И

Л

И

Л

и

и

И

Л

и

л

л

Л

И

и

и

и

И

И

2. Если Иван занимается спортом, то Иван никогда не болеет. Иван занимается спортом. Следовательно, Иван никогда не болеет. Это рассуждение по истинна, значит, рассуждение правильное

схеме

А—>В,А

В

. Формула F2 (А, В) = ((А —> В) л А) —> В (табл. 6) тождественно

Таблица 6

Формула F2(A,B)

А

в

А^В

(А—>В)лА

((А-»В)лА)->В

Л

л

И

Л

И

Л

и

и

л

И

и

л

л

л

И

и

и

и

и

И

Распространенными схемами правильных рассуждений являются сле-

А^В.А А->В.В дующие схемы: --—-- и--=—=.

Рассмотрим условное высказывание вида А —> В, где А - конъюнкция посылок, В - заключение. Иногда удобнее вместо доказательства истинности этого условного высказывания установить логическую истинность некоторого другого высказывания, равносильного исходному. Такие формы доказательства называются косвенными методами доказательства.

Одним из них является способ доказательства от противного. Предположим, что утверждение А —ложно. Тогда, исходя из этого предположения, приходим к противоречию, то есть доказываем, что некоторое утверждение (соответствующее высказыванию С) выполняется и не выполняется одновременно. Применимость этой формы косвенного метода доказательства оправдывается равносильностью

А -> В = (А->В) л С) = (А л В) -> (С л С).

Существуют и другие схемы доказательства от противного

А-э» = (АлйНА; Ач6е(АаВ)^В.

Еще одной формой косвенного метода доказательства является доказательство по закону контрапозиции, основанное на равносильности А —> В = В —> А, когда вместо истинности А —> Z? доказывается истинность В->7.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >