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

76

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

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

и СКНФ

x

0

0

1

1

СДНФ

СКНФ

y

0

1

0

1

f

0

(x,y) 0 0 0 0

не имеет

(x ∨ y)(x ∨ y)(x ∨ y) ⋅ (x ∨ y)

f

1

(x,y) 0 0 0 1

xy

(x ∨ y)(x ∨ y)(x ∨ y)

f

2

(x,y) 0 0 1 0

x ⋅ y

(x ∨ y)(x ∨ y)(x ∨ y)

f

3

(x,y) 0 0 1 1

x ⋅ y ∨ xy

(x ∨ y)(x ∨ y)

f

4

(x,y) 0 1 0 0

xy

(x ∨ y)(x ∨ y)(x ∨ y)

f

5

(x,y) 0 1 0 1

xy ∨ xy

(x ∨ y)(x ∨ y)

f

6

(x,y) 0 1 1 0

xy ∨ xy

(x ∨ y)(x ∨ y)

f

7

(x,y) 0 1 1 1

xy ∨ xy ∨ xy

x ∨ y

f

8

(x,y) 1 0 0 0

x ⋅ y

(x ∨ y)(x ∨ y)(x ∨ y)

f

9

(x,y) 1 0 0 1

x ⋅ y ∨ xy

(x ∨ y)(x ∨ y)

f

10

(x,y) 1 0 1 0

x ⋅ y ∨ xy

(x ∨ y)(x ∨ y)

f

11

(x,y) 1 0 1 1

x ⋅ y ∨ xy ∨ xy

(x ∨ y)

f

12

(x,y) 1 1 0 0

x ⋅ y ∨ xy

(x ∨ y)(x ∨ y)

f

13

(x,y) 1 1 0 1

x ⋅ y ∨ xy ∨ xy

x ∨ y

f

14

(x,y) 1 1 1 0

x ⋅ y ∨ xy ∨ xy

x ∨ y

f

15

(x,y) 1 1 1 1 x ⋅ y ∨ xy ∨ xy ∨ xy

не имеет

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

Пример 4.9

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

Пример приведения логической функции к форме СДНФ

Логическую функцию f

(x

1

, x

2

, x

3

) = (x

1

∼ ¬x

2

) → ((x

1

∨

x

3

) & x

2

) представить

булевой формулой — в виде СДНФ.

Решение:

1. Функция f

(x

1

, x

2

, x

3

) задана не булевой формой.

2. По исходной формуле восстановим её таблицу истинности.

3. По таблице истинности составим СДНФ заданной функции:

f

(x

1

x

2

x

3

) = x

1

x

2

x

3

∨

x

1

x

2

x

3

∨

x

1

x

2

x

3

∨

x

1

x

2

x

3

∨

x

1

x

2

x

3

.

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

4.5 Минимизация булевых функций

Под минимизацией (упрощением) БФ понимаются такие тождественные пре-

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

В пределе эти преобразования дают минимальную форму.

4.5 Минимизация булевых функций

77

Под вхождением аргументов понимается суммарное число аргументов, входя-

щих в данную формулу, вместе с их повторами.

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

Пример 4.10

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

Дана функция: f

= ABC + ABC + BC + AC.

Функция f зависит от трёх аргументов, но имеет десять вхождений аргу-

ментов.

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

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

Алгебраический метод упрощения булевых функций основан на эквивалент-

ных преобразованиях булевых (логических) функций.

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

Пример 4.11

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

Пример применения метода упрощения булевых функций

f

(x,y,z) = xy ∨ x(y ∨ xz)(x(y ∨ z) ∨ yz) =

= xy ∨

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

= xy ∨ xy

(x ∨ yz) ⋅ (y ∨ z) = xy ∨ xy(x y ∨ xz ∨ yy z ∨ yz z) =

= xy ∨ xy

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

= y

(x ∨ z) = xy ∨ yz.

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

Эквивалентные преобразования логических функций.
Основные эквивалентные соотношения (законы) в булевой алгебре:

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

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

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

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

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

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

= x; x ∨ x = x;

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

= x;

6) закон действия с константами 0 и 1:

а) x ⋅ 1

= x;

б) x ∨ 1

= 1;

78

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

в) 0

= 1; 1 = 0;

г) x ⋅ 0

= 0;

д) x ∨ 0

= x;

е) x ∨ x

= 1; x & x = 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 ∨ y;

• Закон поглощения: а) x ∨ x

= x; б) x

(x ∨ y) = x;

