Игошин Математическая логика и теория алгоритмов (1019110), страница 18
Текст из файла (страница 18)
Что же происходит в этих рассуждениях с точки зрения (математической) логики? А происходит то, что доказательство данной теоремы Х вЂ” » У фактически заменяется (подменяется) доказательством теоремы — У-» Х, противоположной обратной (или обратной противоположной) для данной теоремы. Почему это возможно сделать? А потому, что в этом состоит логический закон контрапозиции Х вЂ” > Уп — У-» — Х, устанавливающий равносильность этих утверждений. Таким образом, описанный метод доказательства от противного основывается на логическом законе контрапозиции.
В задаче Ы 3.4 Задачника приведены примеры теорем, доказываемых методом от противного, основывающимся на законе контрапозиции. Метод доказательства от противного применяется также и в других формах. Например, вместо импликации Х вЂ” > Удоказывают Равносильную ей импликацию (Х> У) -» Х, т.е. предполагая, что истинны угверждения Хи — У, выводят истинность утверждения Хв противоречие с предположением. На основании равносильности Х вЂ” > У=- (Х» — У) -» — Хделается вывод об истинности импликации Х-» К Вторая равносильность Х вЂ” > Усч (Хл — У) — > 1' дает возможность заменить доказательство импликации Х вЂ” > У доказательством импликации (Х л — У) -» У, т.е.
предположив, что истинны утверждения Х и — У, вывести отсюда истинность утверждения у в противоречие с предположением. Наконец еще одна форма этого метода, являющаяся также одной из форм метода приведения к абсурду (см. 9 3, О значении тавтологий), основана на равносильности Х вЂ” » У= (Х» У) -» (У» У). Предполагая, что истинны утверждения Хи ~У, выводим из них некоторое утверждение и его отрицание. Метод приведения к абсурду (нелепости, противоречию) (по- латински гег?исйо ад а?>зигйит) имеет две модификации, которые 71 являются существенно различными как по форме, так и по существу, т.е.
по своей логической (дедуктивной) силе. Это — метод приведения противоположного утверждения к абсурду и метод приведения данного утверждения к абсурду. Метод приведения противоположного утверждения и абсурду состоит в следующем. Пусть требуется доказать угверждение Х Рассматривается (допускается) противоположное ему угверждение (т.е. утверждение, являющееся его отрицанием) — Хи из него выводятся два противоречащих друг другу утверждения (т.е.
некоторое утверждение и его отрицание) Ги ~У: ~Х» Уи ~Х вЂ” » ~К Из этого делается вывод о том, что справедливо исходное утверждение Х Оправданием этому методу может служить следующая тавтология; ( Х -» У) -» (( Х -» «') -» Х). Метод приведения данного утверждения н абсурду состоит в следующем. Пусть требуется опровергнуть угверждение Х, т.е. доказать отрицательное угверждение Х В этом случае два противоречащих друг другу утверждения Г и — «' выводятся не из утверждения Х, а из самого данного утверждения Х: Х» Уи Х» К Из этого делается вывод о том, что справедливо утверждение ~Х, т.е. данное утверждение Хопровергнуто.
Оправданием этому методу служит следующая формула, также являющаяся тавтологией: (Х » -» К) -» ((Х-+ У) » — Х). Приведем пример рассуждения (доказательства) этим методом. Пример 7.2. Доказать, что не существует биекции множества М на множество Р(М) всех его подмножеств. Другими словами, требуется опровергнуть следующее утверждение А; «Существует биекция множества М на множество Р(М) всех его подмножеств». Обозначим эту биекцию ~р. Теперь нам нужно указать некоторое высказывание В, для которого оно само и его отрицание —,В можно вывести из угверждения А. Предварительно нам потребуется рассмотреть следующее множество: М, = (х е М: х я я д(х)) — множество всех таких элементов из М, которые не принадлежат своему образу (а это есть некоторое подмножество множества М) при биекции у.
Так как Ма ~ М, а у — биекция М на Р(М), то существует такой элемент хв е М, что Мв = у(хв). Рассмотрим теперь такое высказывание В: «х» е Мв». Докажем, что В истинно. Допустим противное, т.е. истинно — В. Тогда хв я Мв. Но М» = ~р (хв). Тогда хв я <р (хе). Следовательно, в силу определения Ме заключаем, что х, е М,. Получаем противоречие, из которого делаем вывод, что предположение о том, что В истинно, неверно. Следовательно, истинно В. (Но тогда истинно и высказывание А -» В.) Теперь докажем, что ~В истинно. Допустим противное, т.е.
истинно В. Тогда х, а М,. Но по определению М, это означает, что хв я <р(х»). Но ~р(хв) = Ме. Следовательно, х, я Мо. Получаем проти- 72 воречие, из которого заключаем, что предположение об истинности высказывания В неверно. Следовательно, истинно — В, но, тогда истинно и высказывание — А — > — В. Таким образом, мы пришли к абсурду, противоречию: из данного утверждения А вывели истинность двух взаимно отрицающих друг лруга утверждений В и В. Значит, данное утверждение А неверно, а верно его отрицание А. П Доказательство методом приведения к абсурду может основываться также на следующей тавтологии (см. теорему 3.1, и): - ( Х вЂ” > -> (Уп — У)) — > Х. Метод доказательства, основанный на данной тавтологии, состоит в следующем. Допустим, нужно доказать некоторое утверждение Х.
Предполагаем, что справедливо его отрицание Х, и выводим отсюда некоторое утверждение г'и его отрицание К В результате заключаем, что справедливо утверждение Х Нередко в математических доказательствах используется правило цепного заключения, или правило силлогизма (см. теорему 3.1, п). Пусть нужно доказать утверждение Р -» А.
Находим такое утверждение О, для которого можем доказать истинность утверждений Р » Д и Ц -+ Л. Тогда на основании правила силлогизма заключаем, что справедливо и утверждение Р» Я. Например, из двух теорем «Если треугольник равносторонний, то все его углы равны» и «Если в треугольнике все углы равны, то величина каждого его угла равна 60'» — по правилу силлогизма получаем теорему «Если треугольник равносторонний, то величина каждого его угла равна 60'».
Существуют и другие методы математических доказательств, состоятельность которых подтверждается математической логикой. Далее будет приведена теорема 7.18, предоставляющая еще один метод получения математических теорем. Дедуктивные и иидукппщые умозаключения. На этом этапе весьма целесообразно рассмотреть вопрос о том, что представляют собой Рассуждения, умозаключения, каковы их структура, вилы и критерии правильности, какие умозаключения изучает логика и, в частности, математическая логика.
Умозаключение есть логическая (мыслительная) операция (процедура), состоящая в получении нового суждения (высказывания, утверждения) из одного или нескольких ранее известных суждений. Ранее известные суждения, входящие в состав умозаключения, называются его посылками, а новое суждение называется его следствием (или заключением). С содержательной точки зрения умозаключение есть переход от уже имеющегося (наличного) знания к новому знанию.
С формальной точки зрения умозаключение есть переход от посылок к следствию. В логике умозаключение принято представлять в виде фигуры, в которой посылки записаны одна под другой и отделены горизонтальной чертой, под которой записано следствие. Рассуждение есть последовательность умозаклю- 73 чений, причем посылками последующих умозаключений служат следствия предыдущих умозаключений данной последовательности. Умозаключения делятся на дедуктивные и индуктивные.
Расхожим является мнение о том, что дедуктивные умозаключения— это «умозаключения от общего к частному», а индуктивные— «от частного к общему». Эти «определения» лишь в самых общих чертах характеризуют, в частности, дедуктивные умозаключения. Это одно приведенное свойство еще не является для них определяющим. Дедуктивное умозаключение, прежде всего, основано на анализе формальной (логической) структуры посылок и следствия, индуктивное умозаключение основано на анализе их содержания.
Рассмотрим и проанализируем следующие примеры. Пример 7.3 «Если четырехугольник является квадратом, то его диагонали равны»; «Четырехугольник АВСЮ вЂ” квадрат». «Диагонали четырехугольника АВС0 равны». Пример 7.4 «Если число делится на 6, то оно четное»; «Число 18 делится на 6». «Число 18 четное», Пример 7.5 «Дуб — лиственное дерево»; «Береза — лиственное дерево»; «Липа — лиственное дерево».
«Все деревья — лиственные. Пример 7.6 «Обь замерзает зимой»; «Енисей замерзает зимой»; «Лена замерзает зимой». «Все сибирские реки замерзают зимой». В примерах 7.3 и 7.4 сделаем соответствующие выводы исходя из анализа формальной структуры посылок и следствия, фактически не обращая внимания на их содержание. Более того, с точки зрения логики эти умозаключения представляются одинаковыми, несмотря на то что не имеют между собой ничего общего по содержанию. Это типичные примеры дедуктивных умозаключений.
В то же время, переходя от посылок к следствиям в умозаключениях примеров 7.5 и 7.6, мы не можем отвлечься от их содержания. И хотя эти умозаключения также имеют одинаковую структуру, анализ их содержания приводит нас к построению неверного умозаключения. Дело в том, что все посылки каждого из этих умозаключений истинны, но вывод истинен только 74 в примере 7.6„а в примере 7.5 он ложен. Таким образом, умозаключения примеров 7.5 и 7.6 не носят дедуктивный характер, они не основаны на анализе формальной структуры умозаключения, на строгих законах формальной логики. Это — индуктивные умозаключения.
Их изучение не входит в задачу формальной логики. Еше более ярким примером индуктивного умозаключения, в котором связь между посылками и следствием является связью не по логической форме, а по содержанию, является следующее чмозаключение. Пример 7.7 «Спичка зажжена»; «Зажженная спичка поднесена к бумаге». «Бумага воспламеняется». В нем связь между посылками и следствием носит и вовсе некий физический причинно-следственный характер. Важнейшим методологическим вопросом, связанным с дедуктивными умозаключениями, является вопрос об определении правильности (верности) умозаключения.
Распространенная ошибка здесь состоит в том, что правильность умозаключения отождествляется с истинностью получаемого на основании этого умозаключения вывода: умозаключение считается правильным, если «в результате мы приходим к истине>. Это не так. Правильность дедуктивного умозаключения означает, что оно приводит к истинному выводу не всегда, но всякий раз, когда оно исходит из всех истинных посылок. Другими словами, умозаключение считается правильным, если мы, имея посылки и следствия данной структуры (как определено в умозаключении), при условии истинности всех посылок непременно будем получать истинность следствия. Таким образом„чтобы доказать неправильность умозаключения, нужно указать такую его конкретизацию (пример), в которой все посылки были бы истинными, а следствие было бы ложным. Такой пример называется опровергающим (или контр- примером).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
