В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 9
Текст из файла (страница 9)
г)~(-Хч г)ьз(-Х Чч ч (Ул ~Я)) л (~Хч ~Чч (Ул ~2)) л (Хч ~Уч (Чл -зУ)) л (зХч -зЪ ч (Чч ~ У) = ( зХ ч Чч Я) л (~Хч Ч ч -зЧ) л (зХ ч - Чч У) л ( ъХ ч ч -П ч -~Я) л (Хч Чч -зЯ) л (Хч -з Чч -~У) л (-зХч Чч ~У) л (-зХ ч Чч ~У) = — (~Х 1'ч У) л (-зХ Чч ~Я) л (-зХч -зЧч Я) (зХч ч -~ Чч зУ) л (Хч Уч ~Я) л (Хч -М ч зЯ). 2.5.
По данному набору значений переменных постройте конъюнктивный одночлен, принимающий значение 1 только на этом наборе значений переменных: а) (О, 0); д) (О, О, 1); и) (1, О, 1); б) (О, 1); е) (1, О, О, 1); к) (1, 1, 1, 0); в) (1, 1); ж) (О, 1, О, 0); л) (О, 1, 1). г) (1, О, 0); з) (О, О, О, 1); Решение. л) Так как конъюнктивный одночлен Х~ л Чз л 1з принимает значение 1 тогда и только тогда, когда Ч, = 1, 1; = 1, 1;= 1, то конъюнкция -зХ~ л Х, л Хз принимает значение 1 тогда и только тогда, когда -зХ, = 1, Хт = 1, Хз = 1, т.е.
когда Х~ = О, Х,= 1, Х, = 1, а значит, -зХ~ л Х~ л Х, — искомый конъюнктивный одночлен. 2.6. Используя СДН-форму, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них: а) Г(0, 0) = Г(1, 1) = 1; б) Г(1, 0) = 1; в) Г(0, 1, 0) = Г(1, О, 1) = Г(1, 1, 1) = 1; г) Г(0, 1, 1) = Г(1, 1, 0) = 1; д) Г(1, О, 0) = Г(0, 1, 0) =Г(0, О, 1) =1; е) Г(0, 1, 1) = Г(1, О, 1) =Г(1, 1, 0) = Г(1, 1, 1) = 1; ж) Г(1, О, 1) =Г(0, 1, 0) = Г(0, О, 0) =1; з) Г(0, 1) =Г(1, 0) =Г(1, 1) =1; и) Г(1, 1, О, 0) =Г(0, О, 1, 1) =1; к) Г(0, 1, О, 1) = Г(1, О, 1, 0) = Г(1, О, О, 0) = Г(1, 1, 1, 0) = 1; л) Г(0, О, 0) = Г(0, 1, 0) = Г(1, 1, 1) = 1. Р е ш е н и е. л) Первому условию удовлетворяет лишь конъюнктивный одночлен ~Хи-~Чл-зУ, второму — -~Хл Чл-зУ, третьему — Хл Чл Е Тогда формула Г(Х, Ч Я) -=(-зХл -з Чл-зЯ) ч (-зХл л Чл-зУ) ч (Хл Ул У) обращается в 1, если и только если -зХл л -з Чл-з2' обращается в 1, или -зХл Чл-~У обращается в 1, или Хл Ул У обращается в 1, т.е.
если и только если (Х, 1; Е) = =(0„0, 0), или (Х, У, У) =(О, 1, 0), или (Х, Ч У) = (1, 1, 1). Следовательно, Г(Х Ч, 2') — искомая формула. 2.7. Докажите, что всякая выполнимая формула алгебры высказываний обладает, и притом единственной, СДН-формой. 2.8. По данному набору значений переменных постройте дизьюнктивный одночлен, принимающий значение 0 только на этом наборе значений переменных: а) (0,0); д)(0,0,1); б) (1, 0)„е) (1, О, О, 1); в) (1, 1); ж) (О, 1, О, О); г) (1, О, 1); з) (1, О, 1, 1); Решение. л) Поскольку дизъюнктивный одночлен У м 1;~ У, принимает значение 0 тогда и только тогда, коша 1; = О, 1з = О, У, = О, то дизъюнкция Х, ~ -~Х, ч -~Х, принимает значение 0 тогда и только тогда, когда Х~ = О, -чХ~ = О, -юХЭ вЂ” - О, т.е.
когда Х~ = О, Х~ = 1, Х3 = 1. Значит, Х, ~ -зХ~ ч -~Х3 — искомый дизъюнктивный одночлен. 2.9. Используя СКН-форму, найдите формулу, принимающую значение 0 только на следующих наборах значений переменных: а) Г(0, 1) =Г(1, 1) =0; б) Г(0, 1) = 0; в) Г(0, 1, 1) = Г(1, 1, 1) = О; г) Г(1, О, 0) = Г(1, О, 1) = 0; д) Г(0, 1, 1) = Г(0, О, 0) = Г(0, 1„ 0) = 0; е) Г(1, 1, 1) = Г(0, О, 1) = Г(1, 1, 0) = Г(1, О, 0) = О; ж) Г(1, 1, О, 1) = Г(0, О, 1, 0) = Г(1, О, 1, 0) = Г(0, О, 1, 1) = Г(0, О, О, 0) =О; з) Г(0, 1) = Г(1, 0) = Г(1, 1) =0; и) Г(1, О, О, 0) = Г(0, 1, 1, 1) = 0; к) Г(0, 1, О, 1) = Г(1, О, 1, 0) = Г(1, О, О, 1) = Г(0, 1, 1, 0) =0; л) Г(0, О, 0) = Г(0, 1, 0) = Г(1, 1, 1) =О.
Решение. л) Первому условию удовлетворяет лишь следующий дизъюнктивный одночлен Х~ Уч У, второму — Хч-~Ух У, третьему — -зХ~-~У ~ -~Л Тогда формула Г(Х У, Я) = (Хч У~~ У) л л (Хч .з Уч Я) л (~Хм -з Уч ~Я) обращается в О, если и только если Х~ Уч У обращается в О, или Хч.зУ~ У обращается в О, или -чХ~~-~У ~-~У обращается в О, т.е.
если и только если (Х У Я) = =(О, О, 0), или (Х, У У) = (О, 1, 0), или (Х, У, У) = (1, 1, 1). Следовательно, Г(Х, У, Я) — искомая формула. 2ЛО. Докажите, что всякая опровержимая формула алгебры высказываний обладает, и притом единственной, СКН-формой. 2.11. Для каждой из следующих формул алгебры высказываний найдите СДН-форму с помощью ее таблицы истинности: а) Х-э У; б) (Хл У) ~У; в) (Х++2)-+(Хл-зУ); г) Хч(У-+(У++(Хл У))); д) ((Хл~у) чУ) л Т; е) (Х++ У) л ( Ус-+ 2) л (У++ Т); ж) ((Х ~ У) -+ 2) ++ -зХ; з) (-г -У)- ((Х 2) У); и) (Х ++ У) л (-зУ-+ ( Т л -зХ)); к) ((Хч-зс~) л У)++((Уч-~Х) лЯ); л) -~(Хл У) -> -ч(Хн У). Р е ш е н и е. л) Составим таблицу истинности данной формулы: Теперь, выбирая наборы значений переменных, на которых формула обращается в 1, подобно тому как это делалось при решении задачи 2.6, л, записываем совершенную дизъюнктивную нормальную форму для данной формулы: -з(Хл У)-»-ч(ХчЯ) — = (-зХл-зул-~2) ч(-~Хл Ул-з2) ч(Хл Ул л -зЯ) ч(Хл УлЯ).
2.12. Для каждой из следующих формул алгебры высказываний с помощью ее таблицы истинности найдите СКН-форму: а) Х<-» У; б) (Хч У) лУ; в) ~(-зХч-~У) л(Х вЂ” «(У'лЯ)); г) (ХлулУ)чТ; д) Хл -з(-ч Ул (2-«(Х++ У))); е) (Хл У) ч(Ул2) ч(Ул Т); ж) (Хл((Тли) ч Т)) ч-ьТ; з) -»(Хл-~У) л(Х++(-зХл У)); и) -ч(((Хч У) -+ -з(Хч У)) л -чУ); к) ((Хч У) -«Я)++-зХ; л) -з(Хл У) -« -з(Хч Х).
Р е ш е н и е. л) Составим сначала таблицу истинности данной формулы (см. решение задачи 2.11, л). Затем, выбирая наборы значений переменных, на которых формула обращается в О, подобно тому как это делалось при решении задачи 2.9, л, записываем СКН-форму для данной формулы: -з(Хл У) -+ -ч(Хч 2) — = (Хч Уч -~У) л (Хч ~Уч ~2) л (.зХч ч УчУ) л~~Хч Уч-чУ). 2.13.
Докажите, что отрицание -»Г всякой формулы Г алгебры высказываний равно дизъюнкции тех и только тех совершенных 45 конъюнктивных одночленов от тех же самых переменных, которые не входят в СДН-форму формулы Г. 2.14. Докажите, что отрицание -зГ всякой формулы Г алгебры высказываний равно конъюнкции тех и только тех совершенных дизъюнктивных одночленов от тех же самых переменных, которые не входят в СКН-форму формулы Г 2.15. Применяя утверждения задач 2.13 и 1.66, перейдите от СДН-формы к СКН-форме для данной формулы: а) à — = (-зХл У) ч(Хл-зу); б) à — = (-зХл ~ У) ч(Хл У); в) à — = (-~Хл-зул-з2) ч(Хл Ул2); г) Г— : (~Хл-зул 2) ч(Хл Чл-з2) ч(-зХл-зул-з2); д) à — = (зХл~Чл-з2) ч(-зХл-зул2) ч(~Хл Чл~2); е) à — = (-зХ л -з Ул -з2) ч (-зХ л Чл -з2) ч (Хл -з Чл -з2) ч (Х л л 1'л~2); ж) Г ь— з (зХл-зул2) ч(Хл ~Чл ~2) ч(~Хл Ул-з2) ч(зХл Чл л 2) ч (Хл 1'л -з2); 3) Г = (-зХл Чл-ч2) ч(-зХл Ул2) ч (Хл Чл2); и) à — = (-зХл -з Чл -з2л -з Т) ч (Хл з Чл 2л -з Т) ч (-зХл Чл -з2 л л з Т) ч (Хл -з Чл -з2л -~ Т) ч (-зХл -з Чл -з2л Т) ч (Хл Чл 2л Т); к) Г г— а (Х л -з Чл -з2 л Т) ч (Х л -з Чл 2 л -ч Т) ч (Х л ~ Ч л 2 л л Т) ч (Хл Ул з2л -з Т) ч (Хл Ул з2л Т) ч (Х л Ул 2л -~ Т) ч (зХл л Ч л 2 л Т) ч (Х л Ч л 2 л Т); л) Г = — (-зХл-зЧл-з2) ч (-чХл Чл2) ч (Хл-зУл 2) ч (Хл Ул л -з2) ч(Хл Чл2).
Р е ш е н и е. л) Согласно задаче 2.13 отрицание данной формулы имеет следующую СДН-форму: зГн (зХл-зул2) ч(~Хл л Чл з2) ч (Хл ~Чл з2). Теперь, применяя утверждение задачи 1.66, находим отрицание этой формулы: Гга (Хч Чч-й,') л (Хч-туч 2) л (-зХч Чч 2). Это и есть СКН-форма данной формулы Г 2.16. Применяя утверждения задач 2.14 и 1.66, перейдите от СДН-формы к СКН-форме ддя данной формулы: а) Г— = (зХч Ч) л(Хч-зУ); б) Г= (-зХч чУ) л (Хч У); в) Г = — (-зХч -П ч -з2) л (Хч Уч 2); г) Г в(-зХч -з Чч 2) л (Хч Чч з2) л (Хч Уч 2) л (-зХч .~ Чч -з2); д) Гн~~Хч-з1'ч-~2) л(-зХч-~Чч2) л(~Хч Чч-з2); е) Г— = (-зХч ~ Уч з2) л (зХч 1'ч з2) л (Х ч -ч Уч -з2) л (Хч ч Уч-з2); ж) Гаем,~Хч-зуч 2) л(Хч-~Ччз2) л(зХч Учз2) л(~Хч Уч ч 2') л (Хч Уч ~2); 3) Г ьз (~Хч -~ Чч ~ 2ч ~ Т) л (-~Хч -~ Чч -~2 ч Т) л (~Х ч Ч ч 2 ч ч -з Т) гЛ,~Хч Чч 2ч Т) л (Хч Чч 2ч Т); и) ГМХч-зуч з2ч Т) л(ХчзУч2ч-~Т) л(Хч-зУч 2ч Т) л л (Хч Уч -з2ч-зТ) л (Хч Чч-з2ч Т) л (Хч Чч 2ч-зТ); 46 к) Г— = (зХч~уч ~ХччТ) л ( зХч чУч2ч ~7) л (-~Хч УччЯч -зТ) (Хч ~Уч~Хч-~Т) л(-~Хч-~У~-~У~ Т) (Хч УчУч Т); л) Г: — ~;~Хч Уч Я) л (Хч ч Уч -зЯ) л ( зХч Уч -зЯ) л (Хч Уч Я), Р е ш е н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
