ЛМвИИ (1086253), страница 6
Текст из файла (страница 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.
Но фразы "Я не приду, если она не извинится" и "Она не извинится, если я неприду" конечно же имеют разный смысловой оттенок.Другая трудность перевода состоит в двусмысленности определенных терминов, когдаих надо переводить связками. Например, если в меню кафе указано: "Чай или кофе бесплатно",то ничего удивительного в том, что попросив и чай и кофе, мы получим увеличенный счет.Двусмысленностей можно избежать, если при переводе фразы в символьную формувоспользоваться исходной формой, а не равносильной ей. Другое дело, что в процессе выводанеизбежно используются всевозможные равносильные преобразования.Важно в процессе доказательства выводимости формул из аксиом умело использоватьправила, которые следуют из классической логики высказываний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
