И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 9

(т) ((РчР)~Р); (у)на )~(( а) ( ))); - (ф) ((( а) ) " (х) ( РЭ(РЭД)), 1О. При каких значениях переменных Х, У, х„11, У, И' ложны следующие формулы: (а) (((ХЗ(УЮ))|(тУ:| тХ))Э-~У); (б) ((Х8 У)ч(Хая)ч(ЛК)ч(иа~~.(иаИ» ()аИ» ( Ха (()); (в) (((Хч У)чк) э((Хч У) ~(Хчх))); (г) (((Хч У) а((У К) а(КАЯХ))) Э((Ха У) аК)); (д) ((Хчу)~((-ХЬУ)ч(ХЙ- У)))? 11. Доказать, что если формула А тождественно истинна, то формула А(Р|В) товщественно истинна. (Здесь Р— пропозициональная переменная, а  — формула.) 12. Доказать, что если формулы А н (АЭВ) тождественно истинны, то формула В тождественно истинна. 13.

Доказать, что: (а) если формулы (АчВ) и (.чАчС) тождественно истинны, то формула (ВчС) тождественно истинна; (б) если формулы (АчВ), (АЭС), (В:|Р) тождественно истинны, то формула (СчР) тождественно истинна; (в) если формулы (-ь4чВ), (-1Сч В) тождественно истинны то формула (А:)-|В) тождественно истин 14. Доказать, что 15. Доказать, что: (а) А — А; (б) А — В ~  — А; (в) (А — В и  — С) ~ А — С. 54 Ч.11. МАТЕМАТИЧЕСКАЯ ЛОГИКА 16.Доказать, чтоизА, — А иВ, — В следует: (а) -А, — -А; (о) (А(ЙВ1) (Аг~ Вг)1 (в) (А чВ,) — (Агчвг), (г) (А ЭВ ) — (А ЭВ ). 17.

Доказать, что если А — В, то А(Р 1С) — В(Р(С) для л1обых фор- мулА, ВиСипеременнойр. 1а Доказать, что если  — В1 и А, есть результат замены некоторого вхождения подформулы В в формулу А на формулу В, то А-А. 1' 19. Доказать эквивалентности: (а) (РЙР) — Р; (б) (Рао) — (ЦЙР); (в) (Ра(<2ЙЯ)) — ((РМ2) ЙЯ); (г) (Ра(очв)) — ((РЙО)ч(рая)); (д) (Ра(дч )) — Р; (е) (Рчр) — Р; (ж) (РчЦ) — Ячр) (з)(Р (а )) — (( а) ); (и) (рч(айя)) — ((рча) а(рчя)); (к) (Рч®ЙР)) - Р. 20. Доказать эквивалентности: (а) А — А; (б) (А~в) — (- Ачв); (в) - (Аав) — (-зАч-~В); (г) ~(АЭВ) — (АачВ); (д) - (АчВ) — (-Аа В); (е) (Аа(вч-~в)) — А; (ж) (Ач(ВЙ В)) — А; (з) (АЭ-~А) — А; (и) ((Ачв) ИАчС) Й(вчр) Й(Сч р)) — ((А Йр)ч(ВЙС)); (к) (Ай(АчС) &(ВчС)) — ((АйР)ч(ВйС))1 (л) ((Ачл) а(вчс) а(счА)) — ((АаВ)ч(ВаС)ч(СЙА)); (м) ((Ачв) Й(ВчС) Й(Счр)) — ((АЙС)ч(ВЙС)ч(вар)); (н) $ (АчвчС) Й(ВчСчР) Й(СчРчА)) — ЦА ЙВ)ч(А ЙР)ч(В ЙР) чС)1 (о) ((АчВ)а(Ач В)) — А; (и) ((АЙВ)ч((Ачв)а( Ач В))) — (АчВ); (р) (Ач(- АЙВ)) — (АчВ).

21. Доказать, что: (а) (А га А) — (В и В); 5 1 АЛГЕБРА ВЫСКАЗЪ|ВАНИЙ 55 (б) (А - (В и С)) — ИА и В) и С); (в) (А и В) — (В и А). 22. Доказать, что для любой формулы существует эквивалентная ей формула с тесными отрицаниями, т. е. формула, в которой нет символа Э и отрицания относятся только к пропозициональным переменным.

