Главная » Просмотр файлов » С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра

С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 23

Файл №1127136 С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра) 23 страницаС.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136) страница 232019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

множество ( W, ~), элементы носите­ля которого называ1от мирами;•для каждого мира указать,какие из логическихпеременных в нём являются истинныминые переменные в этом мире ложны).(осталь­5.5.(IIIпоток)265Факт истинности переменной х в миревают символически w 1 ~ х, ложности - ww записы­I,Yх.При формировании шкалы Крипке требуется, чтобыи ~vи и 1~ х::::} v1~ х,т. е .

, как говорят, <<область истинности переменной на­следуется вверх>> или <<сохраняется в больших мирах>>.Н еформально порядок и ~претируется как то , что мирvvмежду мирами интер­есть состояние мираив следующий момент времени, понимая время не в фи­з ическом , а в логическом смысле: каждый мир описы­вается состоянием знаний в данный момент и однаждыустановленная истинность или доказанный факт оста••ется таковым и впоследствии.Логическое время не обязательно обладает линей­ным порядком .Опр еделение( W,~, 1~),а 1~ ~Wвящеех5.11 .Шrк;алагде редуктVar( W, ~) -естьч.у.тройкамножество ,-соответствие <<один ко многим>>, ста-каждомулогическихKpunrк;eмирусовокуп ностьпеременныхиистинныхудовлетворяющеев••немусловиюнаследования и стинности .Для построенной шкалы Крипке определим истин-ность данной q)ормулы А в л1обом миреw 1 ~ А & В {::} w 1~ А и w 1~ В;w 1~ Аwwv В {::}w:w 1~ А или w 1~ В;1~ А => В{::} V(и ~w)и 1 ~ В или иI,Y А;1~ 'А {::} V( и ~ w) и I,Y А(т.

е. если 1~ ,А, то не существует большего мира,в котором бы 1~ А).266Глава 5. Ч.у. множестваВ ведённые шкалы Крипке зада}ОТ се.мантиrх;у ИИВ ,придавая смысл фор муламразделяя их на истинные-и ложные в данн о м ми р е .• Истинная в данном мире формула остаётся истин­ной и в старших (больших) мирах.• Ложная в данном мире формула была ложной иво всех младших (меньших) мирах.•Если формула содержит только связки••&иV,••то ее истинность в данном мире не зависит от ееистинности в др угих ми р ах .•И ст инности импликации и отрицания используютпорядо к на множестве мир ов .• Следствием предыдущего является факт незави­симости импликации от других связок: в ИИВ , на­пример , фор мулы А => В и -.АVВлогически неэквивале нтны .ААРи с.5.16.ААААШ калы Крипке : варианты истинности фор­мулы в шкале из двух ми ров5.5.

(III поток)Тео ема2675.6 (корректности ИИВ относительно шкалКрипке). Формула, въtводи.ма.я в ИИВ, истина во всех.мирах всех шк;ал Крипк;е .Доказательство. П окажем, что(1)все аксиомы истины во всех мирах и(2) правило МР сохраняет истинность .Второе очевидно: если и А , и А => В истины во всехмир ах, то В будет также истина во всех мирах .Замечание: чтобы в мире•w проверить оценкуистинность импликацииА => Вриться, что w 1~ А =? w 1~ Внадо удостове­( w l)fА эта импли­кация подавно истина);•ложность импликации А => В надо удостовериться, что w 1~ А =? wТео емаl)fВ.о5.7 (корректности ИИВ относительно шкалКрипке). Формула, выводимая в ИИВ, истина во всех.мирах всех шк;ал Крипк;е .Доказательство.

Покажем, что(1)все аксиомы истиныво всех мирах и (2) правило МР сохраняет истинность.Второе очевидно: если и А , и А=> В и стины во всехмирах, то В будет также истина во всех мирах .Замечание: чтобы в мире w проверить оценку•истинность импликацииА => Вриться , что w 1 ~ А =? w 1 ~ Внадо удостове­( w l)fА эта импли­кация подавно истина);•ложность импликации А => В надо удостоверить­ся, чтоw 1~ А =? w l)f В.268Глава 5. Ч.у. множестваПроверим l -Io аксиому А => ( В=> А) .Если в векотором мире и имеет место и 1 ~ А , тово всех мирахvv ):и (в том числе и в и) справедливо1~ В => А.Проверим 2 -ю аксиому(А => (В => С)) => ((А => В) => (А => С)) .Пусть существует мир и , где она ложна::::}в нёмдолжны быть истины формулы А => (В => С) , А => В и-А, а Сложна.Н о из и 1 ~ А и и 1~ А => В следуетмирахv ):ведливостьи. При и1=v 1=В во всехА => (В=> С) это означает спра­w 1= С во всех мирах w ): v .

Отсюда сле­дует справедливость и1=С-противоречие.Остальные аксиомы проверяются аналогич но.оСле ствие . Дл.я доrк;азателъства невыводимости фор­мулы в ИИВ достаточно уrк;азатъ шrк;алу Крипrк;е, водном из миров rк;оторой она ложна .Такая шкала называется rк;онтрмоделъю для даннойформулы .

Существует контрмодель , являющаяся кор­невым деревом, в которой мир с ложной формулой-его корнем .При мер5.6. 1.Постоим шкалу Крипке , содержащуюмир, в котором формула хВ озьмём два мира и иV --,хvложна.такие, что и ~v,иIY: хv 1 ~ х . Тогда v IY: --,х, откуда и IY: --,х, что, в своюочередь даёт и IY: х V --,х (но v 1~ х V --,х) .и5.5.

(III поток)269vvхх-.хuuххvvх-.ххu-.хuхх-.хx v -.xvх-.хxV-.xuх2.Постоим шкалу Крипке , содержащуi{) мир, в ко­тором формулаПустьив1хмиреIY ~х V 11х.V 11 хиТогда иложна .даннаяIY ~хфор мулаи иложна,IY 11х .Построим два несравнимых между собой мираw,большие и , в которых :• vIY1х и vlr-11х;т. е .vиГлава270• w IJL11х и w 1~115. Ч.у.

множествах.Искомая контрмодель получена:•правила истинности и ложности формул в моделисоблюдены;•формула х будет истинна только в мире v.vwххu-.-.х-.хРис.5.17.JV-.х-.-.хКонтрмодель для1хV 11 хШкалы Крипке: применение•Метод автоматической верификации параллель­ных вычислительных системing),(англ. model check-позволяет про верить, удовлетворяет ли за­данная модель системы формальным специфика­циям. В качестве модели обычно используют шка­лы Крипке, а для спецификации аппаратного ипрограммнога обеспечения - те.мпоралъrну1о (вре­менную) логику.5.5.

(III поток)•Модалъ'Ные271логиrх;иформализуютсилъ'Ныеислабъtе модалъ'Нъtе выражения вида << необходи­мо/ возможно>> , << всегда/ иногда>>, << здесь/ где-то >> ит. д. Заменив в определении шкалы Крипке ча­стичный порядок наотношение толерантности-получим семан­тику для брауэравой логики В;аморфное отношениеки-семантику для логи­SS;диагональноегики М.-модель для модальной ло­.

Характеристики

Тип файла
PDF-файл
Размер
32,22 Mb
Тип материала
Высшее учебное заведение

Список файлов лекций

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее