ЛМвИИ (1086253), страница 5

Файл №1086253 ЛМвИИ (Учебник - Логические методы в искусственном интеллекте (2,3 и 5 глава)) 5 страницаЛМвИИ (1086253) страница 52018-01-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Запись А≡В будет означать, что высказывания А и Вравносильны.Основные равносильности исчисления высказываний:1. Коммутативный законAvB≡BvA,A^B≡B^A.2. Ассоциативный законAv (ВvC)≡(Av В) v C,А^ (В ^ C)≡(А ^ В)^С.3. Дистрибутивный законAv(B^C) ≡ (AvB )^(Av C),A^(BvC) ≡ (А^ B)v(A^C).4. Закон Де Моргана¬(AvB) ≡ ¬A^¬B,¬(A^B) ≡ ¬Av¬B5. Закон идемпотентностиAvA≡A,A^A≡A.6.

Закон поглощенияАv(А ^ B)≡A, A^(AvB) ≡ A, Av(¬A^ B)≡AvB.7. Закон склеивания7'. Закон неполного склеивания(A^B)v(A^¬B)≡A(A^B)v(A^¬B)≡Av(A^B) v (А^¬В)8. Закон исключенного третьегоAv¬A=lи закон противоречияА^¬А=09. Закон двойного отрицания ¬¬A≡A или в общем случа嬬...¬ A ≡{ A , если n−чётное }¬ A , если n−нечётноеn раз10.11.12.13.14.15.16.17.18.Av0≡A,А^0≡0Av1 ≡ 1,A^1 ≡ A¬0≡1,¬1≡0A→B ≡ ¬AvBА↔В ≡ (А→В)^(В→А) ≡ (A^B)v(¬A^¬B) ≡ (¬AvB)^(Av¬B)А⊕В ≡ (A^¬B)v(¬A^B)A|B ≡ ¬(A^B) ≡ ¬Av¬BA↓B ≡ ¬(AvB) ≡ ¬A^¬BКонтрапозиция А→В ≡ ¬В→¬А.Необходимо сделать некоторые- дополнения о импликации. Эта связка отражаетструктуру рассуждений. Первый операнд называется посылкой (или антецедентом), а второй заключением (или консеквентом). Из таблицы истинности следует, что при истинностипосылки заключение истинно.

Однако, и при ложной посылке заключение может оказатьсяистинным. Эта единственная связка, обладающая свойством:• если посылка истинна, истинность импликации совпадает с истинностью заключения;• значение истинности зависит от двух операндов;• импликация некоммутативна.Теперь покажем примеры выполнимых, невыполнимых и общезначимых формул:высказывание а выполнимо, отрицание высказывания также выполнимо; (avb) и (а^b) выполнимые формулы: они истинны, в частности, при истинности а и b. Формула (a^¬a)невыполнима. Общезначимые формулы: (av¬a), (a→а), ¬¬а.Покажем, как использовать таблицы истинности для доказательства общезначимостиформулы(a → (b → c)) ↔ ((a ^ b) → c)Таблица истинности будет содержать восемь строк - интерпретаций (n=3, 23=8).Обозначим левую часть этой формулы буквой А, а правую - В, т.е. имеем А↔В.

