Эквивалентные преобразования дискретная математика

Эквивалентные преобразования — преобразования, использующие эквивалентные соотношения и правило замены.

Два правила замены:

1. Правило подстановки формулы f вместо переменной х. При подстановке формулы f вместо переменной х все вхождения переменной х в исходное соотношение должны быть одновременно заменены формулой f.

2. Правило замены подформул. Если какая-либо формула f, описывающая функцию φ, содержит f₁ в качестве подформулы, то замена f₁ на эквивалентную f₂ (f1= f₂) не изменит функции φ.

Основные эквивалентные соотношения (законы) в булевой алгебре.

Ассоциативность конъюнкции и дизъюнкции:
	(1)

Коммутативность конъюнкции и дизъюнкции:
	(2)

Дистрибутивность конъюнкции относительно дизъюнкции:
	(3)

Дистрибутивность дизъюнкции относительно конъюнкции:
	(4)

Идемпотентность:
	(5)

Закон двойного отрицания:
	(6)

Свойства констант 0 и 1:
	(7)

Правила де Моргана:
	(8)

Закон противоречия:
	(9)

Закон исключенного третьего:
	(10)

Основные эквивалентные соотношения (1) – (10) отличаются тем, что они не выводимы друг из друга и этих соотношений достаточно для выполнения любых эквивалентных преобразований.

Для упрощения формул так же используются следующие эквивалентные соотношения, выводимые из основных с помощью эквивалентных преобразований:

Поглощение:
	(11)

Склеивание:
	(12)

Обобщенное склеивание:
	(13)

(14)

Приведение к дизъюнктивной нормальной форме.

Элементарная конъюнкция — конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Дизъюнктивная нормальная форма (ДНФ) — формула, имеющая вид дизъюнкции элементарных конъюнкций.

Приведении формулы к ДНФ осуществляется в 4 этапа:

1. все отрицания «спустить» до переменных с помощью (6) и (8);

2. раскрыть скобки с помощью (1), (3), (4);

3. удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью (5), (9), (10);

4. удалить константы с помощью (7).

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

Приведение к конъюнктивной нормальной форме.

Элементарная дизъюнкция — дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Конъюнктивная нормальная форма (КНФ) — конъюнкция элементарных дизъюнкций.

Пусть ДНФ F имеет вид F=k₁Úk₂Ú…Úk_m, где k_1,k_2,…,k_m — элементарные конъюнкции. Приведение ДНФ к КНФ состоит из двух шагов:

1. Применить к F правило двойного отрицания и привести к ДНФ k¢₁Ú k¢₂Ú…k¢_p где k¢₁Ú k¢₂Ú…k¢_p — элементарные конъюнкции. Тогда

2. С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции D₁,D₂,…D_p Тогда

Совершенная КНФ (СКНФ) — КНФ, каждая элементарная дизъюнкция которой содержит все переменные.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9138 — | 7301 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Как и в элементарной алгебре, в математической логике на базе элементарных операций можно строить сложные выражения, которые называются формулами. Например, (х, ах₂ )у(х, ах₂), (х₃ vX|)®(X| л(х, ©х₂)) представляют собой формулы.

Для любого набора значений переменных х,, х₂, . х„ значение формулы может быть всегда вычислено. Вычислим, например, формулу (х₃ ух,)@(х₁ л(х, ©х₂)) на наборе х, =1, х₂ = 1, х₃ = 0. Получим: х₃ ух! =1; х, л(х, ®х₂) = х, л0 = 0; 1®0 = 1. Формула, вычисленная для всех 2" наборов значений ее переменных, даст некоторую таблицу истинности, т.е. функцию, заданную на множестве <0, 1>.

Таким образом, для каждой формулы существует единственная функция, представляющая эту формулу. Вместе с тем одна и та же функция может быть представлена различными формулами. Например, функцию «штрих Шеффера» можно представить двумя такими формулами: х, vx₂ их, лх₂, т. е. дизъюнкцией отрицаний х,, х₂ и отрицанием конъюнкции х, и х₂.

Определение 4.5. Формулы, представляющие одну и ту же логическую функцию, называются эквивалентными, или равносильными.

Эквивалентность формул обозначается знаком равенства. По-э тому для бинарной функции Р₁₄ можно записать / г ,₄ =х, vx₂ =

Для определения равносильности двух формул существует ряд методов. Очевидный из них — построение таблиц истинности для всех наборов переменных и сравнение их между собой. Если таблицы истинности совпадают, формулы равносильны. Однако такой способ требует2-2 я вычислений, если считать, что обе формулы зависят от п переменных. Поэтому практически он достаточно трудоемок. В связи с этим для доказательства равносильности двух формул используют их эквивалентные преобразования.

