Дискретная математика

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

1.Определяем множество всех переменных X = {x1, x2, . . . , xn}, входящих в формулу.

2. Определяем порядок выполнения элементарных функций f1, f2, . . . , fm в соответствии с приоритетом выполнения функций алгебры логики.

3.Для каждого набора σe = (σ1, σ2, . . . , σn) Bn вычисляем значение каждой функции f1, f2, . . . , fm, входящей в формулу.

4.Самый правый столбец таблицы соответствует вектору значений функции, заданной исходной формулой.

Решение.

1.Очевидно, что f(xe) - функция трех переменных x1, x2, x3.

2.Определим порядок действий.

5

e 1 4 2 3

f =(x1 → x2) (x1 x3)& x2

Сначала выполняются действия в скобках (→ и ), затем умножение (&), потом логическое сложение ( ). Отрицание выполняется последним, так как инвертируется формула, а не переменная.

3. Разобьём формулу на 5 элементарных функций:

Каждой из этих функций соответствует столбец в таблице истинности:

21

Последний столбец таблицы равен вектору значений заданной функции

fe(x1, x2, x3) = (00001100).

4. Найдем носитель исходной функции, выписывая те наборы, на которых значение функции равно 1 (эти наборы подчеркнуты):

Nf = {(100), (101)}

Пример 2.10. Построить таблицу истинности функции

ge = ((x y) | (z → y)) &(x z) (y z).

Решение.

1. Функция g(xe) также является функцией трех переменных.

22

2. Определим порядок действий.

e

3. Построим таблицу истинности функции g(xe).

4.Получили, что g(xe) = ( 0000 0000 ) . Функция принимает значения "ложь" на всех двоичных наборах. Носитель этой функции не содержит ни одного двоичного набора, то есть является пустым множеством.

Определение 2.9. Функция, принимающая значение "ложь" на всех двоичных наборах, называется тождественно-ложной. Функция, принимающая значение "истина" на всех двоичных наборах, называется тождественно-истинной.

2.3.6Основные эквивалентности (законы) алгебры логики

1.Коммутативность (переместительный закон)

x ◦ y = y ◦ x, где ◦ {&, , , , |, ↓}

2.Ассоциативность (сочетательный закон)

23

(x ◦ y) ◦ z = x ◦ (y ◦ z), где ◦ {&, , , }

3.Дистрибутивность (распределительный закон)

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

x&(y z) = (x&y) (x&z)

(b) дистрибутивность конъюнкции относительно сложения по модулю 2

x&(y z) = (x&y) (x&z)

(c)дистрибутивность дизъюнкции относительно конъюнкции x (y&z) = (x y)&(x z)

4.Законы де Моргана

(a)x&y = x y

(b)x y = x&y

5.Закон двойного отрицания

x = x

6.Законы поглощения

(a)x xy = x

(b)x(x y) = x

7.Идемпотентность

8. Закон противоречия

x&x = 0

9.Закон "исключенного третьего "

x x = 1

10.Свойства констант

24

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

xy xy = y

12.Законы сложениия по модулю два

x x = 0 x x = 1 xy xy = y

Всправедливости этих эквивалентностей можно убедиться путем построения таблиц истинности соответствующих им функций.

Замечание 2.20. Функции алгебры логики (умножение, логическое сложение и сумма по модулю два) иногда похожи на обычные аналогичные арифметические действия, а иногда - нет. Так, например, переместительный и сочетательный законы будут выполняться при замене логических функций на алгебраические. Свойства (а) и (b) распределительного закона также справедливы, а свойство (с) в арифметике не выполняется. Булевы константы "0" и "1" также не являются числами в обычном смысле: для константы "0" выполняются все свойства констант, а для "1" верно только свойство умножения (x · 1 = x).

2.4Задачи для самостоятельного решения

Найти вектор значений следующих функций:

1.fe1 = (x&y) (x → z) ↓ ((y z) | (x z)) ;

2.fe2 = ((x ↓ y) & (y z)) (x z) → (y|z);