Таблицаистинности примет следующий вид:Таблица 1.2abcb→ca→(b→c)a^b(a^b)→cA↔BИИИИИИИИИИЛЛЛИЛИИЛИИИЛИИИЛЛИИЛИИЛИИИИЛИИЛИЛЛИЛИИЛЛИИИЛИИЛЛЛИИЛИИ1.4. Формы представления высказываний.Одно и то же сложное высказывание может быть представлено в различных формах.Элементарной дизъюнкцией называется выражение A1v...vAi ...vAn , где каждое Ai(i=1..n) является либо элементарным высказыванием, либо отрицанием элементарноговысказывания и Ai≠Aj при i≠j. Пустой дизъюнкт - единственный невыполнимый дизъюнкт. Егообычно обозначают  или Л.Элементарной конъюнкцией называется выражение B1^B2^...^Bm , где каждое Вi (i=1..m)является либо элементарным высказыванием, либо отрицанием элементарного высказывания.Исчисление высказываний занимается только теми логическими соотношениями,которые возникают из факта построения одних высказываний из других (называемыхэлементарными формулами, или атомами), которые уже не анализируются.В классическом исчислении высказываний принято, что всякое неанализируемоевысказывание (атом) истинно или ложно, но не то и другое вместе.1.2.3.Примеры:¬xvyv¬zx^¬y^¬z¬x4.x^y v z5.6.¬(xvy) v zx^¬(у^z)- элементарная дизъюнкция- элементарная конъюнкция- можно считать частным случаем как элементарной конъюнкции, таки элементарной дизъюнкции;- не является ни элементарной конъюнкцией, ни элементарной`конъюнкцией;- не является элементарной дизъюнкцией;- не является элементарной конъюнкцией.Дизъюнктивной нормальной формой (ДНФ) данного высказывания называетсяравносильное ему высказывание вида K1v...vKi...vKS, где Ki (i=1..s) - элементарная конъюнкция.Конъюнктивной нормальной формой (КНФ) данного высказывания называетсяравносильное ему высказывание вида D1^...^Di...^DT, где Di (i=1..t) - элементарная дизъюнкция.Алгоритм приведения формулы к нормализованной конъюнктивной форме достаточнопрост:• Сначала исключаются из формул в соответствии с приведенными вышеравносильностями связки →, ↔.• Необходимое число раз применяются правила Де Моргана.• Применяется правило дистрибутивности.В процессе приведения исходной формулы необходимо упростить полученную напромежуточном этапе формулу.

При этом надо помнить, что дизъюнкты, содержащиепротивоположные литеры (т.е. высказывание и его отрицание), общезначимы и могут бытьопущены. Кроме того, можно опустить повторения одного и того же высказывания в пределаходного дизъюнкта.На простом примере покажем применение этих правил для приведения формулы кКНФ.Понятие дизъюнкта используется в логическом программировании и, в частности, вязыке Пролог.Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая ДНФ,в которой каждая элементарная конъюнкция (называемая также конституентой единицы)содержит все элементарные высказывания либо их отрицания по одному разу. Конституентыединицы в СДНФ не повторяются.Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ,в которой элементарная дизъюнкция (называемая также конституентой нуля) содержит всеэлементарные высказывания либо их отрицания по одному разу.

Конституенты нуля в СКНФ неповторяются.Каждое высказывание, кроме тавтологии и противоречия, имеет единственную СДНФ иединственную СКНФ.Тавтология не имеет СКНФ. а противоречие — СДНФ.1.2.3.4.5.6.7.8.Примеры:(x^y)v(x^z)vy - ДНФ;(xv¬y)^(¬xv¬z)^x - КНФ(¬x^y^¬z)v(x^¬y^z)v(x^y^z)v(¬x^¬y^¬z) - СДНФ(x v y v z) ^ (¬x v y v ¬z) ^ (¬x v ¬y v z) - СКНФ.¬xvy - можно рассматривать как ДНФ и как КНФ.(¬x ^ y ^ z) v (x ^ ¬y ^ z) - является СДНФ.(x v ¬y v ¬z) ^ (w v ¬x v ¬z) - не является СКНФ.(x^y^¬z)v(x^y^z)v(x^y^¬z) - не является СДНФ.При переходе от ДНФ к СДНФ используются следующие равносильности:A^1 ≡ A;Bv¬B≡1;A≡A^(Bv¬B)≡(A^B)v(A^¬B)Пример:Привести к КНФ формулу (x→(y→z))→((x^q)→z).Исключим импликации:¬(x→(y→z)v((x^q)→z) = ¬(¬xv(¬yvz))v(¬(x^q)vz).Внесем внешние отрицания в скобки, используя закон Де Моргана:(¬¬x^¬(¬yvz))v(¬(x^q)vz) = (x^(¬¬y^¬z))v(¬xv¬qvz) = (x^(y^¬z))v(¬xv¬qvz).Теперь применим дистрибутивный закон и одновременно упростим получаемыевыражения, помня замечание об общезначимости дизъюнкта, содержащего противоречие:(xv(¬xv¬qvz))^((y^¬z)v(¬xv¬qvz)) = (xv¬xv¬qvz)^(yv¬xv¬qvz)^(¬zv¬xv¬qvz).Первая и третья скобки (дизъюнкты) общезначимы, поэтому И^(yv¬xv¬qvz)^И =¬xvyv¬qvz.

Таким образом, полученная конъюнктивная нормальная форма содержит одиндизъюнкт. Эта формула ложна при истинности х, ложности у истинности q и ложности z.Пример:xv(¬x^y)v(¬x^¬y^z) = x^(yv¬y)^(zv¬z)v(¬x^y)^(zv¬z)v(¬x^¬y^z) =(x^y^z)v(x^y^¬z)v(x^¬y^z)v(x^¬y^¬z)v(¬x^y^z)v(¬x^y^¬z)v(¬x^¬y^z).При переходе от КНФ к СКНФ используются следующие равносильности:Av0 ≡ A;B^¬B ≡ 0;A ≡ Av(B^¬B) ≡ (AvB)^(Av¬B).Пример:x^(¬xvy)^(¬xv¬yv¬z) = [xv(y^¬y)v(z^¬z)]^[¬xv¬yv(z^¬z)]^(¬xv¬yvz) =(xvxvz)^(xvyv¬z)^(xv¬yvz)^(xv¬yv¬z)^(¬xvyvz)^(¬xvyv¬z)^(¬xv¬yvz).При переходе от СДНФ к СКНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через дизъюнкцию недостающих (до полного перечня)конституент единицы, а затем взять отрицание этого высказывания и выполнить преобразованияпо закону Де Моргана.Пример:f = (x^y^z)v(x^y^¬z)v(x^¬y^z)v(x^¬y^¬z)v(¬x^y^z);¬f = (¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z);¬¬f = ¬[(¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z)] = (xvyvz)^(xvyv¬z)^(xv¬yvz).При переходе от СДНФ к СКНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через дизъюнкцию недостающих (до полного перечня)конституент единицы, а затем взять отрицание этого высказывания и выполнить преобразованияпо закону Де Моргана.Пример:f = (x^y^z)v(x^¬y^z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^y^z);¬f = (¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z);¬¬f = ¬[(¬x^¬y^¬z)v(¬x^¬y^z)v(¬x^y^¬z)] = (xvyvz)^(xvyv¬z)^(xv¬yvz).При переходе от СКНФ к СДНФ вначале необходимо получить отрицание исходноговысказывания за счет выписывания через конъюнкцию недостающих (до полного перечня)конституент нуля, а затем взять отрицание этого высказывания и выполнить преобразования позакону Де Моргана.Пример:f = (xvyvz)^(xvyv¬z)^(xv¬yvz);¬f = (¬xv¬yv¬z)^(¬xvyv¬z)^(¬xv¬yvz)^(¬xvyvz)^(xv¬yv¬z);¬¬f = f = ¬[(¬xv¬yv¬z)^(¬xvyv¬z)^(¬xv¬yvz)^(¬xvyvz)^(xv¬yv¬z)] =(x^y^y^z)v(x^¬y^z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^y^z).1.4.1.

Минимизация сложных высказываний с помощьюметода Квайна.Существуют различные методы минимизации сложных высказываний. Рассмотримодин из них, удобный для алгоритмизации, а следовательно, для переноса процессаминимизации на ЭВМ - метод Квайна. Этот метод использует следующие равносильности:• неполное склеивание (А^В)v(А^¬В) ≡ (А^В)v(А^¬В)vА;• поглощение AvA^B ≡ A.1.2.3.Минимизация выполняется в три этапа:Высказывание из произвольной формы переводится в СДНФ.Исходя из СДНФ, получают сокращенную дизъюнктивную форму (СкДНФ).На основе СДНФ и СкДНФ строится импликантная матрица, с помощью которойполучается минимальная дизъюнктивная нормальная форма (МДНФ).Заметим, что данный метод (как и большинство других) находит минимальную средидизъюнктивных нормальных форму для данного высказывания (т.е. требование нормальностиформы является серьезным ограничением).Первый этап минимизации был рассмотрен ранее, когда обсуждался переход от ДНФ кСДНФ.На втором этапе минимизации СДНФ выполняют все возможные операциипоглощения.

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

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

Список файлов книги

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