Шаг 3. Так как i n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G4, добавляя к графу G3 новое ребро минимальной длины из ребер (x1, x5), (x2, x3), (x2, x5), (x4, x5). Такое ребро длины два одно: (x2, x3). Вместе с этим ребром включаем в G4 вершину x3, не содержащуюся в G3. Полагаем i = 4 и переходим к шагу 3.

Шаг 3. Так как i n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G5, добавляя к графу G3 новое ребро минимальной длины из ребер (x1, x5), (x2, x5), (x4, x5). Таких ребер длины три два: (x2, x5) и (x4, x5). Возьмем (x2, x5). Вместе с этим ребром включаем в G5 вершину x5, не содержащуюся в G4. Полагаем i = 5 и переходим к шагу 3.

Шаг 3. Так как i = n, то граф G5 - искомое минимальное остовное дерево. Суммарная длина ребер равна 1 + 1 + 2 + 3 = 7.

Процесс построения минимального остовного дерева изображен на рис. 3.15.

Рис. 3.15

Контрольные вопросы к теме 3

1. Какое из двух утверждений верно: а) ориентированный граф является частным случаем неориентированного графа; б) неориентированный граф является частным случаем ориентированного графа?

2. Перечислите все возможные способы задания графов.

3. Что характеризует сумма элементов столбца матрицы смежности неориентированного графа?

4. Что характеризует сумма элементов строки матрицы смежности неориентированного графа?

5. Что характеризует сумма элементов столбца матрицы смежности ориентированного графа?

6. Что характеризует сумма элементов строки матрицы смежности ориентированного графа

7. Всегда ли матрица смежности симметрична относительно главной диагонали?

8. Как по матрице смежности определить число ребер неориентированного графа?

9. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?

10. Может ли матрица быть матрицей смежности неориентированного графа?

11. Какие из следующих утверждений являются правильными: а) если матрица смежности несимметричная, то граф ориентированный; б) если граф неориентированный, то матрица смежности симметричная; в) если диагональные элементы матрицы смежности - нули, то граф неориентированный?

12. Может ли вершина, входящая в цикл графа, иметь степень, меньшую двух?

13. Как называется путь, у которого начало первой дуги совпадает с концом последней?

14. Как называется маршрут, у которого первая вершина совпадает с последней?

15. Можно ли утверждать, что сильно связный граф всегда содержит контур?

16. Какие из следующих матриц полностью задают граф:

а) матрица инцидентности; б) матрица односторонней связности; в) матрица связности; г) матрица сильной связности; д) матрица смежности?

17. По какой матрице можно без дополнительных вычислений определить число компонент связности неориентированного графа: а) матрице смежности; б) матрице инциденций; в) матрице расстояний; г) матрице связности?

18. Может ли число компонент связности графа превосходить число его вершин?

19. Верно или неверно утверждение, что в ориентированном графе с контурами минимальный путь может содержать контуры?

20. Как называется связный граф без циклов?

21. Пусть n - число вершин, а m - число ребер в связном графе без циклов. Какие из следующих соотношений возможны:

а) n = m; б) n < m; в) n m; г) n > m; д) n m?

22. Сколько ребер имеет связный граф без циклов с n вершинами?

23. Чему равно наименьшее и наибольшее число ребер в связном графе без петель и кратных ребер с n вершинами?

24. Чему равно наименьшее и наибольшее число ребер в графе без петель и кратных ребер с n вершинами?

25. Верно или неверно следующее утверждение: Минимальное остовное дерево может содержать циклы?

26. Постройте дерево наименьшей общей длины, ребра которого соединяют вершины правильного шестиугольника.

27. Сколько компонент связности может иметь дерево?

28. Можно ли построить дерево, все вершины которого имеют степень больше, чем единица?

29. Какая модель теории графов адекватна следующей задаче:

Различные организации x1, ... , xn обмениваются некоторой информацией (при этом связи могут быть направленными). Если между организациями xi и xj возможен непосредственный обмен информацией, то затраты на него составляют rij рублей. Возможен ли обмен информацией между двумя организациями? Если возможен, то как осуществить этот обмен с наименьшими затратами?

30. Какая модель теории графов адекватна следующей задаче:

Имеется схема городских дорог с перекрестками и, возможно, односторонним движением. Необходимо найти маршрут, соединяющий две точки на карте. Как найти такой маршрут при условии, что его длина минимальна?

31. Какая модель теории графов адекватна следующей задаче: Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.

32. Какая модель теории графов адекватна следующей задаче:

Имеется сеть связи, соединяющая n узлов. Если выйдут из строя некоторые каналы, то связь между узлами может быть нарушена. Какие каналы можно удалить без нарушения связи? Какие каналы нужно удалить, чтобы связь не нарушалась, а общая стоимость всех каналов была минимальной?

33. Какая модель теории графов адекватна следующей задаче:

Разрабатывается проект газопровода, соединяющего буровые скважины в Мексиканском заливе с находящейся на берегу приемной станцией. Следует выбрать проект, в котором строительство газопровода имеет минимальную стоимость.

34. Какая модель теории графов адекватна следующей задаче:

Пусть имеется n изолированных городов. Какое минимальное количество дорог между некоторыми городами надо построить, чтобы иметь возможность попасть из любого города в любой другой? Если заданы расстояния между городами, то как выбрать сеть дорог с минимальной общей длиной?

ТЕМА 4. БУЛЕВЫ ФУНКЦИИ

4.1 Определение булевой функции

Определение 4.1. Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x1, x2, ... , xn и сама функция f принимают значения 0 или 1, т. е. xi {0, 1}, i = 1, 2, ... , n; f(x1, x2, ... , xn) {0, 1}.

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

Любая булева функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных (их 2n), а в правой части - значения функции. Пример такого задания представлен в таблице 4.1.

Таблица 4.1

x1 x2 x3	f(x1, x2, x3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 1 1 1

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

Всего существует 22 различных булевых функций n переменных.

Функций одной переменной - 4. Из них выделим функцию “отрицание x”(обозначается Шx). Эта функция представлена в таблице 4.2.

Таблица 4.2

x	Шx
0 1	1 0

Булевых функций двух переменных - 16 (22при n = 2). Те из них, которые имеют специальные названия, представлены в таблице 4.3.

Таблица 4.3

x1 x2	x1Vx2	x1& x2	x1x2	x1x2	x1 ? x2	x1 x2	x1 x2
0 0 0 1 1 0 1 1	0 1 1 1	0 0 0 1	1 1 0 1	1 0 0 1	0 1 1 0	1 0 0 0	1 1 1 0

В таблице 4.3 представлены следующие функции двух переменных:

x1Vx2 - дизъюнкция;

x1& x2 - конъюнкция;

x1Йx2 - импликация;

x1x2 - эквивалентность;

x1Е x2 - сложение по модулю 2;

x1x2 - стрелка Пирса;

x1 x2 - штрих Шеффера.

Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции.

4.2 Формулы логики булевых функций

Определение 4.2. Формула логики булевых функций определяется индуктивно следующим образом:

1. Любая переменная, а также константы 0 и 1 есть формула.

2. Если A и B - формулы, то ШA, AVB, A&B, A Й B, A B есть формулы.

3. Ничто, кроме указанного в пунктах 1-2, не есть формула.

Пример 4.1.

Выражение (ШxVy)&((y Й z) x) является формулой.

Выражение Шx&y Й z Ш x не является формулой.

Часть формулы, которая сама является формулой, называется подформулой.

Пример 4.2.

x&(y--Йz) - формула; y--Йz - ее подформула.

Определение 4.3. Функция f есть суперпозиция функций f1, f2, ... , fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.

Пример 4.3.

f1 = x1&x2 (конъюнкция); f2 = Шx (отрицание).

Возможны две суперпозиции:

1) f = f1(f2) = (Шx1)&(Шx2) - конъюнкция отрицаний;

2) f = f2(f1) = Ш(x1&x2) - отрицание конъюнкции.

Порядок подстановки задается формулой.

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

Пример 4.4.

Построим таблицу значений функции f(x1, x2, x3) = Ш(x2 Шx3) (Шx1Vx2).

Таблица 4.4 представляет последовательное вычисление этой функции.

Таблица 4.4

