Доказать что формула является тавтологией

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

Пусть дана некоторая формула F логики высказываний и надо выяснить, является ли формула F тавтологией. Простой метод доказательства – использовать таблицу истинности. Хорошо, если эта таблица небольшая, но когда высказывательных переменных много, то такой подход трудоемок. В случае, когда F имеет вид F1⊃F2, желательно использовать метод доказательства от противного. Вы предполагаете, что формула

F ложна и, делая отсюда выводы, приходите к противоречию или определяете значения переменных, при которых формула ложна. Для формул указанного вида ложность F1⊃F2 однозначно определяет: F1 – истинна, а F2 – ложна.

Пример. Является ли формула ((P ⊃ Q)& P) ⊃ (Q ⊃ ¬P) тавтологией?

Решение. Предположим, что формула ((P ⊃ Q) & P) ⊃ (Q ⊃ ¬P) ложна при некоторых значениях высказывательных переменных P и Q.

Получили значения переменных (Q = И и P = И), при которых формула ((P ⊃ Q)& P) ⊃ (Q ⊃ ¬P) = Л, следовательно, эта формула не является тавтологией.

Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.

Пусть A и B — две формулы и <X1, X2,…, Xn> — множество всех высказывательных переменных, входящих в формулу A и/или в формулу B. Будем называть эти формулы равносильными, если при любом распределении истинностных значений для переменных <X1, X2,…, Xn>, они принимают одинаковые значения. Равносильность формул A и B будем обозначать A≡B.

Теорема 1. Основные равносильности. Для любых формул A, B, C справедливы следующие равносильности:

1. A&B ≡ B&A (коммутативность &);

2. A&A ≡ A (идемпотентность &);

3. A&(B&C) ≡ (A&B)&C (ассоциативность &);

4. A∨B ≡ B∨A (коммутативность ∨);

5. A∨A ≡ A (идемпотентность∨);

6. A∨ (B∨C) ≡ (A∨B) ∨C (ассоциативность ∨);

7. A∨ (B&C) ≡ (A∨B)&(A∨C) (дистрибутивность ∨ относительно &);

8. A&(B∨C) ≡ (A&B) ∨ (A&C) (дистрибутивность & относительно ∨);

9. A&(A∨B) ≡ A (первый закон поглощения);

10. A∨ (A&B) ≡ A (второй закон поглощения);

11. ¬¬A ≡ A (снятия двойного отрицания);

12. ¬ (A&B) ≡ ¬A∨¬B (первый закон де Моргана);

13. ¬ (A∨B) ≡ ¬A&¬B (второй закон де Моргана);

14. A ≡ (A&B) ∨ (A&¬B) (первый закон расщепления);

15. A ≡ (A∨B)&(A∨¬B) (второй закон расщепления).

B ≡ (A⊃B)&(B⊃A) ≡ (A&B) ∨ (¬A&¬B);

17. A⊃B ≡ ¬A ∨ B ≡ ¬ (A&¬B);

18. A∨B ≡ ¬A⊃B ≡ ¬ (¬A&¬B);

19. A&B ≡ ¬ (A⊃ ¬B) ≡ ¬ (¬A∨¬B).

Доказательство A∨ (B&C) ≡ (A∨B)&(A∨C) с помощью таблицы истинности.

Доказательство ¬ (A&B) ≡ ¬A∨¬B без таблицы истинности. Пусть на некотором наборе истинностных значений переменных

формула ¬(A&B) принимает значение Л. Тогда формула A&B принимает значение И, а поэтому обе формулы A и B принимают значение И.

Но в этом случае, очевидно, и правая часть равносильности 12 принимает значение Л. И наоборот, пусть формула ¬A∨¬B принимает значение Л.

Тогда формулы ¬A, ¬B принимают значение Л, а формулы A, B – значение И. Очевидно, что и левая часть равносильности ¬ (A&B) ≡ ¬A∨¬B

принимает значение Л.

• Нужно различать символы

является символом формального языка, с помощью которого строятся формулы, а символ ≡ обозначает отношение на множестве формул.

• Очевидным образом, A ≡ B тогда и только тогда, когда A

B есть тавтология (которая обычно называется эквивалентностью).

• Кроме того, если A ≡ B, то A ⊃ B является тавтологией.

1. Высказывания, формулы, тавтологии

Определение. Высказыванием называется утверждение, которое является истинным или ложным (но не одновременно).

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

Пример. “Москва – столица России” – истинное высказывание.

“5 –четное число” – ложное высказывание.

“” – не высказывание (неизвестно, какие значения принимает ).

“Студент второго курса” не высказывание (не является утверждением).

Высказывания бывают элементарные и составные.

Элементарные высказывания не могут быть выражены через другие высказывания. Составные высказывания можно выразить с помощью элементарных высказываний.

Пример. “Число 22 четное” – элементарное высказывание.

“Число 22 четное и делится на 11” – составное высказывание.

Высказывания обозначают заглавными буквами латинского алфавита: , , ,… Эти буквы называют логическими Атомами.

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

Истинностные значения истина и ложь сокращенно обозначаются и, л или T, F, или 1,0. Мы будем использовать обозначения 1 и 0. В определенной интерпретации буквы принимают значения 1 или 0.

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

Таблицы истинности основных логических операций.

Более строго формула определяется так.

Определение. 1) Всякая буква есть формула.

2) Если , — формулы, то формулами являются также , , , , .

3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

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

Значение формулы в заданной интерпретации обозначают (или , или ).

Часть формулы, которая сама является формулой, называется Подформулой данной формулы.

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

Другими словами, тавтология – это тождественно истинная формула.

Установить, является ли формула тавтологией, можно:

– по таблице истинности,

– используя свойства логических операций.

Из курса дискретной математики известны основные логические эквивалентности (свойства логических операций), которые являются примерами тавтологий.

1. Коммутативность: , .

, .

, .

4. Идемпотентность: , .

5. Закон двойного отрицания: .

6. Закон исключения третьего: .

7. Закон противоречия: .

8. Законы де Моргана:

, .

9. Свойства операций с логическими константами:

, , , .

Здесь , и – любые буквы.

Примеры. 1. Доказать, что формула является тавтологией.

Доказательство. Допустим, что при некоторых значениях букв (то есть в некоторой интерпретации)

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

2. Доказать, что формула является тавтологией.

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

Допустим, что при некоторых значениях букв

Следовательно, исходная формула – тавтология.

3. Доказать, что формула является тавтологией.

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

Следовательно, исходная формула – тавтология.

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

Теорема. Пусть формулы и – тавтологии. Тогда формула – тавтология.

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

Теорема. Пусть формула – тавтология, , , …, – буквы в формуле , , , …, – любые формулы. Тогда новая формула – тавтология.

Тавтология и противоречие. Равносильность высказываний

Формула х₂,лг_я) называется тавтологией или тождественно истиной формулой, если при любых значениях высказываний х_х> х₂,значение F= 1.

Например, рассмотрим формулу Л v -Д, соответствующую высказыванию «этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный.

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

Формула F(x 1, х₂, . х_п) называется противоречием или тождественно ложной формулой, если при любых значения высказываний х_1у х₂. х_п значение F = 0.

Формула называется выполнимой, если существует такой набор значений переменных, при котором эта формула принимает значение 1. Формула называется опровержимой, если существует такой набор значений переменных, при котором эта формула принимает значение 0.

Пример 4.14. Рассмотрим формулу А & -Л, которой соответствует, например, высказывание «Катя — самая высокая девочка в классе, и в классе есть девочки выше Кати». Очевидно, что эта формула ложна, так как либо Л, либо ^Л обязательно ложно.

Пример 4.15. Выясним, является ли следующая формула тождественно истинной: F — [(Л —> В) & -‘В] —> -*Л.

Решение. Построим таблицу (табл. 4.13) истинности заданной формулы, используя определения логических операций.

Тавтологии алгебры высказываний

Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих высказываний. Так, если для установления того, истинны или нет высказывания "Саратов основан в 1590 году", "Солнце вращается вокруг Земли", необходимо обладать специальными знаниями или заглянуть в специальную литературу, то для выяснения значения истинности высказываний "Треугольник , а второго — формулой . Легко убедиться в том, что обе эти формулы суть тавтологии. Данные формулы дают две схемы построения всегда истинных высказываний. И такова каждая формула, являющаяся тавтологией. Но главное значение тавтологий не в этом.

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

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

Термин "тавтология" имеет греческое происхождение, составлен из двух слов ταντοζ (то же самое) и λογοζ (слово) и означает повторение одного и того же определения, суждения иными, близкими по смыслу словами. В тавтологиях, относящихся к математической логике, заключительной логической связкой является эквивалентность

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

Основные тавтологии в математической логике

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

Теорема 3.1. Следующие формулы алгебры высказываний являются тавтологиями:

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

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

Последний столбец таблицы, состоящий из значений истинности данной формулы, содержит лишь единицы. Это означает, что данная формула — тавтология.

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

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

Тавтологии, собранные в теореме 3.1, лежат в основе многих математических рассуждений, что уже обсуждалось в начале этой лекции относительно тавтологии теоремы 3.1, пункт п). Применение некоторых других тавтологий в процессе математических рассуждений рассмотрено в следующих лекций. Тавтологии последующих теорем данного параграфа выражают свойства логических операций.

Свойства конъюнкции и дизъюнкции

Теорема 3.2 (свойства конъюнкции и дизъюнкции). Следующие формулы алгебры высказываний являются тавтологиями:

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

Рекомендуется доказать самостоятельно тождественную истинность остальных формул теоремы 3.2, а также формул следующих далее теорем 3.3 и 3.4.

Свойства импликации и эквивалентности

Теорема 3.3 (свойства импликации и эквивалентности). Следующие формулы алгебры высказываний являются тавтологиями:

Выражение одних логических операций через другие

Теорема 3.4 (выражение одних логических операций через другие). Следующие формулы алгебры высказываний являются тавтологиями:

Основные правила получения тавтологий

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

Теорема 3.5 (правило заключения). Если формулы .

Доказательство. Пусть и . Предположим, что формула не является тавтологией. Это означает, что существуют такие конкретные высказывания , что . Поскольку — тавтология, то для имеем . Вычисляем, пользуясь соотношением (1.4):

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

Правило заключения называется также правилом отделения или правилом " модус поненс " (лат. modus ponens ).

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

Если в ту же формулу вместо переменной .

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

Аналогично определяется одновременная подстановка в формулу

Теорема 3.6 (правило подстановки). Если формула , является тавтологией, то подстановка в формулу любой формулы .

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

Например, если в тавтологии выполнить подстановку формулы вместо переменной , то получим тавтологию

Замечание 3.7. Отметим, что правило подстановки позволяет рассматривать каждую из тавтологий, приведенных в теоремах 3.1 — 3.4, не как отдельно взятую тавтологию, а как схему образования тавтологий. Значит, каждая из пропозициональных переменных в данных формулах может рассматриваться не как переменная, а как произвольная формула алгебры высказываний. Например, тавтология б) из теоремы 3.3 предоставляет бесконечное множество тавтологий вида , где — произвольные формулы алгебры высказываний.

Два рассмотренных правила образования тавтологий — "модус поненс" и правило подстановки — будем называть основными. Существуют и другие правила, которые будем называть вторичными или производными правилами и которые рассмотрим в последующих лекциях.