В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 43
Текст из файла (страница 43)
Правильные и неправильные рассуждения. Решить задачи 10.9 и 10.10. 10.9. Проанализируйте следующие рассуждения на предмет их правильности. Для этого выявите логические схемы, на которых они основаны, и выясните, справедливы ли они. а) Все люди смертны. Сократ — человек. Следовательно, Сократ смертен; б) Некоторые люди взошли на Эверест. Эдмунд Хиллари— человек.
Следовательно, Эдмунд Хиллари взошел на Эверест; в) Во всех городах за Полярным кругом бывают белые ночи. Петербург не находится за Полярным кругом. Следовательно, в Петербурге не бывает белых ночей; г) Все сильные шахматисты знают теорию шахматной игры. Иванов не является сильным шахматистом. Следовательно, Иванов не знает теорию шахматной игры; д) Некоторые змеи ядовиты. Ужи — змеи. Следовательно, ужи— ядовиты; е) Всякий металл является твердым веществом. Ртуть не твердое вещество. Следовательно, ртуть не металл. Р е ш е н и е.
е) Рассуждение основано на следующей логической схеме: (~х)(5(х) -+ Р(х)), -чР(а) ~= ~Я(а). Проверьте, что она верна. 10.10. Проанализируйте следующие рассуждения на предмет их правильности. Для этого выявите логические схемы, на которых они основаны, и выясните, справедливы ли они: а) Все рациональные числа — действительные. Все целые числа — рациональные. Следовательно, все целые числа — действительные; б) Ни одно действительное число не является мнимым числом.
Все целые числа — действительные. Следовательно, ни одно целое число не есть мнимое; в) Все целые числа — рациональные. Некоторые вещественные числа — целые. Следовательно, некоторые вещественные числа — рациональные; г) Все ромбы — параллелограммы. Все прямоугольники — параллелограммы. Следовательно, все ромбы — прямоугольники; д) Все ромбы — параллелограммы. Все прямоугольники — параллелограммы. Следовательно, все прямоугольники — ромбы; е) Некоторые четные функции периодические.
Ни одна монотонная функция не является четной. Следовательно, ни одна периодическая функция не монотонна; 208 ж) Некоторые четные функции периодические. Ни одна монотонная функция не является четной. Следовательно, ни одна монотонная функция не является периодической; з) Все квадраты — правильные многоугольники. Ни одна трапеция не есть правильный многоугольник. Следовательно, ни одна трапеция не есть квадрат; и) Некоторые математики суть логики. Все логики знакомы с произведениями Аристотеля. Следовательно, некоторые математики знакомы с произведениями Аристотеля; к) Все студенты СГУ вЂ” жители Саратовской области. Некоторые жители Саратовской области — пенсионеры. Следовательно, некоторые студенты СГУ вЂ” пенсионеры; л) Все хирурги — врачи.
Некоторые врачи — Герои России. Следовательно, некоторые хирурги — Герои России; м) Все пловцы — спортсмены. Ни один спортсмен не курит. Следовательно, ни один курящий не является пловцом. Решение. л) Введем обозначения для предикатов: У(х): «х— хирург», Е(х): «х — врач», Н(х): «х — Герой России». Тогда посылки данного рассуждения на языке логики предикатов запишутся в следующем виде: (чхКН(х) -э Е(х)) и (ЗхКЕ(х) л Н(х)), а заключение — в виде (ЗхКН(х) л Н(х)).
Таким образом, структура данного умозаключения имеет следующий логический вид: ('ФхКН(х) -+ Е(х)), (ЗхКЕ(х) л Н(х)) ~= (ЛхКУ(х) л Н(х)). Выясним, верно ли данное логическое следование. Рассуждаем методом от противного. Допустим, что оно неверно, т.е. для некоторых конкретных предикатов А(х), В(х), С(х), заданных над множе- ством М, имеет место: Ц(ЧхКА(х) -+ В(х))] = 1, Х[(ЛхКВ(х) л л С(х))] = 1, но Р~[(ЛхКА(х) л С(х))] = О. Из первого и третьего соотношений тогда следует, что Х[А(а) -+ В(а)] = 1 и Х[А(а) л С(а)] = 0 для любого а е М из второго — ЦВ(Ь) л С(Ь)] = 1 для некоторого Ь е М Итак, если предикаты А(х), В(х), С(х), заданные над множеством М, таковы, чгоА'~ В', В'л С'~ Я, аА'л С'=Я, то все полученные соотношения будуг удовлетворены. Например, А(х): «х — рациональное число», В(х): «х — действительное число», С(х): «х — иррациональное числом Это и означает, что рассматриваемое следование неверно. м) Введем обозначения для предикатов: Е(х): «х — пловец», С(х): «х — спортсмен», К(х): «х — курильщик».
Тогда посылки данного рассуждения на языке логики предикатов запишутся в следующем виде: (чхКЕ(х) -» С(х)) и (~гхКС(х) -+ -1К(х)), а заключение — в виде (чхКК(х) -+ ~А(х)). Таким образом, структура данного умозаключения имеет следующий логический вид: (чхКТ,(х) -+ С(х)), (чхКС(х) -+ -1К(х)) ~= (~~хКК(х) -+ -чТ,(х)). Выясним, верно ли данное логическое следование. Рассуждаем методом от противного. Допустим, что оно неверно, т.е.
для некоторых конкретных предикатов А(х), В(х), С(х), 209 заданных над множеством М, имеет место: Л[(~х)(А(х) -» В(х))) = ° = 1 (1), Л[(Фх)(В(х) -+ -» С(х))) = 1 (2), а Л[(«х)(С(х) -+ -зА(х)Ц = 0 (3). Из (3) тогда следует, что Л[С(Ь) -+ -зА(Ь)) = 0 для некоторого Ь е М, т.е. Л[С(Ь)) = 1 (4) и Л[А(Ь)) = 1 (5). Далее, из (1) следует, что Л[А(а) -+ В(а)) = 1 для любого а е М, и в силу (5), это дает Л[В(Ь)) = 1 (6). Далее, (2) и (6) дают ЦС(Ь)) = 0 (6), что противоречит (4). Вывод: рассмотренное логическое следование выполняется и проведенное рассуждение верно. Логика нредикатов и алгебра множеств.
Решить задачи 10.11 и 10.12. 10.11. Докажите на языке логики предикатов следующие утверждения из алгебры множеств (используйте при этом определение равных множеств А = В «» (тх)(х е А ++ х е В), вытекающий из него критерий А = В «=» А ~ В и В ~ А, и тавтологии логики высказываний и(или) логики предикатов): а) А «» А = А (идемпотентность объединения); б) А «.» А = А (идемпотентность пересечения); в) А «» В= В»» А (коммугативность объединения); г) А «» В= В»-» А (коммутативность пересечения); д) (А «.» В) «.» С= А»» (Ви С) (ассоциативность объединения); е) (А «» В) «» С= А «» (Вг» С) (ассоциативность пересечения); ж) А и (В»-» С) = (А «.» В) г» (А и С) (дистрибутивность объединения относительно пересечения); з) А г» (В «.» С) = (А «.» В)»» (А «-» С) (дистрибутивность пересечения относительно объединения); и) А «.» (В г» А) = А (1-й закон поглощения); к) А г» (В «.» А) = А (2-й закон поглощения); л) А«.»В = Аг»В (1-й закон де Моргана); м) Аг В=А«.»В (2-й закон де Моргана); н) А «.» У= У, А «-» У= А; о) АиЯ=А,АиЯ=Ы; п) А«»А=У,Аг~А=И; р) Й=(~, Р=о; с) А=А; т) А~В=А«» В; у) Ас В«» А и В=А; ф) А с В «=» А и В = В; х) АаА«.» В; ц) А «-» В а А.
Решение.а)хеАнА«»хе Архе А«-.~хе А.Напоследнемшаге применена тавтология из теоремы 3.2, а Учебника: (Р ч Р) ++ Р. е) х е (А л В)»-» С «~ х е А л В л х е С ««(х е А л х е В) л х е С «« «=» х е А л (х е В л х е С) ««х е А л х е В г» С «=» х е А «» (В г» С). Использована тавтология из теоремы 3.2, г Учебника: ((Р л Д) л л Я) «-» (Р л ((2 л Я)).
210 и) х е А (.) (В г) А) «=» х а А !х а В г) А «=» х а А ч (х а В ( х а А) «=» е» х а А. Использована тавтология из теоремы 3.2, е Учебника: (Рч 1 (Д >«Р)) «-» Р. л) ха А(.>В «=» ха А(.) Ве»-)(х е А(.! В) «» -((х е А)«х а В) «=» «» -з(х а А) >« ~(х а В) «» х а А л х а В е» х а А л х е В «=» х е а А (.) В. Использована тавтология из теоремы 3.2, ж Учебника: ~(Р «Д)++ («Р «« -)Д).
у) А г) В = А е» А г) В с А л А с А (-«В «» (х е А г) В -+ х а А ) л (х я а А » х е А г) В) е» ((х а А л х а В) -» х а А) л (х а А -+ (х а А л л х а В)) е» 1 л (х а А — » (х а А л х а В)) «=» х е А -+ (х а А л х е е В) «=» -)(х а А) «> (х а А л х а В) е-.» (-)(х а А) «х а А) л (((х а а А) ч х а В) е» 1 л (~(х я А) ) х е В) е» (х я А -+ х е В) «=» А с В. Проанализируйте приведенную цепочку рассуждений и выявите использованные тавтологии.
х) ха А=»хе А««ха Ве»хе А(.) В. Использованатавтологияиз теоремы 3.2, б Учебника: Р -+ (Р ! Ц). ц) ха АлВ»»ха Алх а В>»ха А. Использованатавтологияиз теоремы 3.2, б Учебника: (Р ( Ц) -+ Р. 10.12. Докажите на языке логики предикатов следующие утверждения из алгебры множеств. Используйте при этом определения объединения и пересечения семейств множеств ЦМ, =(х:(3!'а1)(хаМ())> ПМ! =(х:(«((а1)(хе М!Ц и тавтологии логики высказываний и(или) логики предикатов: а) Х г) 1 ) у) = 1 ) (Х () 11); Ы1 >е1 б) Х ПУ)»(1(Х У)); 1»1 )е! в) (О Х!) ~(Ц У!)» Ц (Х! (.)У!); !т 1 (1, !) »1«>1 г) (ПХ() (П у!)= П (Х) у.); 1»1 ((, Л«1«>1 д) ф Х(),(Ц У!) = ) 1 (Х(,,У!); 1»1 1е.) (1, 1)е(».1 1«1 !е1 (), !)»1>>1 ж) ()Х! =ПХ,; >е1 (е( з) ПХ,»11Х(; Ы( (е! 211 и) (О Х() (Ц уу) = ] ] (Х у)); 1 «,1 (1, 1) «1е1 к) (П Х)) х (П 1 ) = П (Х( х У ).
е»1 1«1 (С1)е) 1 Р е ш е н и е. к) Рассуждаем следующим образом: (х, у) е (П Х,) х ( П 11) «» х е (П Х,) л у е (П );) «=» (И е У)(х е 1е) )е1 )«1 1«1 е Х.) л (Ч/ е .7)(у е 1;.) «» (М е 1)(»/ е У)((х е Х) л (у е у~)) «» «» (У(1', 1) а 1 х У)((х, у) е Х х 11) «» (х, у) а П (Х, х 1'-). (Ь1)«1 1 Равносильные преобразования неравенств и уравнений при их решении. Каждое уравнение и каждое неравенство с одним неизвестным представляет собой одноместный предикат, заданный, чаще всего, над множеством вещественных чисел. Все решения того или иного уравнения или неравенства представляют собой множество истинности соответствующего предиката. Решение уравнения или неравенства есть не что иное, как равносильное его преобразование: ведь на каждом шаге мы хотим сохранить множество корней (т.е. множество истинности), не потеряв ни одного и не добавив лишнего; в конце преобразований мы приходим к столь простому уравнению или неравенству (или их системе), из которого его множество истинности (и, значит, множество истинности исходного уравнения или неравенства) отчетливо видно.
Процесс же равносильных преобразований есть уникальный синтез математики и логики: математическое существо подвергается логическому анализу. Непонимание законов логики приводит к запугыванию в случаях и подслучаях, математика здесь тогда не выручает. Придумываются различные методы решения (например, метод интервалов), позволяющие не упустить ни одной возможности, но все они вторичны.
Первична же логика равносильных преобразований. 10.13. Выделите логическую систему случаев для решения неравенств и уравнений следующих типов: а) /(х)/я(х) > 0; ж) ]/(х)] > я(х); б) /(х)/я(х) < 0; з) /(]х]) = я(х); в) Щ(х) < я(х), где Ус е Ф; и) ]/(х)] = я(х); г) Щ(х) > я(х), где I( е М; к) Ь(]/(х)]) = я(х); д) 1об,Ях) > 1оа, я(х); л) ]Ц/(х)])]=я(х). е) ]/(х) ] < р (х); Р е ш е н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
