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

Замкнутый класс б называется нреднолным, если сг м С и 6 не содержится ни в каком другом замкнутом классе, отличном от С. Независимая система функций сз называется базисом замкнутого класса )с, если всякая функция из 1с есть суперпозиция функции из сг. Введем специальные обозначения для основных функций алгебры логики: 0(х) = О, 1 (х) = 1 для всех х, 1'(х) = х; 0 при х=1, 1 при х=О; 11 при х = у = 1, '(О в остальных случаях; ~0 при х=у=О, хчу = (1 в остальных случаях; (О при х= у, х+ у= (1 при хму; хну = - х»у, х и у =- (х+ у), х ! у = - (х у). 1 2.

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ 59 Через С обозначается класс функций, удовлетворяющих условию У (1, 1, ..., 1) = 1, а через С, — класс функций, удовлетворяющих условию У(0, О, ..., 0) = О. 1. есть клаас всех линейных функций, т. е. функций вида х + ... + х + е, где е н (О, 1). 1) есть класа само- двойственных функций, т. е. функций, удовлетворяющих условию У (х,, ..., х ) =-У (- х, ..., пх ).

Через М обозначается клаас всех монотонных функций, т. е. функций, удовлетворяющих условию х ну,...,х ~у ~У(х,...,х)яУ(у,,...,у). Пусп Т вЂ” терм, представляющий некоторую функцию алгебры логики, в записи которого встречаются только знаки с, ч и и и переменные ап ..., а . Обозначим через е (Т, х) формулу теории множеств, полученную из терма Т подстановками вместо переменных а,, ..., а соответственно выраженийхн х, ..., хи Я„, Обозначим через Я (Т) выражение, которое получаетая из терма Т заменой переменных а. символами Я., символов о, ч, и — соответственно символами Г), (.), —.

При интерпретации а в теории множеств символы х. будут обозначать подмножества универсального множества К 1. Показать, что каждой формуле А алгебры высказываний можно сопоставить функцию у(А) алгебры логики так, что А1 А2 "У ('1)) Р (Аг)' 2. Сколько имеется функций алгебры логики от н переменных? 3. Найти все существенные переменные следующих функций: (а) (убх)ч(~уВа); (б) (хну)ч-зх; (в) (хЗ(уЭз)):)((хну) Э(хЭх)). 4. Выразить а помощью суперпозиций: (а) 8 и З чсрезч и тц (б) ч и З через Ь и тц (в) о ич через Э и хц (г) о,ч, Э,.~ через П (д) - через Э иО; (е) .

через + и 1; (ж) ч через З, 5. Доказать, что С, С, 1., Р и М являются различными замкнутыми классами, отличными от С. Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА 60 6. Доказать, что нельзя выразить с помощью суперпозиций: (а) -1 через а,ч, ~им; (б) ~ через а, ч; (в)'а ре ч,э. 7. (а) Доказать, чтодля каждой функцииг'(х, х, ..., х ) выполняется равенство 1(х, х,, ...,х ) = (х )'(1, х,, ..., х )) ч(-~х.у(0, х, ..., х )). (б) Пусть л ) ( ~ 1. Доказать, что каждую функцию г (х,, ..., х„) алгебры логики можно представить в виде где с.Е (О, Ц, х. = -~х., х.

= х,. о 1 ' ' / Г 1 ! 8. Доказать полноту систем функц| й: (а) (а, ч,-); (б) (ч, -1); с ) (а',.);' (г) (~, -1). 9. Доказать неполноту систем функций: (а) (&, ч, э); (б) (-). 10. Доказать полноту систем функций: (а) ((); (б) (ь) (здесы = -з(хну)); (в) (~, 0); с ) (+, , Ц. 11. Доказать, что: (а) (+, °, Ц вЂ” полная система функций; (б) любая функция )'(х,, ..., х ) единственным образом предста- вима в виде: е, .

х ...х,, А>О !я! <..</ яв 1 где с.. Е(0, Ц. 1 1 12. Показать, что следующие системы функций независимы: са) (, =); (б) (-1, +); 1 2. ФУНКНИИ АЛГЕБРЫ ЛОГИКИ (в) [ы, +); (г) [м, у). 13. Показать полноту и независимость следующих систем функций; (а) [Э, /[, где х/у = .ч(уЭх); (б) [О, 1, [...,. Ц, где [х, у, х] = [убх) г[-нуйа); (в) [ы, ч, 0). 14.

Покажите, что м, + не составляют полной системы функций. Выясните все возможные способы сделать зту систему полной системой независимых функций добавлением одной не более чем 2-местной функции. 15, Какая система из одной 2-местной функции является полной? Найти все такие системы. 16. Привести пример полной системы функций: (а) состоящей из одной 3-местной функции; (б) состоящей из одной л-местной функции [пн2). 17. Доказать, что из всякой полной системы функций можно выделить конечную полную подсистему.

18. Доказать, что: (а) [8, 'э] — базис для С; 1' (б) [8, +) — базис для С,; (в)» [ч, й,О, Ц вЂ” базисдляМ; (г) (О, ы] — базисдля1.; (д) ь [ ч, ху + хх + ух) — базис для 1). 19. Доказать, что классы С, С являются предполгыми классами. 20. Доказать, что: (а) из всякой немонотонной функции и функций О и 1 можно получить суперпозициями функцию -~; (б) класс М является предполным классом. 21. Доказать, что: (а) из всякой несамодвойс)венной функции и функции ~ можно получить суперпозициями функций О и 1; (б) класс Э является предполным классом. 22. Доказать, что: (а) из всякой нелинейной функции и функций О, 1, и можно получить суперпозициями функцию $; (б) класс Ь является предполным классом.

23. Доказать, что любой замкнутый класс К м С содержится в некотором предполном классе. Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА 62 24. Доказать, что система функций полна тогда и только тогда, когда она не содержится ни в одном из предполных классов. 25».

Доказать, что не существует предполных классов, отличных от С, С, Е, Р и М (теорема Э. Поста>. 26. Доказать, что всякий базис С содержит не более четырех функций. 27. Пусть Т и Т вЂ” термы, представляющие некоторые функции 1 алгебры логики, е (Т, х) — формула теории множеств, определенная в конце вводной части параграфа. Доказать, что: (а) е ((ТчТ ), х) «» (е (Т, х)че (Т, х)); (б).((тат,), ) (.(т,х)а.(т,,х)); (в) е (-1Т, х) «» -«е (Т, х).

28. Доказать, что в теории множеств: (а) е, (-1Т) = — Е(Т), где — Я = ЮЕ; (б) 2, (Т Ч т ) = е. (Т)(.)Е (т ); (в) 2 (ТаТ ) = 2 (Т)Г)Е(т ). 29. Доказать, что в теории множеств е (Т, х) «» хЕЕ (Т). 30. пусть функция 2 представима термом т, а д — термом т,. Доказать,что: (а) если /'(а,, ..., а„) = я(а1, ..., а ) для всех а,, ..., а , то в теории множеств выполняется тождество х.

(Т) = Е (Т ); (б) если (1" (а, ..., а„)~д (а,, а )) = 1 для всех а,, ..., а, то в теории множеств выполняется соотношение е, (Т) С2(т ); (в) если 2'(а, ..., а ) = 1 для всех а, ..., а, то в теории множеств 1' ''' 1' "' Х' выполняется тождество 2 (Т) = (2; (г) если 2 (а, ..., а ) = О для всех а, ..., а„, то в теории множеств 1 ~ Ь 1' "' «' выполняется тождество 2 (Т) = и . 31. Доказать, что если функция У (а1, ..., а„) представима термом Т н е, (Т) = (( для произвольных множеств е,, ..., Е С(2, то У(а,, ..., а ) = 1длявсеха, ...,а .

32, На основании каких тождеств алгебры логики можно получить следующие теоремы теории множеств: (а) (ХНУ)0х, = Х0(У0х); (б) ХГ)У»» УГ)Х; (в) — (ХЙУ) = — Х0 — У; (г) — ( — Х) = Х? 53.ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ 63 33. Какие теоремы теории множеств можно получить из следующих тождеств алгебры логики: (а) (а$(-«ачЬ))~Ь = 1; (б) аб(ачЬ) = а; (в) ач-«а = 1; (г) (абЬ)Э(ачЬ) = 1; (д) абЬ = Иа; (е) а = а$(Ьч-«Ь); (ж) -«(а«ЪЬ) = .«ач-«Ь; (з) (абЬ)ча = а; (и) (абЬ)бс = аб(Ьбс); (к) -«(ачЬ) = -«аб-«Ь; (л) ач(абЬ) = а; (м) (ачЬ)чс = ач(Ьчс) (н) аб -«а = О? 1) Э.

ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ Определим исчисление высказываний ИС. Рассмотрим алфавит б=(Ь«о(Ь,«.)взи(Ь4, где В«=(Р«,Р,,...), (Ь,=(,а,ч,~), 6,= = ((, ),,), 64 — — («-). Понятие формулы определяется, как в 9 1. Секвенциями называются выражения следующих трех типов, где А, ..., А,  — любые формулы; !' ''' и* А,, ...,А «-В, где п>0 (аизА,, ...,А следует В»), «-В (В доказуема), (система А,, ..., Ап противоречива). Х, ". Хе Правилом вывода называется выражение вида Х, где Х,, Х, Х вЂ” произвольные секвенции. Х называется непосредственным следствием Х, ..., Х по данному правилу вывода. Исчисление ИС определяется следующими схемой аксиом и правилами вывода (где символы А, В, С обозначают произвольные формулы, Г,, Г, Г, à — конечные последовательности формул, возможно, пустые). Схема аксиом: А «-А.

Правила вывода". Г ьА, Г ьВ Г А ) (введение Г ь(А ч.п. мАтнмлтичнскля логикл 64 Г ь(А $В) Г.( Г ь(АЗВ) 3. ГьА Г КАчВ) Г «-В ' Гь(АчВ) (удаление $); (удаление $); (введение ч); (введение ч); Г ь(АчВ)«Г, А «С, Г, В «С Г,Г Г С г з Г, А«-В 7. ' (введение Э); ' Гь(А~В) Г, ьА, ГгКАЭВ) Г Г В (удале иеМ); г~ Г,Аь 9. ,' (введение -«); " Г«--«А Г, «-А, Г «--«А 10...

(сведение к противоречию); г,г «- Г, -«Аь 1 1 Г ( (удаление ~); Г «-А Г«- 12. — (утончение); ' Г«-А Г «-А 13.. (расширение); ' Г,ВьА Г,А,В,Г «С 14. Г В А Г С (нереста~еще)' Г, А, А «С 15. 1. ' (сокращение). Аксиомой называется выражение, получакицееся из схемы аксиом подстановкой вместо символа А конкретной формулы, Вывод в ИС есть конечнаг последовательность секвенций Х, ..., Х такая, что для каждого 1 (1~1~й) Х. есть либо аксиома, 1' "' либо непосредственное следствие предыдущих секвенций по прави- ' лам 1-15.

Секвенция Х называется выводимой (или доказуемой) в ИС, если существует вывод в ИС, оканчивающийся секвенцией Х. 1 з. исчисления высказываний ' Х,,...,Х, Правило Х называется дон)чтимым в ИС, если нз выводимости в ИС секвенций Х, ..., Х следует выводимость секвенции Х. Определим исчисление ИВ. Схемами аксиом исчисления ИВ являются следующие выражения: 1. (А~(ВЗА)); 2. ((АЭВ) Э((АЭ(ВЭС)) Э(АЗС))); 3.

((АЯВ)ЗА); 4. ((АЯВ) ЭВ); 5. ((А~В) ~((А~С) ~(А~(ВбС)))); б. (А~(АчВ)); 7. (ВЭ(Ачв)); 8. ((АЭС).:>((ВЭС)З((АчВ)ЭС))); 9. ((А~-вВ)~(В~-зА)); 10. (т~АЭА). Исчисление ИВ имеет следующее правило вывода (людна ропепз): А, ~АЭВ1 В Аксиомой (или вариантом схемы аксиом) называется выражение, получаемое из данной схемы аксиом подстановкой вместо символов А, В и С конкретных формул.