• Правило «склеивания»: xy ∨ xy

= x;

• Обобщённое склеивание: xz ∨ yz ∨ xy

= xz ∨ yz.

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

Пример 4.12

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

Пример упрощения формул с помощью эквивалентных соотношений

f

= A + AB + BC + AC = A

(1 + C) + AB + BC = A + AB + BC.

Число вхождений переменных уменьшилось до пяти.
Можно продолжить упрощение, применяя «вторую» группу эквивалентных со-

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

f

= A + AB + BC = A ⋅ 1 + AB + BC = A ⋅

(B + B) + AB + BC =

= A ⋅ B + A ⋅ B + A ⋅ B + B ⋅ C + AB = B + A + B ⋅ C = A + B

(1 + C) = A + B.

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

Рассмотренный способ алгебраической минимизации требует большого опыта

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

4.5 Минимизация булевых функций

79

Для минимизации сложных функций есть более эффективный способ нахожде-

ния минимальной формы, не требующий изощрённой изобретательности в приме-
нении эквивалентных преобразований. Это метод Квайна. Основу метода Квайна
составляет теорема «склеивания».

Введём новые определения: минтерм, импликанта, простая импликанта, эле-

ментарное произведение.

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

Пример 4.13

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

Пусть задана функция f четырёх аргументов, принимающая значения «1» на

следующих минтермах:

f

=

(0,1,3,6,7,8,12,13,14,15).

Запишем эти минтермы в алгебраической форме — f

= A B C D+A B CD+A BCD+

+

ABCD + ABCD + AB C D + ABC D + ABCD + ABCD + ABCD.

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

дый минтерм сравниваем со всеми остальными, находящимися правее него, и (если
это возможно) применяем правило «склеивания».

Результат операции склеивания записываем в отдельную строку.
Пронумеруем минтермы (для удобства работы с ними) —

f

=

1

A B C D+

2

A B CD+

3

A BCD+

4

ABCD+

5

ABCD+

6

AB C D+

7

ABC D+

8

ABCD+

9

ABCD+

10

ABCD.

1-й склеивается со 2-м и с 6-м; получаем конъюнкции — A B C; B C D.
2-й склеивается с 3-м; получаем конъюнкцию — A BD.
3-й склеивается с 5-м; получаем конъюнкцию — ACD.
4-й склеивается с 5-м и с 9-м; получаем конъюнкции — ABC; BCD.
5-й склеивается с 10-м; получаем конъюнкцию — BCD.
6-й склеивается с 7-м; получаем конъюнкцию — AC D.
8-й склеивается с 10-м; получаем конъюнкцию — ABD.
9-й склеивается с 10-м; получаем конъюнкцию — ABC.
Запишем результат первого этапа минимизации —

f

= A B C +B C D +A BD +ACD +BCD +ABC +BCD +AC D +ABD +ABC +ABD +ABC.

Второй этап алгоритма.
Сравниваем полученные конъюнкции, аналогично тому, как это делалось на

первом этапе применительно к минтермам, и выписываем результат:

f

= A B C + B CD + A BD + ACD + BC + AB + AC D.

Склеивающихся конъюнкций больше нет. Получена сокращённая нормальная

форма заданной функции f.

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

80

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

Карты Вейча и диаграммы Карно.
Карты Вейча и диаграммы Карно широко применяются для различных преоб-

разований БФ.

Рассмотрим карту Вейча 2-х аргументов (рис. 4.5 и 4.6).

Рис. 4.5 – Карта Вейча с номерами минтермов

Рис. 4.6 – Карта Вейча с аналитической записью минтермов

Вокруг карты размещены переменные. За каждой переменной строго отведена

своя зона, помеченная чертой. Оставшаяся зона по каждой стороне карты закреп-
лена за инверсной переменной.

Карта Вейча 3-х аргументов с указанием минтермов в их аналитической за-

писи приведена на рисунке 4.7.

Рис. 4.7 – Карта Вейча булевых функций 3-x аргументов

Правила минимизации БФ с использованием карт Карно.

1. В карте Карно группы единиц (для получения ДНФ) и группы нулей (для по-

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

2. Количество клеток внутри контура должно быть целой степенью двойки

(1, 2, 4, 8, 16. . .).

3. При проведении контуров крайние строки карты (верхние и нижние, левые

и правые), а также угловые клетки считаются соседними (для карт до 4-х пе-
ременных).

4. Каждый контур должен включать максимально возможное количество кле-

ток. В этом случае он будет соответствовать простой импликанте.