metod_15.03.04_atppp_moas_2016 (1016590), страница 3
Текст из файла (страница 3)
Например, для формулы А = x y (x y) КНФ А = x (y (x y)) = (x y) (x x y). Так как обе элементарные дизъюнкции содержат все переменные (xи y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкцияx x y содержит переменную х дважды, но x x = x, поэтому КНФ А = (x y) (x y); причем, ни одна из элементарных дизъюнкций не содержитпеременную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x y) (x y).Минимизация булевых функций.
Карты КарноСложность логической функции, как уже было отмечено выше, определяетсясложностью ее аналитической записи. Минимальной формой логической функциина некотором множестве фиксированных операций (базисе) можно считать такую,которая содержит минимальное число суперпозиций функций базиса, допуская искобки. Однако построить эффективный алгоритм такой минимизации с получениемминимальной скобочной формы трудно.Более простой задачей минимизации является нахождение минимальная ДНФфункции.
Для этой задачи существуют простые эффективные алгоритмы. Один изних основан на применении карт Карно.Карта Карно – это двумерная табличная форма представления булевой функции, позволяющая в наглядной графической форме легко отыскать минимальные ДНФлогических функций. Каждой клетке в таблице сопоставляется дизъюнкт СДНФ минимизируемой функции, причем так, что любым осям симметрии таблицы соответствуют зоны, взаимно инверсные по какой-либо переменной. Такое расположениеклеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично.
Например, следующая карта Карно построена для импликации двух переменных х у. В ячейки карты вписываются значения из таблицы истинностифункции, при этом, если перед соответствующей переменной стоит знак отрицания, то в таблице истинности выбирается строка с ложным значением даннойпеременной, иначе – с истинным значением.yyx10x11Все четыре клетки соответствуют всем возможным конъюнкциям СДНФфункции 2 переменных. Единичные значения функции показывают те дизъюнкты, которые присутствуют в СДНФ этой функции.
Расположения элементовв картах Карно функции 2 переменных таково, что в один конъюнкт эта переменная входит без отрицания, а в другой – с отрицанием. Алгоритм поиска минимальной ДНФ по карте Карно основан на выявлении на карте минимального количества максимальных квадратов или прямоугольников со сторонами, равнымистепени двойки, так, чтобы они состояли только из ячеек, содержащих единицы.Для приведенной карты Карно единичные значения покрывают ячейки с координатами х и у, соответственно искомая минимальная ДНФ будет х у.Рассмотрим другую логическую функцию f = p q r q (p r).Знаком обозначается операция сложения по модулю 2 или «исключающееили» (XOR – eXclusive OR), которая определяется следующим образом:хуху000011101110Таблица истинности для данной формулы имеет следующий вид:pqrf00010011010101101000101011011110Карта Карно для функции трех переменных должна содержать, очевидно, 8 ячеек.
Подобную карту можно изобразить следующим образом:qqp0001011p1rrrДля этой карты Карно единичные значения присутствуют в ячейках с координатами q r и q p, соответственно минимальная ДНФ будет q r q p.В силу симметрии карт Карно при построении прямоугольников возможно объединение ячеек, находящихся в крайних позициях, так как приином расположении координат строк или столбцов (переменных без отрицания и с отрицанием) крайние ячейки окажутся внутри карты.
Следующиедве карты Карно эквивалентны (местами поменялись координаты r и r) ина них указано корректное объединение ячеек в прямоугольные области:q001p1001p1rrrppqq01100110qrrrКарты Карно также удобны и для минимизации не полностью определенных функций. Например, пусть объявлена функция, у которой неопределено часть значений:xyzf000-0011010101111000101-1101111-При построении карты Карно для этой функции неопределенные значения можно заменить любыми – 0 или 1. Таким образом, выявляя на картеКарно прямоугольники из единиц, можно использовать ячейки, не содержащие значений.yy1--0111-xxzzzДля данного примера минимальная ДНФ равна y x.Минимизация формулЗадание: из заданных логических выражений получить минимальные дизъюнктивные нормальные формы.1)( A B C ) [( A BC ) B( A C )]2)[ AB ( A C B)] ( A C B C )3)[(AB C) B] (C A B)4)( A B C ) [( A BC ) B( A C )]5)[(AB C) B] (C A B)6)[( BC A) C ] A(C B)7)( B C A) [(C B) A]8)(B C B) (B A C) (BC A)Алгоритмы построения логических формСовершенная дизъюнктивная нормальная форма.
СДНФДизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простыхконъюнкций. Например, выражениеявляется ДНФ.Совершенной дизъюнктивной нормальной формой (СДНФ) называется такаядизъюнктивная нормальная форма, у которой в каждую конъюнкцию входятвсе переменные данного списка (либо сами, либо их отрицания), причем в одноми том же порядке.Например, выражениениеявляется ДНФ, но не СДНФ. Выражеявляется СДНФ.Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот)верны для КНФ и СКНФ. Приведем точные формулировки.Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либоее отрицание).Например, выражение– простая дизъюнкция.Конъюнктивной нормальной формой (КНФ) называется конъюнкция простыхдизъюнкций (например выражение– КНФ)Совершенной конъюнктивной нормальной формой (СКНФ) называется такаяКНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.Например, выражениеявляется СКНФ.Приведем алгоритмы переходов от одной формы к другой.
Естественно, что вконкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующиеконкретный вид данной формы:а) переход от ДНФ к КНФАлгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицаниеДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованиемправила поглощения (или правила Блейка). Отрицание (верхнее) полученнойДНФ (снова по правилу де Моргана) сразу дает нам КНФ:Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;б) переход от КНФ к ДНФЭтот переход осуществляется простым раскрытием скобок (при этом опятьтаки используется правило поглощения)Таким образом, получили ДНФ.ДЛЯ ПЕРЕВОДА ИЗ НОРМАЛЬНОЙ ФОРМЫ В СОВЕРШЕННУЮИСПОЛЬЗУЮТСЯ ВЫРАЖЕНИЯ АЛГЕБРЫ ЛОГИКИ.Полнота системы функций отрицание, конъюнкция и дизъюнкцияИзвестно, что в алгебре логики существует 16 различных функций отдвух переменных.
Все они перечислены в таблице.Константа ложьКонъюнкцияОтрицание импликацииФункция равна первому аргументуОтрицание обратной импликацииФункция равна второму аргументуРазделительная (строгая) дизъюнкция (исключающее ИЛИ, сумма по модулю 2)ДизъюнкцияСтрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ)ЭквивалентностьОтрицание второго аргументаОбратная импликацияОтрицание первого аргументаИмпликацияШтрих Шеффера (отрицание конъюнкции, И-НЕ)Константа истина ()Определение.
Система булевых функций {f1, f2, … ,fn} называется полной, если любую булеву функцию можно выразить через функции f1, f2, … ,fn.Среди функций алгебры логики можно выделить несколько полных систем. Рассмотрим систему хорошо известных вам функций отрицания, конъюнкции и дизъюнкции –– и докажем, что она является полной. Дей-ствительно, для любой булевой функции, кроме тождественного нуля, можнопостроить совершенную дизъюнктивную нормальную форму, а для любойфункции, кроме тождественной единицы, можно построить совершенную конъюнктивную нормальную форму.
Таким образом, любая функция, может бытьвыражена через конъюнкцию, дизъюнкцию и отрицание, а значит, по определению, эта система является полной.Полнота системы функций отрицание и конъюнкцияЛемма. Если система функций {f1, f2, … ,fn } является полной и любая изфункций этой системы может быть выражена через функции g1, g2, … ,gm, тотогда система {g1, g2, … ,gm} также полна.Докажем, что система функций {конъюнкция и отрицание} является полной. Для этого выразим все функции известной нам полной системы {отрицание, конъюнкция и дизъюнкция} через функции системы {отрицание, конъюнкция}.
Если нам это удастся сделать, то на основании выше сформулированнойлеммы, можно утверждать, что система функций {отрицание, конъюнкция} является полной.Введем обозначения:Первые две функции исследуемой системы (отрицание и конъюнкция)совпадают с функциями полной системы.f1 (x1) = g1 (x1), f2 (x1, x2) = g2 (x1, x2).Выразим третью функцию полной системы через исследуемые функции.Для того чтобы выразить дизъюнкцию через отрицание и конъюнкцию, необходимо воспользоваться законом двойного отрицания и законом Де Моргана.Применим к дизъюнкции двойное отрицание, а затем внутреннее отрицание«опустим» по закону де Моргана для дизъюнкции:В получившейся формуле используются только функции отрицание иконъюнкция из исследуемой системы, то есть нам удалось и третью функциювыразить через функции исследуемой системы. Следовательно, эта системафункций {отрицание, конъюнкция} является полной.Заметим, что аналогично можно доказать и полноту системы.Полнота системы, состоящей из одной функцииКак ни удивительным это может показаться, но существуют полные системы, которые состоят только из одной функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
