Файл: Дискретная математика.pdf

4.3 Аналитическое представление булевых функций

71

2. Закон склеивания

xy ∨ xy

= x.

3. Закон обобщённого склеивания

xz ∨ yz ∨ xy

= xz ∨ yz.

Доказательство: применим склеивание в обратную сторону (расщепление)
и поглощение:

xz ∨ yz ∨ xy

= xz ∨ yz ∨ xyz ∨ xyz = xz ∨ yz.

4. Закон Порецкого

x ∨ xy

= x ∨ y.

Доказательство:

x ∨ xy

= xy ∨ xy ∨ xy = xy ∨ xy ∨ xy ∨ xy = x ∨ y.

Приведение булевых функций к дизъюнктивной нормальной форме (ДНФ)

и к совершенной дизъюнктивной нормальной форме (СДНФ).

Элементарными конъюнкциями называются конъюнкции переменных или их

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

ДНФ называется формула, имеющая вид дизъюнкции элементарных конъюнк-

ций (ДНФ функции может быть не единственной).

Приведение к ДНФ.

1. С помощью двойного отрицания

(x = x) и правил де Моргана все отрица-

ния «спускаются» до переменных.

2. Раскрываются скобки (применяя свойства): а) xx

= x; б) x ∨ x = x (идемпо-

тентность); в) xx

= 0 (закон противоречия) и г) x∨x = 1 (закон исключённого

третьего).

3. Удаляются лишние конъюнкции и повторения переменных.

4. Удаляются константы (применяя свойства констант).

. . . . . . . . . . . . . . . . . . . . . .

Пример 4.7

. . . . . . . . . . . . . . . . . . . . .

Привести к ДНФ выражение xy ∨ x

(y ∨ xz)(x(y ∨ z) ∨ yz).

Решение:
1) преобразуем выражение

((x(y ∨ z) ∨ yz));

x

(y ∨ z) ∨ yz = (x(y ∨ z)) ⋅ y z = (x ∨ (y ∨ z)) ⋅ (y ∨ z) = (x ∨ y ⋅ z)(y ∨ z) = (x y ∨ x z ∨

∨

yy z ∨ yz

) = (x y ∨ x z ∨ yz);

2) подставим полученное выражение в исходное и продолжим преобразования:
xy ∨

(xy ∨ xxz)(x y ∨ x z ∨ yz) = xy ∨ xy(x y ∨ x z ∨ yz) = xy ∨ xyy ∨ xyz ∨ xyz = xy ∨ xyz =

= y

(x ∨ x z) = y(x ∨ xz ∨ xz) = yx ∨ yz.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

Глава 4. Переключательные функции

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

содержат не все переменные

(xy = xyz ∨ xyz), например: xy ∨ xyz = xyz ∨ xyz ∨ xyz.

4.3.1 Булева алгебра функций и эквивалентные
преобразования в ней

Все эквивалентные преобразования в булевой алгебре проводятся с помощью

основных эквивалентных соотношений (законов):

1) ассоциативность;

2) коммутативность;

3) дистрибутивность:

а) относительно дизъюнкции;

б) относительно конъюнкции;

4) идемпотентность x ⋅ x

= x; x ∨ x = x;

5) закон двойного отрицания x

= x;

6) свойства констант 0 и 1:

а) x ⋅ 1

= x; б) x ∨ 1 = 1; в) 0 = 1;

б) x ⋅ 0

= 0; д) x ∨ 0 = x; е) 1 = 0;

7) правила де Моргана

а) x

1

x

2

= x

1

∨

x

2

;

б) x

1

∨

x

2

= x

1

⋅

x

2

;

8) закон противоречия x ⋅ x

= 0;

9) закон исключённого третьего x ∨ x

= 1.

Данные эквивалентные соотношения отличаются тем, что:

1) они не выводимы друг из друга — убедиться в их справедливости можно,

используя стандартный метод доказательства эквивалентности формул, т. е.
построение таблиц истинности;

2) этих соотношений достаточно для выполнения любых эквивалентных пре-

образований логических формул.

Упрощение формул.
Наряду с основными соотношениями для упрощения формул также исполь-

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

• поглощение

а) x ∨ xy

= x; б) x

(x ∨ y) = x;

• склеивание

xy ∨ xy

= x;

4.3 Аналитическое представление булевых функций

73

• обобщённое склеивание

xz ∨ yz ∨ xy

= xz ∨ yz;

x ∨ xy

= x ∨ y.

Правила приведения к ДНФ.
Элементарная конъюнкция — это конъюнкция переменных или их отрицаний,

в которой каждая переменная встречается не более одного раза.

Примеры ДНФ.

1) yz ∨ xy ∨ xz ∨ xy z;

2) yz ∨ xy ∨ xz ∨ xyz.

Все процедуры приведения к ДНФ основаны на законах булевой алгебры и сво-

дятся к следующему:

1) все отрицания «спустить» до переменных;

2) раскрыть скобки с помощью основных эквивалентных преобразований;

3) удалить лишние конъюнкции и повторения переменных в конъюнкциях

с помощью основных законов булевой алгебры (идемпотентность, проти-
воречия, исключённого третьего);

4) удалить константы, применяя закон «свойства констант 0 и 1».

Процедура приведения к КНФ.
Элементарной дизъюнкцией называется дизъюнкция переменных или их отри-

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

КНФ называется конъюнкция элементарных дизъюнкций.
Пример булевой функции, заданной в КНФ:

(x ∨ y)(x ∨ z)(x ∨ y ∨ z).

Процедура приведения булевой функции от ДНФ к КНФ:

1. Применить к формуле правило двойного отрицания:

F

= K

1

∨

K

2

∨

. . . ∨ K

m

и привести K

1

∨

K

2

∨

. . . ∨ K

m

к ДНФ K

′

1

∨

K

′

2

∨

. . . ∨ K

′

p

,

где K

′

1

∨

K

′

2

∨

. . .∨K

′

p

— элементарные конъюнкции. Тогда: F

= K

1

∨

K

2

∨

. . .∨K

m

=

= K

1

∨

K

2

∨

. . . ∨ K

m

= K

′

1

∨

K

′

2

∨

. . . ∨ K

′

p

.

2. С помощью правил де Моргана освободиться от второго отрицания и пре-

образовать отрицания элементарных конъюнкций в элементарные дизъ-
юнкции D

1

, D

2

, . . ., D

p

. Тогда

F

= K

′

1

∨

K

′

2

∨

. . . ∨ K

′

p

= K

1

⋅

K

2

⋅

. . . ⋅ K

p

= D

1

D

2

. . .D

p

.

4.3.2 Представление переключательных функций в виде
многочленов

Конституентой «1» называется переключательная функция n аргументов, кото-

рая принимает значение «1» только на одном наборе аргументов. Число различных
конституент «1» среди функций n аргументов равно 2

n

. Так, для n

= 2 это f

1

, f

2

, f

4

и f

8

.

74

Глава 4. Переключательные функции

Обычно конституенты «1» выражают через произведение всех аргументов,

каждый из которых входит в произведение либо x

i

, либо x

i

.

Теорема Жегалкина.
Любая переключательная функция может быть представлена в виде полинома

f

(x

1

, x

2

, . . ., x

n

) = a

0

⊕

a

1

x

1

⊕

a

2

x

2

⊕

. . . ⊕ a

n

x

n

+

. . . + a

n

+1

x

1

x

2

+

. . . + a

n

x

1

x

2

. . .x

n

, (4.4)

где a

0

, a

1

, . . ., a

n

— некоторые константы, равные «0» или «1». Знак ⊕ означает опе-

рацию сложения по модулю 2:

• x ⊕ 0

= x;

• x ⊕ 1

= x;

• x ⊕ x

= 0 (если чётное число переменных);

• x ⊕ x ⊕ x

= x (если нечётное число переменных);

• x ⊕ y

= y ⊕ x;

x ∨ y

= x y =

(x ⊕ 1)(y ⊕ 1) ⊕ 1 = xy ⊕ x ⊕ y.

При записи конкретной функции коэффициенты a

