Игошин Математическая логика и теория алгоритмов (1019110), страница 9
Текст из файла (страница 9)
Она состоит в следующем. Допустим, что требуется доказать истинность некоторого утверждения А. Предполагается, что истинно его отрицание А. Затем доказывается, что имеется некоторое такое утверждение В, для которого истинными являются оба утверждения 4 -» В и -А -+ — В.
Доказательства истинности этих импликаций зависят от содержания высказываний А и В и 33 2 иг устанавливаются на основании методов и законов той математической теории, к которой они относятся. Считаем, что истинность утверждений 4 -+ В и 4 -+ ~В установлена. Одновременный вывод двух утверждений В и -  — противоречие, абсурд. Тогда утверждаем, что истинно высказывание А.
Такой метод доказательства называется методом приведения к абсурду. Термин «тавтология» имеет греческое происхождение, составлен из двух слов тат>то( (то же самое) и ) оуо~ (слово) и означает повторение одного и того же определения, суждения иными, близкими по смыслу словами. В тавтологиях, относящихся к математической логике, заключительной логической связкой является эквивалентность с-» . Например, тавтология (Р п (0» А))++ <-» ((Р п (г)» (Р» А)) выражает одинаковость форм (формул) в ее левой и правой частях, т.е.
имеется в виду семантическая одинаковость, выражаемая разными словами — формами (формулами). Совершенно аналогично в этом смысле арифметическое тождество х(у + г) = ху + хг, которое отражает ту же внутреннюю сущность посредством разных слов. И каждое из этих двух выражений является объективным законом, действующим каждый в своей сфере: первый — в сфере мыслительных процессов, второй — в сфере чисел.
Каждый из этих законов несет объективную информацию об определенной части окружающего нас мира. Труднее в этом смысле истолковать тавтологии вида Р«- Р, Р-»Р, Р -» (0-» Р) и т.п., но на них данный термин просто распространяется. Основные тавтологии. Приведем некоторые основные тавтологии, выражающие свойства логических операций, а также тавтологии, на которых основаны некоторые схемы математических доказательств. Теорема 3.1.
Следующие формулы алгебры высказываний являются тавтологиями: а) закон исключенного третьего Р > — Р; б) закан отрицания противоречия — (Р» — Р); в) закон двойного отрицания Р «-» Р; г) закон тождества Р— » Р; д) закон контрапозиции (Р -+ Д) «-» (-,0 — » —,Р); е) закон силлогизма (правило цепного заключения) ((Р -+ 0) л (0 -» А)) — » (Р -+ А); ж) закон противоположности (Р»-» Д) «-» (-Р +-» — О); з) правило добавления антецедента («истина из чего угодно») Р-+(0 — » Р); и) правило «из ложного что угодно» вЂ” Р -» (Р— » Д); к) правило «модус понено> (тойиз ропепз) (Р > (Р— » Д)) -+ Д; л) правило «модус толленс (тодиз гойепз) ((Р— » Д) и — (г) -» — Р, м) правило перестановки посылок (Р -+ (Д -+ А)) с-» Я -+(Р -+ А)); 34 и) правило объединения (и разъединения) посылок (Р -+ ((г -+ А)) <-э ((Р л Д) -э А); о) лравило разбора случаев ((Р -+ А) л (0 -+ А)) <-> ((Р м (г) — > А); и) правило приведения к абсурду ((.
Р -+ 0) л (-Р -+ - 0)) -+ Р, (- Р -+ (0 л - Д)) — > Р. Доказательство. Отметим, что непосредственно из определений логических операций вытекает тождественная истинность формул а), б), в), г); для формулы д) доказательство имеется в Задачнике (см. № 1.28, д). Установим тождественную истинность формул л) и н) (для остальных проверьте самостоятельно). л) Изучая тавтологии, важно уяснить, что имеется простой и надежный алгоритм (общий метод), позволяющий для любой формулы логики высказываний дать ответ на вопрос, является она тавтологией логики высказываний или нет — этот алгоритм состоит в построении ее таблицы истинности.
Составим таблицу истинности данной формулы: Последний столбец таблицы, состоящий из значений истинности данной формулы, содержит лишь единицы. Это означает, что данная формула — тавтология. н) Доказательство тождественной истинности формул с помощью составления их таблиц истинности проходит автоматически. Приведем следующее доказательство, рассуждая о тех значениях, которые формула может принимать.
Покажем, что левая часть данной эквивалентности обращается в ложное высказывание тогда и только тогда, когда в ложное высказывание обращается формула, стоящая в правой части эквивалентности. Действительно, формула Р— ь (0 — > А) превращается в ложное высказывание, если и только если Х(Р) = 1, Х(Д -+ А) = О. В свою очередь, Х(0 — ~ А) = О тогда и только тогда, когда Х(0) = 1 и ЦА) = О. Итак, ЦР -ь (0-> А)) = О в том и только в том случае, когда ЦР) = 1, Х(0) = 1, Х(А) = О. С другой стороны, формула (Р л 0) — > А обращается в ложное высказывание, если и только если ЦР л д) = 1 и Х(А) = О. В свою очередь, ЦР л Д) = 1 тогда и только тогда, когда Х(Р) = 1 и Х(Д) = !.
Итак, Х((Р л Д) -+ А) = О в том и только в том случае, когда Х(Р) = 1, Х((г) = 1 и Х(А) = О. Доказанное означает, что правая и левая части эквивалентности одновременно превращаются либо в истинные высказывания, либо 35 в ложные. Следовательно, по определению эквивалентности вся формула всегда превращается в истинное высказывание, т.е. яв- ляется тавтологией.
П Тавтологии, собранные в теореме 3.1, лежат в основе многих математических рассу»кдений, что уже обсуждалось в начале 5 3 относительно тавтологии теоремы 3.1, и (см. с. 33). Применение некоторых других тавтологий в процессе математических рассужде- ний рассмотрено в 9 7. Тавтологии последующих теорем данного параграфа выражают свойства логических операций. Теорема 3.2 (свойства конъюнкции и дизъюнкции). Следующие формулы алгебры высказываний являются тавтологиями: а) законы идемпотентности (Р л Р) <-» Р, (Р ч Р) +.» Р; б) законы упрощения (Р л й) — » Р, Р— » (Р ч (г); в) законы коммутативности (Р л Д) ++ (Д к Р), (Р ч О) <-» (О ч Р); г) законы ассоциативности (Р л (Д п Я)) <-» ((Р л Д) п Я), (Р ч (Ц ч В)) ++ ((Р ч О) ч А); д) законы дистрибутивности (Р л (Д ч В)) +-» ((Р л Д) ч (Р п Я)), (Р ч (О л Я)) +» ((Р ч (г) л (Р ч Я)); е) законы поглощения (Рл(Рч Д))+-»Р,(Рч(Рл О))+-» Р; ж) законы де Моргана — (Р л Д) с-» (.
Р ч — Д), — (Р ч Ц) (-» (- Р н — Д). До к аз ател ьств о. Докажем для примера, что первый закон де Моргана (см. формулу 3.2, ж)) является тавтологией. Пусть А и  — произвольные конкретные высказывания. Рассмотрим два со- ставных высказывания (А п В) и 4 л ~В, получающиеся из частей данной эквивалентности при замене пропозициональных переменных Р и (г конкретными высказываниями А и В соответ- ственно. Предположим, во-первых, что высказывание (А к В) истинно. Тогда конъюнкция А л Вложна; следовательно, по мень- шей мере одно из высказываний А или В ложно.
Но в таком слу- чае хотя бы одно из высказываний — А или В истинно, следова- тельно, их дизъюнкция -А ч — В истинна. Предположим, во-вто- рых, что высказывание — (А п В) ложно. Тогда конъюнкция А л В истинна. Следовательно, оба высказывания А и В истинны, а их отрицания 4 и В оба ложны, т.е. дизъюнкция -А ч В ложна. Таким образом, для любых двух высказываний значения частей рассматриваемой эквивалентности совпадают.
Следовательно, формула тождественно истинна. П Рекомендуется доказать самостоятельно тождественную истин- ность остальных формул теоремы 3.2, а также формул следующих далее теорем 3.3 и 3.4. Теорема 3.3 (свойства импликации и эквивалентности). Следу- ющие формулы алгебры высказываний являются тавтологиями: 36 а) (Р— » (Π— » А)) -+ ИР— » О) — » (Р— » А)); б) Р-+(О-+(Рл О)); в) (Р -+ А) -» ИΠ— » А) -+ ИР ч О) -» Р)); г) (Р -» О) -+ ИР -» - О) -+ - Р)); д) (-Оп (Р-+ О)) — » — Р; е) (-,Р п (Р ~ О)) -» О; ж) (Р-+ О) — »ИРч А) — »(О «А)); з) (Р -+ О) -+ ИР л А) -+ (О л А)); и) (Р -+ О) -+ ИΠ— » А) — » (Р -+ А)); к) (Р -+ О) «(Π— » Р); л) (- Π— » -1Р) -» И- О -+ Р) -» О); м) ИР -+ О) л (А -+ О)) +-» ИР «А) — » О); и) ИР— » О) п (Р— » А)) +-» (Р -+ (О п А)); о) Р++Р; и) (Р «-» О) «-» (О «-» Р); р) ИР <+ О) л (О +-» А)) -+ (Р «-» А). Теорема 3.4 (выражение одних логических операций через другие).
Следующие формулы алгебры высказываний являются тавтологиями: а) (Р -+ О) +.+ (- Р «О); б) (Р -+ О) +-» — (Р л — О); в) (Р л О) +-» — (- Р г — О); г) (Р л О) +-» —,(Р -+ —,О); д) (Р ~ О) +-» -(- Р л — О); е) (Р «О) «-» (- Р -» О); ж) (Р «-» О) +-+ ИР -+ О) л (Π— » Р)). Основные правила получения тавтологий.
Опишем два правила, которые позволяют получать новые тавтологии из уже имеющихся. Теорема 3.5 (правило заключения). Если формулы Г и à — » Н являются тавтологиями, то формула Н также тавтология. Другими словами, из ~ Ги ~ Р— » Н следует ~ Н. Доказательство. Пусть ~ Р(Х„л., Х„) и ~ Г(Х„..., Х„) — » -» Н(Хи ..., Х„). Предположим, что формула Н(Хь ..., Х„) не является тавтологией. Это означает, что существуют такие конкретные высказывания А„..., А„, что Х(Н(Ан ..., А„)) = О.
Поскольку Р(Хь ..., Х„) — тавтология, то для А„..., А„имеем Х(Г(Аь ..., А„)) = 1. Вычисляем, пользуясь соотношением (1.4): к(Г(А„..., А„) -» Н(А о ..., А.)) = Х(Р(Ао ..., А„)) — » Л,(Н(Ап ..., А„)) = 1 -» О = О, что противоречит тождественной истинности формулы à — » Н. Следовательно, предположение неверно. Тогда ~ Н, что и требовалось доказать. П Правило заключения называется также правилом отделения или правилом «модус поненс«(тодиз ропепз). Второе правило получения тавтологий носит название правила подстановки. Пусть в формуле Гсодержится пропозициональная переменная Х (а возможно, и другие пропозициональные переменные), и Н вЂ” любая формула.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
