Дискретная математика (Конспекты 15 лекций)

Страница 6

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

1. Существование

F = ДНФ = F{&,V, NOT}

X V Y = XY+X+Y

NOT(X) = X+1

Из этого следует, что функция представима в виде МЖ.

2. Единственность

Сосчитаем МЖ

ЭК без отрицания 2n – 1 + 1

Всего разных многочленов Жегалкина 2N – 1, где N = 2n

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

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

Классы функций. Замкнутые и незамкнутые классы. Получение констант и элементарных булевых функций из заданной системы функций

Определение. Функция называется линейной, если ее многочлен Жегалкина не содержит ни одной конъюнкции переменных.

Замкнутые классы функций.

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

Пусть дан класс функций B (т.е. конечное или бесконечное множество функций),объединенных по общему признаку. Замыканием этого класса (обозначение – [B]) будем называть множество всех суперпозиций функций из класса B.

Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

B = [B]

Теорема 1

Класс всех линейных функций замкнут.

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

Пусть L – класс линейных функций (так и будем обозначать в дальнейшем).

L = {a0+a1x1+a2x2+…+anxn}

Подставим вместо переменной x в одну из функций функцию y такого же вида.

Получим

L = [L].

Утверждение (теорема 2)

Необходимое условие линейности.

Если функция линейна и не равна некоторой постоянной, то на половине своих наборов она равна 1.

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

Функция называется самодвойственной, если двойственная к ней функция является самой этой функцией. F* = F.

S – класс всех самодвойственных функций.

Класс S является функционально замкнутым.

Доказательство следует из принципа двойственности.

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

Функция называется монотонной, если из условия a £ b следует, что f(a) £ f(b).

Теорема.

Класс M монотонных функций замкнут.

Свойство.

У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то есть все простые импликанты не содержат отрицаний.

Другие замкнутые классы

T0 – константа 0 (класс функций, обращающихся на нулевом векторе в 0).

Т1 – константа 1 (класс функций, обращающихся на единичном векторе в 1)

Теорема

Классы Т0 и Т1 функционально замкнуты.

Лемма о несамодвойственной функции.

Если функция несамодвойственна, то путем подстановки вместо аргументов переменной x или not(x) можно получить константу.

011 – нарушена самодвойственность

f(not(x),x,x) = const = 1 при любом x.

001 – нарушена самодвойственность

Если 0, то х с отрицанием, если 1, то без отрицания.

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

F Ï S Þ $a : F*(a) ¹ F(a) Þ F*(a) = F(a)Þ F(a) = F(a) Þ F(a) = F(a)

f(x) = {x1a, x2a2, … xnan}

f(0) = {0a, 0a2, … 0an}

Путем подстановки получаем, что f(x) = const.

Лемма о немонотонной функции

Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).

000 £ 001

F(000) = 1 F(001) = 0

F(00X) = NOT(X)

F(100) = 1

F(110) = 0

100 < 110

F(1,x,0) = NOT(X)

Лемма о нелинейной функции

Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

_

F(x0y) = (xy)

Лекция 9

Доказательство леммы 3

F(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)

Вместо x1…xn ставим константы a1…an, такие, что

f1(a1…an) = 1

1. A = B = 0

F(x1x2…a3…an) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.

1. Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).

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

[S] = [B] = B

Но S - множество всех булевых функций, а B – не всех.

Получили противоречие.

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

Дано

S Ë {S, M, L, T0, T1}

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

1. Получение констант.

F1(00…0) = 1

a) F(111) = 1

b) F(111) = 0

F(xxxx) = 1

F2(111) = 0

2. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

3. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

Лекция 10

Функциональные элементы. Схемы

F

Функциональный элемент с n упорядоченными входами и одним выходом

.

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

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

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

Два и более входов можно отождествлять.

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

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

Число функциональных переменных считаем сколь угодно большим.

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

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

Пример полного базиса.

	&

V