x1 x2 x3	Шx3	x2 Шx3	Ш(x2 Шx3)	Шx1	Шx1Vx2	f(x1, x2, x3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 0 1 0 1 0 1 0	1 1 1 0 1 1 1 0	0 0 0 1 0 0 0 1	1 1 1 1 0 0 0 0	1 1 1 1 0 0 1 1	0 0 0 1 1 1 0 1

Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций: Ш, &, V, Й--и .

4.3 Равносильные преобразования формул

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

Шx1VШx2 и Ш(x1&x2)

реализуют одну функцию - штрих Шеффера.

Две формулы, реализующие одну и ту же функцию, называются равносильными.

Равносильность формул A и B будем обозначать следующим образом: A є B.

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

Основные равносильности булевых формул.

Для любых формул A, B, C справедливы следующие равносильности:

1. Коммутативность.

а) A&B--є B&A (для конъюнкции);

б) AVB є BVA (для дизъюнкции).

2. Ассоциативность.

а) A&(B&C) є (A&C)&C (для конъюнкции);

б) AV(BVC) є (AVB)VC (для дизъюнкции).

3. Дистрибутивность.

а) A&(BVC) є A&BVA&C (для конъюнкции относительно дизъюнкции);

б) AV(B&C) є (AVB)&(AVC) (для дизъюнкции относительно конъюнкции).

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

а) Ш(A&B)--єШAVШB (отрицание конъюнкции есть дизъюнкция отрицаний);

б) Ш(AVB)--є ШA&ШB (отрицание дизъюнкции есть конъюнкция отрицаний).

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

а) A&A є A (для конъюнкции);

б) AVA є A (для дизъюнкции).

6. Поглощение.

а) A&(AVB) є A (1- ый закон поглощения);

б) AVA&B --є A (2- ой закон поглощения).

7. Расщепление (склеивание).

а)A&B V A&(ШB) є A (1-ый закон расщепления);

б) (AVB) & (AVШB) є A (2-ой закон расщепления).

8. Двойное отрицание.

Ш(ШA) є A.

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

а)A&1 є A; б) A&0 є 0; в)AV1 є 1; г) AV0 є A; д) Ш0--є 1; е) Ш1--є 0.

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

A&ШA є 0.

11. Закон “исключенного третьего”.

AVШA є 1.

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “є”. Докажем, например, равносильность 4а. Для этого составим таблицу 4.5.

Таблица 4.5

A	B	A&B	Ш(A&B)	ШA	ШB	ШAVШB
0 0 1 1	0 1 0 1	0 0 0 1	1 1 1 0	1 1 0 0	1 0 1 0	1 1 1 0

Из таблицы 4.5 видно, что Ш(A&B) є ШAVШB, что и требовалось доказать.

Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания:

12. AЙB єШAVB є--Ш(A&ШB).

13. AB є (AЙB)&(BЙA) є (A&B) V (ШA&ШB) є--(АVШB)&(ШAVB).

14. AЕB--є--(AVШB) V (ШA&B).

15. AB є--Ш(AVB) є--ШA&ШB.

16. AB є--Ш(A&B)--є--ШAVШB.

Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности):

17. (A1VA2V...VAn)&(B1VB2V...VBm) є--

A1&B1VA1&B2V...VA1&BmV...VAn&B1VAn&B2V...VAn&Bm.

18. (A1&A2&...&An)V(B1&B2&...&Bm) є

(A1VB1)&(A1VB2)&...&(A1VBm)&...&(AnVB1)&(AnVB2)&...&(AnVBm).

Используя равносильности 4а и 4б и метод математической индукции, можно получить также следующие равносильности (обобщенные законы де Моргана):

19. Ш(A1&A2&...&An) є--ШA1VШA2V...VШAn.

20. Ш(A1VA2V...VAn) єШA1&ШA2&...&ШAn

В равносильностях 1 - 20 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим.

Правило равносильных преобразований

Пусть для формул A и B справедливо утверждение A є--B. Пусть CA - формула, содержащая A в качестве своей подформулы. Пусть CB получается из CA заменой A на B. Тогда CA є--CB.

Пример 4.5.

Пусть A = x Йy, B = ШxVy.

Равносильность 12 позволяет утверждать, что A єB.

Пусть CA = (x Й--y) & z, т.е. A есть подформула CA. Тогда CB = (ШxVy) & z и CA є--CB, т.е. (x Й--y) & z є--(ШxVy) & z.

4.4 Двойственность. Принцип двойственности

Символы &, V называются двойственными.

Формула А* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, V на двойственные.

Например,

A = xV(y&Шz);

A* = x & (yVШz).

Теорема 4.1. (Принцип двойственности).

Если A є--B, то A* є--B*.

Доказательство принципа двойственности можно найти, например, в [3].

Принцип двойственности можно использовать для нахождения новых равносильностей. Например, для 1-го закона поглощения (равносильность 6а) имеем:

A&(AVB) є A.

Следуя принципу двойственности, получим новую равносильность:

AVA&B--є A (2- ой закон поглощения).

4.5 Булева алгебра (алгебра логики). Полные системы булевых функций

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

Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.

Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 - 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ш, &, V} является полной. Также полными являются следующие системы функций:

а)--{Ш, V}; б) {Ш, &}; в) {Ш, Й}.

Полнота систем --{Ш, V} и {Ш, &} следует из полноты системы {Ш, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A&B--єШ(ШAVШB); AVB--є Ш(ШA&ШB).

Поэтому система {Ш, &, V} может быть сокращена на одну функцию:

Полнота системы {Ш, Й} следует из полноты системы --{Ш, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:

AЙB єШAVB.

4.6 Нормальные формы

Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.

Пример 4.6.

x, y, x&y, Шx1&x2&(Шx3) - элементарные конъюнкции.

xVy, x1&Шx2 VШx1&x2 - не элементарные конъюнкции.

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

Пример 4.7.

x, x&y, x V Шx&(Шy), Шx1&x2&(Шx3) V x1&(Шx2)&x3 V x1&x2&(Шx3) - ДНФ.

(xVy)&Шx - не ДНФ.

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

Пример 4.8.

x&y, x&Шy V Шx&y - СДНФ функции двух переменных.

xVШx&y, xVy - не СДНФ.

Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.

Пример 4.9.

x, y, xVy, Шx1Vx2V(Шx3) - элементарные дизъюнкции.

x&y, (x1VШx2) & (Шx1Vx2) - не элементарные дизъюнкции.

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

Пример 4.10.

x, x&y, x & Шx&(Шy), (Шx1Vx2)&(Шx3)&(x1VШx2Vx3) - КНФ.

x&y V Шx - не КНФ.

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

Пример 4.11.

xVy, (xVШy) &(ШxVy) - СКНФ функции двух переменных.

x &(ШxVy), x&y - не СКНФ.

Теорема 4.2. Для каждой формулы булевой функции A имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).

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

Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)).

Шаг 1. Все подформулы A вида B Й C (т.е. содержащие импликацию) заменяем на ШBVC или на Ш(B&ШC) (в соответствии с равносильностью 12 раздела 4.3).

Шаг 2. Все подформулы A вида B C (т.е. содержащие эквивалентность) заменяем на (A&B) V (ШA&ШB) или на --(AVШB)&(ШAVB) (в соответствии с равносильностью 13).

Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).

Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).

Шаг 6. для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.

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

Пример 4.12.

Приведем к ДНФ и КНФ рассмотренную ранее в примере 4.4 формулу f(x1, x2, x3) = Ш(x2 Шx3) (Шx1Vx2).

1. Устранив импликацию, получим:

Ш(Шx2 VШx3) (Шx1Vx2).

2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим:

(x2&x3) (Шx1Vx2).

3. Устранив эквивалентность, получим:

(x2&x3) & (Шx1Vx2) V Ш(x2&x3) & Ш(Шx1Vx2).

4. Применив закон де Моргана ко второму члену дизъюнкции, получим

(x2&x3) & (Шx1Vx2) V (Шx2VШx3) & (x1& Шx2).

5. Применив закон дистрибутивности 3а, получим

(x2&x3&Шx1 V x2&x3&x2) V (Шx2&x1&Шx2 V Шx3&x1&Шx2).

6. Применив законы идемпотентности 5а и 5б, и располагая переменные по возрастанию индексов, получим:

Шx1&x2&x3 V x2&x3 V x1&Шx2 V x1&Шx2&Шx3.

7. Применив 2-ой закон поглощения (6б), вместо Шx1&x2&x3.V x2&x3 запишем x2&x3, а вместо x1&Шx2 V x1&Шx2&Шx3 запишем x1&Шx2 и в результате получим ДНФ нашей формулы:

f(x1, x2, x3) є x2&x3 V x1&Шx2

При приведении к КНФ применим закон дистрибутивности 3б и получим:

