Логические формулы и их преобразования

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

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

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

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

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

XI /Ч X 2 •

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

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

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

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

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

Рп = (*| дх2 лх3)у(х, лх2 лх3)у(Х| лх2 лх3)у(х, лх2 лх3).

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

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

применяя

X,

*2

х3

рт

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

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

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

= (х, vx2 vx3)л(x1 ух2 ух3).

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

ТО

2’

валентную

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

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

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

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

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

х, л(х2 лх3) - (х, лх2) лх3; (х, vx2)vx3 = х, v(x2 vx3);

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

х, лх2 - х2 лх,; хІ 2 - х2 VI,;

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

х, л(х2 ух3) = (і| лі2)у(і| лх3);

X; V(х2 лх3) = (х, ух2)л(х, ух3);

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

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

Х[

ь

хх Л *2

Х{ А %

*1

X,

х1 V Х2

0

0

0

1

1

1

1

0

1

0

1

1

0

1

1

0

0

1

0

1

1

1

1

1

0

0

0

0

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

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

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

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

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

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

= (хл?)у(1лД

  • г) х V (х л у) - х V у;
  • д) X, V /(х,, х2,х„) = хх v/(0, х2,х„).

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

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

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

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

V (х, лх3) у(х2 лх3), что не трудно проверить по таблице (рис. 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;

XZ vxy = yz v XZ V xy.

Таким образом, дизъюнкция левых частей соотношений совпадает с функцией F{x, у, z)- К левым частям применим операцию полного склеивания 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.

 
< Пред   СОДЕРЖАНИЕ     След >