AA3-4(Posets) (1127142), страница 3
Текст из файла (страница 3)
Часть IV: Частично упорядоченные множестваЗадачи c решениямиРазделы1Основные понятия теории ч.у. множеств2Операции над ч.у. множествами3Линеаризация4Задачи c решениями5Модели Крипке6Что надо знать40 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениямиВопрос ЧУМ-1: Есть ли разница между утверждениямиЧ.у. множество содержит (а) бесконечную цепь и(б) цепь, длина которой больше наперёд заданного числа”?Ответ:◦ [h[[ NhhNN◦NhhNhNN◦ h...◦◦NNNN◦ ◦ [[ ◦ ◦ AAA[ AAAA◦41 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениямиЗадача ЧУМ-2Приведите пример ч.у.м., имеющего в точности одинмаксимальный элемент и не имеющего наибольшего.Решение....◦◦...◦42 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваЗадачи c решениямиЗадача ЧУМ-3В ч.у. множестве h N, | i для подмножества A = {12, 18}найти1AM ;2AO ;3sup A ;4inf A .Решение.1AM = { 36n | n = 1, 2, . . . } ;2AO = { 1, 2, 3, 6 };3sup A = НОК (12, 18) = 36 ;4inf A = НОД (12, 18) = 6.43 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениямиЗадача ЧУМ-4Разложить в пересечение минимального количества цепей ч.у.множество Pc14c2hhhbbhhh4444haa4441212Решение.P = [ a1 , b1 , a2 , c1 , b2 , c2 ] ∩ [ a2 , b2 , a1 , c2 , b1 , c1 ] .44 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениямиЗадача ЧУМ-51Сколько существует частичных порядков на множестве{ a, b, c }?2Сколько среди них неизоморфных?3Сколько среди них линейных порядков?45 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениями46 / 76Задача ЧУМ-5...Решение.Неизоморфных трёхэлементных порядков 5:тривиальный, 3 и следующие◦◦◦◦◦[[[ ◦Они порождают порядки на { a, b, c }:тривиальный — 1,цепь 3 — 6,2 + 1 — 6,Z3 и двойственный к нему — по 3Всего — 19◦ [[[◦◦ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваЗадачи c решениямиЗадача ЧУМ-6Постройте ч.у. множества I(1) и I(2) всех интерваловбулевых единичных кубов размерностей 1 и 2.Решение.Булев единичный кубов размерности n содержит 3n различныхинтервалов, при этом имеется Cnk 2k интервалов размерностиk, k = 0, 1, . . . , n.I(1):(0)(−)[[(1)47 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЗадачи c решениями48 / 76Задача ЧУМ-6...I(2) = I(1) × I(1)(двойными линиями показаны экземпляры I(1)):(−−)[[[[AAA [ A[AAA(1−)(−1)(−0)(0−)[[[[[[AAAA[[AAAAAA [[ AAAA [[(11)(10)(01)(00)ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели КрипкеРазделы1Основные понятия теории ч.у. множеств2Операции над ч.у. множествами3Линеаризация4Задачи c решениями5Модели Крипке6Что надо знать49 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели Крипке50 / 76Интуиционистское исчисление высказываний ИИВ: формулыПрименение ч.у. множеств в математической логике моделиКрипке как общего способа установления истинности формуллогических исчислений.Зафиксируем множестваV ar = { x, y, . .
. } логических переменных — символоватомарных высказываний;Φ = { ¬, N, ∨, } — логических связок.ОпределениеФормулой над множеством Φ логических связок называетсялибо некоторая логическая переменная (атомарная формула),либо одно из знакосочетаний вида (¬A), (AN B), (A ∨ B) или(A B) (молекулярная формула), где A и B — формулы.A — множество всех логических формул.ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели КрипкеИBВ: экономия скобок и истинностные значенияДля сокращения записи формул принимают соглашения —правила экономии скобок и приоритета связок: внешние скобкиу формул опускаются и сила связок убывает в порядке,указанном при их введении выше (> — «сильнее»)¬ >N > ∨ >Каждая логическая переменная может принимать, вообщеговоря, счётное множество истинностных значений{ 0, 1, .
. . , }. Первое значение 0 назовём выделенным.Неформально выделенное значение символизирует «истину»(И), а остальные — различные ситуации отсутствияистинности: неопределённость высказывания, различныеформы его «ложности» (Л) и т.д. В классической логикемножество истинностных значений сужается до двух: { И, Л } ивыделенное — И.51 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели КрипкеИИВ: аксиомыСледующие формулы назовём схемами аксиом ИИВ:12345678910A (B A);(A (B C)) ((A B) (A C));AN B A;AN B B;A (B (AN B));A A ∨ B;B A ∨ B;(A C) ((B C) (A ∨ B C));¬ A (A B);(A B) ((A ¬B) ¬A).Аксиомы ИВВ получаются при подстановке в схемыконкретных формул вместо метасимволов A, B и C.52 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели КрипкеИИВ: правило вывода и выводимые формулыВ ИИВ имеется единственное правило вывода, обозначаемоеMP (лат. modus ponens, правило отделения), позволяющее изформул A и A B получить формулу B:A, A B ` BФормула A называется выводимой, если найдётся конечнаяпоследовательность формул A1 , .
. . , Al такая, что Al = A икаждый элемент последовательностилибо является аксиомой,либо получен по правилу MP из каких-то двух предыдущихформул.Выводимость формулы A записывается как ` A, в случаеотсутствия вывода пишут 6` A.53 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели КрипкеИИВ: пример вывода формулыПриведём вывод формулы x ∨ y y ∨ x.Для удобства формулы вывода будем писать друг под другом,нумеруя их и давая краткие комментарии по их получению.(1) x y ∨ x— подстановка в схему 7y∨x— подстановка в схему 6(2) y(3) (x y ∨ x) ((y y ∨ x) (x ∨ y y ∨ x)) —подстановка в аксиому 8: A 7→ x, B 7→ y, C 7→ y ∨ x(4) (y y ∨ x) (x ∨ y y ∨ x)(5) x ∨ yy∨x— по MP из (1) и (3)— по MP из (2) и (4)Напоминание:» A A ∨ B;¼ B A ∨ B;½ (A C) ((B C) (A ∨ B C)).54 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели КрипкеИИВ: выводимость из множества формулПусть Γ — конечное множество формул.Формула B называется выводимой из множества формул Γ(символически Γ ` B), если найдётся конечнаяпоследовательность формул B1 , . . . , Bl такая, что Bl = B икаждый элемент этой последовательностилибо является аксиомой,либо принадлежит Γ,либо получен по правилу MP из каких-то двух предыдущихформул.Факт выводимости Γ ` B не изменится, если вместомножества Γ взять конъюнкцию составляющих его формул,так что можно рассматривать только одноэлементныемножества Γ и опуская фигурные скобки, писать A ` B.Знак ` является символом отношения предпорядка намножестве A.55 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели КрипкеПроблема выводимости —— одна из важнейших проблем любого логическогоисчисления L: «выводима ли в L данная формула?».` A — можно либо предъявить соответствующий вывод, либодоказать его существование;6` A — возможно лишь дать доказательство несуществованиявывода A.Метатеория — теория, изучающая язык, структуру и свойстванекоторой другой (предметной, или объектной) теории:корректность,непротиворечивость,различные виды полноты,проблема разрешимости,независимость систем аксиом и правил вывода...56 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели Крипке57 / 76Классическое исчисление высказываний КИВ: определениеЕсли к схемам аксиом добавить ещё одну:11A ∨ ¬A— логический закон TND(лат. tertium non datur, «третьего не дано»),то получим классическое исчисление высказываний КИВ.Тогда каждой логической переменной можно приписать одноиз двух истинностных значений 1 или 0, понимаемых как«истина» и «ложь» соответственно, и по правилам|¬A| = 1 ⇔ |A| = 0;|AN B| = 1 ⇔ |A| = |B| = 1;|A ∨ B| = 0 ⇔ |A| = |B| = 0;|A B| = 1 ⇔ |B| = 1 или |A| = 0.получить оценку |F | ∈ {1, 0} любой формулы F .ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели КрипкеКИВ: тавтологииФормулы, истинные при любых интерпретациях — возможныхвариантах приписываний логическим переменным значений (1или 0) — называются тавтологиями.Примеры: все аксиомы 1–11, ¬¬x x, ¬(x ∨ y) ¬xN ¬y, ...В КИВ выводимыми оказываются все тавтологии и только они⇒ проблема выводимости сводится к проверке формулы натавтологичность.В ИИВ задача радикально усложняется: это исчисление неимеет конечнозначной интерпретации, т.е. если в любомконечном наборе T r = { 0, 1, . .
. , k − 1} объявив значение 0выделенным и задав правила оценки формул так, чтобы привсех интерпретациях переменным из V ar значений из T r всеаксиомы всегда принимали бы только значение 0, найдётсяневыводимая формула ИИВ такая, что её оценка тоже всегдабудет принимать выделенное значение.58 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваМодели КрипкеИИВ: проблема разрешимостиЛюбая выводимая в ИИВ формула выводима и в КИВ.Обратное неверно: например, формулы, получаемые изсхемы TND и ¬¬x x, ¬(x ∨ y) ¬xN ¬y, ... невыводимыв ИИВ.Для разрешения проблемы выводимости в ИИВ применимметод, основанный на построении шкал Крипке.Сол Крипке (Saul Aaron Kripke, 1940)— американский философ и логик,один из десяти выдающихся философовпоследних 200 лет.Ещё юношей внёс значительный вклад вматематическую логику, философиюматематики и теорию множеств.59 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваМодели КрипкеШкалы Крипке: построениеЧтобы задать такую шкалу нужно:указать ч.у. множество h W, 6 i, элементы носителякоторого называют мирами;для каждого мира указать, какие из логическихпеременных в нём являются истинными (остальныепеременные в этом мире ложны).Факт истинности переменной x в мире w записываютсимволически w x, ложности — w 6 x.При формировании шкалы Крипке требуется, чтобыu 6 v и u x ⇒ v x,т.е., как говорят, «область истинности переменной наследуетсявверх» или «сохраняется в бо́льших мирах».60 / 76ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
