В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 3
Текст из файла (страница 3)
Решение. л) Искомое высказывание должно быть ложно лишь в одном случае: когда высказывание Сложно, а оба высказывания А и В истинны. Таким высказыванием могло бы стать 12 высказывание вида М-+ С, где высказывание Мдолжно быть истинно и так сконструировано из высказываний А и В, что если хотя бы одно из высказываний А или В будет ложным, то ложным станет и М.
Ясно, что в качестве М следует взять конъюнкцию А л В. Итак, искомое высказывание имеет следующий вид: (А л В) -+ С. 1.1б. Определите логическое значение последнего высказывания, исходя из логических значений всех предыдущих высказываний: а) Л(А — > В) = 1, Л(А ++ В) = О, ЦВ-+ А) =; б) Л(А-э В) =1, Л((-зАл В)-+(-зАч В)) =; в) Л(А++ В) =О, Л(-тВ-+А) =; г) Л(А л В) = О, Л(А -+ В) = 1, Л(В-+ -зА) =; д) Л(А ++ В) = О, ЦА -+ В) = 1, Ц(-тА -+ В) ++ А) =; е) Л(А ч В) = 1, Л(А -+ В) = 1, Л(-зВ-+ А) =; ж) Л(А л В) = О, Л(А++ В) = О, ЦА -+ В) = 1, Л(А) =; з) Л(А л В) = О, ЦА++ В) = О, Л(А -+ В) = 1, Л(В) =; и) ЦА л В) =О, Л(Ач В) = 1, ЦА-+ В) = 1, Л(В-+А) =; к) Л(А -+ (В++ А)) = О, ЦА -+ В) =; л) Л((А ч В)-+А)=1, Л(А-+В)=1, Л(~А++-зВ) =; м) Л(А++ В) =1, Л((А-+В) л (-зА-+-зВ)) = .
Решение. л) Из первого условия Л((А ч В) -+А) =1 заключаем, что невозможна ситуация, когда ЦА ч В) = 1, а Л(А) = О, т.е. ЦА) = О и при этом Л(В) = 1. Второе условие Л(А ч В) = 1 исключает ситуацию, при которой ЦА) = 1 и ЦВ) =О. Следовательно, высказывания А и В имеют одинаковые значения истинности. Значит, одинаковые значения истинности имеют и их отрицания -~А и -~В. А раз так, то высказывание -зА++ ~В будет истинным. м) Из условия Л(А++ В) = 1 следует, что А и В имеют одинаковые значения истинности. Тогда одинаковые значения истинности имеют и их отрицания -чА и ~В.
Значит, обе импликации А — ~ В и ~А + -~В истинны. Следовательно, истинна и конъюнкция двух последних высказываний. 1.17. Для каждого из помещенных ниже высказываний определите, достаточно ли приведенных сведений, чтобы установить его логическое значение (если достаточно, то укажите это значение; если недостаточно, то покажите на примерах, что возможны и одно и другое истинностные значения): а) А л(В-э С), ЦВ-+ С) =О; б) А ч( — > С), Л(В) =О; в) -з(А ч В) ++ (-зВ л ~А ), Л(А ) = 1; г) (А -+ В) -+ (~А -+ -зВ), Л(В) = 1; д) (А л В) -+ (А ч С), Л(А) = О; е) -з(В-+А)++-з(Ач С), ЦА)=1; ж) (А++ В) ч(А л С), Л(А) =О; 13 з) (~(А-+ В)-+(А л ~В)) ч С, Л(А-+ В) =0; и) (А л-зС)++((~А я~С) -+(В л Р)), Л(А г В) =0; к) А-+(В++ С), Л(В) =1; л) (А -+ (В ~~ -ч С)) ++ С, Ц С) = 0; м) (А л В) -+ ((зА++ С) л (В ч С)), ЦА л В) = 1.
Р е ш е н и е. л) Поскольку Л(С) = О, то Л(-~ С) = 1 и, следовательно, Л(В ~ -з С) = 1, независимо от значения Л(В). Далее, имеем Л(А-+ (Вч ~С)) = 1, независимо от значения ЦА). Наконец находим Л1((А-+ (Вч ~С)) ++ С]= Л(А-+ (Вч ~С)) ++ Л(С) = 1++ 0 = О. Таким образом, если С вЂ” ложное высказывание, то и все данное высказывание также будет ложным, т.е. приведенных сведений достаточно для того, чтобы определить логическое значение данного составного высказывания.
м) Поскольку Л(Ал В) =1, то ЦА) =1 и Л(В) =1. Тогда Л(Вч ч С) = 1, независимо от значения Л(С). С другой стороны, относительно значения Ц~А++ С) мы не можем высказаться определенно при имеющихся данных (Л(~А) = 0). Оно может оказаться как истинным (при Л(С) = 0), так и ложным (при Л(С) = 1). В первом случае следствие данного составного высказывания окажется истинным, а во втором — ложным. Следовательно, в первом случае, т.е.
при Л(С) = О, данное в задаче высказывание истинно, а во втором, т.е. при Л(С) = 1, — ложно. Таким образом, приведенных сведений недостаточно для того, чтобы установить логическое значение данного высказывания. 1.18. Существуют ли три таких высказывания А, В, С, чтобы одновременно выполнялись для них следующие условия: а) Л(А л В) = 1, Л(А л С) = О, ЦА л В л -~ С) = 0; б) Л(В-+А) = 1, ЦАч С) =О, ЦА++(Вл~С)) =0; в) Л(А ч В) = О, Л(~В л С) = 1, Л((А ч -з С) ++ (-~ В -+ -з С) = 1; г) ЦА л -зВ) = 1, ЦВ ч С) = 1, Ц-з(В-+ А) ~~ С) = 0; д) Л(зА л В) = О, Л(А ч С) = О, Ц(А ч В) а з С) = 1; е) Л(А ч В) = О, ЦВ ч С) = 1, Л(( С-+ А )ч (С-+ В)) = 1; ж) Л(А -+ В) = О, ЦА -+ С) = 1, Л((С-+ А) -+ (С-+ В)) = 1; з) ЦА ч С) =1, ЦАч В) =О, ЦС-+(Ач В))=1; и) Л(В ~~ С) = О, Л(~ С-+ А) = О, ЦА -+ В) = 0; к) Л(А л С) = 1, Л(С++ -чВ) = О, Л(А -э В) = 1; л) Л(А к~В) =О, Л(В-ь (Ач С)) =О, Ц~С-+-юВ) =1.
Р е ш е н и е. л) Из первого условия, по определению дизъюнкции, следует, что Л(А) = 0 и Л(-зВ) = О, т.е. ЦВ) = 1. Тогда второе данное условие, по определению импликации, влечет Л(А ч С) = О. Отсюда Л(С) = О. Следовательно, Л(-ч С-+ -зВ) = -зЛ(С) -э ~Л(В) = = ~0 -+ з1 = 1-+ 0 = О, что противоречит третьему данному условию. Значит, трех высказываний А, В, С, удовлетворяющих данным условиям, не существует.
1.19. Для каких из следующих высказываний их логическое значение не зависит от логического значения высказывания А: 14 а) АлО; г) Ач~А; ж) А-«-зА; к) -~А-«А; б) А-+1; д) АчО; з) Ал1; л) Ач1; в) А-+А; е) 0-+А; и) А+«А; м) А<-«-«А. Р е ш е н и е. л) По определению дизъюнкция двух высказываний истинна тогда и только тогда, когда по меньшей мере одно из этих высказываний истинно. Следовательно, высказывание А ч 1 истинно, независимо от логического значения высказывания А. м) Ясно, что высказывания А и зА имеют противоположные логические значения (т.е. 0 и 1 или 1 и О). Поскольку эквивалентность двух высказываний истинна тогда и только тогда, когда эти высказывания имеют одинаковые значения истинности, то эквивалентность А++ ~А высказываний А и зА ложна, независимо от значения истинности высказывания А.
1.20. Докажите теорему об обратимости системы двух импликаций: если истинны высказывания А~ -+ Вь А2-+ Въ А, ч Аъ -~(В, л и Вг), то истинны и высказывания В, -+А„В,-+ Аж 1.21. Докажите теорему об обратимости системы т импликаций (принцип полной дизъюнкции): если истинны высказывания А~ -+ Вь Аг — «Въ ..., А — «В, А~ ч А2 ч ...
ч А, -з(В; л В~), 1л/, ,1= 1, 2, ..., и, то истинны и высказывания В~ — «Аь В2 — «Аы ..., В„-+ А„. Формулы алгебры высказываний. Пропозияиональными переменными называются такие переменные, вместо которых можно подставлять конкретные высказывания. Эти переменные будем обозначать:Р, Д,й,о", ...,Рь Р,,Рз, ...,Х, КУ,ХьХмХп ... Понятие 4юрмулы алгебры высказываний определяется следующим (инлуктивным) образом: а) всякая пропорциональная переменная есть формула; б) если Г, и Г2 — формулы, то выражения зГ, (Г, и Г,), (Г, ч ч Г,), (Г, -+ У;), (У; +«Г,) также являются формулами; в) других формул, кроме построенных по правилам двух предыдущих пунктов, нет. Обычно внешние скобки у формулы договариваются не писать. Под4ормулой формулы называется всякая ее часть, которая сама является формулой.
Если Г(Х,, Х„..., Х„) — формула алгебры высказываний, содержащая пропозициональные переменные Х„Х„..., Х„, и А„А„..., А„— некоторые конкретные высказывания, то, подставив последние в данную формулу вместо соответствующих пропозициональных переменных, получим составное высказывание Г(А„Аъ ...,А„). Логическое значение Х(Г(А„Ам ...,А„)) этого высказывания можно определить, если теперь вместо высказываний А„Аъ ..., А„вставить символы их логических значений (О или 1), а затем выполнить над этими символами последовательно все предписываемые формулой операции, т.е. Х(Г(Ао Аъ ..., А„)) = Г(Х(А~), Х(А2), ..., ЦА„)). Например, если 15 ЦА~) = 1, Х(Аг) = О, ЦАз) = 1, то логическое значение составного высказывания (А~ -+Аг) л-~Аз есть Х((А~ -+Аг) п -~Аз) = =(Х(А~)-+ ЦАг)) л-зР~(Аэ) = =(1-+ О) л-з1 = Оп 0 = 0.
В этом случае говорят, что формула (Х, -+ Х,) п -за принимает значение О, если входящие в нее переменные Хн Хц Хз принимают значения 1, О, 1 соответственно. Значок Х часто опускают. Это связано с тем, что в алгебре высказываний полностью отвлекаются от содержания высказываний, а изучают их только в связи с их свойством быть истинными или ложными. Поэтому каждое ложное высказывание можно рассматривать как элемент О, а истинные — как элемент 1 и писать вместо г.(Р) =0 или ЦР) = 1 лишь только Р=О или Р= 1 (этим сокращением мы будем пользоваться, в частности, при составлении таблиц истинности формул). Формула Г(Хь Хц ..., Х„) называется выполнимой (опровержимой), если существует такой набор высказываний А„А„..., А„, который обращает эту формулу в истинное (ложное) высказывание Р(А„Ам ..., А„).
Формула называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если она обращается в истинное (ложное) высказывание при всех наборах значений переменных. Обозначение тавтологии: ~= Г(Хь Хм ..., Х„). 1.22. Определите, является ли последовательность символов формулой: а) (РД); б) ((Р++ 0) п Я) -+(Рч Я)„' в) ((~Р-+ Д)-+ (Ял(цчо))); г) ((Рч-зД) -+ (Я-з Я)); д) (Р— э(Дл Я-+-зР)); е) -з((-чРл ~(г) -+(,Рч (Яп зо))); ж) ((Рч ~Д) -+ (-ъРг, -юЯ п (Д++ Я))); з) Р— ъД-+Я; и) тчР-+Р; к) (Р-+ 0) ч(0-+ Р); л) ((Рп Д)Я)-+ зЯ; м) ((Рп (-зД-+ Я))ч ((-чР++ Я) л-зц)).
Решение. л) Данная последовательность не является формулой. В самом деле, пропозициональные переменные Р, 0 и Я согласно п. а) определения формулы являются формулами. Следовательно, согласно п. б) этого определения последовательность ((Р п 0)Я) формулой не будет, так как входящие в нее формулы (Рп 0) и Я не соединены ни одним из допустимых символов: п,ч, -+ и ++. Поэтому и данная последовательность формулой не является. м) Согласно пп. а) и б) определения формулы пропозициональные переменные Р, Д, Я и выражения -зр,-зД, (~Д-+ Я), 16 (ъР~-» Я) будут формулами.
Далее, формулами будут выражения (Рл (-ъД-» Я)), ((-ъР+» Я) л-ъД). Наконец выражение ((Рл (-ъД-+ Я)) ч ((~Р++ Я) л -ъД)), пред- ставляющее собой данную последовательность, также является формулой. 1.23. В следующей последовательности символов всевозможны- ми способами расставьте скобки так, чтобы получилась формула: а) Р-+ Дл -ъЯч о'; ж) Р««Дл -ъЯ-+ о'; б) Р-» чДчЯ вЂ” » ъР— »-ъЯ; 3) Рч Дл-ъЯлРчЯ; в) ъРл Д-+ Я; и) ~Р».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
