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

отрицания, используя равенство (5), убрать дизъюнкции, используя равенство

(7), раскрыть скобки и упростить формулу, используя равенства (2), (3), (4), то

получим формулу в виде суммы по модулю 2 конъюнкций переменных и,

может быть, единицы. Представленная в таком виде булева функция называется полиномом Жегалкина.

Пример 1. Найти полином Жегалкина для эквиваленции.

f9 x1, x2 x1 x2 x1 x2

x1 x2 x1 x2 1.

Пример 2. Найти полином Жегалкина для функции стрелка Пирса. f8 x1, x2 x1 x2 x1 x2

x1 x2 x1 x2 x1 x2 x1 x1 1.

Из теоремы о единственности представления булевой функции в СДНФ и равенств (5) и (7) следует терема о представления булевой функции в виде полинома Жегалкина.

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

Булева функция, полином которой имеет

n

f x1, x2 ,..., xn a0 ai xi ,

i 1

где коэффициенты a0 , ai равны либо 0, либо 1, называется линейной.

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

функцией, так как содержит конъюнкцию переменных x1 x2 .

71

vk.com/club152685050 | vk.com/id446425943

§ 15. Функционально полные системы. Теорема Поста

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

Из теорем о единственности представления любой булевой функции в СДНФ и в СКНФ следует, что множество функций , , является базисом.

Этот базис называется базисом Буля.

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

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

дизъюнктивным.

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

булевых функций , ,1 . Этот базис называется базисом Жегалкина.

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

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

Функция f x1, x2 ,..., xn называется функцией, сохраняющей 0, если f 0,0,..., 0 0 .

Множество булевых функций, сохраняющих 0, обозначим T0 . Например, конюъюнкция сохраняет 0, отрицание не сохраняет 0 Функция f x1, x2 ,..., xn называется функцией, сохраняющей 1, если

f 1,1,...,1 1.

72

vk.com/club152685050 | vk.com/id446425943

Множество булевых функций, сохраняющих 1, обозначим T1. Например,

дизюъюнкция сохраняет 1, отрицание не сохраняет 1.

Считается, что для двух наборов переменных выполнено отношение предшествования x1, x2 ,..., xn y1, y2 ,..., yn , если xi yi для 1 i n .

Функция f x1, x2 ,..., xn

x1, x2 ,..., xn y1, y2 ,..., yn ,

следует неравенство f x1, x2 ,..., xn f y1, y2 ,..., yn . Множество монотонных булевых функций обозначим M .

Например, конъюнкция и дизъюнкция монотонны. Импликация не является монотонной функцией, так как 0,0 1,0 , но

f13 0,0 1 f13 1,0 0 .

Без доказательства приведем теорему Поста.

Теорема Поста. Для того, чтобы система булевых функций

f1, f2 ,..., fm была полной, необходимо и достаточно, чтобы она содержала:

1)хотя бы одну функцию, не сохраняющую 0;

2)хотя бы одну функцию, не сохраняющую 1;

3)хотя бы одну немонотонную функцию;

4)хотя бы одну несамодвойственную функцию;

5)хотя бы одну нелинейную функцию.

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

Пример. Доказать полноту системы функций f12 x1, x2 , f13 x1, x2 . Таблица Поста для заданной системы будет иметь следующий вид (табл.7).

Таблица 7

Функция

f12 x1, x2 x1

f13 x1, x2 x1

В клетках таблицы пишем знак «+» или «–» в зависимости от того, принадлежит рассматриваемая функция множествам T0 ,T1, S, L, M или нет.

73

vk.com/club152685050 | vk.com/id446425943

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

T0 ,T1, S, L, M . Исследуем функцию f12 x1, x2 .

f12 x1, x2 M .

Исследуем функцию f13 x1, x2 .

1.Так как f13 0, 0 1, то f13 x1, x2 T0 .

2.Так как f13 1,1 1, то f13 x1, x2 T1 .

3. Так как f13 x1, x2 f13 x1, x2 x1 x2

x1 x2 x1 x2 f4 x1, x2 , то f13 x1, x2 S .

4.Так как f13 x1, x2 x1 x2 x1 x2

x1 x2 x1 x2 x1 1 x2 x1 1 x2

x1 x2 x2 x1 1 x2 x1 x2 x1 1, то f13 x1, x2 L .

Вкаждом столбце таблицы Поста имеется минус, т.е. система функций

f12 x1, x2 , f13 x1, x2 является полной.

Система булевых функций , называется базисом Фреге.

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

f8 x1, x2 , f14 x1, x2 , f4 x1, x2 , f9 x1, x2 ,

f7 x1, x2 , f12 x1, x2 , f2 x1, x2 , f15 x1, x2 .

74

vk.com/club152685050 | vk.com/id446425943

§16. Контактные схемы

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

Будем описывать булевой функцией наличие тока в некоторой схеме. Булеву функцию в этом случае называют функцией проводимости. Функция проводимости принимает значение 1, если ток в схеме есть, и – значение 0, если тока нет. Пусть в схеме имеется какой-либо переключатель (механический, электромагнитный, электронный и т. д. – от устройства переключателя отвлекаемся). Если переключатель замкнут, то ток в схеме есть. Обозначим переключатель и это его состояние x . Если переключатель разомкнут, то тока

в схеме нет, это состояние обозначим x . Тогда два последовательно соединённых переключателя реализуют конъюнкцию, так как ток в схеме будет, если оба переключателя одновременно замкнуты. Два параллельно соединённых переключателя реализуют дизъюнкцию, так как ток в схеме будет, если хотя бы один из переключателей замкнут. Таким образом, мы имеем три устройства: переключатель, два последовательно соединённых переключателя и два параллельно соединённых переключателя (обозначение их на схемах показано на рис. 7), которые реализуют функции базиса Буля:

, , .

Рис. 7

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

Появляется возможность решать два вида задач.

1.Анализ контактных схем. Дана контактная схема. Надо построить соответствующую ей булеву функцию проводимости. Если функцию

можно упростить, то можно упростить и соответствующую ей схему.

75

vk.com/club152685050 | vk.com/id446425943

2. Синтез контактных схем. Задана булева функция проводимости (формулой или таблично). Надо построить реализующую её контактную схему.

Пример 1. Дана контактная схема (рис. 8). Построить упрощенную контактную схему.

x

Рис. 8

Получили упрощенную функцию проводимости: f x, y, z x y . Соответствующая ей упрощенная схема показана на рис. 9

x

y

Рис. 9

76

vk.com/club152685050 | vk.com/id446425943

Пример 2. Построить контактную схему, реализующую булеву функцию f x, y, z x y z y .

Приведем функцию к одной из нормальных форм с помощью равносильных преобразований.

fx, y, z x y z y

x y z y x y z y

x y z y y x y z

x y z y y x y z

x y z y x y z y

x y z y x y z y y x z .

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

x

y

z

Рис. 10

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

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

2.Какова область определения булевой функции?

3.Каково множество значений булевой функции?

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

77

vk.com/club152685050 | vk.com/id446425943

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

6.Какова структура конъюнктивной нормальной формы (КНФ) булевой функции?

7.Какая ДНФ называется совершенной?

8.Какая КНФ называется совершенной?

9.Как найти СДНФ булевой функции, заданной таблично?

10.Как найти СКНФ булевой функции, заданной таблично?

11.Как с помощью преобразований найти СДНФ булевой функции, заданной формулой?

12. Как с помощью преобразований найти СКНФ булевой функции, заданной формулой?

13.Какая функция называется двойственной к булевой функции f x1, x2 ,..., xn ?

14.Какая булева функция называется самодвойственной?

15.В чем заключается принцип двойственности?

16.Какая функция называется импликантой булевой функции f ?

17.Какая импликанта называется простой?

18.Какая ДНФ называется сокращенной?

19.Какая ДНФ называется минимальной?

20.Какие действия надо выполнить, чтобы получить МДНФ булевой функции методом Квайна?

21.Какие действия надо выполнить, чтобы получить МДНФ булевой функции с помощью карты Карно?

22.Какова структура полинома Жегалкина?

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

24.Какая булева функция называется функцией, сохраняющей 0?

25.Какая булева функция называется функцией, сохраняющей 1?

26.Какая булева функция называется монотонной?

27.Какая система булевых функций называется полной (базисом)? 28.Какие функции входят в базис Буля? Какие другие базисы существуют? 29.Сформулируйте теорему Поста.

30.Как с помощью таблицы Поста установить полноту заданной системы булевых функций?

78

vk.com/club152685050 | vk.com/id446425943

Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Граф – одна из форм представления бинарного отношения.

Предполагается, что начало теории графов было положено Леонардом Эйлером. Одна из первых задач теории графов об обходе мостов в Кенигсберге была сформулировано Эйлером в 1736г.

В г. Кенигсберге на реке Преголь есть два острова и семь мостов, соединяющие острова с берегами.

берег

Задача. Можно ли пройти по каждому мосту по одному разу и вернуться обратно?

§ 1. Основные определения

Опр. Неориентированным графом G называется совокупность G M , ,

состоящая из непустого множества М, элементы которого называются вершинами графа, и множества Г: Г М 2 , элементами которого являются неупорядоченные пары различных вершин (х,у). Эти пары называются ребрами.

соединяющими вершины.

79

vk.com/club152685050 | vk.com/id446425943

Замечание. Это один и тот же граф, т.е. видимое пересечение вершин вне ребер не учитывается.

Опр. Вершины x и y графа G, соединенные ребром (х,у), называются

инцидентными ребру (х,у); ребро (х,у) называется инцидентными вершинами х и

у

Опр. Если в графе G существует ребро (х,у), то вершины х и у называются смежными.

Замечание. Понятие смежности устанавливает бинарное отношение между элементами одного множества (множества вершин) М М . Понятие

инцидентности – между элементами разных множеств М Г .

Опр. Степенью вершины x называется количество ребер, инцидентных данной вершине: deg x . Множество всех ребер, инцидентных вершине х

обозначим Г(х), тогда мощность этого множества Г (х) deg x ; вершина степени 0 называется изолированной; вершина степени 1 называется висячей.

Теорема Эйлера (о соотношении количества вершин и ребер графа).

Пусть G=<М,Г> - граф без петель, Г число ребер графа, тогда сумма

степеней всех вершин графа равна удвоенному числу ребер: deg x 2 Г .

x M

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

Каждое ребро имеет 2 инцидентные ему вершины и, следовательно, добавляет по единице в степень каждой из них (Лемма о рукопожатиях).

G=<М,Г>; М=<А,В,С,D,Е>; Г А, В ; А, С ; В, D ; D,С ; D, Е

Замечание. Граф задает симметричное, антирефлексивное (нет петель) отношение.

80