0

, a

1

, . . ., a

n

выпадают, так как

члены, при которых a

i

= 0, можно опустить, а коэффициенты, равные 1, — не писать.

Доказательство. Пусть задана произвольная переключательная функция f

(x

1

,

x

2

, . . ., x

n

), равная «1» на некоторых наборах с номерами m

1

, m

2

, . . ., m

p

. Очевидно,

что f

(x

1

, x

2

, . . ., x

n

) можно записать:

f

(x

1

, x

2

, . . ., x

n

) = K

m

1

+

K

m

2

+

. . . + K

m

p

= 1,

(4.5)

где K

m

i

— конституента «1».

Так, для набора с номером m

i

получаем

K

m

1

+

K

m

2

+

. . . + K

m

i

+

. . . + K

m

p

= 0 + 0 + . . . + 1 + . . . + 0 = 1.

От формулы (4.5) легко перейти к формуле (4.6), если представить K

m

i

в виде

произведений и заменить все переменные с отрицаниями, используя соотношения
x

= x ⊕ 1 (так как отрицания не входят в (4.4)).

Пусть K

i

= x

1

x

2

x

3

x

4

. Получим K

i

=

(x

1

⊕

1

)x

2

x

3

(x

4

⊕

1

). Далее, используя соот-

ношения для конъюнкции:

⎧⎪⎪⎪⎪

⎪⎪⎪⎪⎪

⎪⎪⎪⎪⎪

⎪⎪

⎨⎪⎪⎪

⎪⎪⎪⎪⎪

⎪⎪⎪⎪⎪

⎪⎪⎪⎩

x ⋅ 0

= 0;

x ⋅ 1

= x;

x ⋅ x

= x;

x ⋅ x ⋅ . . . ⋅ x

= x;

xy

= yx;

xx

= 0;

x

(y + z) = xy + xz − дистрибутивность,

(4.6)

и приводя подобные члены в соответствии с соотношениями (4.6)–(4.7):

x ⊕ x ⊕ . . . ⊕ x

´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

n

=

⎧⎪⎪

⎨⎪⎪

⎩

0,

при n четном,

1,

при n нечетном.

(4.7)

4.4 Функционально полные системы

75

. . . . . . . . . . . . . . . . . . . . . .

Пример 4.8

. . . . . . . . . . . . . . . . . . . . .

Представить в виде полинома Жегалкина функцию f

14

(x,y).

f

14

= x y ∨ xy ∨ xy.

Решение:
f

14

= K

0

⊕

K

1

⊕

K

2

= x y ⊕ xy ⊕ xy =

(x ⊕ 1)(y ⊕ 1) ⊕ (x + 1)y ⊕ x(y + 1) = 1 ⊕ x ⊕ x ⊕

⊕

y ⊕ y ⊕ xy ⊕ xy ⊕ xy

= 1 ⊕ xy.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Функционально полные системы

Система функций

∑ называется функционально полной системой, если лю-

бая логическая функция может быть представлена формулой над

∑, т. е. являться

суперпозицией функций из

∑.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

Действительно, для всякой логической функции, кроме константы «0», таким

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

Константу «0» также можно представить булевой формулой xx.
Из теоремы следует, что система

∑ = {&, ∨, ¬} является функционально полной:

f

(x

1

, x

2

, . . ., x

n

) = K

j1

∨

K

j2

∨

. . . ∨ K

jm

,

где K

ji

— это наборы переменных, где функция принимает значение «1». СДНФ

функции f представляет собой разложение функции по всем n переменным.

Согласно принципу двойственности, справедливому в алгебре Буля, имеем сле-

дующий вывод: любая булева функция f

(x

1

, x

2

, . . ., x

n

) может быть представлена

в виде конъюнкции дизъюнкций её аргументов на тех наборах их значений, на
которых f

(x

1

, x

2

, . . ., x

n

) принимает значение «0». Таким представлением булевой

функции служит совершенная конъюнктивная нормальная форма (СКНФ).

Представление булевых функций двух аргументов в формах СДНФ и СКНФ

приведены в таблице 4.4.