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

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

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

Полученная в результате форма называется сокращенную дизъюнктивнуюформу (СкДНФ).На заключительном этапе строится импликантная матрица, столбцами которойявляются конституенты единицы исходной СДНФ, строками - элементы СкДНФ, называемыеимпликантами. Выбирается набор импликант, содержащий минимальное количествоэлементарных высказываний и такой, что совокупность выбранных импликант имеет вхожденияво все конституенты единицы. Дизъюнкция этих импликант дает МДНФ.Примеры:1. Получить МДНФ для высказывания (x↓y)v((xvy) ^ ¬z).Начнем с получения СДНФ:(x ↓ y)v((x v y) ^ ¬z) = (¬x^¬y)v(x^¬z)v(y^¬z) =(¬x^¬y^z)v(¬x^¬y^¬z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^y^¬z)12345Далее получим СкДНФ. При склеивании будем указывать порядковые номераконъюнкций, участвующих в склеивании, и рядом записывать результат.

Неполное склеиваниебудет обеспечено за счет того, что конъюнкции, участвующие в склеивании, не уничтожаются:1-2: ¬x^¬y 63-5: y^¬z 102-4: ¬y^¬z 77-10: ¬z2-5: ¬x^¬z 88-9: ¬z3-4: x^¬z 9Теперь выполняются поглощения. Результат каждого склеивания поглощаетконъюнкции, участвующие в склеивании. Выполнив все возможные склеивания, получимСкДНФ ¬x^¬y v ¬z. Получим МДНФ (табл.

1.3):Таблица 1.3.¬x^¬y^z¬x^¬y^¬zx^y^¬zx^¬y^¬z¬¬x^y^¬z¬x^¬y¬z++++++Из импликантной матрицы следует, что МДНФ совпадает с СкДНФ.2. Получить МДНФ для высказывания ((x|y)→(y↓z))v¬(¬x→¬z).Получим СкДНФ:((x | y) → (y ↓ z))v¬(¬x → ¬z) = ¬¬(x^y)v(¬y^¬z)v(¬x^z) = (x^y)v(¬y^¬z)v(¬x^z) =(x^y^z)v(x^y^¬z)v(x^¬y^¬z)v(¬x^¬y^¬z)v(¬x^y^z)v(¬x^¬y^z)123456Получим СкДНФ:1-2: x^y1-5: y^z2-3: x^¬z3-4: ¬y^¬z4-6: ¬x^¬y5-6: ¬x^zСкДНФ имеет вид:(x^y)v(y^z)v/(x^¬z)v(¬y^¬z)v/(¬x^¬y)v(¬x^z).В данном случае получается две МДНФ (табл. 1.4):МДНФ1: (x^y)v(¬y^¬z)v(¬x^z);МДНФ2: (y^z)v(x^¬z)v(¬x^¬y).Таблица 1.4.x^y^zx^y^¬zx^¬y^¬z¬x^¬y^¬zx^y+y^z+x^¬z¬y^¬z¬x^¬y¬x^z¬x^y^z¬x^¬y^z++++++++++1.4.2.

Правила минимизации с помощью карт Карно.Строение карты. Карта Карно представляет собой поле клеток, число которых равночислу наборов аргументов 2l . Столбцы и строки нумеруются частичными наборами в порядкекода Грея (рис. 1.4а) Также широко используется второй способ нотации карты (1.4b).Черточками обозначены группы клеток, в которых данный аргумент равен 1.

В неохваченныхчерточкой клетках этот аргумент равен 0. Расположение букв-аргументов, в принципе, можетбыть произвольным, но для единообразия всегда будем считать, что x1 - первый (младший)разряд, а x4 - старший разряд.Каждая клетка находится на пересечении столбца и строки соответствует одномуполному набору аргументов (одному из 2l минтермов). Поэтому клеткам присваиваются номерастрок таблицы истинности (рис. 1.5)Рис. 1.5.В клетку записывается 1, если на соответствующем наборе функция у=1. Избыточныеклетки заполняются следующими знаками:х - набор запрещен или никогда не появляется;Ф - функция безразлична к данному набору;φ - условно-безразличное значение.Остальные клетки соответствуют нулевым значениям представляемой функции.Пример.

Недоопределенная функция четырех переменных задана комплексамиединичных значений и избыточных наборов000001010001K '={1100 } x={0010 }100111011110Карта Карно этой функции изображена на рис. 1.6.Рис. 1.6.В простых задачах, когда опасность ошибки исключена, нули можно не записывать, оставляяклетки пустыми.Общие свойства карты Карно.

Соседние клетки отображают соседние минтермыСДНФ. Значит, определенные группы соседних клеток с единицами могут быть подвергнутыоперации склеивания сразу. Такие группы обводятся овалами.Каждая склеиваемая группа клеток с единицами дает одно слагаемое искомой МДНФ,выражаемое только теми аргументами, значениями которых одинаковы для всех клеток даннойгруппы.Число клеток в группе, склеиваемой сразу, всегда равно целой степени двух.Общие правила склеивания.

Во избежание появления избыточных импликант нужно:a) прежде всего склеивать группы, содержащие такие клетки с единицами, которые невходят ни в какую другую группу;b) стремиться к тому, чтобы группа содержала как можно больше клеток с единицами, ачисло групп было как можно меньшим;c) обводить овалами склеиваемые группы так, чтобы каждый новый овал охватывал покрайней мере одну новую (еще не охваченную) клетку с единицей.Примечание. В тех случаях, когда число клеток с единицами превышает половинукарты, удобнее склеивать клетки с нулями, определяя первоначально ¬у, а затем инвертироватьрезультат.Правила образования групп.А.

Пары клеток с единицами.а) Соседними клетками считаются не только две смежные клетки, но и клетки,расположенные на краях одной и той же строки или одного и того же столбца. При наличии вних единиц, они обводятся частями овала (рис. 1.7).y = x1¬x2+¬x1x3.б) Соседние пары огут выбираться в произвольном порядке и каждая клетка можетбыть использована много раз. Однако неоправданные перекрытия овалов могут привестинеминимальной тупиковой ДНФ...Например, нерациональная группировка (рис 1.8а.) дает y=x1¬x2+¬x1x2+x2¬x3+¬x2x3,тогда как рациональная (рис 1.8б) приводит к МДНФ у = x1¬x3+¬x1x2+¬x2x3.Рис.

1.8.Б. Квадраты. Две соседние пары с единицами составляют группу клеток, называемую"квадратом". Соседними парами считаются не только смежные пары, но и пары, расположенныена противоположных краях карты. Оки обводятся частями овала, охватывающего квадрат.Квадрат также образуется четырьмя угловыми клетками с единицами.Например, на карте рис. 1.9 имеется три квадрата. Так, чтоy = ¬x1¬x3+¬x2¬x3+¬x2¬x4.Рис. 1.9.Нужно избегать избыточных квадратов. Например, каждая клетка квадрата (пунктир нарис.

1.10) уже использована в парах, т.е. этот квадрат избыточен.Рис. 1.10.В. Целые строки и столбцы. Если целая строка или целый столбец заполненыединицами, то они склеиваются сразу, давая конъюнкцию только тех аргументов, которыесоставляют номер склеиваемой строки или столбца. В примере на рис. 1.11y = x1x2+x3x4.Рис. 1.11.Г. Соседние четверки. Два соседних неперекрывающихся квадрата или двесоседних целых строки, а также два соседних целых столбца склеиваются сразу. Соседнимитакже считаются строки и столбцы, расположенные на противоположных краях карты.Склеивание долей всей карты.

