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

Страница 3

Таблица всех элементарных булевых функций, применяемых в записи формул

X	Y	0	&	_ Y®X	X	_ X®Y	Y	+	V	¯	~	_ Y	X ®Y	_X	Y®X	/	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

Суперпозиции булевых функций

Ф = {ф1…фk}

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

1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

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

Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)

Ф(1) – множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.

Функция g называется суперпозицией функций из системы, если

$ N : g Î Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

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

G = Fф

Суперпозиция элементарных булевых функций – формула.

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

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

X ® Y = X V Y

_ _

X ¯ Y = X Y

Лекция 4

Дизъюнктивные нормальные формы (ДНФ)

Конъюнктивные нормальные формы (КНФ)

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

_

Xа = X, если а = 1 и X, если а = 0

Элементарной конъюнкцией (ЭК) называется выражение вида

X1a1 X2a2…Xnan

ЭК называется правильной, если все входящие в неё переменные различны.

Правильная ЭК называется полной относительно данного набора переменных, если в неё входят все эти переменные.

Для элементарных дизъюнкций (ЭД) – аналогичный набор определений.

ЭД – выражение вида

X1a1 V X2a2 V…V Xnan

ДНФ – дизъюнкция разных правильных элементарных конъюнкций.

X1 V X1X2 V X1X2X3 – ДНФ.

ДНФ называется совершенной (СДНФ), если все входящие в неё элементарные конъюнкции полны относительно данного набора переменных.

КНФ – конъюнкция разных правильных элементарных дизъюнкций.

СКНФ – совершенная КНФ. У нее все ЭД полны.

Теорема.

Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде СДНФ по формуле:

F(x1… xn) = V(X1a1 X2a2…Xnan)

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

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

1. F = G

N(f) Ì N(G) – носители функции.

" a Ì N (F) Þ F(a…an) = 1

G(a) = G(a…an) = (aa…anan) V (…) , где пустые скобки – оставшееся выражение.

Подставив координаты, получим:

1*1V(…) = 1 ) Þ a Ì N (G) ÞN(F) = N(G)

2. b Î N(G)

G(b bn) = 1 – тогда, когда хотя бы одна

b1a1 b2a2 …bnan = 1 Þ b1 = a …bn = an b = a Þ N(G) = N(F)

Первая часть доказана.

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

Посчитаем, сколько полных ЭК может быть

Всего – 2n = N (по перестановке комбинаций)

Число СДНФ – 2N-1 – число различных формул СДНФ.

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

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