В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 13
Текст из файла (страница 13)
2.42. Найдите все такие не равносильные между собой формулы Г(Х, У, У) от трех переменных, что: а) Г л (Х-+ ~ У) ~= ~ ((Х л 2) -+ -з У); б) (У-+ (Хл ~У)) -+ Г ~= Ул (Х-+ У); в) Г++ ((Хч 2) -+ У) ~ (Х л Л) ч У; г) (Х -+ Р) л ( У ч Я) ~= ~У -+ (Х л У); д) -чРл (Х-+ зУ) ~= Хл Ул -зЕ; е) Р л (У-+ (Х++ У)) ~= ((Х-+ У) -+ -з(У-+ Х)) и (Х л У л -ч2); ж) ((Х-+ У) и 2) л Г ~= (~Х л Ул Я) и (Х л -з У л ~2); 3) (У -+ (-з 1'л Х)) -+ Г В= У л (Х вЂ” + У); и) Р <-+ ((1'-+ Л) -+ Х) ~= ~((~Х -+ У) ч 2); к) Рч (-ч(Х-+ У) л У) с= (Х-+ У) л ~У; л) (У ч (У-+ -зХ)) -+ Г ~= Ул -зЛ Р е ш е н и е. л) Составим сначала таблицу истинности для формул, стоящих слева и справа от знака ~=. При этом будем учитывать, что нам не известны значения истинности, принимаемые формулой Г(Х, У, Я) на тех или иных наборах значений входящих в нее пропозициональных переменных Х, У, Е Таким образом, истинностные значения первой формулы, т.е.
формулы (У~ (У-+ -зХ)) -+ Г(Х, У, 2), будут конечно же зависеть от значений формулы Г(Х, У, У). Таблица имеет следующий вид: При вычислении значений в предпоследнем столбце использованы следующие соотношения: 1 -+ Г= Г, О -+ Г- =1. Чтобы теперь найти требуемую формулу Г(Х, У, У), нужно сначала определить, какие истинностные значения принимает она на всевозможных трехэлементных наборах, составленных из нулей и единиц. Это надлежит выяснить исходя из того требова- 66 ния, что из формулы (У~ (У-+ -~Х)) -э Глогически следует формула Ул -~Е Для этого сопоставим столбцы их истинностных значений. Если формула Г(Х 1; Л) такова, что Г(0, О, 0) = 1, то, поскольку в первой строке таблицы значений для Ул ~Устоит О, формула Ул -~Хне может быть логическим следствием формулы (У ~ ( У-+ -чХ)) -+ Г, так как значением формулы (У» ( У вЂ” э -чХ)) -+ -+ Г(Х, У, 2) при Х = О, У= О, У = 0 является именно значение Г(0, О, 0) = 1.
Следовательно, Г(0, О, 0) = О. Аналогично находим Г(0, О, 1) = Г(0, 1, 1) =Г(1, 0,0) =Г(1,0, 1) = Г(1, 1, 1) =О. Далее, в 3-й строке рассматриваемых двух таблиц значение формулы Ул ~бранно 1. Следовательно, какое бы значение при Х=О, У= 1, У = 0 ни принимала формула (У ч (У-+ тХ)) -+ Г (а оно совпадает со значением Г(0, 1, 0)), отношение следования здесь нарушаться не будет. Аналогична ситуация с 7-й строкой, хотя там значение формулы (У ч (У-+ ~Х)) -+ Г(Х, 1; У) никак не связано со значением формулы Г(Х У, Я) при Х= 1, У= 1, У = О. Таким образом, получаем таблицу истинности для искомой формулы Г(Х, У Х) (на месте символа * может стоять любое значение 0 или 1): Это дает возможность получить четыре формулы, не равносильные между собой и удовлетворяющие условию задачи.
Столбцы их истинностных значений представлены в последней таблице. Из них видим, что Г,(Х, У, 2) — любая тождественно ложная формула. Для определения вида остальных формул нужно воспользоваться СДН-формой: Г2(Х, У, У) = Хл Ул -тУ; Гз(Х У Я) = — -зХл Ул -~У; Г4(Х У, Я) = (Х л Ул ~У) ч (~Х л Ул -~Я) — = Ул -чЕ Для проверки нужно подставить найденную формулу вместо Гв левую формулу, данную в условии, и либо равносильно преобразовать полученную формулу к такому виду, что следование форму- 67 лы У л -зХ станет очевидным, либо составить таблицу истинности полученной формулы и, руководствуясь определением логического следования, сравнить ее с таблицей значений формулы Ул -чЕ Проверим, например, формулу Рг.' (Х~(У-+~Х))-«Г,(Х, У, Л) — = (У~(У-+-~Х))-»(Хл Ул-ч2) —= = -з(Уч -зУн -чХ) ч (Хл Ул -зЯ) — = (-зал Ул Х) ч (Хл Ул -зЯ) —= — = Хл Ул -~У. Ясно, что Хл (Ул -з У) ~= Ул -зУ(конъюнкция сильнее каждого из сомножителей).
Проверьте самостоятельно правильность нахождения остальных формул. й 3. Приложения алгебры высказываний к логико-математической практике В этом параграфе собраны разноплановые задачи, обьединяемые тем, что при решении каждой из них могут быть применены методы алгебры высказываний. Первая группа задач посвящена нахождению обратных и противоположных теорем для исходных прямых теорем, имеющих разнообразные логические структуры. Далее следуют задачи на применение принципа полной дизъюнкции (теоремы об обратимости системы импликаций) для доказательства справедливости обратных теорем, на установление необходимых и достаточных условий, на упрощение совокупностей высказываний, на построение умозаключений из данных посылок.
Заключительная группа задач этого параграфа — это, как их иногда называют в школьной практике, логические задачи, или задачи на рассуждение. Некоторые из них могут быть решены и без применения алгебры высказываний: «методом рассуждений», но методы алгебры высказываний обеспечивают гарантированный успех при их решении.
Обратная и противоположная теоремы. Решить задачи 3.1 — 3.10. 3.1. Сформулируйте утверждения, обратные следующим теоремам: а) Если последовательность рациональных чисел сходится, то она фундаментальна (т.е. является последовательностью Коши); б) Если последовательность сходится, то она ограниченна; в) Если треугольник равнобедренный, то углы при его основании равны; г) Если четырехугольник — ромб, то его диагонали взаимно- перпендикулярны; д) Если параллелограмм — ромб, то его диагонали взаимно- перпендикулярны; е) Точка пересечения диагоналей параллелограмма является его центром симметрии; ж) В прямоугольном треугольнике квадрат длины гипотенузы равен сумме квадратов длин катетов; 68 з) Если последовательность монотонна и ограниченна, то она имеет предел; и) Если каждое слагаемое является четным числом, то и сумма — четное число; к) Если в четырехугольник можно вписать окружность, то суммы длин его противоположных сторон равны между собой; л) Если свободный член с квадратного уравнения ах~+ Ьх+ с=О (а;» 0) равен нулю, то один из корней этого уравнения равен нулю.
Какие из обратных утверждений истинны, т.е. являются теоремами? Р е ш е н и е. а) Для утверждения вида «Если А, то В» (или символически А -+ В) обратным является утверждение «Если В, то А (или символически В -+ А). Так как формулы Х-+ У и У-» Х не равносильны (проверьте, составив их таблицы истинности), то высказывания А -» В и В -+ А не обязаны быть одновременно истинными. Другими словами, если А -+  — теорема, т.е. в данном случае верное угверждение, то В -+ А таковым может не быть. Именно так обстоит дело в настоящем примере. Обратное утверждение: «Если последовательность в множестве рациональных чисел фундаментальна, то она сходится к некоторому элементу этого множеств໠— неверно.
(Фундаментальной, но не сходящейся в множестве рациональных чисел последовательностью является, например, последовательность рациональных приближений к какому-нибудь иррациональному числу, скажем, к,/2 .) 3.2. Сформулируйте предложения, противоположные теоремам, приведенным в задаче 3.1. Какие из этих предложений верны, т.е. сами являются теоремами? Сопоставьте ответы на этот вопрос с ответами на второй вопрос задачи 3.1.
Совпадают ли они? (Если какие-нибудь два ответа не совпадут, то один из них неверен.) Решен ие. а) Для данного предложения А -+ В противоположным ему является предложение -»А -+ -»В. Формулы Х-+ Уи -»Х-» -»Уне равносильны (составьте и сравните их таблицы истинности), поэтому если А -+  — теорема, то противоположное предложение »А -+ зВ может теоремой не бьггь.
Но ввиду закона контрапозиции У-+ Х = -зХ вЂ” » -з У(см. задачу 1.28, д) обратное утверждение В -+ А и противоположное утверждение -»А -+ -»В для данной теоремы А -+ В одновременно истинны или нет. Поэтому ответы об истинности утверждения из задачи 3.1 и противоположного утверждения из данной задачи должны совпадать. Противоположное утверждение в настоящем примере формулируется так: «Если последовательность рациональных чисел не сходится, то она не фундаментальна». 3.3.
Для каждой теоремы из задачи 3.1 сформулируйте теорему, равносильную ей согласно закону контрапозиции (см. задачу 1.28, д), т.е. теорему, обратную противоположной. 69 Решение. а) На основании закона контрапозиции Х-+ У=- - =-з У-+ ~Х некоторое утверждение А -+ В и обратное противоположному ему утверждение зВ -+ зА одновременно истинны или ложны. Поэтому если А -+  — теорема, то теоремой будет и утверждение -зВ-+ -~А. Причем доказывать эту теорему нет необходимости: она вытекает из прямой теоремы А — » В и логического закона конграпозиции.
В настоящей задаче теорема, обратная противоположной, формулируется так: <Если последовательность рациональных чисел не фундаментальна, то она не сходится». 3.4. Пользуясь законом контрапозиции, докажите теоремы: а) Если «ш — нечетное число, то т и «нечетны (т, « — целые числа); б) Если значение выражения 21/(Р+ 1) — иррациональное число, то г иррационально; в) Если а~ » Ь~ ~ О, то а ~ 0 или Ь ~ 0; г) Если две прямые порознь параллельны третьей прямой, то они параллельны между собой; д) Если две параллельные прямые пересечены третьей, то внутренние накрест лежащие углы равны; е) Среди простых чисел нет наибольшего.
Р е ш е н и е. г) Докажем утверждение, обратное противоположному для данного, а именно: «Если две прямые не параллельны между собой, то по крайней мере одна из них не параллельна третьей прямой». В самом деле, пусть различные прямые 1, и 1~ не параллельны.
Тогда они пересекаются в некоторой точке М Утверждаем, что либо 1, не параллельна третьей прямой 1, либо 1~ не параллельна 1 Действительно, в противном случае через Мпроходили бы две различные прямые 1, и 1в параллельные третьей прямой 1, что противоречило бы аксиоме о параллельных Евклида. Утверждение, обратное противоположному, доказано.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