3.fe3 = (x y) | (y z) & ((x ↓ z) (y → x)) ;

4.fe4 = (x ↓ y) (y|z) → ((x z) (y · z)) ;

5.fe5 = ((x|y) ↓ (z → x)) (x z) & (y z).

Ответы к задачам для самостоятельного решения

1. fe1 = ( 0000 0110 );

25

2.fe2 = ( 1110 0011 );

3.fe3 = ( 0010 0110 );

4.fe4 = ( 1101 1111 );

5.fe5 = ( 1010 1100 ).

26

Глава 3

Специальные представления булевых функций

3.1Дизъюнктивные и конъюнктивные нормальные формы

27

Определение 3.1. Логическое произведение переменных и их отри-

ющая собой логическую сумму переменных и их отрицаний.

Пример 3.2. Элементарными дизъюнкциями являются:

D1 = x1 x3; D2 = x1 x2 x3; D3 = x1 x2 x3.

Замечание 3.1. В элементарные конъюнкции и дизъюнкции не могут входить одинаковые переменные, а также одновременно переменная и её отрицание. Например, конъюнкции K4 = x1x3x1 и K5 = x1x2x3x1 не относятся к элементарным.

Определение 3.3. Количество переменных и их отрицаний, входящих в элементарную конъюнкцию (элементарную дизъюнкцию) называется её рангом.

Пример 3.3. Вычислим ранг элементарных конъюнкций из примера 3.1:

r1 = 2; r2 = 3; r3 = 3.

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

Пример 3.4. feднф = K1 K2 = x1x3 x1x2x3.

28

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

Пример 3.5. feкнф = D2D3 = (x1 x2 x3)(x1 x2 x3).

Замечание 3.2. Учитывая приоритет выполнения булевых операций (см. пункт 2.3.4 на стр. 20), в ДНФ скобки обычно не пишутся. При записи КНФ скобки писать обязательно, так как иначе в формуле нарушается порядок логических действий.

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

Пример 3.6. r(днф) = r1 + r2 = 2 + 3 = 5 - ранг ДНФ функции из примера 3.4.

r(кнф) = r2 + r3 = 3 + 3 = 6 - ранг КНФ функции из примера 3.5.

Замечание 3.3. Рассмотрим некоторую функцию алгебры логики, заданную в виде ДНФ, и упростим формулу:

fднф(xe) = x1x2 x1x2x3 x2x4 = x1x2(1 x3) x2x4 = x1x2 x2x4.

Так как формула, полученная в результате преобразований, также является ДНФ исходной функции, то представление булевой функции в виде ДНФ , вообще говоря, не единственно. При этом ранг исходной ДНФ равен 7, а упрощенной - 4.

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

29

3.2Совершенная дизъюнктивная нормальная форма

Теорема 3.1. О разложении булевой функции по одной переменной Всякую функцию алгебры логики f(x1, x2, . . . , xn) при любом m (1 6 m 6 n) можно представить в виде

f(x1, . . . , xm−1, xm, xm+1, . . . , xn) =

=xmf(x1, . . . , xm−1, 0, xm+1, . . . , xn)

xmf(x1, . . . , xm−1, 1, xm+1, . . . , xn). (3.1)

Это равенство называется разложением функции по переменной xm, а функции f(x1, . . . , xm−1, 0, xm+1, . . . , xn) и f(x1, . . . , xm−1, 1, xm+1, . . . , xn) - компонентами разложения.

Доказательство. Рассмотрим произвольный набор переменных (α1, α2, . . . , αn) Bn. Покажем, что при подстановке данного набора в правую и левую части соотношения (3.1), обе части равенства принимают одно и то же значение.

αm может принимать 2 значения: 0 или 1. Рассмотрим оба варианта.

αm = 0 αm = 1

αm · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

αm · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=0 · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

0 · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=1 · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

0 · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=f(α1, . . . , αm−1, 0, αm+1, . . . , αn) =

=f(α1, . . . , αm−1, αm, αm+1, . . . , αn).

30