23. Доказать, что для любой формулы существует эквивалентная ей: (а) конъюнктивная нормальная форма; (б) дизъюнктивная нормальная форма. 24. Привести к дизъюиктивной и конъюнктивной нормальным формам: (а) (((РЗД) ~(Я~- Р))З(- ДЭ'Я)); (б) (((((РЭД) Э-|Р) Э.чЦ) Э-чЯ) ЗЯ); (в) ((РЭ(ЦЗЯ)) 3 ((Р:1 пЯ) Э(РЭ.чЯ))). 25. Доказать, что если А есть тождественно истинная к.и.ф., то для любого дизъюнкта формулы А существует переменная Р такая, что Р и чР входят в этот дизъюнкт.

26. Доказать, что если А есть тождественно ложная д.н.ф., то для любого конъюнкта формулы А существует переменная Р такая, что Р и чР входят в этот конъюнкт. 27. Пусть А — формула с тесными отрицаниями (см. задачу 22) и А, получается из А заменой $ на ч, ч на $ и переменных А на чАГ | Доказать, что А — - А. 1 28 . Пусть А н  — формулы с тесными отрицаниями (см. задачу 22) и А,  — формулы, двойственные к А и В соответственно (А получается из А заменой $ на ч, ч на Й). Доказать, что из А — В следует А — В (закон двойственности).

29. По данному набору значений переменных построить коньюнкт, истинный только для этого набора значений переменных. (Назовем такую формулу коньюнктом, соответствующим данному набору значений переменных.) 30. Доказать, что всякая формула А эквивалентна дизъюикцни конъюнктов, соответствующих тем наборам значений переменных, при которых данная формула истинна (см. задачу 29).

31. (а) Доказать, что для любой выполнимой формулы существует эквивалентная ей с.д.н.ф. (б) Доказать, что для тождественно ложной формулы не существуег эквивалентной ей с.д.н.ф. 32. По данному набору значений переменных построить дизьюнкт, ложный только для этого набора значений переменных. (Назо- ч.п, млтимлтичкскля логикл вем такую формулу дизъюнктом, сооп!веп!с!пеуюи(им данному набору значений переменных. ) ЗЗ.

Доказать, что всякая формула А эквивалентна конъюнкции дизъюнктов, с<ютветствующих тем наборам значений переменных, при которых данная формула ложна (см. задачу 32). 34. (а) Доказать, что для любой опровержимой формулы сущест- вует эквивалентная ей с.к.н.ф. (б) Доказать, что для тождественно истинной формулы не сущест- вует эквивалентной ей с.к.н.ф. 35. Привести к совершенной дизъюнктивной нормальной форме, т.

е. найти с.д.н.ф., эквивалентную данной формуле: (а) (( РЗ О)Э((08Л)Э(РЗЯ))); (6) (((РЭЦ)Э Р)Э(РЭ(Ц8Р))); (в) (.((ИЦР) Э.Р) а ((Р8ИЭ.Ц)). 36. 1!ривести к совершенной конъюнктивной нормальной форме, т. е. найти с.к.н.ф., эквивалентную данной формуле: (а) ((Я~Р):)(- (ЦчЛ) ~Р)); (6) (-((Рааэр)ч(ра((2~Я))); (в) (~(РВ(Очи))Э((Р8Ц)чЯ)). 37. Построить формулу А такую, чтобы данная формула была тож- дественно истинной: (а) (((АЬД)Э-~Р)Э((РЭ-~Ц)ЭА)); (б) (((Я Э(-зЦЬР)) ЭА) ~(А8 (РЭД) 8Л)). 38. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

39. Построить формулу от трех переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных. 40. Построить формулу А от переменных Р„Я, Я так, чтобы: (а) (, 8А) — (Рай и (РчА) — (Р К). (б) (Я:!А) — (К~(РЩ) и (А!Я) — (-з(РчЦ)!Я); (в) (РЭА) — ЯЭ(.зрчЯ)) и ((ЯЭЦ)ЭР) — (-зР!-зА). 41. Доказать, что формула от и переменных является тождествен- но истинной (тождественно ложной) формулой тогда и только тогда, когда ее с.д.н.ф. (с.к.н.ф.) содержит 2" попарно не эквивалентных конъюнктов (днзъюнктов) .

42. Пусть формула А записана в с.к.н.ф..Строим формулу В сле- дующим образом: 1) выписываем конъюнкцию дизъюнктов, не входящих в А; 2) меняем 8нач, чна 8, Р.иа !Р., -!Р.нар, ! ! 1 ! Доказать, что формула  — с.д.н.ф. формулы А. 57 8 2. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 43. По с.к,н.ф. формулы А построить: (а) с.д.н.ф.

А*, где А' — двойственная к А (см. задачу 28); (б) с.к.н.ф. формулы -тА; (в) с.д.н.ф. формулы -чА. 44. По с.д.н.ф. формулы А и с.д.н.ф. формулы В построить; (а) с.к.и.ф. и с.д.н,ф. формулы (АУВ); (б) с.к.н.ф. и с.д.н.ф. формулы (АЙВ); (в) с.к.н.ф. и с.д.н.ф. формулы (АЗВ). 45'. Доказать, что формула А от переменных Р, ..., Р эквивалентна некоторой формуле, содержащей лишь Ь, ч, ~ и не содержащей -, тогда и только тогда, когда в ее слс.н.ф. отсутствует дизьюнкт(пр ч...ч Р ). 46*. Пусть формула А не содержит других связок, кроме м. Доказать, что А является тождественно истинной тогда и только тогда, когда каждая переменная входит в А четное число раз. 47'. Пусть формула А не содержит других связок, кроме и и -~.

Доказать, что А является тождественно истинной тогда и только тогда, когда каждая переменная и знак отрицания входят в А четное число раз. $2, ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ Функцией алгебры логики называется любая и-местная функция из (О, 1) в (О, 1). Множество всех функций алгебры логики обозначается через С. Будем говорить, что функция г(х,, ..., х,, х( х,,, ..., х ) существенно зависит от переменной х., если существует такая последовательность а,, ..., а., а,, а из О и 1, что Переменные, от которых функция Г'(х, ..., х ) существенно за- 1'"' и висит, называются существенными переменными для функции У(х,, ..., х ), остальные — фиктивными. Будем отождествлять функции, из которых добавлением фиктивных переменных можно получить одну и ту же функцию.

Пусть имеется некоторое множество !г функций алгебры логики. Каждой и-местной функции Г' из б поставим в соответствие функциональный символ 1. Пусть г, г, г ...— счетное множество снмво- О' !' 2' ''' лов, называемых переменными. Определим понятие терма: 58 Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА (а) переменная есть терм; (б) если У вЂ” н-местная функция из 0 и Т, ..., Т вЂ” термы, то 1''" н 1(Т, ..., Т ) — терм; (в) других термов нет. Сопоставим каждой переменной»о, »,, ... ее значение во множестве (О, Ц.

Опрег елим значение терма т при данных значениях переменных: (а) если Т вЂ” переменная, то значение Т совпадает со значением этой переменнс й; (б) если Т=((Т, ..., Т ), а значения Т,, ..., Т есгъг, ..., г соответственно, то значение Тесть|(г, ..., г„). Говорим, что н-месгная функция я алгебры логики нредставима термам Т, если все переменные Т содержатся среди», ..., » и для любых значений переменных», ..., » значение терма Т совпадает со 1' ' н значением К (»Г ..., » ).

Говорим, что функция я есть сунериозис(ия функций у, ..., у', если я представима термом, все функциональные 1' ' и' символы которого содержатся среди 11, ..., 1 . Система функций О называется полной, если любая функция алгебры логики есть некоторая суперпозиция функций из С. Система функций 0 называется независимой, если никакая функция Усистемы б не представима суперпозициями функций из Ы (Д. Класс функций сг называется замкнутым, если вместе с любыми функциями он содержит и все их суперпозиции.