Существует строгое доказательство того, что любая логическая формула путем эквивалентных преобразований может быть представлена набором переменных х,, х₂, . х_п, связанных между собой операциями конъюнкции, дизъюнкции и отрицания. Формула, полученная в результате таких преобразований и содержащая только указанные операции, называется булевой формулой. Такое название она получила в честь американского математика Дж. Буля, который заложил основы алгебры на множествах двоичных наборов переменных.

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

Пусть задана логическая функция п переменных Г(х^ х₂, . х_п) и соответствующая ей таблица истинности. Тогда для получения функции в виде СДНФ каждой единице в таблице истинности необходимо поставить в соответствие конъюнкцию п переменных (конъюнкцию ранга п). При этом в конъюнкцию аргумент х,-, / = 1, 2, . п входит без отрицания, если в соответствующем наборе переменных он принимает значение 1, и с отрицанием, если в этом же наборе его значение равно 0. После этого все полученные конъюнкции ранга п объединяются операцией дизъюнкции. Рассмотрим применение описанных правил для построения СДНФ мажоритарной функции, таблица истинности которой представлена на рис. 4.4.

Эта таблица содержит четыре единицы: в 4-й, 6-й, 7-й и 8-й строках. Следовательно, СДНФ будет включать четыре конъюнкции ранга 3. Первая конъюнкция, соответствующая четвертому набору переменных (4-й строке) х, = 0, х₂ = 1, х₃ =1 такая: х, лх₂ лх₃. Остальные конъюнкции получаем аналогичным путем: х, дх₂ лх₃, х, лх₂ лх₃, х, лх₂ лх₃. Объединяя все конъюнкции рангов 3 операцией дизъюнкции, получим, что СДНФ мажоритарной функции будет иметь такой вид:

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

В качестве примера рассмотрим построение СКНФ для функции, таблица истинности которой представлена на рис. 4.5.

Рис. 4.5. Таблица истинности функции трех переменных

Эта таблица содержит два нуля: во 2-й и 5-й строках. Следовательно, СКНФ будет включать две дизъюнкции. Первая дизъюнкция х, ух₂ vx₃ имеет место для набора х, = 0, х₂ = 0, х₃ = О, вторая дизъюнкция х, ух₂ ух₃ — для набора х, = 1, х₂ =0, х₃ =0. Поэтому СКНФ рассматриваемой функции будет иметь следующий вид: У 7 . =

Пусть функция У 7 , задана формулой Р_х, а функция ?₂ — формулой Р₂. Подстановка Р_х и Р₂ в дизъюнкцию X, V х₂ даст формулу Р_х V Р₂, а подстановка Р_х и Р₂ в конъюнкцию х, дх₂ даст формулу Р_х л Р₂. Если взять формулу Р <,эквивалентную Р_х, т. е. тоже представляющую функцию У 7 ,, и формулу Р₂, экви-

дизъюнкцию и конъюнкцию, получим формулы Уу V Р₂, Уу л Уу, эквивалентные формулам Р V Р₂ , Р_< А Р₂.

Таким образом, дизъюнкцию и конъюнкцию можно рассматривать как бинарные операции на множестве логических функций, которые каждой паре функций У 7 ,, У^, независимо от представляющих их формул, ставят в соответствие функции У, V У₂ и У 7 ! л Р₂. Аналогичным образом можно рассматривать отрицание — как унарную операцию над логическими функциями. Определение 4.6. Алгебра (X, V, д,

которой является все множество логических функций X, а операциями — дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.

Операции булевой алгебры называются булевыми операциями. Они подчиняются следующим законам:

1) ассоциативному (сочетательному) —

2) коммутативному (переместительному) —

3) дистрибутивному (распределительному) —

• 4) идемпотентности — хлх = х;хух = х;
• 5) двойного отрицания — х = х;
• 6) поглощения — хл0 = 0;хл1 =х; хуО = х; х VI = 1;
• 7) противоречия — х л х = 0;
• 8) исключенного третьего — XVх — V,
• 9) силлогизма (дедуктивного заключения) —
• ((х -»у) л (у -» г)) -> (х -> г);
• 10) де Моргана — х, лх₂ = х, vx₂; х, ух₂ = х, лх₂.

Законы легко можно проверить стандартным методом — вычислением обеих частей равенств на всех наборах переменных х,, х₂. В качестве примера проверим правильность первого закона де Моргана. Для этого приведем табличное представление конъюнкции х, дх₂, ее отрицания х, лх₂, т.е. левой части первого равенства де Моргана, а затем вычислим формулу х, vx₂ для всех наборов х,, х₂. Полученные результаты приведены в таблице на рис. 4.6.