x2&x3 V x1&Шx2 є--( x2Vx1) & (x2VШx2) & (x3Vx1) & (x3VШx2).

Учитывая, что. x2VШx2 є--1--(равносильность 11),--и применив свойство 9а, получим окончательно КНФ для f(x1, x2, x3)

f(x1, x2, x3) є--( x1Vx2) & (x1Vx3) & (Шx2Vx3).

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

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

Теорема 4.4. Каждая формула A, не равная тождественно единице, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.

Доказательство этих теорем состоит в указании алгоритма приведения формулы А к СДНФ и СКНФ.

Алгоритм 4.2. (Алгоритм приведения формулы булевой функции к СДНФ)

Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.

Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:

A&ШA є 0, B&0 є 0, СV0 є С.

Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A є A.

Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание Шx, то на основании 1- го закона расщепления (равносильность 7а) заменяем С на (С&x) V (C&Шx).

Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная xi, либо ее отрицание Шxi.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС є С.

Пример 4.13.

Найдем СДНФ формулы из примера 4.4:

f(x1, x2, x3) = Ш(x2Шx3) (Шx1Vx2).

1. Найденная ранее в примере 4.12 ДНФ формулы f(x1, x2, x3) имеет вид:

x2&x3 V x1&Шx2.

2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре):

f(x1, x2, x3) є x2&x3&x1 V x2&x3&Шx1V x1&Шx2&x3 V x1&Шx2&Шx3).

После применения шага 5 получим:

f(x1, x2, x3) є x1&x2&x3 V Шx1&x2&x3 V x1&Шx2&x3 V x1&Шx2&Шx3.

4. Шаг 6 не требуется. Найденное выражение формулы f(x1, x2, x3) является СДНФ этой формулы.

Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &.

Пример 4.14.

Найдем СКНФ формулы из примера 4.4:

f(x1, x2, x3) = Ш(x2 Шx3) (Шx1Vx2).

1. Найденная в примере 4.12 КНФ формулы f(x1, x2, x3) имеет вид:

f(x1, x2, x3) є--(x1Vx2) & (x1Vx3) & (Шx2Vx3).

2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом:

x1Vx2 є--( x1Vx2Vx3) & (x1Vx2VШx3).

x1Vx3 є--(x1Vx3Vx2)&(x1Vx3VШx2).

Шx2 Vx3 є(Шx2Vx3Vx1) & (Шx2Vx3VШx1).

Поэтому имеем:

f(x1, x2, x3) =--(x1Vx2Vx3)&(x1Vx2VШx3)&(x1Vx3Vx2)&(x1Vx3VШx2)&(Шx2Vx3Vx1)&(Шx2 V x3VШx1).

3. Применив шаг 5, получим:

f(x1, x2, x3) є--(x1Vx2Vx3)&(x1Vx2VШx3)&(x1Vx2Vx3)&(x1VШx2Vx3)&(x1VШx2Vx3)&(Шx1 VШx2Vx3).

4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3):

f(x1, x2, x3) є--(x1Vx2Vx3)&(x1Vx2VШx3)&(x1VШx2Vx3)&(Шx1VШx2Vx3).

4.7 Разложение булевой функции по переменным

Пусть s принимает значения 0 или 1, т.е. s {0, 1}.

Введем обозначение:

xs = Шx, если s = 0, xs = x, если s = 1.

Т.е. x0 = Шx, x1 = x.

Очевидно, что xs = 1, если x = s и xs = 0, если x s.

Теорема 4.5 (о разложении булевой функции по переменным).

Каждая булева функция f(x1, x2, ... , xn) может быть представлена в виде:

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

V x1s1&x2s2&...&xmsm& f(s1, s2, ... sm, xm+1, ... , xn), (4.1)

mn, где дизъюнкция берется по всем наборам (s1, s2, ... , sm) (их 2m).

Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2m = 22 =4) конъюнкции и имеет вид:

f(x1, x2, x3, x4) = x&x&f(0, 0, x3, x4) V x&x&f(0, 1, x3, x4) V x& x&f(1, 0, x3, x4) V x& x&f(1, 1, x3, x4) = Шx1&Шx2&f(0, 0, x3, x4) V Шx1&x2&f(0, 1, x3, x4) V x1&Шx2&f(1, 0, x3, x4) V x1&x2&f(1, 1, x3, x4).

Доказательство теоремы 4.5.

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y1, y2, ... , ym, ym+1, ... , yn) .

Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).

В левой части получим f (y1, y2, ... , yn) .

Т. к. ys = 1 только, когда y = s, то среди 2m конъюнкций y1s1&y2s2&...&ymsm в правой части (4.1) только одна обратится в 1 - та, в которой y1 = s1,…, ym = sm. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y1y1&y2y2&...&ymym&f(y1, y2, ... , ym, ym+1, ... , yn) = f(y1, y2, ... , yn) .

Теорема 4.5 доказана.

Теорема 4.6 (о представлении булевой функции формулой в СДНФ),

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

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

При m = n получим важное следствие теоремы 4.5:

f(x1, x2, ... , xn) = V x1s1&x2s2&...&xnsn, (4.2)

f(s1, s2, ... , sn) = 1

где дизъюнкция берется по всем наборам (s1, s2, ... , sn), на которых f = 1.

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

Очевидно также, что для булевой функции f(x1, x2, ... , xn), тождественно равной 0, разложение (2) не существует.

В силу изложенного для получения формулы булевой функции f(x1, x2, ... , xn) в СДНФ можно воспользоваться следующим алгоритмом.

Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).

Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f равно 1, т. е. f (s1, s2, ... , sn) = 1.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x1s1&x2s2&...&xnsn, где xisi = xi, если si = 1 и xisi =?xi, если si = 0, i = 1, 2, ... ,n.

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Пример 4.15.

Найдем формулу в СДНФ для функции f(x1, x2, x3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f(x1, x2, x3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.

2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк:

x10&x21&x31 = Шx1 &x2&x3.

x11&x20&x30 = x1&Шx2&Шx3.

x11&x20&x31 = x1&Шx2&x3 .

x11&x21&x31 = x1&x2&x3 .

3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:

f(x1, x2, x3) = Шx1&x2&x3V x1&Шx2&Шx3 V x1&Шx2&x3 V x1&x2&x3.

Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.

Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции.

Теорема 4.7 (о представлении булевой функции формулой в СКНФ),

Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

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

Рассмотрим функцию Шf(x1, x2, ... , xn). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F1. Очевидно, условие, что функция Шf(x1, x2, ... , xn) не равна тождественно 0, равносильно условию, что функция f(x1, x2, ... , xn) не равна тождественно 1. Кроме того, по закону де Моргана формула F2 є ШF1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания

F2--є ШF1 є ШШf(x1, x2, ... , xn) є f(x1, x2, ... , xn),

что и доказывает теорему.

Для получения формулы булевой функции f(x1, x2, ... , xn) в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)

Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f (s1, s2, ... , sn) = 0.

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию

x1 Шs1Vx2Шs2V...VxnШsn, где xi Шsi = xi, если si = 0 и xi Шsi = Шxi, если si = 1, i = 1, 2, ... , n.

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.

Пример 4.16.

Найдем формулу в СКНФ для функции f(x1, x2, x3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f(x1, x2, x3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.

2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк:

x11Vx21Vx31 = x1Vx2Vx3.

x11Vx21Vx30--=--x1Vx2VШx3.

x11Vx20Vx31 = x1VШx2Vx3.

x10Vx20Vx31 = Шx1VШx2V x3.

3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:

f(x1, x2, x3) = ( x1Vx2Vx3)&(x1Vx2VШx3)&(x1VШx2Vx3)&(Шx1VШx2Vx3).

Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.

Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n.

Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 23.

4.8 Минимизация формул булевых функций в классе дизъюнктивных нормальных форм

Как было установлено выше, произвольная булева функция может быть представлена формулой в ДНФ и КНФ, причем такое представление неоднозначно. Равносильными преобразованиями можно получить формулу, содержащую меньшее число вхождений переменных. Например, две различные формулы: f1(x1, x2) = x1V x1&x2 V Шx2 и f2(x1, x2) = x1 V Шx2 равносильны, так как в силу 2-го закона поглощения (равносильность 6б из раздела 4.3) x1 V x1&x2 є-- x1.

Но в формуле f1(x1, x2) содержится четыре вхождений переменных, а в формуле f2(x1, x2) - два.

Определение 4.10. ДНФ называется минимальной, если она содержит наименьшее общее число вхождений переменных среди всех равносильных ей ДНФ.

Определение 4.11. Импликантом булевой функции f(x1, x2, ... , xn) называется элементарная конъюнкция С, не равная тождественно 0, такая что C V f f. Отметим, что любая конъюнкция любой ДНФ в силу закона идемпотентности (равносильность 5б) является импликантом этой функции.

Определение 4.12. Импликант C функции f называется простым импликантом, если после отбрасывания любой переменной из C получается элементарная конъюнкция, не являющаяся импликантом функции f.

Пример 4.17.

Для функции x&yVx&zVx&y&z є x&(yVz) конъюнкции x&y и x&z - простые импликанты, а x&y&z - импликант, но не простой.

Определение 4.13. Дизъюнкция всех простых импликантов булевой функции f называется сокращенной ДНФ функции f.

Для нахождения сокращенной ДНФ используется следующий алгоритм, в основе которого лежит метод Квайна.

Алгоритм 4.5. (Алгоритм Квайна построения сокращенной ДНФ).

Шаг 1. Находим для данной булевой функции f ее формулу F, находящуюся в СДНФ.

Шаг 2. Находим все простые импликанты функции f. Для этого все элементарные конъюнкции формулы F попарно сравниваем между собой. Если две элементарные конъюнкции таковы, что они имеют вид C&xi и C&?xi, то выписываем конъюнкцию С. Это является следствием 1-го закона расщепления (склеивания) (равносильность 7а). Конъюнкция С содержит n - 1 вхождение переменных. Элементарные конъюнкции, для которых произошло склеивание, помечаем. После построения всех конъюнкций, включающих n - 1 вхождение переменных, вновь сравниваем их попарно, производим, если возможно, склеивание, выписываем полученные конъюнкции из n - 2 членов, помечаем склеивающиеся конъюнкции из n - 1 членов и т. д. Процесс заканчивается, когда дальнейшее склеивание невозможно. Все непомеченные элементарные конъюнкции являются простыми импликантами. Их дизъюнкция даст нам формулу F1, равносильную F, находящуюся в ДНФ и состоящую из простых импликантов, т.е. сокращенную ДНФ.

Пример 4.18.

Найдем сокращенную ДНФ функции из примера 4.4:

f(x1, x2, x3) = Ш(x2Шx3) (Шx1Vx2).

1. Шаг 1 был выполнен ранее (см. примеры 4.13, 4.15). СДНФ формулы f(x1, x2, x3) является формула

F(x1, x2, x3) = Шx1&x2&x3V x1&Шx2&Шx3 V x1&Шx2&x3 V x1&x2&x3.

2. Попарно сравниваем все 4 трехчленные конъюнкции (всех сравнений C= 6) и применяем, где это возможно, закон склеивания:

Шx1&x2&x3V x1&x2&x3 = x2&x3.

x1&Шx2&Шx3 V x1&Шx2&x3 = x1&Шx2.

x1&Шx2&x3 V x1&x2&x3 = x1&x3.

Итак, на первом этапе получили 3 двучленные конъюнкции:

x2&x3, x1&Шx2, x1&x3.

Все трехчленные конъюнкции оказались помеченными.

Попарно сравниваем все 3 двучленные конъюнкции (всех сравнений 3) и замечаем, что склеивание невозможно.

В результате получим сокращенную ДНФ формулы f:

F1(x1, x2, x3) = x2&x3 V x1&Шx2 V x1&x3.

На практике для построения сокращенной ДНФ удобнее пользоваться модифицированным методом Квайна - Мак-Класки. Этот метод состоит в автоматизации процесса склеивания. Разберем этот метод на конкретном примере.

Алгоритм 4.6. (Алгоритм Квайна - Мак-Класки построения сокращенной ДНФ).

Шаг 1. Составим таблицу значений булевой функции (если функция задана формулой в СДНФ, то в силу замечания к алгоритму 4.3 это всегда можно сделать)

Для нашего примера такая таблица уже составлена - это таблица 4.4.

Очевидно, в силу алгоритма 4. 3 (см. также пример 4.15), эта функция имеет следующую формулу в СДНФ:

f(x1, x2, x3) = Шx1&x2&x3V x1&Шx2&Шx3 V x1&Шx2&x3 V x1&x2&x3.

Шаг 2. Выпишем наборы переменных, на которых функция принимает значение 1, причем эти наборы упорядочим по группам так, что в каждую группу входят наборы с одинаковым числом единиц. Пусть Ai - группа наборов переменных, таких, что каждый набор содержит i единиц, и функция на этом наборе переменных принимает значение, равное единице.

Группы A0 (где все переменные нули, а значение функции равно 1) нет.

Группа A1 (где одна переменная единица, остальные нули, и значение функции равно 1):

1 0 0

Группа A2:

0 1 1

1 0 1

Группа A3:

1 1 1

Шаг 3. Производим попарное сравнение наборов переменных, входящих в соседние группы. Если при этом сравнении обнаружатся два набора, которые отличаются только в одном разряде, то вместо них записывается один набор, в котором вместо несовпадающих разрядов ставится “ - “ (прочерк). После всех возможных сравнений из предшествующего списка вычеркиваются все наборы, которые участвовали в образовании хотя бы одного набора с прочерком. Формируются два массива наборов: наборы с прочерками (массив P) и невычеркнутые (массив R).

Эти действия соответствуют склеиванию конъюнкций и уменьшению числа вхождений переменных.

Для нашего примера при сравнении групп A1 и A2:

вместо (1 0 0) и (1 0 1) получим (1 0 -);

При сравнении групп A2 и A3:

вместо (0 1 1) и (1 1 1) получим (- 1 1);

вместо (1 0 1) и (1 1 1) получим (1 - 1);

После этого этапа массив R пуст, т. к. все наборы участвовали в образовании наборов с прочерками, а массив P = P(1) включает следующие наборы:

(1 0 -);

(- 1 1);

(1 - 1).

Далее рассмотрим наборы с прочерками. Они вновь попарно сравниваются между собой. При этом имеет смысл сравнивать лишь наборы, в которых прочерк стоит в совпадающих разрядах. Если сравниваемые наборы отличаются друг от друга только в одном разряде, то выписываем набор с двумя прочерками (старым и новым). После всех попарных сравнений из множества наборов с одним прочерком вычеркиваются все наборы, имеющие один прочерк и участвовавшие в образовании набора с двумя прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R.

Для нашего примера попарное сравнение наборов с одним прочерком не приводит к образованию наборов с двумя прочерками.

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

Для нашего примера процедура сравнения заканчивается после формирования наборов с одним прочерком. Массив R после этого включает наборы:

(1 0 -);

(- 1 1);

(1 - 1).

Сокращенная ДНФ имеет вид:

f(x1, x2, x3) = x2&x3 V x1&Шx2 V x1&x3.

Далее процесс нахождения минимальной ДНФ сводится к отбрасыванию некоторых простых импликантов.

Определение 4.14. Простой импликант называется существенным (ядровым) импликантом, если его удаление из сокращенной ДНФ функции приводит к ДНФ, которая не равносильна исходной ДНФ.

Построение минимальной ДНФ сводится к отбрасыванию несущественных импликантов из сокращенной ДНФ.

Определение 4.15. Будем говорить, что элементарная конъюнкция A покрывает элементарную конъюнкцию В, если она является частью этой конъюнкции, т.е. целиком входит в нее.

Пример 4.19.

Элементарная конъюнкция x1&Шx2 покрывает элементарные конъюнкции x1&Шx2&x3 и x1&Шx2&Шx3, но не покрывает элементарные конъюнкции x1&x2&x3 и Шx1&Шx2&Шx3.

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

Рассмотрим следующий алгоритм нахождения минимальной ДНФ.

Алгоритм 4.7. (Алгоритм построения минимальной ДНФ с помощью таблицы покрытий).

Шаг 1. Составление таблицы покрытий.

Для данной функции

f(x1, x2, ... , xn) = Ai є--Bj, m k,

где Ai -элементарные конъюнкции, входящие в СДНФ, i = 1, 2, ..., k, k n, а Bj - простые импликанты сокращенной ДНФ, j = 1, 2, ... ,m, m k, построим таблицу покрытий, число строк которой равно числу полученных простых импликантов, а число столбцов - числу элементарных конъюнкций в СДНФ. Если в некоторую элементарную конъюнкцию входит какой-либо простой импликант, то на пересечении соответствующего столбца и строки ставится метка (например, “ * “).

...