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

(!е)) и обозначается через ! 5 ь. двйствия нлд клгдинлльными числлмн 45 т = ,'~~ п., если каждое множество мощности т эквивалентно () А,, (н) (Н) где А. = и и все А. попарно не пересекаются. 1 1 Кардинальное число т называется произведением кардинальных чисел п, и п и обозначается через п п, если ка;кдое множество мощности ш эквивалентно АхВ, где А и В имеют мощности п,, п . Аналогично, кардинальное число т называется произведением кар- дипальпьгх чисел п. (1е() и обозначается ш = П п., если каждое мно! П; (Н1 жество мощности ш эквивалентно П А., где А = п, П; 1Н) Кардинальное число т называется степенью кардинальных чисел п, и п и обозначается через и, г, если каждое множество мощности ш и эквивалентно А, где А и В имеют мощности п, и и .

и 1. Доказать, что для произвольных мощностей ш и п выполняется одно и только одно из условий ш=п, ш<п или п<т (п1рихоп1омия). 2. Доказать, что кардинальные числа линейно упорядочены отношением <. 3. Доказать, что среди кардинальных чисел нет наибольшего. 4. Доказать, чтш (а) 3+5=8; (б) и+ й = КО, где п конечное; О О' О О О' (г))( +с=с; О (д) с + с = с, 5.

Доказать, что: (а) для любых множеств А, А существуют множества В,, В такие, чтоА, — В,, Аг — ВгиВ (1В2 — — а; (б) сумма двух кардинальных чисел всегда существует. б. Доказать для произвольных кардинальных чисел: (а) п1+ п2 = п2+ п1 ' (б) п1+ (пг+ пз) = (п1+ пг) + пз, (в) и+О=о. 7. Пусть А, В, С, А, ..., А — конечные множества. Доказать, что: 1'"' и (а) ЛиВ = Я + З вЂ” А773; 46 Ч.!. ТЕОРИЯ МНОЖЕСТВ (б) ЖИГОЛО = М+ 3 + à — 37% — Я~С вЂ” 377С + ~7~С; и и (в) б( и А,.) = ~ Л,. + ...

+ (-1)" ' 'Я Л.77.;.7т + ...; (=! !,...,! = ! '! ! ! ! «,„! ! и и ! >т;"х;;..:х.= т и+...~!-г>'-' т ут-..ит.'+... !=! !',...,! ! ! ! ! « ° ! ! '" ! 8. (а) Доказать, чтоп<т ~ и+1<в. (б) Привести пример таких кардинальных чисел п и т, что и+1<а, нов<и, 9. Доказать, что п<т тогда и только тогда, когда существует п, такое, что п + п, = пг. Показать, что такое п, определяется не однозначно. 10. Доказать, что: (а)З 5=15; (б) (о ~о (в) йо'с = с; (г) с с =с. 11.

Доказать, что: (а) еслиА — В и С-0, тоАхС вЂ” Вхг); (б) произведение двух кардинальных чисел всегда существует. 12. Доказать для произвольных кардинальных чисел: (а)п, пг = !'г "!' (б) п (п2 пз) (и, пг) "3! ! ( 2 3) ( 1 2) ( ! 3)' (г) п.1 = п; (д) п О = О; (е)' п !и = п, если т — конечное, а п — бесконечное кардинальное число; (ж)' и й = п, если п — бесконечное кардинальное число. .о 13'. Доказать, что пг = п, если п — бесконечное кардинальное число. 14. Доказать, что если п и щ — кардинальные числа и одно из них бесконечно, то п т = п + т = !пах(п, т), если п !и 0 и т;40.

15. Доказать, что: (а) 2 о = с; )( 1ь. днйствия нлд кагдинлльными числлми 16. Доказать, что для двух кардинальных чисел п и п) всегда существует п~. 17. Доказать для произвольных кардинальных чисел !п, п и р: (а) !п" Р = сп" !пР; (б) (юп.п)Р = юпР пР; (! ) (н!в)Р пгв'Р. (г)щ =!и; (д)1 =1. 18. Доказать, что РЯ~ = 2, М 19.

Доказать для произвольных'кардинальных чисел: (а) если гп(п и п«р, то пг(р; (б) если !п«п, то !п+р«п+р; (в) если!пяп, тот р«п р; (г) если !п«п, то !пР«пР; (д) если в«п, то р~«рв; (е) если !п, п>1, то !п+пя!п.п; (ж) !и+и = п тогда и только тогда, когда йо и) «п; (з) если п+т = п и п,>п, топ,+!п = п,; (и) п + щ = п тогда и только тогда, когда и+1 щ = п ЯйА', к>0); (к) п+ т = п тогда итолькотогда, когдап+)( !и = п; о (л) а«2~. 20.

Доказать для произвольных кардинальных чисел: (а) если 2~ийо, то 2~>2 о; (б) если пт" = )(о, то !п = йо, а п конечное. 21. Доказать для произвольных кардинальных чисел: (а) если п>М, то 2"=и"; — о' (б) если1«щ«п, й «п,топР=п". 22. Доказать для произвольных кардинальных чисел: (а) если7 сп, п.=пдля всех !Е1, тот п= У п; ! .йг !нз!' (б) если !и + р = п + р и р конечно, то !п=п; (в) если 2 п =2.п, топ,=п . чл. тиогия множиств 23. Доказать, что -эх <,",л, НЗ1 аа1 24.

(а) Пусть (т.) ((Е1) — семейство кардинальных чисел, причем т. = О для (ЕЙ!. Доказать, что ( 'Ят,= '~~ 1П 1Н1 (Н1)Х (б) Пусть (1П.) ((ЕЛ вЂ” семейство кардинальных чисел, причем т, = 1 для (ЕХС1. Доказать, что П;=П г (Н1 (Н1М (в) Доказать, что П зп,.= О тогда и только тогда, когда существует (Е! !;,Е1такое, что и(( = О. о 25. Доказать, что если у — подстановка на множестве 1, то: (а) у и),.

= ,'> пз (Е! (Н1 (б П (Е1 26. Пусть (А1) есть разбиение множества У на непустые попарно непересекающиеся множества. Доказать, что: "'х =х(х ): И! 1еС !нА.„ п-,=п (п-,~ (Е1 ЛЕС 1ЕА1 27. Доказать, что (а) и ~~>„(п и),) = ~~> (п ип,); (Н1 !Н! п(х -,) =х п-.„.-.-п, 1НХ )Н1 !НК !Н! на! 28. Доказать, что если !п ~ п.для всех (Е1, то: (а) ~ юп, е ~> п.; (Н1 (Н1 ЧАСГБ П МАТЕМАТИЧЕСКАЯ ЛОГИКА $ К АЛГЕБРА ВЫСКАЗЫВАНИЙ Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в алфавите б называется произвольная конечная (возможно, пустая) последовательность символов из б. Произведением слов А и В называется слово АВ.

Слово В называется подсловом слова А, если А = СВР для некоторых слов С и П. Слово В может входить как подслово в слово А несколько раз. Результатом замены данного вхождения подслова В в слово СВ.0 на слово Е называется слово СЕВ. Результатом подстановки А(а1В) в слово А слова В вместо символа а называется слово, полученное одновременной заменой всех вхождений символа а в слово А на слово В. Через А(а 1В, ...,а 1В ) обозначается результат одновременной подстановки в А формулы В, вместо а,..., формулыВ вместо а . и и' рассмотрим алфавит б = б ).)б 1.)бз, где ! б, — (Р~, РГ Р~, ...), б — (~, А, ~, М), б — Н,)).

Символы из б называются переменными высказываниями или про! позициональными переменными. Символы из б называются логическими связками. Связка~ называется отрицанием, й — коньюнкцией, ч — дизъюнкцией, ~ — импликацией. Скобки из б называются 3 вспомогательными символами. Понятие формулы алгебры высказываний определяется следуютдим образом: 1) пропозициональная переменная есть формула; 2) если А и  — формулы, то -~А, (АЬВ), (АчВ), (АЗ В) — формулы; 3) других формул, кроме построенных по пп. 1, 2, нет.

Подформулой формулы А называется любое подслово слова А, которое само является формулой. В 8 1-3 будут использоваться буквы Р, Д, ..., возможно, с индексами, для обозначения произвольных пропозициональных переменных, а буквы А, В, С, ...— для обозначения формул. Будем обозначать формулу ((АгВ)ЦВЗА)) через (А ьп В). (> ! . АЛГЕБРА ВЫСКАЗЫВАНИЙ 5! Будем интерпретировать логические связки как функции, определенные на множестве (и, л) (истина, ложь), со значениями в этом же множестве следующим образом. Отрицание: чи = л, чл = и.

Конъюнкция: иби = и, и8л = л8 н = л8л = л. Дизъюнкция: ичи = ичл = >гги = и, л>гл = л. Имплнкация: и зи = л~и = л ~ л = и,и~л = л. Тогда каждая формула будет интерпретироваться как функция, определенная на множестве (и, л), со значениями в этом же множестве, полученная из ч, $, >г, з по правилам построения данной формулы.

Такую функцию будем также называть таблицей истинности данной формулы. Значением формулы А приданных значениях переменных в множестве (и, л) называется значение функции„соответствующей формуле А, при этих значениях переменных. Формулы А н В называются эквивалентными (обозначается через Л вЂ” В), если при любых значениях переменных значение А совпадает со значением В. Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, прн которых эта формула принимает значение и (л). Формула называется тождественно истинной или тавтологией (то:кдественно ложной илн противоречием), если эта формула принимает значение и (л) при всех значениях переменных. Пусть А, ..., А — формулы (и н 1). Будем называть конъюикци!' ''' ей формул А,, ...,Ав формулу (...(А 8А )...8А ) и обозначать ее через (А 8А 8...8А ).

Будем называть дизьюнкцией формул А,, в' Л, ..., А формулу (...(А ч А )..м Ап) и обозначать ее через (Л !>А >г..лА ). Формула, которая есть пропозициональная переменная или отрицание переменной, называется литералом. Произвольная коньюнкция литералов называется конъюнктом или элементарной коиьюпкцией; произвольная днзъюнкция литералов называется дизъюнктом или элементарной дизъюикцией. Дизъ>онктивной пормильной формой (д.юф.) называется произвольная дизъюнкция конъюнктов, а копъюнктивной нормальной формой (к.н.ф.) — произвольная конъюнкция дизъюнктов. Д.н.ф.

(к.н.ф.) А называется совершенной и обозначается с.д.и.ф. (с.к.п.ф.), если каждая переменная формулы А входит с отрицанием нли без отрицания в каждый конъюнкт (дизъюнкт) точно один раз. Д,н.ф. (к.н.ф., с.д.н.ф., с.к.н.ф.), эквивалентная данной формуле Л, называется с.д.и.ф. (к.н.ф., с.д.н.ф., с.клаф.) формулы Л. 5г Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА 1. Определить, является ли данная последовательность формулой: (а) (Р 8Р,)Р, Рз; (б) (~ о8Р1) ~Рг ~~ «3~~0)~ РО)' (г) «(-1Р )ЭР )Э-з(Р чР )). 2. Сколькими способами можно расставить скобки в последова- тельности, чтобы получилась формула (а) Ро~ Р1чРг8Ро' (б) РРРРРз~ "РР "Ргу 3.

Выписать все подформулы формулы: (') «(, Р,)8(Р, Р,)) (-,,В 1б) «1 о~~ 1)~«Ро~ Р1)~ Р1в 4. Доказать, что всякая формула С, не являющаяся пропозици- опальной переменной, может быть представлена в одном из следу- ющих видов: ~А, (А 8В), (АчВ), (А~В) для некоторых формул А и В. 5. Доказать, что результат замены некоторого вхождения формулы С в формулу А вместо подформулы В снова есть формула. б. Доказать, что результат подстановки А(Р1В) формулы В вместо пропозициональной переменной Р в формулу А снова есть формула. 7.

Построить таблицы истинности для следующих формул: (а) «РЭЯ)ч(РЭЯ8 Р))); (61 (-~(Р~-~(ОЯ,Р)) ~(РчВ)); (в) «Р8ЯЭР)) Э.зР); (г) «(Р8 -з(г) ЭД) ~(РЗЯ)); (д> «Р~ИРВ)) ~«Р~0):1(Р~В)))' (е) «РЬЯч-~Р)) Ь«(СЭР)чд)). 8. Доказать выполнимость формул: (а) (РЗ Р); (б) «РЭЦ)ЭСЭР)); (в1 «ДЭ(РЗЯ))8 «РчЯ)ЭД)). 9. Доказать тождественную истинность формул: '1а1 «РЭД)ч(ДЗР)); (б) «РЗЦ)ч(РЭ- (3)); (в) (РЭЯЭ(РЯД))); ( ) «а)~«а Й( )в (д) «-ъРЭ-зЦ)ЭСЭР)); '(е) (РЭЯЭР)); (ж) (Рч-1Р); 1 1. АЛГЕБРА ВЫСКАЗЪ|ВА11ИЙ 53 (з) ((РЭЦ) Э((РЭ(ДЗЯ)) З(РЭВ))); (и) ((МДРР); (к) ((Раева', (л) (РЗ(РчД)); '(м) (Цз(РчЯ)); (н) ((Р~Я) Э(ИЗ Я) э((РчВ ЭЯ))); (о) ((РЭЦ)Э((РЭ тЦ)~ тР)); (и) ( РЭР); (р) (РЭ (с) ((- (~З'Р)З(( (~~Ррд)).