Игошин Математическая логика и теория алгоритмов (1019110), страница 20
Текст из файла (страница 20)
Первая посылка А -» В: «Если а и Ь вЂ” целые числа, то их Разность а — Ь существует и есть число целое». Вторая носылка А: "Числа 3 и 5 (а также 7 и 5) — целые», Заключение В; «Разности 3 — 5 и 7 — 5 существуют, и 3 — 5 = — 2, 7 — 5 = 2». 79 Данное умозаключение сделано по правилу МР: Х » ); Х ~ )' и потому является правильным. Второй шаг (возведение чисел -2 и 2 в квадрат). Первая носылка А -» В: «Если число а целое, то его квадрат а' существует и является неотрицательным целым числом». Вторая досылка А: «Число -2 (а также число 2) — целое».
Заключение В: «Квадраты чисел -2 и 2 существуют, причем (-2)' = 4 и 2' = 4». Умозаключение и здесь сделано по правилу МР: Х-» Р Х ~ ); и потому и на этом шаге рассуждения ошибка не допущена. Третий шаг (заключение о равенстве чисел 3 и 7). Первая лосылка А -+ В: «Если целые числа равны, то равны и их квадраты». Вторая посылка В: «Квадраты целых чисел -2 и 2 равны: 4 = = 4». Заключение А: «Равны сами числа — 2 и 2, т.е. 3 — 5 = 7 — 5, т.е. 3 = 7», На данном этапе рассуждения умозаключение сделано по схеме: Х-+ ); 'г' ~ Х, которая не является правильной. Следовательно, в этом умозаключении сделана логическая ошибка, которая и привела к ложному выводу, несмотря на то что исходили мы из всех истинных посылок.
Второй распространенный тип неправильных рассуждений выглядит так. Мы исходим из некоторого неверного предположения и, правильно рассуждая, приходим к некоторому выводу. Отсюда делаем заключение, что полученный вывод неверен. С точки зрения математической логики схема этого рассуждения такова: из истинности утверждений Хи Х вЂ” » г'делается вывод об истинноети утверждения К Следующие два примера рассуждений, основанных на этой схеме, позволяют ответить на вопрос о ее правомочности. Пример 7.14.
«Если число натуральное, то оно рациональное (А » В). Число 3/4 не натуральное ( А). Следовательно, число 3/4 не рациональное (. В)», Пример 7. 15. «Если число натуральное„то оно рациональное (А -+ — » В). Число /2 не натуральное (-А). Следовательно, число /2 не рациональное ( В)». В каждом из этих рассуждений обе посылки являются истинными утверждениями.
Но в первом случае мы приходим к ложному заключению (число 3/4 — рациональное), а во втором — к истинному (число,/2 нерациональное). Это снова означает, что неверной является сама схема построения умозаключения, примененная в этих примерах, т.е.
эта схема при всех истинных посылках не обязательно дает истинное следствие. Вывод, основанный на примерах, подтверждается математической логикой: из формул Х-+ Уи -Хне следует формула - ); в чем нетрудно убедиться, проверив, что формула ((Х-+ У) л Х) — > 'г'не является тавтологией. 80 Решение «логических» задач. Алгебра высказываний может быть с успехом применена к решению олного типа задач, которые на- зывают «логическими». Эти задачи можно решать и непосредствен- ным рассуждением, но не всегла очевиден путь таких рассужде- ний. Применение алгебры высказываний дает единый и достаточ- но общий метод решения указанных задач. Рассмотрите задачи 1чо 3.54 и 3.57 в Задачнике.
Отметим некоторые особенности решения «логических» задач методами алгебры высказываний. В таких задачах, как правило, имеется ряд высказываний, относительно которых известно, что столько-то из них истинны, а столько-то ложны, но не известно, какие именно истинны, а какие ложны. Например, имеется три высказывания (7, Р И~ из которых два истинны, а одно ложно. Учитывая эти условия, нужно составить из этих высказываний некое сложное высказывание, которое будет заведомо истинно (или ложно). Затем, используя законы логики, преобразовать его к виду, из которого определится ответ на вопрос задачи. В процес- се равносильных преобразований использовать другие условия за- дачи. В рассматриваемом примере такое сложное высказывание строится исходя из следующих соображений.
Так как из высказы- ваний 11, Р, И'два истинны, то все дизъюнкции пар этих выска- зываний также будут истинны: (7 ~ Р, Уч И', Р'ч 1К Следователь- но, будет истинной и конъюнкция этих высказываний: (Уч Р) л л ((7~~ 1Р) л ()'~~ И'). Равносильное преобразование этого выра- жения будет зависеть от структуры высказываний У, Р 1К Разбе- рем пример решения такой задачи. Пример 7.1б.
Перед финалом школьного шахматного турнира, в который вышли Александров, Васин и Сергеев, один болель- щик сказал, что первое место займет Александров, второй бо- лельщик сказал, что Сергеев не будет последним, а третий— что Васину не занять первого места. После игр оказалось, что один болельщик ошибся, а два других угадали.
Как распредели- лись места, если никакие два участника не заняли одно и то же место? Для решения введем следующие высказывания (1= 1, 2, 3): А,: «Александров занял 1-е место>, В;: «Васин занял 1-е место»,. С,: «Сергеев занял 1-е место». Тогда три высказывания болельщиков можно записать так: 1-й болельщик (7: А~,' 2-й болельщик Р: С~', 3-й болельщик И'. Вь Составим сложное высказывание, которое будет заведомо истин- ным. Так как из трех высказываний (7, Р )г'два высказывания ис- тинны, то каждая из дизъюнкций ((7 ~ Р), ((7 ~ И~), (Рч И~) будет истинной, а значит, истинной будет и их конъюнкция ((7 ~ Р) л 81 л (У ч И") л (Ич И'). Преобразуем это высказывание равносильным образом: (У ч И) л (Уч И') л (~'ч И") в (А, ч — Сз) л (А, ч - В,) л л (- С, ч В>) = (А~ ч (А> л . В,) ч (-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,т.е. В,=О.Здесьмы получаем две возможности распределения мест: АВС или АСВ; В, л С,=1.Тогда В,=1 и С,=1,т.е. В,=О и С,=О. Здесь варианты распределения такие: АСВ, САВ, СВА. В итоге получаем варианты ответов: АСВ„АВС, САВ, СВА. Проверяя первый вариант, видим, что при нем истинными оказываются все три высказывания У, К И" болельщиков, что не соответствует условию задачи.
Окончательно получаем три решения: АВС, САВ, СВА. Рассмотренный метод решения привел к получению своего рода «лишнего корня», что потребовало проверки полученных вариантов на соответствие условию задачи. Рассмотрим более тонкий метод, который сразу даст только те ответы, которые удовлетворяют условию задачи. Он основан на составлении вместо высказывания (Уч И) л (У ч Ил) л (И ч И') такого высказывания, которое более точно передает (описывает) суть условий задачи.
Эта передача (описание) достаточно точна для того, чтобы не могло возникнуть никаких двусмысленностей и кривотолков. Для составления такого высказывания кроме У, К И'рассмотрим также высказывания: Х: «1-й болельщик угадал»; У; «2-й болельщик угадал»; У: «3-й болельщик угадал». Тогда нетрудно понять, что из двух высказываний Хл Уи Хл л- ваточно одно высказывание истинно. Значит, истинна и их дизъюнкция: (Хл У) ч ( Хл У). Аналогично, истинны следующие высказывания, связанные со 2-м и 3-м болельщиками: (Ул Р) ч ч (- Ул — Р) и (Ул И') ч (-Ул — И').
Следовательно, истинна и конъюнкция всех этих трех высказываний: Их. и) ( х и)). Иу Р) ( у и)) Ик и) ( г и)). (7.1) 82 Для преобразования этого высказывания нужно применить закон дистрибутивности конъюнкции относительно дизъюнкции. В итоге получится СДН-форма от переменных Х, У, У, 11, К И'. Но многие ее совершенные конъюнктивные одночлены в силу условий задачи окажутся равными О. Так как из трех высказываний Х, У, ваточно два высказывания истинны, конъюнктивные одночлены, содержащие сомножители Хл ~Ул Х, Хл ~Ул Х, Х л У л — У, — Х л — У л — У, обратятся в О.
Так как из трех высказываний Х, 1; Уодно высказывание ложно, конъюнктивный одночлен„содержащий сомножитель Х л У л У, также равен О. В итоге в СДН-форме останутся лишь три совершенных конъюнктивных одночлена: это те, которые содержат сомножители Х л Ул У, -Хл Ул У, Хл Ул Е Данная СДН-форма имеет вид (Хл Ул -ч~л ч' л к л — )г) ч (-~Хл Ул Ул — Ул Ул И') ч (Х л л — УлУл Пл — Ил И). Для рассматриваемой задачи эта СДН-форма имеет вид (Х л Ул -2' л А~ л -~Сз л В~) ч (-~Х л У л У л -А~ л -~Сз л -~В~) ч ч (Хл — Ул Ул А, л Сз л -~В~).
Истинность этого высказывания означает, что истинна хотя бы одна элементарная конъюнкция. Рассмотрим последовательно все эти случаи: 1) Х л У л У л А, л С, л В, = !. Тогда А, = 1, Сз — — 1, а следовательно, С, = О и В, = 1. Этот случай не может иметь места, так как А и В оказываются на первом месте; 2) Хл Ул 2'л -А~ л -~Сз л В~ — — 1. Тогда А~ = 1, Сз = 1, — В~ = 1 и, следовательно, А, = О, С, = О, В, = О, т.е. получаются две возможности распределения мест: САВ, СВА; 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}
