В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 11
Текст из файла (страница 11)
Для этого будем придавать переменным Х и У всевозможные значения и, исходя из данных условий, определять соответствующее значение формулы Р(Х У). Полагая во втором данном соотношении Х = О, получаем Р(0, У) -+ 0 — = 0 ч У, или -1Р(0, У) — = К При У= 0 находим Р(0,' 0) = 1, а при У= 1 находим Р(0, 1) = О. Положив в первом соотношении Х=1, получаем (1-+ У) ч Р(1, У) - =1 -+ У т.е. У ч Р(1, У) - =К Отсюда при У= 0 получаем 0 ч Р(1, 0) = О, т.е. Р(1, 0) = О. При У= 1 равносильность У ч Р(1, У) =- У превращается в верное равенство вне зависимости от того, каково значение Р(1, 1).
В результате для искомой формулы Р(Х У) получаем следующую таблицу значений: 53 В ней на месте (е) может стоять любое значение: 0 или 1. В ре- зультате получаем две формулы Г,(Х У) и У~(Х У), которые на- ходим с помощью СДН-формы: Г,(Х, У) - =-чХ л -э У; Г,(Х У) =- = (~Х л -ч У) ч (Х л У) — = Х++ У. Проверим, что каждая из этих формул действительно удовлет- воряет обоим условиям задачи: (Х-+ У) ч Г, — = (Х-+ У) ч (зХ л -э У) — = -ьХч Уч (эХл -ч У) — = эХч ч УьзХ-» У; Г~ -+ Х— = (-чХл -~ У) -+ Х=— -~(-~Хл -~ )) ч Х = (Хч У) ч Х— = Хч У; (Х-+ У) ч Р~ — = (Х-+ У) ч (-чХл -~У) ч (Хл У) = — -ьХч Уч (-чХл л У) ч (Х л У) = — -~Х ч У = Х-+ У; Рг -+ Х— = ((-~Хл -~У) ч (Хл У)) -+ Х— = -ч((-зХл -чу) ч (Хл У)) ч ч Хьт (-~(-чХл эу) л э(Хл У)) ч Х= — ((Хч У) а (-чХч -~У)) ч Хьт — = (Хч УчХ) а (-~Хч-ъУч Х) — = Хч У.
2.30. Найдите все такие не равносильные между собой форму- лы Г(Х, У, Я) от трех переменных, чтобы: а) У-+ Г=- У-+ (Хл У) и à — » Ум -ч(Хч У) -+ У; б) Х-+ Г = У-+ (~Хч У) и ~Х -+ ~à — = (Е-» У) -+ Х; в) Гл У=— Ул (~Хч-~У) и Гч Хч У= Хч Уч-~У; г) Гл Х— = Хл Уи -~Г-» Хь— т Хч Уч У; д) Уч Г= (Хч Я) л Уи Х вЂ” » Г— = Х-» (Уч Я); е) Хл Г— = Хл (Уч У) и -зХл Г=— -чХл -ч(Ул 2); ж) Гч У— = (Хл У) ч Уи Гл -~У= — Хл Ул-~У; з) У вЂ” » Г = У-» (Х-+ У) и Г-+ У вЂ” = (Х л У) -+ У; и) Ул Г— = Хл Ул Уи Гч У— = Хч Уч У; к) Х-+ Га†з Х-» Уи Хч Г— = Х-» Х; л) Ха Г— = Хл Уи Хч Г= — Хч У; м) Хч Г— = У-+ Хи Ул Гав з Ул У; н)г- Г-=г- (Х- У) Г- К=(Х~ У)ч г. Решение.
л) Чтобы найти требуемую формулу Г(Х У, Я), нужно сначала определить, какие истинностные значения при- нимает она на всевозможных трехэлементных наборах, составлен- ных из нулей и единиц. Для этого будем придавать переменным Х У и У все возможные значения и, исходя из данных условий, определять соответствующее значение формулы Г(Х У, Я). Так как Х л Г(Х 1; 2) - =Х л У, то, полагая здесь Х = У = 1, получаем 1 л Г(1, 1, Л) =— 1 л 1, т.е. Г(1, 1, У) = 1.
Следовательно, Г(1, 1, 0) = Г(1, 1, 1) = 1. (1) Положим теперь в первом данном соотношении Х = 1, У= О. Тогда получаем 1 л Г(1, О, У) = 1 л О, т.е. Г(1, О, У) - =О. Следо- вательно, Г(1, О, 0) = Г(1, О, 1) = О. (2) Далее, поскольку Х ч Г(Х У, 2) — = Х ч У, то, полагая здесь Х= О, У= О, получаем 0 ч Г(0, У, 0) = 0 ч О, откуда Г(0, У, 0) — = О.
Следовательно, 54 (3) Г(0, О, 0) = Г(0, 1, 0) = О. Полагая наконец во втором данном соотношении Х= О, У= 1, получаем 0 ~ Г(0, У, 1) — = 0 ~ 1, т.е. Г(0, У 1) =— 1, откуда заключаем, что (4) Г(0, О, 1) = Г(0, 1, 1) = 1. Полученные соотношения (1) — (4) не противоречат друг другу и дают полную информацию о формуле Г. Используя эти соотношения, запишем СДН-форму для искомой формулы Г(Х У У) и упростим ее с помощью приведенных ниже равносильных преобразований: Г(Х У У) — = (Хл Ул ~Л) ч (Хл Ул Л) ъ ( чХл ~ Ул 2) и (-чХл л Ул У) = — (Хх Ул~;ъХч У)) ч (-~Хл (-зум У) л У) ьт (Хл Ух 1) ч ч (~Хл 1 л У) = — (Хл У) ч (-~Хл Я).
Проверьте, действительно лн найденная формула удовлетворяет обоим требованиям из условия задачи. Поскольку искомая формула непременно должна удовлетворять всем соотношениям (1) — (4), то такая формула единственна с точностью до равносильности. м) Из первого условия при Х= 0 получаем Г(О,У г) =-У.
Из второго условия при У= 1 получаем Г(Х, 1, У) - =Л (2) Покажем, что условия (1) и (2) противоречивы. Так, из (1) при У= 1 получаем (3) Г(0,1,г) -=О, а из (2) при Х= 0 имеем Г(0, 1, У) — = У. (4) Из (3), в частности, следует, что Г(0, 1, 1) = О, а из (4) получается, что Г(0, 1, 1) — = 1, а это невозможно.
Значит, формулы Г(Х У У), удовлетворяющей обоим требованиям задачи, не существует. н) Из первого соотношения при У=! получаем Г(Х У 1) =- — = Х-+ У. Из второго условия при У = 1 получаем ~Г(Х, У, 1) - =Ха л -з У т.е. Г(Х, У 1) = Х вЂ” ~ У. Следовательно, Г(0, О, 1) = Г(0, 1, 1) = Г(1, 1, 1) =1, Г(1, О, 1) =О. Никаких других ограничений на формулу Г(Х У, 2,') не возникает. Следовательно, на остальных четырех наборах 000, 010, 100, 110 формула может принимать произвольные значения.
В результате мы имеем возможность получить 16 не равносильных между 55 собой формул от трех переменных, таблица значений которых имеет следующий вид: Используя СдН-форму, найдем первую формулу: Г (Х, 1; 2) — = (-зХл -з Ул 2) ч (-1Хл Ул 2) ч (Хл У'л 2) = — (-1Хл 2) ч ч (Хл Ул 2) — = (-1Хч (Хл У)) л 2 в = (-1Хч У) л 2= — (Х вЂ” > У) л 2. Проверим, что эта формула удовлетворяет обоим данным соотношениям: 2-+ Г1 — = .з2ч ((-1Хч У) л 2) = — -12ч (-1Хч У) = — 2-э (Х-+ У); Г~ -э -12 — = -1((-1Х ч У) л 2) ч ~2 сч (Х -1 У) ч ~2 ч ~2 = (Х л л ~У) ч.з2. Найдем вторую формулу, используя СКН-форму: Г2 ге(Хч Уч 2) л (Хч -Пч 2) л (-1Хч Уч 2) л (-|Хч Уч -12) ЯХч ч 2) л(~Хч У). Сделаем проверку: 2-+ Г2 =— -~2ч ((Хч 2) л (-1Хч У)) = -12ч (-1Хч У) =- 2-+ (Х-+ У); Гз -+ -12 в = ~((Хч 2) л (-1Хч У)) ч -12 в = (чХ л -12) ч (Хл -1 У) ч ч -~2 = (Х л -1 У) ч -з2 Предлагается самостоятельно найти остальные 14 формул и проверкой убедиться, что все они удовлетворяют обеим требуемым равносильностям.
2.31. Найдите все такие не равносильные между собой формулы Г(Х, У 2) от трех переменных, чтобы: а) Х++ -1à — = (Х л У) -э 2; б) -чХ++ Г = — У-+ Х; в) (Г++ 2) ++ (Х ч У) = — (Х л -зУ) ч 2; г) -~ У++ Газ ((Хл 2) ч У) -+ (Хл Ул 2); д) -1Г++ 2 = У-+ (Х++ 2); е) Г<-> -1Х= — Хч -12; ж) -зГ++ 2 — = (Х л У) -+ 2; з) Г++-з2= Хч Уч 2; и) Г<-э Уев а 2-+ Х; 56 к) Г ~+ ((1'л 2) -+ Х) =- (Х ч У) л -зУ; л) (Х-+ 2) ++ à — = (Х л -1 У) -+ Е Р е ш е н и е.
л) При У= 1 данная равносильность превращается в следующую: Г(Х 1; 1) =— 1, откуда вьггекает, что Г(0, О, 1) = Г(0, 1, 1) = Г(1, О, 1) = Г(1, 1, 1) =1. При У = 0 данная равносильность принимает следующий вид: Х++ Г(Х У 0) = Х-+ К Из последней равносильности при У= 1 получаем -1Х++ Г(Х 1, 0) =— 1. Отсюда при Х= 0 имеем Г(0, 1, 0) = 1, а при Х = 1— -1Г(1, 1, 0) = 1, т.е. Г(1, 1, 0) = О. Из той же равносильности при У = 0 получаем -1Х++ Г(Х, О, 0) = -1Х Отсюда при Х = 0 имеем Г(0, О, 0) = 1, а при Х = 1 — -1Г(1, О, 0) =-11, т.е.
Г(1, О, 0) = 1. Итак, формула Г(Х У, Л) должна быль такой, что только на единственном наборе (1, 1, 0) значений переменных она принимает значение О, а на остальных семи наборах ее значение равно 1. Используя СКН-форму, находим саму формулу: Г(Х, У, 2) =- =--1Хч-1Уч У-=-ч(Х У) ч У— = (Хл У)-+У. Проверим, что найденная формула действительно удовлетворяет условию задачи: (Х-+ 2) ++ ((Хл У) -~ 2) - =(Х-+ Я) ++ (-1Хч -1 Уч У) = ((-1Хч ч Я) -+ (~Хч -М ч Я)) л ((-1Хч ~ Уч 2) -+ (-1Хч 2)) = (~(-чХч 2) ч ч -1Хч зуч 2) л (-1(-1Хч -1 Уч Я) ч -1Хч 2) = ((Хл ~Я)ч ~Хч -~ Уч ч У) л ((Хл Ул -юЯ)ч -1Хч 2) ЯХч -~Х ч -М ч 2) л (~Хч -~Хч -Лч ~У)) л ((Хч ~Хч У) л(Уч ~Х 2) л (~У -ъХч 2)) = Уч-1Хч Х вЂ” = ~(Х л -1 У) ч У вЂ” = (Х л -1 У) -+ У.
2.32. Существуют ли такие не равносильные между собой формулы Ги 6 (не являющиеся ни тождественно истинными (тавтологиями), ни тождественно ложными), что: а)Г-+6~Гл6; д)~Г-+6~=Г; и)Г++6~=Г; б) Гч 6 ~= Г; е) à — ~ 6 ~ Г; к) 6 ~= Г -+ 6; в) Г-+ 6 ~ Г++ 6; ж) Г~= Г-+ 6; л) Г~= Гл 6. г) Г-+ 6 ~= 6; з) Г ~= Г++ 6; Решение. л) Прежде всего отметим, что такое следование выполняется не всегда.
Например, при Г(Х У) - =Хи 6 (Х У) =— — = Хл Уоно не выполняется. Поэтому поставленный вопрос корректен. С другой стороны, обратное логическое следование справедливо: Г л 6 ~= Г Это означает, что ответ на поставленный вопрос будет положительным для таких формул Г и 6, для которых Гл 6г— а Г. В частности, так будет для формул Г(Х, У) =— Хи 6(Х, У) - =Хч У, для которых данное логическое следование превращается в равносильность Х= Хл (Хч У). Нахождение следствий из посылок. Решить задачи 2. 33 — 2.
37. 2.33. Пусть имеется конечное число формул (посылок) Г„ Гм ..., Г и требуется найти все формулы, являющиеся логическими следствиями данных посылок. Предлагается следующий алгоритм. Привести конъюнкцию Р; л Г, л ... л Г„посылок к СКН- 57 форме. Затем перечислить все совершенные дизъюнктивные одно- члены, входящие в нее, а также всевозможные конъюнкции этих одночленов по два, по три и т.д.
Полученные формулы будут исчерпывать совокупность всех логических следствий из данных посылок. Докажите. Р е ш е н и е. Ясно, что каждая такая формула будет логическим следствием данных посылок в силу тавтологии (Рк Ц) -+ Р(коньюнкиин сильнее каждого из саиножителей). Поэтому достаточно убедиться в том, что каждый совершенный дизъюнктивный одночлен из СКН- формы каждой формулы с«, являющейся логическим следствием формул Ро Ръ ..., Р, будет также входить совершенным дизъюнктивным одночленом в СКН-форму формулы Р~ к Р, н ... к Р„.
Докажем это утверждение методом от противного. В самом деле, пусть Ю = Х,"' ч Х,"' ч ... ч Х„" — некоторый совершенный дизьюнктивный одночлен, не входящий в СКН-форму для формулы Р, н Р2 к ... л Г„. Тогда при подстановке Х, = а„Х1 = а„..., Х„= а„ этот одночлен примет значение О. Поскольку далее каждый совершенный дизъюнктивный одночлен в СКН-форме для формулы Р, к н Г, к ... н Г„отличен от Р, то при той же подстановке каждый из них примет значение 1, а следовательно, значение 1 примет вся формула Р| к Р1 и ...
к Р, т.е. каждая посылка Рь Ръ ..., Г„. Но поскольку б является логическим следствием этих посылок, то при этой подстановке она должна также принимать значение 1, а следовательно, совершенный дизъюнктивный одночлен Р не может входить в ее СКН-форму. 2.34. Найдите все не равносильные между собой и не тождественно истинные формулы алгебры высказываний, являющиеся логическими следствиями следующих формул (посылок): а) Х-+ Уи Х; б) Х-+ 1'и -1У; в) Х++ Уи -1Х; г) Х УХи-У; д) Х-+ Уи У- У; е) Х++ Уи У++ У; ж) (Х н У) -+ У и Х ч У; з) (Хн У)-«Уи У вЂ” «Х; и) Х-+ У, Уч Уи (Хн У) ++ У; к) (Х к У) -+ -1У, У и У; л) Х-+ (Уч У) и У-+ У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
