В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 6
Текст из файла (страница 6)
Не глядя более ни в какие другие строки таблицы, на основании определения логического следствия заключаем, что формула ~Р~ ~ Д не является логическим следствием формулы т(Р л Д). Заметим, что для данных формул имеется еще один набор значений переменных (это Р= 1, Д = 0), на котором «проваливается» определение логического следования формул (если говорить о следовании формулы -~Р л -з Д из ~(Рх Д)).
В то же время на остальных наборах значений переменных определяющее свойство выполняется. Тем не менее достаточно одного «провапивающего» набора. Таким образом, формула -~Рл -~Д не является логическим следствием формулы .~(Рл Д). 1.36. Докажите, что справедливы следующие логические следования, руководствуясь определением этого понятия: а) (Р ~ -зЯ) -+ Д ~= (Р-+ Д) л Я; б) (Р-» Д) -+ Я ~= Р— » (Д-» Я); в) (Р з Д) -+ Я ~ (Р л -ч Д)ч Я; г) (Р-» Д) -+ Я ~= (Р л Д) -+ Я; д) (Рл Д) -+ Я Р вЂ” » (Д-+ Я); е) (Р~-» Д) ~ Я ~= (~Р-» -з(2)ч Я; ж) (Р ч Я)++ Д~=(Рч Я)++Я; з) ~( Р м Д) ~= -ъ Р ч Я; и) (Р «Д) -+ Я и=1 Р— » Д)ч (Р «» Я); к) Рл (Дм Я) и=~(Рч Д) л(Рч Я); л) (Рл Д)ч Я ~= Рч (Д-+ Я).
2б Выясните, будут ли верны обратные следования, т.е. будет ли формула, стоящая слева, логическим следствием формулы, стоящей справа. Решение. л) (Изучите сначала ход решения задачи 1.35„м.) Составим таблицу истинности для формул (Р л Д) ч Я и Р ч (Д -+ -э Я), участвующих в отношении следования: Последовательный просмотр по строкам столбцов (а) и (~~) показывает, что как только в какой-либо строке столбца (*) появляется 1, так сейчас же в этой строке и в столбце (а*) обнаруживается 1.
Значит, требуемое логическое следование действительно выполняется (алгоритм см. в Учебнике, с. 55). Обратное же следование неверно, поскольку, например, в первой же строке (т.е. при Р=О, 0=0, Я=О) формула Рч(Д-+ Я) принимает значение 1 (столбец (~*)), а формула (Рл Д) ~ Я тем не менее принимает значение О (столбец (*)). 1.37. Для следующих формул выясните, будет ли какая-либо из них логическим следствием другой: а) (Р— ь О) -+ Я, Р ч 0 ч Я; б) Р— ь(Д-+ Я), (Р— э 0) -+ Я; в) Я-+(Дч-чР), Р-+(Дл Я); г) Р— ь (О л Я), (Рл О) -+ Я; д) (РчЯ)++0, (Рча)++Я; е) Рч(Д-+ Я)ч Д, (Рч Д)++Я; ж) (Р ~ь 0) -+ (Д++ Я), Р-+ (Д -+ Я); з) Р-+ 0, (Р— ь Я) ~ Д; и) (Рл 0) -+ Я, (Р-+ Д)ч Я; к) (Р-ь Д) -+ (Р— ь Я), (Р— ь 0) -+ Я; 27 л) (Р л Д) -+ Я, (Р ч О) -+ Я; м) (Рл О) -+ А, Рч(Д-+ Я).
Р е ш е н и е. л) Составим таблицу истинности данных формул: Сопоставляя столбцы (~) и (еэ), видим, что во всякой строке, в которой в столбце (эе) стоит 1, в столбце (*) также стоит 1, но не наоборот (например, третья строка). Это означает, что первая данная формула является логическим следствием второй, но вторая, в свою очередь, не является логическим следствием первой. м) Составим таблицу истинности данных формул: 28 Сравнивая столбцы значений данных формул, видим, что в третьей строке первая формула принимает значение 1, а вторая— значение О, в то время как в седьмой строке вторая формула принимает значение 1, а первая — О.
Следовательно, ни одна формула из двух данных не является логическим следствием другой. 1.38. Пользуясь определением понятия логического следствия, выясните, справедливы ли следующие логические следования: а) Р-+ Д, Р— +-~0~-~р. б) Р— ь Д, Д -+ -~ Р ~= -~Р. в) Р-+ О, Р~=0; г) -~Д-э — ьР„Р~= 0; д) Р-э О, -~Р-+ 0 ~= (з; е) (Р-+ 0) + Д ~р ~у~= Я. ж) Р— э Д, Рч Я ~=1 Рч Я) -+ (Р ~ 0). з) Рч Я, Я -+ Д ~= Р ч 0; и) (Р л Д) -+ Я, ~ 0 ~= ~Я. к) Р, Я-+~(Рм Д) ~=-~Я; л) Рл 0, -зЯ-+~0~= Я; м) (Р л 0) -+ Я, -~Я ~= -з Д. Р е ш е н и е.
л) Составим сначала таблицу истинности для всех трех данных формул Р л Д, -~Я -+ -з 0 и Я, участвующих в рассматриваемом отношении: Отметим столбцы таблицы, отвечающие данным формулам Рл 0, -зЯ-+-~0, Я, символами (*), (**), (**в) соответственно. Чтобы проверить выполнимость определения логического следования для данных формул, нужно найти все те строки таблицы, в которых в обоих столбцах (~) и (*е) стоят единицы, и убедиться, что в каждой из этих строк в столбце (э~а) также стоит единица. 29 Значит, доказываемое логическое следование справедливо (строки, в которых не в обоих столбцах (*) и (**) стоят единицы, автоматически удовлетворяют условию из определения логического следования: для них посылка этого условия, представляющего собой импликацию, ложна, а значит, сама импликация истинна).
м) Составим таблицу истинности для всех трех данных формул: Найдем те строки, в которых обе посылки (Рл Д) -+ Я и -зЯ принимают значение 1. Это 1-я, 3-я и 5-я строки. При этом в 1-й и 5-й строках формула з Ц также принимает значение 1, но в 3-й строке этого не происходит: т Д принимает значение О. Именно здесь «проваливается» определение логического следования, а значит, формула ~ Д не является логическим следствием формул (Р л л Д) -+ Я и -~А. 1.39. Расположите формулы так, чтобы из каждой логически следовали все стоящие после нее: а) Рч Д, ЧР— »(Д-» Р)), -~(~Рл~Д), зР«-» Д, -~Рл Д; б) Р-+ Д, .зРл-зД, Р-+ Я-»(Рл Д)), Дч-1Р, Р«» Д; в) (Р— » О)ч Р, ~(Р-+ Ц) л -~Щ -» Р), -ъ(Р ~» Д), -1(Р л Д), тР л лД; г) Р«-» Д, -4Рч Д), ~(Р» |~Р-» О)), ~Р-» (Р— » Д), Д-»~(Рч -О); д) (з Р л О ) -+ Р, Р ч -з Д, (Р ч Д ) л (Р л Д), Р +» О, (Р -+ Ц ) ч ч(Д-» Р); е) (Рч Д) ++ Р, -1 Дч Р, (-зР— » Д) ++(Дч Р), Рл Д, Д-+ (Д-» -+ Р); ж) ~(-з Д л Р) л (Д-» Р), О ч ~Р, (~Р— » т Д) -» (Д-+ Р), -з Д-+ -» ~Р, Р-» Ц; з) (Р л Ц) -+ Д, -~Р » Ц, ~((Р«+ т Д) ++ Д), Рл Ц, (~Р— » Ц) л Р; 30 и) »(0 л (» Рч -» 0))ч (-»Р — ь Д), »-»Р, »(Р— ь Д), 0++ (Р л О), Цл-»(Р» О); к) »Р л Д, -»Д-+(Р ч-»Р), Я++ ~Р, (Рл 0) -+(Р~ь Д), Р» -+ »Д; л) (-»Д-+-»Р) ч-»Р, Р» Д, (-»Р — » Д) ч -»Р, »Р++ »Д, Р л Д.
Решение. л) Пронумеруем данные формулы в той последовательности, в какой они записаны в условии, и составим для них таблицу истинности (проверьте самостоятельно правильность ее составления): Из таблицы видно, что (5)»= (41) и (4)»= (2). Далее, формулы (1) и (2) равносильны. Наконец (1)»= (3). Итак„требуемое расположение данных формул выглядит следующим образом: (5), (4), (2), (1), (3). 1.40. Методом от противного выясните, верны ли следующие логические следования: а) Г-+ 6, К-+ А, Гч К~ бч А; б) Г-+ б, ((Гч Ь) л Н) -+ М, Ь -+ Н»= ((Гч А) л 6) -» -»М; в) (Гл 6) -+ -»Я, (Гл Н) -+ К, Г-+ -»К, (Гл -» 6) -~ Н»= Г-+ -»Я; г) Г-+ б, -»К-+»Х, Я-+ Н, -»Г-+»К Н-+А»= Я-+ б; д) (Гл 6) -+ Н, (Нл К) -+ Е, -»М-+ (Кл Е) ~ (Гл 6) -+ М; е) Г-+(б-+ Н), (Нл К)-+Ь, -»М-+(Кл-»Ь)»= Г-+(6-+ М); ж) (Гч С) -+ (Нл К), Ч(Кч Е) -+ М»= Г-+ М; з) Г-+ (бл Н), ъ»бч К (Е-~ »М) -~ »К, б-+~ Гл»Л)»= С-Ф.»,; и) (Г-+ 6) л(Н вЂ” э К), (6-+ Х) л (К-+ М), »(Ал М), Г-+ Н~=-»Г; к) Г-+ б, б-+ Н, -»Н»= -»Г; л) Г-+ б, К-+ »Н, Нч -» 6»= à — » -»К.
Решение. л) Допустим, что данное логическое следование не выполняется, т.е. существуют такие конкретные высказывания, которые превращают все формулы-посылки в истинные высказывания, а формулу-заключение Г-+ -»К — в ложное. Тогда из Г-+-»К= О следует, что Г= 1 и -»К= О, т.е. К= 1. Из Г-~ б= 1 и Г= 1 следует, что 6= 1. Далее, из Н»-»б= 1 и б= 1 заключаем, что Н=1, т.е. »Н=О.
Наконец из К-»-»Н=! и »Н=О получаем К=О. Пришли к противоречию. Следовательно, формула Г-+ -+ ~К не может превращаться в ложное высказывание, если все формулы Г-+ б, К вЂ” » -»Н, Н ч -» 6 превратились в истинные выс- 31 казывания. Это означает, что рассматриваемое логическое следование верно. 1.41. Выясните„выполняются ли следующие логические следования: а) Р-» Д, Я-+ Е, Рл Я»= О л Е; б) Р-+ Д, Я-+ Е, -»Рч-»Я»=-»Оч-»Е; в) Р-» О, Я-+Я, -»Дл-»Е»=-»Рл-»О; г) (Рч Ц) — »(Ял Е), Р»=Яви; д) (Рч Ц)-+(Ял Е), »Я~-»Рл-»Д; е) (Р— » О) -+ (Ял Е), »Я»= Рл- О; ж)(Рч Д)-+(Я-+Е), »Р»,-»О»= Я,«-»Я; з) Р— » Ц, Я-» Е, Рч Е»= 0ч Я; и) Р» Д, Я»Ю, РчЯ~ ДлЕ; к) (Р ч Д) -+ (Я л о), ~,Бч Я) -+ Е»= Р— » Е.
1.42. Докажите, что Г»= 6 тогда и только тогда, когда»= Г-+ 6. 1.43. Покажите, что утверждение «Г ~ 6» является более сильным, нежели утверждение «Если»= Г, то»= 6». Другими словами, покажите, что из первого утверждения следует второе. 1.44. Покажите, что из утверждения «Если»= Г, то»= 6» не всегда следует утверждение «Г»= 6». Для этого приведите примеры конкретных формул Ги 6, подтверждающие сказанное.
Указание. Рассмотрите, например, формулы Г(Р, О, Я) —= = — (Р-» Д) л(Рч Я) и ЯР, Д, Я) — = (Р-+Я). Покажите сначала, что импликация «Если ~ Г, то ~ 6» истинна, так как ее посылка «~ Г» ложна. Затем покажите, что утверждение «Г»= б» ложно. 1.45. Покажите, что если из формул Г и »6 в качестве логического следствия можно вывести тождественно ложную формулу (например, Рл -»Р), то Г»= б. Другими словами, если Г, »6»= Р л л-»Р, то Г~ б. 1.46.
Докажите или опровергните, что Г~ 6-+ Нтогда и только тогда, когда Г, -»6»= Н. 1.47. Докажите, что если Г»= б и Г»= Н, то Г»= 6»» Н и Г»= ~бчН. 1.48. Докажите, что если б — тавтология, то Р;, Гм ..., Г»= 6 для любых формул Г„Г~, ..., Г . 1.49. Докажите, что если à — тождественно ложная формула, то ее логическим следствием является любая формула: Г~ б. 1.50. Докажите, что если Г, 6~Ни ~ Г, то 6»=Н.
1.51. Докажите, что если Г»= б и Г~-»б, то ~-»Г. 1.52. Докажите, что если Г, 6»= Н, то Г, 6, Е»= Н, где Е— произвольная формула. 1 53. Пусть Г(Р, О, Я) и(Р», ДлЯ) ч(»Рл Ц»» Я)ч(РЛ-»Дл л ~Я) ч (Р л -» Д л Я) ч (»Р л -1 Д л -»Я) '„ 6(Р, Ц, Я) ж (»Р л -» О л -1 Я)ч (»Р л -1 Ц л Я) ч (-»Рл Д л Я)ч (Р л л -1 Д л Я ), Н(Р, Ц, Я) - =(-» Р л ~ Д л -» Я) ч (-1 Р л Д л Я) ч (Р л -1 О л л Я). 32 Докажите, что для произвольной формулы Е алгебры высказываний Г, 6 ~= Е тогда и только тогда, когда Н ~= Е. Равносильность формул.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
