Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Разложение логической функции по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ)

нормальная форма (СДНФ)

Для любой логической функции, отличной от константы, существует представление ее в некотором стандартном виде, который является частным случаем более общего представления - разложения Шеннона.

Введем обозначения: х° = ^х, х1=х. Пусть а - параметр, равный О или 1. Тогда легко проверяется, что ха = 1 ох = а.

Теорема 3.3. Всякая логическая функция /фц,..., хп) представима в следующем виде:

где тДп. а дизъюнкция берется по всем 2т наборам значений оц,... ,аш.

Доказательство. Для доказательства теоремы вычислим значение правой части равенства (3.2) для произвольного набора значений переменных: Xi = <7i, г — 1,2,..., п. Убедимся, что оно совпадает со значением /((71, . . . , (7п). Только для одной из всех 2Ш конъюнкций ... УяД™

в правой части соотношения (3.2) выполняются равенства: ai = <7i, ..., аГп = о‘т- Поскольку ха = 1^>х = а то, только эта конъюнкция равна 1, а все остальные конъюнкции равны 0. В силу тождеств: а V 0 = 0 и аУ1 = а правая часть равенства (3.2) принимает вид:

Равенство (3.2) называется разложением Шеннона или разложением функции по переменным х,...,хт.

Для простоты записи принято опускать знак конъюнкции, т. е. писать ху вместо тУ/у, и отрицание обозначать с помощью черты над переменной, т. е. -iх = х. Далее мы будем использовать эти обозначения. В качестве примера запишем разложение Шеннона для функции /(ад, Х2, Жз, Ха) четырех переменных (п = 4) по переменным ад, ад (ш = 2).

При т = 1 из (3.2) получаем разложение по одной (любой) переменой, которое имеет вид:

Важнейшим частным случаем формулы (3.2) является разложение по всем переменным (?т = п). При этом все переменные в правой части принимают фиксированные значения, и значения функции в конъюнкциях становятся равными 0 или 1, следовательно, остаются только те конъюнкции, в которых функция имеет значение 1. Таким образом, получаем:

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

Исходя из формулы (3.3), можно сформулировать следующий алгоритм построения СДНФ по таблице истинности:

  • 1) выделяем в таблице истинности единичные наборы, т. е. наборы значений переменных, на которых функция принимает значение 1;
  • 2) каждому единичному набору сопоставляем дизъюнктивное слагаемое, т. е. конъюнкцию переменных, причем переменная берется без отрицания, если она в этом наборе имеет значение 1 и с отрицанием, если 0;
  • 3) записываем дизъюнкцию построенных конъюнкций.

П р и м е р 3.8. Представить в совершенной дизъюнктивной нормальной форме (СДНФ) функцию /(од,од,аз), заданную табл. 9.

Таблица 9

Х

х2

х3

f{xux2ix 3)

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

Для построения СДНФ выделяем в таблице единичные наборы, их четыре: (0, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1). Таким образом, СДНФ состоит из четырех дизъюнктивных слагаемых и согласно формуле (3.3) имеет вид:

Из теоремы 3.3 и определения СДНФ легко следует

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

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

Дадим точное определение СДНФ.

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

  • 1) каждое дизъюнктивное слагаемое содержит все п переменных:
  • 2) все дизъюнктивные слагаемые различны;
  • 3) ни одно дизъюнктивное слагаемое не содержит одновременно переменную и отрицание этой переменной;
  • 4) ни одно дизъюнктивное слагаемое не содержит одну и ту же переменную дважды.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>