С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 22
Текст из файла (страница 22)
Пустъ Р - таrх;ое ч.у.мно:исество, что л1обое его rх;онечrное ч.у. подмrно;уtсе ство имеет размерrностъ, не превосхо д.ящу1оТогда dim(P ) ~wp1:n41_d.С1logn~ dim(P ) ~n ==Определ ение5.9.Ч .у.< dn41_С2logn'рмножествоrнесводимъtм для некоторогоdim (P ')d.Рн азываетсяd-d ? 2, если dim(P ) == d идля любого собственного ч . у. подмножества Р' С Р.d-несводимые множества :2 - двухэлементная антицепь (единственное);5.4.(IIIпоток)3 - s 3 , sh, sh ~255+ ...
-описаны, регулярны и хорошо изученJдостаточно часто встречаются и весьма причудливы;4-t - St (единственное 2t-элементное)•каждоеt-несводимоесяподмножествомч.у.ч.у.+ ... ;множествовекоторогоявляет(t+1 )-несводимого .оооооооооР ис .Проблемак(d, п)5.15.оо4-несводимое ч . у. множествоНогина.мощностиКаковомножестванаибольшеезначениемаксимальныхэлементовd-несводимого п-элементного ч.у. множествапри4?d~Данная проблема до сих пор остаётся открытой .Утве ж ение5.1.к(d,п) ~n- d.Глава2565.4Задачи с решениямиЗадача5.
1.Ч.у. множества5.Приведите пример ч.у ..м., имеющего в точности один .ма'}{;си.малъныu элемент и не имеющегонаибольшего.Реш е ни е.• • ••оо•ЗадачаВ ч. у . .множестве5.2.ства А==• •{12, 18}1) А6,( N, )дл.я под.множе-наuти2) A v,3)s нрА,4) infА.Р е шение .{ 36n n == 1, 2, ... } ;{ 1, 2, 3, 6 };sнр А4. infЗадачаА5.3.== НОК (12, 18) == 36;== НОД (12, 18) == 6.Разло;нситъ в пересечегние .мини.малъгногополичества цeneu ч.
у . .мно;нсество Р5.4. (III поток)257Решение .р== [а1 ,ЗадачаЬ1 , а2, С1 , Ь2 , С2 ] П [ а2, Ь2 , а 1 , С2, Ь1 , С1 ] .5.4.1.Сх;олъх;о существует частичнъtх по-р.ядх;ов на .мно;нсестве{ а,Ь, с} ?2.Сх;олъх;о сре ди них неизо.морфных?3.Сх;олъх;о сре ди них линейных пор.ядх;ов?Реш ен ие . Н еизоморфных трёхэлементных порядковтривиальный,оо3иооооооОни порождают порядки на {а , Ь , с }:тривиальныйцепь32+1-1,6,6,Z з и двойственный к нему- ПОВсего- 193о5:258ГлаваЗадача5.5.5.Ч.у. множестваПостроИте ч . у . .мкожества1(1)и! (2)всех иктервалов булевъtх е дикичкъtх %убов раз.меркостеu1и2.Решение . Б улев единичный кубов р азмерностиn содержит зп различных интервалов, при этом имеется C~ 2kинтервалов р азмерностиk, k ==! (1):О,1, ... , n .(-)(О)1(2) == 1(1)х(1)1(1)(двойными линиями показаны экземпляры1(1)):(--)(1-)(11)5.5( - 1)(-0)(10)(01 )(О -)(00)Модели КрипкеИнтуиционистскоеИИВ: формулы.исчислениевысказыванийПрименение ч.у.
множеств в математической логике .мо дели Криn%е как общего способа5.5.(IIIпоток)259установления истинности формул логических исчислений .Зафиксируем множества{ х,• V arу,... }логичесх;их пере.менл-t/ЫХсимволов атомарных въtс?Са3ъtваниu;• Ф === { -., & , V,Определение=> } -логичесх;их св.я3ок5.10. Формулой над .множеством Ф логи чесх;их св.я3ох; на3ъtваетс.я либо нех;отора.я логи'ltесх;а.япере.менна.я (ато.марна.я формула), либо одно и33'1-la-x;ocoчeтa'l-tиu вида (-.А), (А & В) , (А V В) или (А=> В)(.молех;ул.ярна.яА-формула), где А и В-формулы .множество всех логических формул .Для сок ращения записи фор мул принимают соглашения-правила экономии скобок и приоритета связок : внешние скобки у фор мул опускаются и сила связок убывает в порядке, указанном при их введении выше ( >-<<сильнее>> )-, > & > v >=> .К аждая логическая переменная может принимать, вообще говоря, счётное множество истинностных 3'1-lачениu{ О , 1, ...
, } .Первое значение О назовём въtделенны.м .Н ефор мально выделенное значение символизирует<<истину>> ( И), а остальные -различные ситуации от••сутствия истинности : неопределенность высказывания ,различные формы его <<ложности >> (Л) и т. д. В классической логике м ножество истинностных значений сужается до двух:{ , } и выделенное -.Глава260Ч.у. множества5.С леду1-о щие фор мулы назовём схемами апсиом ИИВ:1. А ~ (В ~ А) ;2.(А ~ (в ~ С)) ~ ((А ~ В)~(А~ С));3.
А& В~ А;4. А& В~ В ;5. А~ (В ~ (А& В)) ;6.А ~ А V В;7.В~ А V В ;s.(А ~ С) ~ ((в ~ c) ~ (Av в~ С));9. -,А ~ (А ~В );10.(А ~ В) ~ ((А ~ -,В) ~ -,А).Апсиомъt ИВВ получа1-отся при подстановке в схемыконкр етных фор мул вместо метасимволов А , В и С .В ИИВ имеется единственное правило вывода, обозначаемое МР (лат.modиsponens,правило отделения (?) размещения), позволяющее из формулАиА~ В получить формулу В:А, А~ В Г ВФор мула А называется въtводимой, есл и н айдётсякон ечная по следовательность формулкая, чтоAz ==А1 , . .
. ,AzтаА и каждый элемент по следовательности•либо является аксиомой ,•либо получен по правилу МР из каких-то двухпредыдущих формул.5.5. (III поток)261Выводимость формулы А записывается как ~ А , вfi А.случае отсутствия вывода пишутПример 5.5 (пример вывода формулы в ИИВ ) . Приведём вывод ф ормулы хVу=> уV х.Для удобства фор мулы вывода будем писать другпод др угом , нуме руя их и давая кр аткие комментариипо их полученИIQ.(1)(2)(3)х => у V х- подстановка в схемуу => у V х- подстановка в схему(х => yVx) => ((у => yVx) => (xVy => yVx))становка в аксиому(4)768:- под-А н х, В н у, С н у(у=> у V х) => (х V у=> у V х)-по МР изVх(1)и(3)(5) хvу=> уНапоминание :8.
(А => С)vх6.- ПО МР из (2) и (4)А => А V В ;=> ( (В => С) => (Аv В =>7.В => А V В ;С)) .Пусть Г - конечное множество фор мул. Фор мула Вназывается выводи.моu из .множества формул Г (символически Г ~ В) , если найдётся конечная последовательность фор мул В 1 , ... ,......Bzтакая, чтоB z ===В икажд ыи элемент это и посл едо ват ель но сти•либо является аксиомой,•либо принадлежит Г ,•либо получен по пр авилу М Р из каких-то двухпредыдущих формул .Факт выводимости Г ~ В не изменится, если вместо м ножества Г взять конъiQнкцию составляющих егоГлава2625.Ч.у. множестваформул, так что можно рассматривать только одноэлементные множества Г и опуская фигурные скобки, писать А~ В.Знак ~ является символом отношения предпорядкана множестве А.Проблема выводимости-одна из важнейш их проблемлюбого логического исчисленияL:<< выводима ли вLданная формула? >>.~ А-можно либо предъявить соответствующий вывод, либо доказать его существование;ff А-возможно лишь дать доказательство несуществования вывода А .Метатеория - теория, изуча1ощая язык, структуруи свойства некоторой другой (предметной, или обве'К;тноu) теории:•корректность,•непротиворечивость ,•различные виды полноты,•проблема р азр ешимости,•независимость систем аксиом и правил вывода•• ••Классическое исчисление высказываний КИВ:определениеЕсли к схемам аксиом добавить ещё одну :11.
А V ·А- логический закон(лат. tertiuт попdatur,TND<<третьего не дано>>) ,(III поток)5.5.тополучим263гк;лассичесrк;оеисчислениевысrк;азываниuКИЕ.Тогда ка)КДОЙ логической переменной МО)КНО приписать одно из двух истинностных значений1или О ,понимаемых как <<истина>> и <<ЛО)КЬ>> соответственно, ипо правилам·А ~А&АVВА ~ О;1 9В ~~ О 9А => В ~А ~ В ~1 91 9получить оценку1;А ~ В ~ О;В ~1или А ~ О .F Е { 1, О} лхобой формулы F.Формулы, истинные при любых интерпретшци.ях возмо)КI-IЫХ вариантах приписываний логическим переменным значений(1 илиО)-называi{)ТСЯ тавтологиями .Примеры тавтологий :-, ( ХV у)=>всеаксиомы1- 11 ,••х => х,•Х & 'У, · ··В КИВ выводимыми оказываi{)ТСЯ все тавтологии итолько они =? проблема выводимости сводится к проверке формулы на тавтологичность.В ИИВ задача радикально усло)Княется: это исчисление не имеет конечнозначной интерпретации, т.
е . еслив ЛI{)бом конечном набореTr ~ { О , 1, ... , k - 1} объявив значение О выделенным и задав правила оценкиформул так, чтобы при всех интерпретациях переменным изV arзначений изTrвсе аксиомы всегда принимали бы только знач ение О , найдётся невыводимаяГлава2645.Ч.у.
множестваформула ИИВ такая, что её оценка тоже всегда будетпринимать выделенное значение .ИИВ: проблема разрешимости•Л1обая выводимая в ИИВ формула выводима и вКИВ.• Обратное неверно: например, формулы, получаемые из схемы TND и ''х => х, ~(xVy) => ~х & 'У ,... невыводимы в ИИВ.Для разрешения проблемы выводимости в ИИВприменимметод,основанныйнапостроениишrк;алКрипrк;е.Сол1940)Kpun""'e (Saul Aaron Kripke,- американский философ илогик, один из десяти выда}ощихсяфилософов последних200лет.Ещё }Оношей внёс значительныйвклад в математическую логику,философию математики и теорию множеств.Шкалы Крипке: построение.Чтобы задать такуiошкалу нужно:• указать ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