Рис. 4.6. Проверка истинности первого правила де Моргана

Применение булевых операций, подчиняющихся приведенным правилам, не зависит от того, каким путем получены значения переменных, т.е. первичны они или вторичны. Поэтому законы остаются справедливыми при подстановке вместо переменных любых формул, представляющих те или иные логические функции. Важно лишь соблюдать следующее правило подстановки. При подстановке вместо переменной х формулы /’в исходном соотношении все переменные должны быть заменены формулой.

Например, соотношение У 7 V У 7 = 1, полученное из хчх = 1, верно, а соотношение У 7 V* = 1, полученное изxvx = 1, ошибочно.

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

При упрощении формул используются следующие соотношения:

• а) поглощения — х V (х а у) = х; х л (х V у) = х;
• б) склеивания — (х л у) V (х л у) = х;
• в) обобщенного склеивания — (1л^)у(1лг)у(1л>’) =

Указанные соотношения легко доказываются при помощи таблиц истинности для всех наборов переменных х, у, а также аналитическим путем. Например, первое соотношение поглощения можно доказать, используя дистрибутивный закон 3) конъюнкции относительно дизъюнкции и свойства констант х л 1 = х; XVI =1. Имеем: ху(хлу) = (хл1)у(хл^) = хл(1 уу) = хл1 =х. Аналогично доказываются другие соотношения.

Определение 4.7. Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Определение 4.8. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.

Таким образом, в отличие от СДНФ дизъюнктивная нормальная форма в конъюнкциях может содержать не все переменные формулы. Например, мажоритарная функция (рис. 4.4) в ДНФ аналитически может быть представлена как Г_т — (х, лх ₂)у

V (х, лх₃) у(х₂ лх₃), что не трудно проверить по таблице (рис. 4.4).

Приведение некоторой формулы к ДНФ выполняется так. Сначала при помощи правила двойного отрицания х = х и правил де Моргана все отрицания переменных преобразуются в переменные. Затем раскрываются скобки, с помощью правил хлх = х, х у х = х, х л х = О, х у х = 1 удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а с помощью правил хл0 = 0 ;хл1 = х;ху0 = х;ху1 =1 удаляются константы.

В качестве примера рассмотрим приведение формулы (х л у) ух л (у ух VI) л (у VI)- Для сокращения письма знак конъюнкции, как это принято, не будем употреблять. Поэтому формула будет иметь вид: ху ух(у ух^)(у у I)- Преобразуем сначала х(уухг). По дистрибутивному закону имеем ху sxxz = ху уО^ = ху. Таким образом, формула будет такой: (ху vxy)(y V По правилу де Моргана дизъюнкцию у V z заменим конъюнкцией у1 = У1• Далее, по дистрибутивному закону получаем хуу1 у хуу1 = ху1 у ху1 = у?,(х у х) = у1—

Определение 4.9. Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Определение 4.10. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.

Приведение некоторой формулы к КНФ выполняется по тем же правилам, что и приведение ее к ДНФ.

Дизъюнктивная и конъюнктивная нормальные формы являются весьма наглядными способами представления булевых функций. Вместе с тем, в программировании для компьютеров очень часто возникает необходимость использовать простейшую формулу представления булевой функции. Проблема построения такой функции получила название задачи минимизации булевых функций.

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

Существует ряд методов минимизации булевых функций: карт Карно для ДНФ и диаграмм Вейча для КНФ, Квайна — Мак — Класки и Порецкого — Блейка. Метод карт Карно и метод диаграммы Вейча являются графическими методами и достаточно сложны в реализации. Они мало пригодны в применении к функциям с количеством переменных больше шести и неприменимы для программной реализации.

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

Метод минимизации Порецкого—Блейка осуществляет минимизацию, используя в качестве исходной формулы произвольную ДНФ булевой функции. Переход от этой ДНФ к минимальной форме осуществляется посредством операций обобщенного склеивания и поглощения. В качестве примера найдем минимальную ДНФ для функции F(x, у, z) = xyz v xz vxy. Операции обобщенного склеивания дают:

xyz v xz = ху v xyz v хг;

xyz vxy = yz vxyz vxy;

Таким образом, дизъюнкция левых частей соотношений совпадает с функцией F К левым частям применим операцию полного склеивания yz v yz = у, xy v xy = у. На этом основании исходная формула примет следующий вид: F(x, у, z) = = xyz Vxz vxy = (xy Vxy) Vxyz Vxz V(yz Vyz) — у Vxyz VXZ vу —= y(xz V 1 )vxz = xzv y.

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком "эквивалентно"

Со знаком "следствие"

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн