Введение

В данном методическом пособии рассматриваются вопросы, входящие в университетский курс по дискретной математике. Большой раздел посвящён проблемам полноты булевых функций. В нём изложены основные определения и результаты по данной проблематике: теорема о представлении булевой функции в виде совершенной дизъюнктивной (конъюнктивной) нормальной формы, полинома Жегалкина, критерий Поста полноты, базисы в предполных классах. Следующий раздел посвящён проблемам минимизации представления булевых функций в виде ДНФ: геометрическая интерпретация, покрытия, интервалы, метод построения сокращённой и минимальных ДНФ. В заключение излагаются основы классического исчисления высказываний: основные определения, теорема дедукции, полнота исчисления высказываний.

Все разделы снабжены большим количеством учебных примеров и задач.

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

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

Булевой функцией f(x₁ … x_n) называют функцию, аргументы которой принимают значения из множества , и значение функции также из множества {0;1}.

1.Табличные способы задания булевых функций :

x1	…	xn	f(x1…xn)
0	…	0	*
0	…	1	*
…	…	…	…
1	…	1	*

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

Пример табличного задания функции:

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

2.Основные булевые функции и их таблицы.

0 – константа ноль ;

1 – константа один ;

x - тождественная ;

- отрицание ;

- конъюнкция (логическое умножение) ;

- дизъюнкция (логическое сложение) ;

+ - модульная сумма ;

~ - эквивалентность (отрицание модульной суммы) ;

- следствие .

x1	x2	0	1	x1		x1x2	x1x2	x1+ x2	x1 ~ x2	x1x2
0	0	0	1	0	1	0	0	0	1	1
0	1	0	1	0	1	0	1	1	0	1
1	0	0	1	1	0	0	1	1	0	0
1	1	0	1	1	0	1	1	0	1	1

3.Свойства булевых функций :

Определения.

Бинарная операция ассоциативна, если тождественно выполняется: ;

бинарная операция коммутативна, если тождественно выполняется: ;

бинарная операция дистрибутивна по отношению к бинарной операции , если тождественно выполняется:

;

Утверждение 1. ,конъюнкция ассоциативна.

x1	x2	x3	x2 x3	x1(x2x3)	x1x2	(x1x2) x3
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	1	0	0	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	1	0
1	1	1	1	1	1	1

Утверждение 2. ,

дизъюнкция ассоциативна.

x1	x2	x3	x2 x3	x1(x2 x3)	x1x2	(x1x2 )x3
0	0	0	0	0	0	0
0	0	1	1	1	0	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	0	1	1	1
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Утверждение 3. ,конъюнкция

коммутативна; , дизъюнкция также

коммутативна;

x1	x2	x1x2	x2x1
0	0	0	0
0	1	0	0
1	0	0	0
1	1	1	1

Предложение 1. Результат выполнения ассоциативной операции не зависит от расположения скобок в скобочном выражении.

Например: Если ассоциативная операция, тогда

.

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

Примечание: использовать индукцию по числу скобок в выражении.

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

Например:

Тогда в силу независимости значения выражений конъюнкций от расположения скобок корректно определение как значение логического произведения при каком-либо порядке расположения скобок. Точно также для дизъюнкции.

Предложение 2. Конъюнкция равна 0, т. и т.т., когда хотя бы один из множителейравен 0.

Дизъюнкция равна 1, т. и т.т., когда хотя бы одно из слагаемыхравно 1.

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

Утверждение 4.

, конъюнкция дистрибутивна по отношению к дизъюнкции.

x1	x2	x3	x2 x3	x1(x2x3)	x1x2	x1x3	(x1x2 )(x1x3 )
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	1	1	1	1

Утверждение 5.

, дизъюнкция дистрибутивна по отношению к конъюнкции.

x1	x2	x3	x2x3	x1(x2x3)	x1x2	x1x3	(x1x2)(x1x3)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Утверждение 6. , следствие не ассоциативная операция.

x1	x2	x3	x2x3	x1(x2x3)	x1x2	(x1x2)x3
0	0	0	1	1	1	0
0	0	1	1	1	1	1
0	1	0	0	0	1	1
0	1	1	1	1	1	1
1	0	0	1	1	0	1
1	0	1	1	1	0	0
1	1	0	0	0	1	1
1	1	1	1	1	1	1

Утверждение 7.

x1	x2	x3	x2x3	x1(x2x3)	x1+x2	x1+x3	(x1+x2)(x1+x3)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	0	0
1	1	0	0	1	0	1	0
1	1	1	1	0	0	0	0

Утверждение 8.

,

конъюнкция дистрибутивна по отношению к сумме по модулю два.

x1	x2	x3	x2+x3	x1(x2+x3)	x1x2	x1x3	(x1x2)+(x1x3)
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	0	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	0	0	1	1	0

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

Определение

Переменная x булевой функции f(x…) называется существенной, если существует набор значений остальных переменных функции, что изменение значения переменной при данном наборе остальных переменных изменяет значение функции.

Пример: x₁ и x₂  существенные переменные (x_{1 по 8 –му и по 5-му наборам;} x₂

_{по 6 и 8 наборам).}

x₃  не существенная переменная

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Определение

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

Теорема: Число различных (неодинаковых) булевых функций от n переменных есть .

Теорема будет следовать из следующего утверждения:

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

Докажем утверждение индукцией по длине n набора.

Для n=1 имеем 0;1 два различных набора длины 1;

2¹ =2. Для n=1 утверждение индукции справедливо.

Пусть утверждение индукции справедливо для n1, то есть число различных двоичных наборов длины n1 есть  2ⁿ.

Покажем справедливость утверждения для n=n+1. Разобьем все двоичные наборы длины n+1 на две группы. В первую группу отнесем двоичные наборы, которые начинаются на 0. Во вторую группу отнесем двоичные наборы, которые начинаются на 1, например, для n+1 = 3 будет такое разбиение:

0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

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

Но по предположению индукции наборов длины n имеется 2ⁿ, поэтому число наборов как в первой, так и во второй группе будет 2ⁿ, поэтому общее число наборов длины (n+1) будет 2ⁿ+2ⁿ = 2ⁿ2 = 2ⁿ⁺¹

Утверждение доказано.

x1	…	xn	f(x1…xn)
0	…	0	*
2n …	…	…	…
1	…	1	*

Функций от n переменных будет ровно столько, сколько существует разных двоичных наборов длины 2ⁿ.

По предыдущему утверждению это число есть . Теорема доказана.

Определение :

Элементарной конъюнкцией на множестве переменных {x₁…x_n} называют функцию логического произведения множителей , где каждый множитель либо переменная, либо отрицание переменной.

В дальнейшем значение в элементарной конъюнкции будем опускать или заменять.

Например: { x₁ x₂ x₃ x₄ }

x₁ x₂ x₄ ; эта функция равна 1, только на одном наборе:

1 0 1 x₁ x₂ x₄=1

x₁ x₂ x₄

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

Например:

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

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

Определение

Элементарной дизъюнкцией на множестве переменных {x₁…x_n} называют функцию логического сложения слагаемых , где каждое слагаемое либо переменная, либо отрицание переменной.

Например: { x₁ x₂ x₃ x₄

x₁ x₂ x₄ ; эта функция равна 0, т. и т.т., когда все слагаемые равны 0. т.е. на наборах 0110 и 0100

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

приведем дизъюнкции к нужном виду; полученная дизъюнкция будет тождественно равна первоначальной.

В силу коммутативности и ассоциативности элементарные дизъюнкции равны, т . и т. т., когда они состоят из одного и того же набора слагаемых.

Дизъюнктивной нормальной формой (ДНФ) на множестве переменных (x₁…x_n) называют функцию логического сложения некоторых слагаемых, где каждое слагаемое есть элементарная конъюнкция на (x₁…x_n) :

{ x₁ x₂ x₃ x₄ }

ДНФ называется совершенной (СДНФ), если каждая элементарная конъюнкция имеет ранг n :

Далее считаем, что слагаемые ДНФ не повторяются (в противном случае можно

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

Теорема о представлении любой булевой функции в виде СДНФ : для любой булевой функции справедлива следующая формула :

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

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

Свойства

1)

2)

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

.

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

Таким слагаемым будет слагаемое, которое соответствует единичному набору , совпадающего с набором .

.

Значение этого слагаемого на наборе есть

в силу того ,что значение каждого множителя равно 1. Последнее справедливо в силу свойства символа .

. То есть левая часть равна 0. Покажем, что и правая часть также равна 0. Для этого нужно показать, что значение всех слагаемых равно 0. Рассмотрим произвольное слагаемое правой части, которое соответствует некоторому двоичному набору , тогдав силу, того, что наборы и  различны, т.к.  - набор, на котором значение функции равно 0, а  - набор, на котором значение функции равно 1. Так как наборы различны, то существует множитель i: , а поэтому и все произведение равно 0.Таким образом каждое слагаемое равно 0, следовательно и вся сумма равна 0, значит правая часть равна 0.

Теорема полностью доказана.

x1	x2	x3	f
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	1	0	1	1	0	0	1
0	1	1	0	0	0	0	0
1	0	0	1	0	1	0	1
1	0	1	1	0	0	1	1
1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0

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

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

Рассмотрим произвольный набор значений переменных , и покажем, что левая и правая часть равны. Левая часть -.

В правой части рассмотрим слагаемое, в котором значение набора  совпадает с первыми k-компонентами набора : .

Значение этого слагаемого на наборе равно.

В силу того, что набор  и первые k-компонент набора  совпадают, рассматриваемые множители равны 1, все слагаемое равно . Все остальные слагаемые равны 0 в силу того, что среди множителейобязательно найдется множитель, в котором и  различаются, а это нулевой множитель. Поэтому правая часть равна (все слагаемые, кроме быть может одного, равны 0).

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

Нетрудно убедиться в справедливости следующих тождеств:

1. 6)

2. 7)

3. 8)

4. 9)

5. 10)

Доказательство предлагается в качестве домашних упражнений.

Последние два тождества называются правилами Де-Моргана.

Определение.

Двойственной к функции называют функцию .

Например, двойственной к конъюнкции является

дизъюнкция, и наоборот, двойственной к дизъюнкции является конъюнкция.

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 1

Утверждение. Двойственной к двойственной функции есть сама функция, т.е.

Теорема о представлении булевой функции в виде конъюнктивной нормальной формы .

КНФ называют логическое произведение некоторых сомножителей, где каждый сомножитель есть элементарная дизъюнкция. КНФ от переменных {x₁…x_n} называется СКНФ, если каждая дизъюнкция полного ранга, то есть в каждую дизъюнкцию входят все n переменных.

Пример: { x₁ x₂ x₃ }

КНФ :

СКНФ:

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

Пример:

x1	x2	f
0	0	0
0	1	1
1	0	0
1	1	0

Доказательство : рассмотрим произвольный набор значений переменных . Либо, либо.

1. Левая часть равенства равна 1. Покажем, что и правая часть равна единице. Рассмотрим произвольный множитель правой части . Значение этого множителя на набореравнот.к. существует i такое, что, что верно в силу того, что - набор, на котором значение f () = 1, а  - набор, на котором значение f()= 0, то есть  и  - два различных набора, а поэтому есть компонента, в которой они отличаются.

Поэтому ; т.к.,.

2. Пусть . Покажем, что и правая часть равна 0. Для этого достаточно показать, что существует множитель, который равен 0 на наборе. Действительно, рассмотрим множитель соответствующий набору правой части , который совпадает с набором.

В силу того, что есть ноль функции, наборсуществует. Тогда значение рассматриваемого множителя на наборе равно

(т. к.для всех i :). А так как существует множитель, равный 0, то и значение всей СКНФ = 0.

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

Для любой булевой функции f(x₁…x_n) тождественно выполнено :

Доказательство. Рассмотрим произвольный набор . Значение левой части есть.

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

Тогда все произведение есть . Что и требовалось доказать.

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

Определение : Полиномом Жегалкина называется сумма по модулю 2 (+) некоторого количества слагаемых, где каждое слагаемое есть элементарная конъюнкция переменных без отрицания.

Пример:

1+x₁x₂+x₃+x₁x₄x₅

Полином Жегалкина, не содержащий ни одного слагаемого, равен 0.

Далее будем рассматривать так называемые приведенные полиномы Жегалкина, т.е. полиномы, в которых все слагаемые различные конъюнкции.

Например 1+x₁x₂+x₃+x₁x₄x₅ (нет двух одинаковых слагаемых).

Если некоторые слагаемые повторяются, то используя правило x+x=0, нетрудно привести любой полином к приведенному виду.

Например x₁x₂+x₃+x₁x₂+x₁x₄x₅+x₃=x₁x₄x₅

Если слагаемое повторяется нечетное количество раз, то оставляем его в единственном экземпляре.

Теорема о представлении булевой функции в виде полинома Жегалкина .

Для любой булевой функции существует представление в виде полинома Жегалкина и это представление единственно.

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

Пример 1:

x1	x2	x3
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Первая часть теоремы следует из теоремы о представлении булевой функции в виде СДНФ. А именно рассмотрим для булевой функции ее СДНФ. Далее операцию выразим через операциюпо правилу Де Моргана.

После чего операцию выразим через операциюи приведем полученную формулу к нормальному виду полинома Жегалкина раскрыв скобки в полученном выражении, используя дистрибутивность конъюнкции по отношению к сумме по модулю два. Для функции из примера1 СДНФ имеет вид :

Покажем, что полученный полином единственен с точностью до перестановки слагаемых и множителей в слагаемых полинома.

Допустим противное : , которая имеет два различных полинома Жегалкина:

Из этих равенств следует,что

прибавим к обеим частям равенства :

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

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

Упражнение: найдите полином Жегалкина следующих функций :

1) 4)

2) 5)

3) 6)

Упражнение

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

л

Т.е в формуле представления функции в виде СДНФ можно заменить логическое суммирование на суммирование по модуля 2.

Определение

Пусть – конечное множество. Отношением на данном множестве будем называть любое подмножество его декартового произведения.

Рассмотрим декартово произведение на себя: . Т.е. это множество всевозможных слов из двух букв в алфавите .

Определение

Отношением эквивалентности называется подмножество декартового произведения, которое удовлетворяет следующих трем свойствам:

1. Рефлексивность. .

2. Симметричность. .

3. Транзитивность. .

Примеры отношения эквивалентности.

Пример 1. Рассмотрим в качестве множества X множество натуральных чисел: . Для него рассмотрим обычное равенство натуральных чисел. Скажем, что два натуральных числа эквивалентны, если они равны в обычном смысле. Очевидно, что это есть отношение эквивалентности.

Пример 2. Рассмотрим произвольное натуральное число . Числа x и y назовем эквивалентными , если они дают один и тот же остаток при делении на . Очевидно, что это есть отношение эквивалентности.

Пример 3. Введем отношение эквивалентности на множестве слов, длина которых не меньше числа . Рассмотрим множество этих слов в алфавите . Скажем, что пара слов и эквивалентны, если совпадают их первые букв. Убедитесь сами, что все три свойства эквивалентности выполнены.

Утверждение. Пусть – множество, – отношение эквивалентности на нем. Тогда разбивает все элементы на классы эквивалентных элементов (Любая пара различных классов не пересекается между собой-, и их объединение совпадает с множеством;; количество классов может быть бесконечным). Любая пара элементов одного класса эквивалентна, а любая пара элементов различных классов не эквивалентна. Данное разбиение однозначно определяется отношением эквивалентности .

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

Определение: суперпозицией булевых функции

называется функция

, полученная путем подстановки

функциив функциювместо некоторой переменной:.

Замечание 1

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

Замечание 2

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

Определение

Будем различать переименование двух видов:

переименование с отождествлением, как в предыдущем примере (переменная переименуется в другую переменную этойже функции );

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

Определение

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

Например эквивалентныи.

Функции и не эквивалентны, так как эквивалентные функции имеют одинаковое число существенных переменных.

Утверждение Двойственная суперпозиции функций- есть суперпозиция двойственных.

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

Тогда утверждение о представлении функции в виде СКНФ непосредственно следует из аналогичного утверждения о представлении функции в виде СДНФ.

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

Теорема о представлении любой булевой функции в виде СДНФ : для любой булевой функции справедлива следующая формула :

Чтобы провести это сведение возьмем двойственную функцию

и представим ее в виде СДНФ:

, тогда справедливы выкладки:

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

Замечание 3

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

Замечание 3

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

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

Пример 1:

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

Пример 2:

Упражнение

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

Определение : замкнутой системой функции называют систему, замыкание которой совпадает с самой системой .

Пример 3:

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