Игошин Математическая логика и теория алгоритмов (1019110), страница 53
Текст из файла (страница 53)
Следствия здесь действительно исключают одно другое, а для посылок Р(х) и — Р(х) ясно, что верно утверждение (чх)(Р(х) г ч — Р(х)), чего и требует условие предыдущей теоремы. (З Приведем пример двух теорем из геометрии, истинность обратных утверждений для которых может быть установлена с помощью рассмотренного частного случая теоремы об обратимости системы импликаций. Пример 24.22. Рассмотрим теоремы: 1) «Если две плоскости параллельны, то всякая плоскость при пересечении с ними дает две 217 прямые линии, которые также параллельны. Символически: ('Фяь я,)[я~ ])яг -» (чя )(я~ Й я ]] пз П я)]»; 2) «Если две плоскости не параллельны, то существует плоскость, которая при пересечении с ними дает две пересекающиеся прямые линии.
Символически: (Чяь я~)[я~ 4' лз -» (Ля)((я, П я) П П (яз П я)» О)]». Ясно, что следствия этих утверждений (Фг)(я~ П л )] я, (! п )] и (Вя)((я, П к) П (яз П к) ~ И)] взаимно исключают друг друга. Тогда можно сделать вывод о справедливости двух обратных утверждений: 1') «Если при пересечении любых двух данных плоскостей всякой третьей плоскостью получаются две параллельные прямые, то и сами данные плоскости также параллельны»; 2') «Если при пересечении любых двух данных плоскостей некоторой третьей плоскостью получаются две пересекающиеся прямые, то и сами данные плоскости также пересекаются».
Метод (полиой) математической индукции — специальный метод доказательства, применяемый для доказательства истинности утверждений типа (чх я Л)(Р(х)), т.е. (Чх)(хе ]»'-» Р(х)). Такие утверждения выражают тот факт, что некоторое свойство Р присуше каждому натуральному числу. Аксиоматическое обоснование этого метода будет дано в 5 29. Сейчас изложим суть этого метода. Формальной основой метода математической индукции служит одна из аксиом, называемая аксиомой индукции (или математической индукции) и выражающая свойство естественного отношения порядка, имеющегося на множестве всех натуральных чисел.
Эта аксиома такова. Если свойством Р обладает число 1 и для всякого натурального числа из того, что оно обладает этим свойством, следует, что и непосредственно следующее за ним натуральное число также обладает им, то и всякое натуральное число обладает свойством Р. Символически, на языке логики предикатов, эта аксиома записывается так: (Р(1) л (»х)(Р(х) — » Р(х+ 1))) — > (чу)(Р(у)).
Эта аксиома дает следующий метод доказательства утверждений, выражающих некоторые свойства всех натуральных чисел. Если нужно доказать утверждение (чу)(Р(у)), где у я 1!г («Всякое натуральное число обладает свойством Р»), достаточно установить истинность высказывания Р(1) («Число 1 обладает свойством Р») и доказать, что (~Гх)(Р(х) — » Р(х+ 1)), т.е. «Если х обладает свойством Р, то этим свойством обладает и число х+ 1, непосредственно следующее за х . Таким образом, логическая схема доказательства методом математической индукции может быть представлена следующим образом: (1): Р(1) — устанавливается проверкой; (2): (»х)(Р(х) » Р(х+ 1)) — доказывается; (3): Р(!) л (Ъх)(Р(х) -» Р(х+ !)) — из (1), (2) по правилу введения конъюнкции; 218 (4): (Р(1) л (Чх)(Р(х) -» Р(х+ 1))) -> (тгу)(Р(у)) — аксиома индукции; (5): (~Уу)(Р(у)) — из (3), (4) по правилу МР.
При этом установление истинности утверждения Р(1) называется основанием или базой индукции; предположение об истинности утверждения Р(х) — предположением индукции; последующее доказательство истинности утверждения Р(х+ 1)— шагом индукции. Методом математической индукции доказано утверждение о том, что число двоичных наборов длины п (упорядоченных л-ок), составленных из нулей и единиц, равно 2' (теорема !0.3), о представлении булевых функций (теорема 10.5), теорема 15.4 о дедукции.
Неоднократно применялась индукция по числу логических связок, входящих в формулу логики высказываний или предикатов (см. теоремы 2.2, 22.3, 22.5). Необходимые и достаточные условия. Отношение следования предикатов и соответствующее ему отношение включения соответствующих множеств истинности этих предикатов могут придать дополнительные штрихи к методике обучения понятиям необходимых и достаточных условий, усвоение которых вызывает значительные затруднения не только у школьников, но и у студентов. Предположим, что некоторая математическая теорема имеет вид: (чх)(Р(х) » Д(х)). Это означает, что предикат Р(х) » Д(х) тождественно истинен, т.е.
его множество истинности (Р-» (2)' = У. Используя теоремы 19.2, 19.6, 19.9, находим: У= (Р-» (2)' = (- Р г ~ Д)' = (- Р) () 0 = Р' () Д'. Следовательно, Р с Д', а значит, предикат Д(х) является следствием предиката Р(х). Исходная теорема (Чх)(Р(х) -» Д(х)) означает, что условие Р(х) является достаточным для условия Д(х), а (2(х) — необходимым для Р(х).
Проведенное только что рассуждение показывает, что это будет тогда и только тогда, когда имеет место включение Р+ ~ Д+ соответствующих множеств истинности. Если теперь изобразить эти множества и отношение включения между ними кругами Эйлера, то, используя обычные житейские представления о терминах «необходимо» и «достаточно», можно заключить: 1) чтобы элемент х принадлежал множеству Д' (т.е. удовлетворял условию Ях)), (вполне) достаточно, чтобы он принадлежал множеству Р' (т.е.
удовлетворял условию Р(х)); 2) чтобы элемент х принадлежал множеству Р', необходимо, чтобы он принадлежал множеству (')+ (ибо в противном случае, если он не принадлежит Д', то он и подавно не принадлежит множеству Р'). Полезно научиться оперировать этими понятиями на наглядном языке эйлеров- 219 ских диаграмм. Эта своего рода материализованная форма умственной деятельности будет способствовать формированию чисто умственных действий, связанных с понятиями необходимых и достаточных условий.
Здесь необходимо освоить два вида деятельности. В о- п ер в ы х, научиться рисовать диаграмму Эйлера, описываюшую ту или иную словесную формулировку. Пример 24.23. Формулировки могут быть, например, такими: 1) Р необходимо для Д; 2) В необходимо лля А; 3) М достаточно для Ф, )т'достаточно для К; 4) А необходимо для В, В необходимо для С; 5) Х необходимо для У, Удостаточно для У; 6) Хдостаточно для ); Унеобходимо для У. Диаграммы Эйлера выглядят так: (в случае 5) (в случае 4) Во-вторых, обратно, в ответ на предложенную диаграмму Эйлера дать соответствуюшую ей словесную формулировку. Пример 24.24. Вот примеры диаграмм: Соответствуюшие словесные формулировки таковы: Удостаточно для Х, Удостаточно для У; А необходимо и для Р, и для 9 Логика предикатов и алгебра множеств.
В в 8 была показана связь алгебры высказываний с теорией множеств. Логика предикатов усиливает эти связи, так как позволяет дать четкое толкование и обоснование известным теоретико-множественным понятиям и концепциям, а также ввести ряд новых. Например, понятие равенства двух множеств (принцип равнообьемности) на языке логики предикатов выражается так: 220 апр. М, = Мз «р ('р'х)(х е М, ~-э х в Мг), а понятие включения множеств следующим образом: апр М, <- Мз «» (ч'х)(хе М, ~-р хе Мг).
Тогда законы логики предикатов позволяют строго обосновать утверждение. Пример 24.25. М, = Мг <:» М, <- Мз л Мз ~ Мо Действительно, доказательство представляет собой цепочку равносильностей: М, = Мз <=» ('р'х)(х в М, <-> х в Мз) «» е» (чх)[(х е М| — > х е Мз) л (х е Мг — > х е М1)] « «» (~Ух)(х е М1 — > х е Мг) л (рх)(х е Мз -р х е М~) «» «»М,с;МглМг~Мь Далее, тавтологии логики высказываний позволяют обосновывать свойства теоретико-множественных операций: дополнения, пересечения, объединения множеств. При этом каждое множество М мыслится как множество истинности одноместного предиката «х е М» (см. Э 8).
Логика предикатов позволяет ввести новые теоретико-множественные понятия. Покажем, в частности, как обобщаются теоретико-множественные операции объединения и пересечения множеств на случай бесконечного числа множеств. Пусть имеется некоторое семейство (М)паг подмножеств множества М. (Это означает, что каждому элементу! е .(взаимно-однозначно сопоставлено подмножество М множества М.
Множество Уназывается множеством индексов семейства (М;)рп и а само семейство называется индексированным.) Объединением данного семейства называется множество, обозначаемое 0 М;, состоящее из всех таких элементl тов множества М, которые принадлежат по меньшей мере одному из подмножеств семейства: () М, = (х е М: (Э(е 1)(х в М )). 1а1 Пересечением данного семейства называется множество, обозначаемое П„,М, состоящее из всех таких элементов множества М, которые принадлежат каждому из подмножеств семейства: ПМ~ (хе М.(Же Т)(хе Мр)).
!а/ Логика предикатов позволяет установить свойства этих теоретико-множественных операций: они в некотором смысле аналогичны соответствующим свойствам объединения и пересечения. 221 Пример 34.2б. Проверим, например, один из законов де Моргана: ОМ,= ПМ;. ыг ыг Используя закон де Моргана для кванторов (теорема 21.9, б)„ получаем О М; = (х: —,(х и 0 М,)) = (х: (3~ и 1)(х и М,И = Ы! ыг (х(Жи 1)(~(хек)))(х(Ыи 1)(хиМ!))ПМ' ы1 Аналогично можно установить второй закон де Моргана для этих операций, законы дистрибутивности одной операции относительно другой и ряд других свойств. Большими возможностями располагает логика предикатов в теории бинарных отношений, где на языке предикатов выражаются фактически все понятия этой теории: проекции, срезы, функциональность, однозначность, взаимная однозначность, сюръективность, обращение и произведение бинарных отношений, их рефлексивность, симметричность, транзитивность, антисимметричность, асимметричность, связность и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
