В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 10
Текст из файла (страница 10)
л) Согласно задаче 2.14 отрицание данной формулы имеет следующую СКН-форму: ~Гав а (~Хч~уч-зУ) х(Хч ч -Лч У) гЛ(Хч Уч -~Я) л ~;ъХч -з Уч Я). Теперь, применяя утверждение задачи 1.66, находим отрицание этой формулы: Г = — (Хл Ух У) ч(-зХл Ул-зУ) ч (-зХл-~УлУ) ч(Хх Ул-~Я). Это и есть СДН-форма данной формулы Г 2.17. СКН-форма некоторой формулы от трех переменных содержит шесть сомножителей (совершенных дизъюнктивных одно- членов).
Что проще — СКН-форма или СДН-форма этой формулы? 2.18. СДН-форма некоторой формулы от трех переменных содержит шесть слагаемых (совершенных конъюнктивных одночленов). Что проще — СДН-форма или СКН-форма этой формулы? Применение нормальных форм. Решить задачи 2.19 — 2.32. 2.19. Найдите наипростейшую формулу от трех переменных среди равносильных формул от трех переменных, последний столбец таблицы истинности которых имеет следующий вид: а)01010101; д)11000011; и)11110000; б)00100100; е)01011010; к)10101110; в)10111101; ж)11001001; л)00001111. г) 11000010; з) 00110011; Решение. л) Для нахождения формулы можно воспользоваться как СДН-формой, так и СКН-формой. Используем, например, СКН-форму. Выделяем те наборы значений переменных, на которых искомая формула обращается в О.
Вот они: Г(0,0,0) =Г(0,0, 1) =Г(0, 1,0) =Г(0,1,!)=О. Выписываем СКН- форму, удовлетворяющую этим условиям, и затем упрощаем ее с помощью равносильных преобразований: Г(Х, У Л) М Х ч У ч У) л Г Х ч Уч -ч Я) х (Х ч ~ Уч Х) л Г Х ч ч Уч ч зУ) — = (Хч Уч (Хл -з2)) л (Хч -з Уч (Ул ~У)) — = (Хч У) л (Хч ч -~ У) = — Хч ( Ул -з У) — = Хч 0 = Х.
2.20. Найдите наипростейшую из равносильных формул от трех переменных, которая: а) всегда принимает то же значение, что и ее второй аргумент; б) принимает такое же значение, как и большинство ее аргументов; в) принимает значение 1 тогда и только тогда, когда точно два ее аргумента принимают значение 0; г) принимает такое же значение, как и меньшинство ее аргументов; д) принимает значение 0 тогда и только тогда, когда по крайней мере один из первого и третьего аргументов принимает значение 0; 47 е) принимает значение 1 тогда и только тогда, когда большинство ее аргументов принимают значение 0; ж) принимает значение 0 тогда и только тогда, когда большинство ее аргументов принимают значение 1; з) принимает значение 1 тогда и только тогда, когда принимают значение 1 первый аргумент и один и только один из двух оставшихся; и) принимает значение 1 тогда и только тогда, когда из первых двух ее аргументов принимает значение 1 ровно один; к) принимает значение 0 тогда и только тогда, когда два ее последних аргумента принимают различные значения; л) принимает значение 1 тогда и только тогда, когда либо первый ее аргумент равен 1, либо все аргументы равны О.
Р е ш е н и е. л) Это означает, что искомая формула удовлетворяет условиям: Г(1, О, 0) = Г(1, О, 1) = Г(1, 1, 0) = Г(1, 1, 1) = Г(0, О, 0)=1. Следовательно, Г(0, О, 1)=Г(0, 1, 0)=Г(0, 1, 1)=0. Выписываем СКН-форму, удовлетворяющую трем последним соотношениям, и затем упрощаем ее с помощью равносильных преобразований: Г(Х, У, 2) — = (Хч Уч-зЯ) л(Хч-зучУ) л(Хч-зуч-з2)ь— з ЦХч ч Уч -зУ) л (Хч ~ Уч ~У)) л ((Х ч -з Уч У) л (Хч з Уч -зУ)) — = (Х ч ~Я) л(Х -зУ) — = Хч(-зУл-~У) — = Хч-з(учЯ). 2.21. Для того чтобы формула логики высказываний была тавтологией, необходимо и достаточно, чтобы в ее КН-форме каждый дизъюнктивный одночлен содержал слагаемым хотя бы одну переменную вместе с ее отрицанием.
Докажите. Р е ш е н и е. ДЪстаточность очевидна. В самом деле, если в каждом дизъюнктивном одночлене КН-формы имеется дизъюнкция типа Хч ~Х, то ввиду тождественной истинности этой дизъюнкции будет тождественно истинен и каждый дизъюнктивный одночлен КН-формы.
Но тогда тождественно истинна и конъюнкция таких дизъюнктивных одночленов, т.е. КН-форма, а значит, и данная формула. Необходимость доказываем методом от противного. Если в некотором дизъюнктивном одночлене КН-формы нет вхождения какой-либо переменной вместе с ее отрицанием, то такой дизъюнктивный одночлен принимает значение 0 на следующем наборе значений входящих в него переменных. Если переменная входит в него без знака отрицания, то ей придаем значение О, если же со знаком отрицания, то — 1. (Например, дизъюнктивный одночлен Х, ч зХ2 ч Хз принимает значение 0 при Х, = О, Х2 = 1, Хз = 0.) Тогда на этом наборе конъюнкция рассматриваемого одночлена с любыми другими дизъюнктивными одночленами, т.е.
вся КН-форма, обращается в О, что противоречит тождественной истинности данной формулы. 2.22. Для того чтобы формула логики высказываний была тождественно ложной, необходимо и достаточно, чтобы в ее ДН- 48 форме каждый конъюнктивный одночлен содержал сомножителем хотя бы одну переменную вместе с ее отрицанием.
Докажите. У к а з а н и е. Доказательство аналогично доказательству двойственного утверждения, сформулированного в предыдущей задаче. 2.23. Применяя критерии из задач 2.21 и 2.22, найдите среди следующих формул тождественно истинные (тавтологии) и тождественно ложные: а) (Х-+ (У-+ У)) -+ «Х-+-зЯ) -> (Х-+ -1У)); б) з(Р -э Д) л ~(0-+ Р); в) (Х-э У) л(Х-+-1У) лХ; г) (Рл Д)-+ (Р+-ь Д); д) (Рл а)- (Р- О); е) (~Р— э О) ч зр; ж) ~(Р-ь (Д-+ Р)); з) Р— э (Ц-+(Рл Ц)); и) (Р— ь Д) ч Щ -+ Р); к) (Х++ У) л «Хл-зУ) ч(-1Хл У)); л) «Хч 2) ч .зЯ) -+ (-1(Хч 2) л Хл У).
Р е ш е н и е. л) Приведем данную формулу к ДН-форме равносильными преобразованиями: «Хч Я)ч-з2) — > (-1(Хч 2) лХл У) — = -з«ХчЯ)ч -~2)ч(-з(Хч2) л лХл У) =(-1(ХчЯ) лУ) ч(-зХл-зЯлХл У) = — (-зХл-зал 2) ч(-1 Хл л-1 Ул Хл У). Каждый конъюнктивный одночлен полученной формы содержит хотя бы одну переменную вместе с ее отрицанием: первый содержит У, второй — Х Следовательно, на основании задачи 2.22 данная формула тождественно ложна.
2.24. Докажите, что тавтологии не имеют СКН-формы. Указ а н и е. Сопоставьте определение СКН-формы с критерием тождественной истинности формулы, приведенным в задаче 2.21. 2.25. Докажите, что тождественно ложные формулы не имеют СДН-формы. Указание. Сопоставьте определение СДН-формы с критерием тождественной ложности формулы, приведенным в задаче 2.22. 2.26. Пользуясь свойством единственности совершенных нормальных форм (см.
задачи 2.7 и 2.11), выясните, равносильны ли следующие формулы, приведя их к СДН-форме или СКН-форме: а) -~(Хл-~У)-+(-~У-+Х) и ~(Х-+ У)чХч У; б) (Хч(Х-+ У) л Уи Ул(-1(У-+ Х) ч Х); в) -1«Р-+ Ц) л(Ц-+-1Р)) и Ц-+ зр; г) (Х++2)-+(Хл-зУ) и «Х -~2)ч(У~~Х)) (Хл-1У); д) (Хч У) л (Хч 2) л ( Уч 2) и (Х л У) ч (Хл Х) ч ( Ул 2); е) (Х У) л (Х- (Ул ХИ и (Х- У) «Х- г) - (Х- ' У)); 49 ж) (Хл 2) -» У и Хл (2-+ У); з) (Х-+ -1 У) -+ ( Ул 2) и (Хл У) ч ( Ул 2); и) (Х-+ У) -+ ( Ул 2) и (2-+ -1 У) » (Хл -» У); к) (Х-» У) -+ 2 и Х-+(У-+ 2); л) (Х++ У) ++ 2 и Х+» ( У++ 2); м) (Рч Д) л Я и Рч (Ол Я). Решение.
л) Найдем СКН-формудля первой формулы: (Х++ У) ++ 2= (-з((-зХч У) л (Хч -1 У)) ч 2) л (((-чХч У) л (Хч ч-1У)) ч~2) = ((Хл-1У)ч (-1Хл У)ч 2) л(~Хч Уч-з2) л(Хч зуч чХ~ = (((Хч У) л(-зХч-зУ)) ч2) л(-1Хч Уч-з2) л(Хч-зуч-з2) =— — = (Хч Уч 2) л(-~Хч-зУч 2) л (»Хч Уч-12) л(Хч-»Уч-и2). Теперь ясно, что дяя получения СКН-формы второй формулы Х+» (У+» 2) нужно в полученной СКН-форме всюду вместо Х написать 2, а вместо 2 — Х Убедитесь, что после такой замены мы получим (с точностью до порядка членов дизъюнкции и конъюнкции) ту же самую СКН-форму. Следовательно, данные формулы равносильны. м) Найдем СДН-форму для первой формулы: (Рч Д) л Я в = (Рл Я)ч (Дл Я) =— (Рл (йч~Д) л Я)ч ((Рч зР) л л Ол Я) га (Рл Ол Я) ч(Рл зЦл Я) ч (зРл Ол Я).
Найдем СДН-форму для второй формулы: Рч (Ол Я) =— Рч (Рл Цл Я) ч (-»Рл Ол Я) = (Рл й) ч (Рл л-»Д) ч (Рл Ол Я)ч (-чРл йл Я) = — (Рл Ол »Я) ч (Рл-»Дл Я) ч ч(Рл зал ~Я) ч(Рл йлЯ) ч(зРл йл Я). Мы видим, что СДН-формы для данных формул не равны. Следовательно, данные формулы не равносильны. 2.27. Найдите все такие не равносильные между собой формулы Г(Х, У) от двух переменных, чтобы следующая формула была тавтологией: а) ((Гл У) -+ -»Х) -+ ((Х-+ ~ У) — » Г); б) ((Гл У) -+ -1Х) -+ ((Х-+ У) — » Г); в) ((-чХл Г) — » -» У) — » ((-1 У-» Х) -+ Г); г) (Х-+ (Гл У)) -+ ((Хл У) ч Г); д) (Г» (Хч У)) — » ((à — » Х) -+ У); е) ((Х-+ У) ч Г) -» (Гл ( Уч -1Х)); ж) ((Г-+ У) л -»Х) -+ ((Хл -1 У) -» Г); з) ((Гч У) л -1Х) -+ ((Х ч У) — » Г); и) (Г-» ~(Хч У)) -+ (~(Хл Г) -» У); к) ((-1Хл У) ч Г) -+ (Гч(Х-+ У)); л) ((-»Хч-зУ) л Г) -+ (Г-+ (Хл У)); м) ((Гч У) -+ Х) -» (Г-+ ( У-+ Х)).
Р е ш е н и е. л) Составим таблицу истинности данной формулы, учитывая, что входящая в нее подформула Г(Х, У) неизвестна и, значит, неизвестны значения, которые она принимает на различных наборах значений своих переменных (при вычислениях пользуемся задачей 1.42, а). 50 Формулу Р(Х У) требуется подобрать такой, чтобы в последнем столбце табпицы стояли только единицы. Тогда Р(Х У) должна удовлетворять условиям: -зР(0, О) = -чР(0, 1) = -зР(1, О) = 1, т.е. Р(0, 0)=Р(0, 1)=Р(1, 0)=0. (ч) Что касается значения Р(1, 1), то оно, как мы видим, ничем не лимитируется: в последней строке составленной таблицы (и в последнем ее столбце) стоит 1 независимо от того, какое значение примет формула Р(Х У) в этой строке (т.е. при Х= 1, У= 1).
Это дает нам возможность получить в качестве решения нашей задачи две неравносильные формулы: первая из них Р,(Х У) удовлетворяет условиям (э) и Р,(1, 1) = 1, а вторая Р;(Х У) — условиям (*) и Р;(1, 1) = О. Следовательно, Р(Х У) =- Хх У, а Р,(Х У) может быть любой тождественно ложной формулой. м) Аналогично предыдущему решению составьте таблицу истинности данной формулы. Вы увидите, что столбец ее значений уже состоит только из единиц независимо от значений искомой формулы Р(Х У).
Это означает, что формула Р(Х У) может быть любой. 2.28. Найдите все такие неравносильные между собой формулы Р(Х У Я) от трех переменных, чтобы следующая формула была тавтологией: а) ((У-+ (~Ул Х)) -+ Р) -+ ((Х-+ У) л Рл Я); б) ((Рл У) -+ -зХ) -+ ((Х-+ У) -+ Р); в) ЬХ Х) У).Р)- тг Х) У)~Р); г) (((-зУлХ)-+Я)-+ Р)-+(Рл(Х-+ У) л2); д) (~Хч У)-+((Ул-зУ) и Р); е) (Рх (Х-+ У)) ч((У-+ Я) х Р); ж) (((Х~ У) -+ Я) -+ Р) -+ (Рх ((зХ-+ У) х-зУ)); з) ((Х-+ У)-+Р) ~((Х~~ У) х РлЯ); и) (Р-+ ((-зУл У) -+Х)) -+ (Хл (У-+ У) л Р); к) ((Р-+(Ул У)) х Л) ч(У-+((Ха~У) ~ Р)); л) ((Х-+ У) ~ Хч Р) -+ ((( У вЂ” ~ Х) -+ Я) -+ Р).
Р е ш е н и е. л) За деталями решения рекомендуется обратиться к решению задачи 2.27. Здесь же отметим основные этапы. Составим таблицу истинности данной формулы, в ней использованы следующие обозначения для подформул: 51 (1) — ( К-+ Х) -+ У; (2) — ((У-э Х) -+ 2) -+ Г; (3) — данная формула ((Х-+ У)ч Хч Г) -+ (((У-+ Х) -+ У) -+ Г)): Для того чтобы данная формула была тавтологией, нужно чтобы искомая формула Г(Х, Г, Я) на пяти наборах значений аргументов 001, 010, 011, 101, 111 принимала значение 1; на остальных трех наборах 000, 100 и 110 она может принимать произвольные значения (при этом значение данной формулы не будет зависеть от них: на этих трех наборах данная формула непременно принимает значение 1).
Столбец значений такой формулы Г приведен в приведенной ниже таблице (места, отмеченные в ней звездочками, могут быль заполнены произвольными значениями). Таким образом, мы приходим к тому, что подходящими для данной задачи будут восемь формул с следующими значениями: 52 Используя СКН-формы, находим все эти формулы: У;(Х У, 2) МХч УчУ) л1;ъХч Уч У)л1;~Хч-~Уч Я) ьз Уч Л) л л (~Хч -~Уч У) — = (Ул (-|Хч У)) У= (-1Х У) ч У; Р2(Х У, 2) = (Х Уч Я) л (-1Хч Уч Я) =— Уч У; Р»(Х 1; У) ~(Хч Уч Я) л (;1Хч ~Уч 2); Р4(Х У, Я) = Хч Уч Х' Р5(Х 1; Х) = (~Хч Уч Я) л (-1Х ч -1 Уч 2) — = -~Х ч у.
Рб(Х У, Я) — = (-1Хч Уч 2) сч Х + (Уч Х). Р7(Х1 У 2) — = (-»Х ч -1 Уч Я); Рз(Х У, Я) — любая тавтология. 2.29. Найдите все такие не равносильные между собой формулы Р(Х У) от двух переменных, чтобы: а) (Хч У) л Рм Уи Хл Р=- Хл У; б) Хл Р— = Хл Уи Р-+ Х— = Хч У; в) Р-» Х= Хч 1'и Хч Р= У-+ Х; г) (Хл Р) ч У= — Уи Хч Р— = Хч У; д) Хч (~Рл У) — = Ул Хи Хч Р— = У-+ Х; е) (Хл -1У) ч Р— = -зУи Кч Р— = -~Хл-»У; ж)(Хл У) — »Р— = 1иХчР=Хч У; з) Р-+ (Хл У) = Хи Хч Р= — 1; и) (Х л -1 У) ч Р = — -1 У и -1Х л Р— = -1Х л -~ У; к) Рч (Хл У) — = Хи Уч Р= Хч У; л) (Х-+ У) ч Р— = Х-» 1'и Р-+ Х= — Хч К Решение. л) Чтобы найти требуемую формулу Р(Х, У), нужно сначала определить, какие истинностные значения принимает она на всевозможных двухэлементных наборах, составленных из нулей и единиц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
