Математика для гуманитарных, экологических и экономико-юридических специальностей. Часть 1

132

4.12. Нанесение функций на карту Вейча

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

f = ABC + ABC + AB C + ABC.

Переведем минтермы в их номера: f = (2, 3, 4, 7).

Воспользуемся картой, изображенной на рис. 4.4. В ее клетках

ëданного выражения f = (2, 3, 4, 7).

то минтерма m2 = ABC. Поскольку он входит в заданную функцию,

то в этой клетке и поставлена единица. То же самое относится и ко всем остальным единицам карты.

Одно из достоинств карты Вейча состоит в том, что на нее нетрудно нанести функцию, представленную не только в СДНФ, но и в виде дизъюнкции конъюнкций, не являющейся СДНФ. Покажем это на примере следующей функции:

f = AB + AC + ABC.

Эта функция зависит от трех аргументов. Соответствующая карта Вейча приведена на рис. 4.9. Первая конъюнкция, входящая в функ-

Находим область на карте, являющуюся

общей для зон Ä è C. Это две клетки, расположенные вертикально.

Они на рис. 4.9 также обведены. Наконец, наносим на карту конъюнкцию ABC. Она на карте занимает единственную клетку на пересечении зон A, B è C. Заметим, что эта конъюнкция является минтермом m5 = ABC.

133

Мы рассмотрели случай, когда каждая конъюнкция занимает на карте области, не пересекающиеся с другими. Рассмотрим другой пример. Нанесем на карту функцию f = A + BC .

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

единице, так как f = 1 + 1× 1 = 1. Следовательно, если в клетке уже

стоит единица, то вторую единицу ставить нет необходимости.

Упражнения

1. Нанесите функцию на карту Вейча четырех аргументов, записывая в клетках не более чем по одной единице. Определите число клеток, занятых единицами:

2. Сколько пустых клеток останется на карте Вейча четырех аргументов, если на нее нанести функцию:

3. (НШК)! Сколько клеток займет функция f = AB, åñëè åå íàíå-

сти на карту трех аргументов; четырех аргументов; пяти аргументов; шести аргументов?

4.13. Нахождение СДНФ при помощи карт Вейча

Пусть дана функция f = A + BC. Чтобы найти ее СДНФ, достаточ-

но функцию нанести на карту Вейча (см. рис. 4.10).

Если карту с нанесенной на нее функцией мысленно совместить с картой, где записаны номера минтермов (см. рис. 4.4), то единицы покажут номера минтермов, образующих данную функцию: f = (3, 4, 5, 6, 7).

135

4.14. Алгебраическое упрощение булевых функций

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

Выясним, что понимается под числом вхождений аргументов и чем оно отличается от числа аргументов. Рассмотрим пример: f = AB + A CD. Эта функция зависит от четырех аргументов A, B, C, D, но имеет пять вхождений аргументов, то есть число вхождений

аргументов — это общее число букв, образующих функцию.

Как уже упоминалось, минимизация основана на теоремах поглощения и склеивания. Проиллюстрируем их применение на примере функции вида f = ABC + ABC + AC + BC.

К первым двум конъюнкциям применима теорема склеивания:

ABC + ABC = AB (C + C) = AB.

В результате получилось выражение f = AB + AC + BC. Запишем конъюнкцию AC â âèäå AC = ABC + ABC.

Подставим это выражение в заданную функцию:

f= AB + AC + BC = AB + ABC + ABC + BC.

Êпервым двум и к двум последним конъюнкциям применима теорема поглощения:

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

В результате получаем искомую минимальную ДНФ заданной функции:

f = AB + BC.

4.15. Метод Квайна

Суть метода Квайна поясним на примере функции

f = ABD + ABC + BCD + ABCD + ABCD.

Сначала функцию представляем в СДНФ:

f = (3, 5, 6, 7, 8, 11, 13, 15).

Затем берем какую-либо пару минтермов и выясняем, применима ли к ним теорема склеивания. Если применима, то их общую часть записываем в отдельную строку. Например:

m3 + m7 = ABCD + ABCD = ACD.

136

Общей частью является конъюнкция ACD . Берем другую пару,

например

m3 + m11 = ABCD + ABCD = BCD.

Эту конъюнкцию записываем рядом с первой. Так поступаем по отношению к каждой паре минтермов. Если какая-либо конъюнкция повторяется, то оставляем только одну. Минтермы, к которым применялась теорема склеивания, вычеркиваем, а оставшиеся (не вы- черкнутые) минтермы и все выписанные конъюнкции объединяем знаками дизъюнкции. В данном случае оказалось, что минтерм m11

не склеивается ни с одним из минтермов заданной функции, а в результате склеивания остальных получилось 8 различных произведений по три переменных каждое. Очевидно, что получившееся выражение тождественно равно заданной функции:

f= ABD+ BCD+ ABD+ ABC + ACD+ ACD+ BCD+ BCD+ ABCD.

Êэтому выражению снова применяем тот же прием, то есть для каждой пары конъюнкций выясняем, применима ли к ним теорема склеивания. Если применима, то общую часть записываем в отдельную строку. Новое выражение заданной функции имеет вид

f = ABCD + BD + CD +ABC.

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

4.16. Минимизация булевых функций при помощи карт Вейча

Сокращенная форма булевой функции не всегда является минимальной. Поэтому для нахождения минимальных форм обычно применяют метод Петрика, при помощи которого можно найти все тупиковые формы, то есть формы, не содержащие лишних простых импликант. Тупиковые формы могут отличаться одна от другой числом вхождений аргументов. Тупиковая форма, содержащая наименьшее число вхождений аргументов, называется минимальной. Таким образом, найдя все тупиковые формы, мы найдем и все минимальные. Подробности о методах Квайна и Петрика, о сокращенных и тупиковых формах можно найти, например, в [32]. Здесь мы их рассматривать не будем, а сразу перейдем к картам Вейча.

При помощи карт Вейча упрощение булевых функций выполняется гораздо легче и быстрее по сравнению с методом Квайна, особен-

138

поиск простых импликант с одного из минтермов m10, m11, m14, m15,

каждый из которых входит в две простые импликанты, то минимальную форму можно не получить. Это произойдет в том случае, если в искомое выражение включить простую импликанту ÀÑ.

Упражнение

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

1)(985) f = (1,2,3,5,6,7,10,11,13,14,15);

2)(905) f = (0,1,2,3, 4,5,6,7,9,11,13,14,15);

3)(ÌÒÌ) f = (6,8,9,10,15);

4)(365) f = (0,1,3,7,9,10,11,13);

5)(ÖÊ5) f = (0,3,4,5,6,7,13,14);

6)(ÏÄË) f = (0,1, 4,5,7,8,9,11,12,13);

7)(432) f = (0,1,7,10,13,14);

8)(ÔÓ1) f = (0,2,3,4,5,6,7,11,15);

9)(343) f = (0,1,2, 4,5,6,9,13);

10)(ÃÏ3) f = (4,7,9,10,12,13,14,15);

11)(ÂËÎ) f = (0,2,3,5,6,7,11,14);

12)(ÑÊÊ) f = (2,3,5,7,9,11,14,15);

13)(926) f = (0,1, 4,5,10,11,13,15);

14)(ÅÄ2) f = (2,3, 4,6,7,9,12,13);

15)(32Ì) f = (2,3,5,6,7,8,9,13);

16)(38Ô) f = (1,2,3,6,9,11,12,14);

17)(ÝÌÈ) f = (0,2,3,4,6,7,13,15);

18)(ÑËÎ) f = (0,3,8,9,10,11,13,14).

4.17. Конъюнктивные формы булевых функций

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

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

Сначала находим СДНФ инверсии заданной функции. В f войдут все

139

минтермы, отсутствующие в f, и ни один минтерм не войдет одновременно в f è f . Затем записываем аналитическое выражение для f и результат инвертируем по теореме де Моргана. Рассмотрим пример. Пусть дана функция f(A, B,C) = (0, 1, 2, 4, 5). В эту функцию

не входят минтермы с номерами 3, 6, 7. Следовательно, они войдут в инверсию функции f : f = (3, 6, 7).

Представим f â âèäå f = ABC + ABC + ABC. Инвертируем по те-

ореме де Моргана: f = (A + B + C)(A + B + C)(A + B + C). Это и есть искомая СКНФ заданной функции f.

Нахождение минимальных КНФ. Чтобы найти минимальную КНФ, действуем следующим образом:

а) на основе заданной функции находим СДНФ ее инверсии; б) для инверсии заданной функции методом Квайна находим со-

кращенную ДНФ, а методом Петрика находим все тупиковые ДНФ, среди которых отыскиваем все минимальные формы. По карте Вейча можно сразу найти минимальную ДНФ;

г) результат инвертируем по теореме де Моргана.

Рассмотрим пример. Пусть требуется найти минимальную КНФ функции

f = AC D + A BCD + ABD + ABCD.

Допустим, что эта функция зависит от четырех аргументов, тогда ее СДНФ представится в виде f = (3, 4, 6, 8,12,14). Находим СДНФ ее

инверсии:

f = (0, 1, 2, 5, 7, 9, 10, 11, 13, 15).

После минимизации получаем минимальную ДНФ функции f :

f= BD + AD + BCD + ABC.

Âрезультате инвертирования по теореме де Моргана этого выражения получаем искомую минимальную КНФ:

f = (B + D)(A + D)(B + C + D) (A + B + C) .

Упражнения 1. Сколько вхождений аргументов в СКНФ следующих функций

2. Сколько вхождений инверсных аргументов в СКНФ следующих функций, зависящих от трех аргументов:

140

3. Даны минимальные ДНФ. Найдите минимальные КНФ. Определите число вхождений аргументов и число инверсий:

(ÎÉÌ) f = AB + AC + A B C + BCD.

4.Заданную КНФ функции представьте в минимальной ДНФ.

Âустройство введите общее число вхождений аргументов минимальной ДНФ, число простых импликант и число инверсий:

(031) f = (A + B + C)(A + B + C)(B + C + D); (732) f = (B + C + D)(A + B + C)(A + B + C); (ÀÍ3) f = (B + C)(C + D)(A + B + D).

5. Заданную КНФ представьте в СДНФ. В устройство введите номера минтермов в порядке возрастания:

(ÐÊ4) f = (A + B)(A + B)(C + D)(C + D); (145) f = (A + B + C)(A + C + D)(B + C + D);

(396)f = A(B + C)(B + C)(B + C + D)(B + C + D).

4.18.Две задачи на применение булевой алгебры

Задача о расписании занятий. Составляется расписание на один день (пять уроков). Преподаватели подали заявки: историк изъявил желание вести 1-й урок, либо 4-й, либо 5-й; литератор — 1-й либо 2-й; физик — 2-й либо 3-й; математик — 2-й либо 5-й; химик — когда угодно, но не первый и не последний. Требуется найти все варианты расписания, удовлетворяющие поданным заявкам.

Введем обозначения: И — историк, Л — литератор, Ф — физик, М — математик, Х — химик. Согласно поданным заявкам составля-

ем формулы:

ϕ1 = È1 + È4 + È5; ϕ2 = Ë1 + Ë2; ϕ3 = Ô2 + Ô3; ϕ4 = Ì2 + Ì5; ϕ5 = Õ2 + Õ3 + Õ4.

Здесь цифры обозначают номера уроков, например: И1 обознача- ет высказывание «историк ведет первый урок», Ф2 — «физик ведет второй урок» и т.д.; ϕ1 обозначает сложное высказывание «историк ведет либо первый урок, либо четвертый, либо пятый», то есть ϕ1 — это заявка историка. Аналогично: ϕ2 — заявка литератора, ϕ3 — заявка физика, ϕ4 — заявка математика, ϕ5 — заявка химика. Все

заявки будут удовлетворены, если выполнится условие