Если склеиваются сразу клетки всей карты, тополучается константа единица. Если склеивается сразу половина карты, то получается однапеременная. Если склеивается сразу четверть карты, то получаются две переменные и т.д.1.5. Анализ рассуждений. Прямые методы вывода.Этот параграф посвящен вопросам использования классического исчислениявысказываний в рассуждениях, проводимых средствами естественного языка. Решитьлогические проблемы, выраженные в словесной форме, можно было бы только, переведя всефразы в символику исчисления высказываний, а затем использовав теорию и аппарат этогоисчисления применительно к полученным формулам.Пример [2].

Я заплатил бы за работу по ремонту телевизора (3), только если бы он сталработать (Р). Он же не работает. Поэтому я платить не буду.Рассуждение можно записать так:З→Р, ¬Р├¬З.Установим эту формулу, выписывая последовательно формулы, выводимые из З→Р,¬Р, начиная с них самих, до тех пор, пока не наткнемся на ¬3:1.

3→Р,2. ¬Р,3. ¬Р→¬3 (из 1 контрапозицией),4. ¬З (из 2 и 3 по m.p.).Пример. Если бы он ей не сказал ¬С, она ни за что не узнала бы ¬У. А не спроси она его¬В, он не сказал бы ей. Но она узнала. Значит, она его спросила.Символически:¬С→¬У, ¬В→¬С, У├В.Установим, что это рассуждение общезначимо.В самом деле: 1. ¬С→¬У,2. ¬B→¬C,3.

У,4. У→С(контрапозиция из 1),5. С→В (контрапозиция из 2),6. С (m.p.. из 3, 4), 7. В (m.p. из 6, 5).Другой вариант: 4. ¬В¬У (транзитивность импликации и дважды m.p. для 2, 1),5. У→В (контрапозиция 4),6. В (m.p. 3, 5).Заметим, что довод, который зачастую выдается за тривиальное умозаключение в одиншаг ("значит"), не получается ни по какому очевидному логическому принципу.

Можно былобы на такие рассуждения возразить, что не очевидно, откуда следует заключение, и заключениене следует из посылок. Рассмотрим еще один пример.Пример. Он сказал, что придет П, если не будет дождя ¬Д. Но идет дождь. Значит он непридет.Символически: ¬Д→П, Д├¬П.Для того, чтобы переделать это рассуждение в виде ¬Д→П, Д├¬П, используем m.p. Нодля этого посылку надо иметь в виде ¬Д. Если подвергнуть ¬Д→П контрапозиции и упроститьзатем ¬¬Д до Д, то получим ¬П→Д, что опять ничего не дает.Пусть Д и П имеют значение "истина".

Тогда обе посылки принимают истинноезначение, а предлагаемое ¬П принимает значение "ложь". Следовательно, ¬Д→П, Д├П неверно, заключение не самом деле не следует из посылок.Переводя выражения естественного языка с помощью связок, мы лишаемся некоторыхоттенков смысла, но зато выигрываем в точности. Так, известно, что в исчислениивысказываний А^В равносильно В^А. Но фразы "Миша открыл дверь и вошел в комнату" и"Миша вошел в комнату и открыл дверь" имеют совершенно разный смысл. В этом примерепорядок высказываний в конъюнкции наводит на мысль о следовании во времени или опричинно-следственной связи. Следование во времени можно выразить с помощью символизмаисчисления предикатов.Другой пример возможного искажения смысла при изменении порядка следованиявысказываний в логических формулах - использование равносильности двух высказываний:AvB и BvA.

Но фразы "Я не приду, если она не извинится" и "Она не извинится, если я неприду" конечно же имеют разный смысловой оттенок.Другая трудность перевода состоит в двусмысленности определенных терминов, когдаих надо переводить связками. Например, если в меню кафе указано: "Чай или кофе бесплатно",то ничего удивительного в том, что попросив и чай и кофе, мы получим увеличенный счет.Двусмысленностей можно избежать, если при переводе фразы в символьную формувоспользоваться исходной формой, а не равносильной ей. Другое дело, что в процессе выводанеизбежно используются всевозможные равносильные преобразования.Важно в процессе доказательства выводимости формул из аксиом умело использоватьправила, которые следуют из классической логики высказываний.

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

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

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

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