В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 5
Текст из файла (страница 5)
если ~= Ги ~= Г-+ 6, то ~ 6. (Правило вывода называется «модус поненс»вЂ” МР.) 1.32. Докажите, что: а) если ~= Г л 6, ~ Г++ б, то ~ 6-+ Н; б) если ~= Г «б, ~= б-+ Н, то ~ Г ~ Н; в) если ~ -зà — » 6, ~ ~бч ~Н, то ~ Н вЂ” » Г; г) если ~= -зб л-~Н, ~= Г ~ б, то ~= -~Г-+ Н; д) если ~ Гч б, ~ Г«-э б, то ~ 6; е) если ~ Г, ~=Г++ б, ~= Г++ Н, то ~= бл Н; ж) если ~ -~Г-+ б, ~-~б л-ьН, то ~ Гч Н; з) если ~= Г++ 6, ~= 6++ Н, то ~ Г++Н; и) если ~= Г, ~= б, ~ Н, то ~= Г-+ (6-+ Н); к) если ~= Г л б, ~= б-+ ~Н, то ~ Г л ~Н; л) если ~= -~Г ч 6, ~= -зб «-~Н, то ~= Г-»-зН; м) если ~= 6-+ Г, ~= (~Г л Н)++ 6, ~= Н, то ~=-зб л Н.
Решение. л) Пусть Г(Х„..., Х„), 6(Х„..., Х„), Н(Х,, ..., Х„) — формулы, о которых идет речь в задаче. Предположим, что формула Г-э -зН не является тавтологией. Это означает, что существуют такие конкретные высказывания А,, ..., А„, что высказывание Г(А,, ..., А„) истинно, а высказывание -~Н(Ан..., А„) ложно. Тогда высказывание -зГ(Аь ..., А„) ложно. Далее, так как формула -~Г~ 6 является тавтологией, то высказывание 6(А„..., А„) истинно. Но с другой стороны, поскольку ~6 ~-зН вЂ” тавтология, то высказывание -~6(А„..., А„) истинно. Получили противоречие. Следовательно, формула Г-+ -+ -~ Н вЂ” тавтология. м) Предположим, что посылка данного утверждения верна, а заключение нет, т.е.
формулы б-» Г, (~Гл Н) «-+ б и Нявляются тавтологиями, а формула -зб л Н вЂ” нет. Последнее означает: найдугся такие конкретные высказывания А„..., А„, что высказывание ~б(Аь ..., А„) л Н(А„..., А„) будет ложным. Это, в свою очередь, возможно лишь в том случае, когда по меньшей мере одно из высказываний ~ 6(Аь ..., А„) или Н(Аь ..., А„) будет ложным. Высказывание Н(А„..., А„) ложным быть не может, поскольку это противоречило бы тождественной истинности формулы Н(Х„..., Х„). Следовательно, ложно высказывание -~6(Аь ..., А„) и, значит, истинно высказывание 6(Аь ..., А„). А раз так, то из 22 истинности высказывания 6(А„..., А„) -+ У(Аь ..., А„) вытекает истинность высказывания Г(Ап ..., А„). Обратимся теперь к высказыванию (-зГ(Аь ..., А,) л Н(Аь ..., А„))»» 6(А„..., А„), которое истинно, поскольку формула (-зГл Н) +» 6, по предположению, является тавтологией.
Ввиду истинности высказывания Г(Ао ..., А„) левая часть рассматриваемой эквивалентности есть ложное высказывание. Значит, ее правая часть, т.е. высказывание 6(А„..., А„), также ложна. Но это противоречит истинности этого высказывания, установленной в предыдущем абзаце. Таким образом, сделанное допущение приводит в противоречию. Следовательно, допущение неверно, а верно доказываемое утверждение. 1.33.
Выясните, справедливы ли следующие утверждения (если утверждение несправедливо, то постарайтесь определить, обе его части «тогда» и «только тогда» не выполняются или только одна): а) ~= Г«-» 6 тогда и только тогда, когда ~(Г-+ С) л(6-+ Г); б) ~= Г ~ С тогда и только тогда, когда ~= Г или ~= 6; в) ~ Г++ 6 тогда и только тогда, когда ~ à — » 6 и ~= 0-» Г; г) ~ Г ~ 6 тогда и только тогда, когда ~ Ги ~6; д) ~ Г-+ 6 тогда и только тогда, когда ~= Г; е) ~= Г-+ 0 тогда и только тогда, когда ~= 6; ж) ~= Г-+ 6 тогда и только тогда, когда ~=-~Г или ~= 6; з) ~= Г л 6 тогда и только тогда, когда ~= Г и ~ 6; и) ~= Г+» 6 тогда и только тогда, когда ~ Г и ~= 6; к) ~ Г ~ 6 тогда и только тогда, когда ~= Г или ~= 6; л) ~= Г-» 0 тогда и только тогда, когда ~= Г и ~= 0; м) ~= з(Г ~ 6) тогда и только тогда, когда ~=-зГ и ~=-з6.
Р е ш е н и е. л) Данное утверждение в полном объеме несправедливо: неверна его часть «тогда» (необходимость). Для подтверждения этого нужно указать такие конкретные формулы Г и 6, чтобы по меньшей мере одна из них не была тавтологией, а формула Г» 6 тавтологией была бы. Вот пример таких формул: Г =- Р, 6=- Д-» Р. Ни одна из них не является тавтологией, но формула Р— » (Д вЂ” » Р) — тавтология. Еще пример: Г= Р— » (Д-» Я), С вЂ” = (Р л л Д) -+ Я.
Проверьте, что этот пример действительно опровергает необходимость данного утверждения. Приведите самостоятельно аналогичный пример. Рассмотрим теперь часть «только тогда» (достаточность) данного утверждения. Оказывается, она верна. В самом деле, предположим, что ~= Ги ~= 6. Это означает, что для любых высказываний А,„..., А„высказывания Г(А„..., А„) и 6(А„..., А„) будут истинными. Следовательно, для любых высказываний А„..., А„истинным будет и высказывание Г(А„..., А„) -+ 6(А,, ..., А„).
А это означает, что формула Г-+ 6 является тавтологией, т.е. ~= Г-+ 6. 23 м) Покажем, что данное утверждение справедливо. Необходимость. Пусть ~= ~(Г ч 6). Следовательно, формула Г ч 6 тождественно ложна. Но тогда, ввиду определения дизъюнкции, тождественно ложны обе формулы Г и 6. А раз так, то отрицание каждой из этих формул з Ги ~ 6 будет всегда принимать лишь истинные значения, т.е.
~= ~Ги ~= -1 6. Докажите достаточность самостоятельно: убедитесь, что каждый логический шаг, сделанный при доказательстве необходимости, может быть проделан в обратном направлении. Логическое следование. Формула 6(Хь Х,, ..., Х„) называется логическим следствием формул Г,(Х„Хн ..., Х„), ..., Г„(Х„Хъ ..., Х„), если она обращается в истинное высказывание на всяком наборе значений переменных, для которого в истинные высказывания обращаются все формулы Гн ..., Г .
Это обозначается: Г„ ...,Г ~=6. 1.34. Формулы Г;(Р, Д, Я) и 6,(Р, Ц, Я) ((=1, 2, 3; 1=1, 2, 3, ..., 11) от трех переменных заданы следующей таблицей истинностных значений: Выясните, какие из формул 6;(/= 1, 2, 3, ..., 11) являются логическими следствиями трех формул Г1, Р~, Гз. Р е ш е н и е. 11) Формула 6н не является логическим следствием формул Г„Г;„Гь так как при Р= 1, Я= О, Я = 1 все формулы Гь Г„Гз принимают значение 1 (превращаются в истинные высказывания), а формула 6п при этих значениях своих переменных принимает значение О, т,е. превращается в ложное высказывание (см. строку б таблицы). 1.35.
Докажите, что справедливы следующие логические следования, руководствуясь определением этого понятия; выясните, 24 будут ли верны обратные следования, т.е. будет ли формула, стоящая слева, логическим следствием формулы справа: а) Р++ Д»= Р » 0; б) Р++-»0»= Рч Д; в) Рл Д»= Рч Д; г) ((Рл 0) -+ (Рч О)) -+ Р ~ Рч 0; д) (Рч (',»)-«(Рл 0)»= Р— + Д; е) Рл»Д«=(-»Рч Д)-+~0; ж)(Р— » Ц) -+ ~ О»= (-» Д -+ Р) -+ Р; з) (-1Д-+ Р)-+ Р»=-»(Д-«Р) -+ (Р~-» Д); и) (Р-+ Д) л (~Р— » Д)»= Д; к) -ь»(Рл 0) лР»=-»О; л) »(Рч Д)»=-»Рч -» Д; м) -»Рл-»О»= ~~,Рл Д).
Р е ш е н и е. м) Составим сначала таблицу истинности для формулы »Рл ~0, стоящей слева от знака»= логического следования, и для формулы »(Рл Д), стоящей справа от этого знака: Итак, логические значения данных формул »Р л -» Ц и -»(Р л Ц) представлены в столбцах построенной таблицы, отмеченных знаками (а) и (*х) соответственно. Сравним теперь эти столбцы, руководствуясь определением логического следования (алгоритм см. в Учебнике, с. 55).
Столбцы нужно сравнивать построчно, так как в каждой строке представлены значения двух формул, отвечающие одному и тому же набору значений пропозициональных переменных Р и О, входящих в эти формулы. В первой строке столбца (е) стоит 1. Следовательно (на основании определения логического следования), мы должны посмотреть, стоит ли также 1 в первой строке столбца (* «), т.е.
принимает ли значение 1 формула -»(Р л Д) на том наборе значений пропозициональных переменных,на котором приняла значение 1 формула -1Рл-1Д (в данной строке этот набор таков: Р = О, Ц = О). Посмотрев на первую строку столбца (**), мы убеждаемся, что в данном случае это действительно так. Переходим ко второй строке. В ней в столбце («) стоит О. Определение логического следования в этом случае никаких требований к логическому значению второй формулы -»(Р л Д) не предъявляет: ее значение в этой строке (т.е.
при Р= О и Д= 1) может быть 25 любым. Поэтому мы можем даже не смотреть, какое значение имеется во второй строке столбца (**). Переходим к третьей строке. В столбце (») обнаруживаем также значение О. Поэтому переходим к четвертой, заключительной, строке таблицы. В столбце («) в этой строке — снова О. Таким образом, все строки таблицы просмотрены. Это означает, что мы сопоставили логические значения формул ~Рл ~Д и -з(Р л Д) при всевозможмых наборах значений их пропозициональных переменных и обнаружили при этом, что на всяком наборе значений переменных, на котором первая формула зРл ~ Д принимает значение 1 (в нашем случае это лишь первая строка: в ней Р=О, 0=0), и вторая формула ~(Рл Д) непременно принимает значение 1. По определению логического следствия это и означает, что формула з(Р», Д) является логическим следствием формулы ~ Р л -з Д, т.
е. -ьР л -~ Д ~ -~~ Р л Д). Дадим теперь ответ на второй вопрос, является ли формула -чРл -з Д логическим следствием формулы -ч(Рл Д). Посмотрим, например, во вторую строку построенной таблицы: в ней в столбце (»») стоит 1, а в столбце (») — О. Это означает, что формула -~(Рл Д) при значениях переменных Р = О, Д = 1 принимает значение 1, в то время как формула ~Р», -~ Д на том же наборе значений переменных принимает значение О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
