В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 8
Текст из файла (страница 8)
Таким образом, исходная задача свелась к определению числа формул, у которых столбец значений истинности имеет указанный вид: в строках 1, 2, 3, 4 и 8 стоят единицы, а в остальных— произвольные значения. А это число, очевидно, равно числу способов, какими можно расставить О и 1 на трех вакантных местах (отмеченных знаком е), т.е. числу наборов длины три, составленных из О и 1. Последнее, как нам известно, равно 2'. Ясно, что все эти формулы будут не равносильны между собой, так как имеют различные столбцы значений. 1.69. Сколько существует не равносильных между собой формул Р(Р, 0, Я) от трех переменных, из каждой из которых логически следует соответствующая формула предыдущей задачи? Р е ш е н и е. л) Воспроизведем найденную в предыдущей задаче таблицу истинности данной формулы -зР~ (Д л Я): Вспоминая определение логического следствия, постараемся понять теперь„как может выглядеть столбец значений формулы Г(Р, О, Я), для которой данная формула ~Рч (0л Я) является логическим следствием.
В тех строках, где данная формула принимает значение О (у нас это строки 5, 6 и 7), формула Г, логическим следствием которой будет данная формула, может также принимать лишь значение О (см. столбец значений формулы Г в 38 последней таблице). В тех же строках, где данная формула принимает значение 1 (у нас это строки 1, 2, 3, 4 и 8), формула Г, из которой логически следует данная, может принимать любое значение (в последней таблице в столбце кэти места отмечены знаком *). Таким образом, искомое число формул равно числу двоичных наборов длины пять (столько вакантных мест отмечено знаком э в столбце значений формулы Г), составленных из 0 и 1.
Это число, как нам известно, равно 2'. Каждому получаемому двоичному набору будет отвечать некоторая формула (ее можно найти с помощью СДН- или СКН-формы; см. 5 2), причем формулы, отвечающие разным столбцам, будут не равносильны между собой. Упрощение систем высказываний. Решить задачи 1.70 — 1.71. 1.70. Упростите данную систему истинных высказываний, т.е. найдите логически эквивалентную ей систему, состоящую из меньшего числа не более сложных высказываний: а) С-~(Ач В), (Вл С)-+А, (АлВ)-+ С; б) А -+1 В ч С), В -+ (А ч С), (А л В) -+ С; в) А-+ В, А-+ (Вч С), В-+ С; г) Р-ь (ЦчА), И~+1 Бч Т), А-+(Дч-чР), (И~л Т)-+-зЮ; д) И~-+(Мч Я), А-+ Т, -чо-+ Т, М-ЙЬч 1Р), Р— +(Тч А); е) -зА -+ ~(В ч С), В -+ -з(А л С), С -+ (А ч -зВ), А -+ (В ч С), (А л л С) -+ В, (-зА л -зВ) -+ С; ж)Р-+Д, Рчо, Ц-+Р; з) Р— + О, Д-э.тР, А-+ Р; и) А ч С,  — > С, (В л С) -+ А; к) А л В, В-+ С, С-+ (А ч В); л) А -+ В, С вЂ” ~ В, (В л С) -+ А.
Р е ш е н и е. л) Упрощение совокупности высказываний основано на том, что каждое из высказываний данной совокупности будет истинным тогда и только тогда, когда истинна конъюнкция всех этих высказываний. Поэтому, составив конъюнкцию из данных высказываний и приведя ее равносильными преобразованиями к конъюнкции более простого вида, можно получить более простую систему высказываний, эквивалентную данной. В нашем случае имеем следующую конъюнкцию, которую последовательно упрощаем: (А -+ В) л (С-+ В) л ((В л С) -+ А) = ( зА ч В) л (~ С ч В) л (з(В л л С) ч А) = (-зА ч В) л ~~ С ч В) л (-зВ ч -з С ч А) = — (-зА ч В) л ((А л л -зА)ч В ч -~ С) л (А ч-ьВ ч-ъ С) = (тА ч В) л (А ч В ч-~ С) л (тА ч В ч ч з С) л (А ч -зВ ч -з С) — = (зА ч В) л (А ч (В л ~В)ч з С) = (-зА ч В) л л (А ч -з С) — = (А -+ В) л (С-+ А).
Следовательно, все высказывания данной системы будут истинны тогда и только тогда, когда будут истинны высказывания А -+ В и С-+ А. Поэтому данная система трех высказываний оказаласьлогически эквивалентной более простой системе двух высказываний А-+ В, С-+А, 39 1.71. Для каждой из следующих систем высказываний найдите логически эквивалентную ей, но более простую систему высказываний, если известно, что в данной системе по меньшей мере одно высказывание истинно: а) -1(А-+ В), -1ВлА, -~Юл С, -~(С-+А); б) А л В л С, чА л ~ В л -з С, А л В л з С, ч(А ч В ч з С); в) Р— ь О, ~(Ц вЂ” > Р), Рл Ц; г) А л -~В л С, А л -К — ь -1 С), А л -4 В ч С); д) Ал-1Вл С, -1(А-+ С) л-1В, -1Ал ~(С-+В); е) -1А ч В, А++ В; ж)А-+В, ВчС, АлС; з) А-+(,Вч С), Вч(А — ь С), Сч(А-+ В), Вч С; и) А л В л -1 С, -1(А -+ С) л -|А, А л (В ч С); к) -1Ал С, А-+ В, Вч(А-+ С); л ) А л В л -1 С, -1 (А -ь В) л -1 С, -1А л -1 (В -+ С).
Решение. л) По меньшей мере одно из высказываний данной совокупности будет истинным тогда и только тогда, когда истинна дизъюнкция всех этих высказываний. Поэтому, составив дизъюнкцию из данных высказываний и приведя ее с помощью равносильных преобразований к дизъюнкции более простого вида, можно получить более простую систему высказываний, эквивалентную данной.
В нашем случае имеем следующую дизъюнкцию, которую затем упрощаем: (А л В л -1 С) ч (-1(А -+ В) л -~ С) ч (-1А л -1( — ь С) ) = — (А л В л л ~ С) ч (-з(~А ч В) л -1 С)ч (~А л -1(-|В ч С)) ьт (А л В л -1 С) ч (А л л ~В л -1 С)ч (-1А л В л -1 С) — = ((А л В л -1 С)ч (А л ~ В л ~ С))ч ((А л л В л з С)ч (~А л В л ~ С)) — = (А л (В ч з В) л ч С)ч ((А ч тА) л В л л -1С) = — (Ал -1С) ч (Вл-1С).
Следовательно, по меньшей мере одно высказывание из данной системы будет истинным тогда и только тогда, когда будет истинным одно из высказываний А л ~ Силн В л ~ С. Поэтому данная система трех высказываний логически эквивалентна более простой системе из двух высказываний А л з С, Вл чС. $2. Нормальные формы для формул алгебры высказываний и их применение Коньюнктивньаи (дизьюнктивным) одночленом от переменных Хп Х„..., Х„называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Дизьюнктивьюй (коньюнктивноя) нормальной ((юрмой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Сокращенная запись: ДН- форма и КН-форма соответственно. Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него. 40 Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных.
Сокращенная запись: СДН-форма (или СДНФ) — совершенная дизъюнктивная нормальная форма, СКН-форма (или СКНФ) — совершенная конъюнктивная нормальная форма. Например, (Х, л зХ~ л Хз) и (Х, л Хз) ~ зХ~ — дизъюнктивная (но не совершенная) нормальная форма от трех переменных Х„Х„ Х,, а (Х, ~ -1Х2) л (~Х, ч Х1) л (-1Х, ~ -зХз) — совершенная конъюнктивная нормальная форма от двух переменных Х~ и Хъ Отыскание нормальных форм. Решить задачи 2.1 — 2.18. 2.1.
Приведите равносильными преобразованиями каждую из следующих формул к дизъюнктивной нормальной форме: а) (Х++ У) л-з(У-+ Т); б) ИХ-+ У) -э (У-+ -1Х)) -+ (У-+ -зЕ); в) (Х-э (У-+ с!)) -+ ((Х-+ зУ) -+ (Х-+ -1 У)); г) ((Х-+ У)ч -чУ) -+(Хч(Х++Я)); д) (Х вЂ” > У)-+У; е) Х-+ ( У-+ 2); ж) (-зХл -1 У) ~ (Х++ У); з) (Х++ У) -+ (Хл Я); и) (Х++ У) -+ ((-1Х-+ Я) -+ -1 У); к) (Хч -з(У-~ Я)) л (Х~~ Я); л) -з(Хч2) л(Х-~ У). Решение.
л) Всякую формулу равносильными преобразованиями можно привести к ДН-форме. Для этого нужно руководствоваться следующими правилами (алгоритмом): 1) сначала избавиться от операций импликации и эквивалентности, выразив их через логические связки з, л и ~ по законам: Х-+ У- =~Хн У, Х++ У= (~Хч У) л (~ У~~ Х); 2) довести знаки отрицания до независимых переменных, используя законы де Моргана: -з(Хч У) — = зХл -1 1", -~(Хл У) — = -зХ ~ -з 1', 3) применяя закон дистрибутивности (Х~ У) л У=(Хл У) ~ ~ (У л Я), преобразовать формулу к дизъюнкции конъюнктивных одночленов; 4) постоянно избавляться от двойных отрицаний: з-зХ- =Х Обратимся к нашей формуле и преобразуем ее к ДН-форме, руководствуясь приведенными правилами: з(Хч Х) л (Х-+ У) — = (~Хл ~У) л (~Х~ У) — = зХл (-зУл (-зХч '~ У)) — = -зХл ((-зУл-1Х) ч (-зал У)) = — (-зХл ~Ел-зХ) м (~Хи Ул л ~У) =— (зХл -з2) ч (-зХл Ул -ь2).
2.2. Приведите равносильными преобразованиями каждую из формул задачи 2.1 к конъюнктивной нормальной форме. Р е ш е н и е. л) Каждую формулу равносильными преобразованиями можно привести к КН-форме, руководствуясь четырьмя правилами, приведенными при решении задачи 2.1, л, с той лишь 41 разницей, что в правиле 3) следует использовать другой (двойственный) закон дистрибутивности: (Хл У) ч У— = (Хч 2) л (Уч Х). Преобразуем данную формулу: -з(Хч Я) л (Х-+ У) = (зХл -зЯ) л (-зХ ч У) - =(зХл ~Я) ч ( зХл л Ул -~Я) = — ((-зХ л -зЯ) ч ~Х) л ((зХ л-зУ) ч У) л ((зХ л зЯ) ч ч~Х) — = -зХл ((зХч У) л (-зУ ч У)) л -зУ = (~Хл (-зХ ч У)) л ~ ((-Г У) ~ Л) = - Х ~ - Л 2.3. Применяя равносильные преобразования, найдите СДН- форму для формул из задачи 2.1. Р е ш е н и е.
л) Чтобы привести формулу к СДН-форме, нужно сначала равносильными преобразованиями привести ее к какой- нибудь ДН-форме (см. задачу 2.1). При этом нужно убрать члены дизьюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся), а из одинаковых членов дизъюнкции удалить все, кроме одного. Далее, если какой-либо конъюнктивный одночлен в ДН-форме содержит не все переменные из числа входящих в исходную формулу, то его умножают на единицы, представляемые в виде дизъюнкций Х,~-зХ. каждой недостающей переменной Х, с ее отрицанием зХ.
(закон исключенного третьего). Затем раскрывают скобки внутри каждого такого конъюнктивного одночлена, применяя закон распределительности (дистрибугивности) коньюнкции относительно дизъюнкции. Наконец, если среди членов полученной дизъюнкции окажутся одинаковые конъюнктивные одночлены, то из каждой серии таковых следует оставить по одному. Приведем данную формулу к СДН-форме, начав преобразования с ДН-формы, полученной при решении задачи 2.1: -з(Хч Е) л (Х-+ У) — = (~Хл ~У) ч (~Хл Ул -зУ) — = ((~Хл ~У) л л (Уч ~У)) ч (~Хл Ул -~2) — = (зХл -зУл У) ч (зХл -зУл-зУ) ч (зХл л Ул -з2) = (зХл Ул зУ) ч (~Хл -з Ул -зУ).
2.4. Применяя равносильные преобразования, найдите СКН- форму для формул из задачи 2.1. Р е ш е н и е. л) Правила приведения формулы к СКН-форме двойственны соответствующим правилам приведения к СДН-форме. Начав с какой-нибудь КН-формы данной формулы (см. задачу 2.2), нужно в каждом ее дизъюнктивном одночлене, в котором присутствуют не все переменные из числа входящих в данную формулу, добавить (через дизъюнкцию) нули, представляемые в виде конъюнкции Х л -зХ каждой недостающей переменной Х с ее отрицанием -~Хь Затем внутри каждого такого дизъюнктивного одночлена раскрыть скобки, используя закон распределительности (дистрибутивности) дизъюнкции относительно конъюнкции. Наконец, если среди членов полученной конъюнкции окажутся одинаковые дизъюнктивные одночлены, то из каждой серии таковых следует оставить по одному. Приведем данную формулу к СКН-форме, начав преобразования с КН-формы, полученной при решении задачи 2.2: 42 -з(Хч У) л (Х-+ Ч) — = -зХл -~У=— (зХч (Чл -з У)) л (зУч (Хл , -Х))=(-Х Ч)~(-Х.-Ч)~(Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
