Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Томский Политехнический Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

DisMathTPU

.pdf

Скачиваний:

Добавлен:

29.05.2015

Размер:

753.61 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 1713 14 15 16 17 > Следующая >>>

121

13.4. Упражнения

Построить кратчайшие системы ДНФ для систем неполностью определенных булевых функций F = ff1; f2; f3g è G = fg1; g2g по матрицам Грея.

Минимизировать те же системы, пользуясь методом конкурирующих интервалов, и ñðàâнить полученные ðåçóльтаты.

c	c		c

d	d	d

f1(a; b; c; d)

f2(a; b; c; d)

f3(a; b; c; d)

g1(a; b; c; d; e)

g2(a; b; c; d; e)

14. Контрольная работа 4

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

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

Задания на контрольную работу (система функций F)

122

7) a

123

10)

11)

12)

13)

14)

15)

124

16)

17)

18)

19)

20)

21)

125

22)

23)

24)

25)

26)

27)

126

28)

29)

30)

15. Важнейшие замкнутые классы булевых функций

Определение. Булева функция f(x1; : : : ; xn) называется суперпозицией булевых функций

f0(y1; : : : ; ym); f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn);

åñëè f(x1; : : : ; xn) представима через них формулой

F = f0(f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)):

Пример. Пусть заданы булевы функции:

f0(y1; y2; y3) = y1y2 ! y3 y1;

f1(a; b) = a _ b; f2(a; b; c) = b # ac; f3(a; b; c) = a ! b ! c:

Их суперпозицией является функция

f(a; b; c) = (a _ b)(b # ac) ! (a ! b ! c) (a _ b):

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

127

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

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

Определение. Булева функция сохраняет константу 0 (принадле- жит классу T 0), если на наборе из всех нулей функция принимает значе-

íèå íîëü.

Примеры. Мажоритарная булева функция сохраняет константу 0 (принадлежит классу T 0):

x y z f(x; y; z)

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

Из элементарных булевых функций классу T 0 принадлежат, например, конъюнкция и тождественная функция; не принадлежат классу T 0, íà- пример, штрих Шеффера и стрелка Пирса.

Утверждение о числе булевых функций класса T 0. Число раз-

личных булевых функций, зависящих от n переменных и сохраняющих константу 0, равно 22n 1:

Доказательство. Число различных булевых функций n аргументов рав- íî 22n (по теореме о числе булевых функций). В векторном представле-

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

компоненте ноль, поэтому число функций, сохраняющих константу 0, есть

22n=2 = 22n 1.

Пример. Из всех 16 булевых функций двух аргументов x1, x2 8 ôóíê-

öèé (222 1) принадлежат классу	T	0: 0,	^	, , , , , - и тождественные
	T		^	_ !

функции x1 è x2.

128

Теорема о замкнутости класса T 0. Множество всех булевых функций, сохраняющих константу 0, является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций èç T 0, то есть функцию

f(x1; : : : ; xn) = f0(f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn));

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

f(0; : : : ; 0) = f0(f1(0; : : : ; 0); : : : ; fm(0; : : : ; 0)) =

[учтем, что f1(x1; : : : ; xn) 2 T 0; : : : ; fm(x1; : : : ; xn) 2 T 0 ]

=f0(0; : : : ; 0) = [ учтем, что f0(y1; : : : ; ym) 2 T 0 ] = 0:

Из этого следует, что суперпозиция f(x1; : : : ; xn) принадлежит классу T 0, значит, класс T 0 замкнут.

Лемма о булевой функции, не сохраняющей константу 0. Если булева функция не сохраняет константу 0, то из нее подстановкой вместо каждого аргумента переменной x можно получить либо константу 1, либо

инверсию x.

Доказательство. Рассмотрим булеву функцию f(x1; : : : ; xn), не сохраняющую константу 0. Заменив каждый ее аргумент xi íà x (такая подстановка допустима по условию леммы), получим функцию одного аргумента g(x) = f(x; : : : ; x): Исследуем ее.

g(0) = f(0; : : : ; 0) = 1; òàê êàê f(x1; : : : ; xn) 2= T 0:

Åñëè g(1) = 1, òî g(x) константа 1. Если g(1) = 0, òî g(x) = x.

Примеры. Рассмотрим две функции, не сохраняющие константу 0: стрелку Пирса a # b и импликацию a ! b. Подставляя в них вместо аргументов

переменную x, получаем:

x # x = x; x ! x = 1:

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

Определение. Булева функция сохраняет константу 1 (принадле- жит классу T 1), если на наборе из всех единиц функция принимает зна-

чение единица.

129

Примеры. Мажоритарная булева функция сохраняет константу 1. Из элементарных булевых функций таковыми являются, например, дизъюнкция и конъюнкция. Не сохраняют константу 1, например, штрих Шеффера и стрелка Пирса.

Утверждение о числе булевых функций класса T 1. Число раз-

личных булевых функций, зависящих от n переменных и сохраняющих константу 1, равно 22n 1:

Пример. Из всех 16 булевых функций двух аргументов x1; x2 8 ôóíê-

öèé (222 1) принадлежат классу T 1: 1, ^, _, , !,	и тождественные
функции x1 è x2.

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

Доказательства утверждения и теоремы аналогичны доказательствам соответствующих результатов для класса T 0.

15.3.Класс линейных булевых функций

15.3.1.Полином Жегалкина

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

Примеры. K1+ = x1x2x3, K2+ = x4, K3+ = 1.

Определение. Полиномом Жегалкина, или алгебраической нормальной формой (АНФ), булевой функции f(x1; : : : ; xn) называется дизъюнкция с исключением различных положительных конъюнкций переменных из множества X = fx1; : : : ; xng, то есть формула вида

P = K1+ : : : Kp+;

задающая функцию f(x1; : : : ; xn).

Пример. P = x1x3 x1x2x4 x2 1 полином Жегалкина.

Определение. Длиной полинома Жегалкина назовем количество конъюнкций в полиноме, а его степенью наибольший из рангов конъюнкций, входящих в полином.

Пример. Длина полинома Жегалкина из предыдущего примера равна 4, а степень 3.

130

Условимся считать константу 0 полиномом длины и степени 0. Определение. Полином Жегалкина называется линейным, если его

степень не превышает единицы.

Примеры. P1 = 1, P2 = x y 1 линейные полиномы.

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

Свойства 0 и 1:	x 0 = x; x 1 =		.
		x
Закон коммутативности:	x y = y x.
Закон ассоциативности:	x (y z) = (x y) z = x y z.
Закон дистрибутивности:	x(y z) = xy xz.

Добавим к ним еще две равносильности (первая очевидна, доказательство второй предоставляется читателю):

x x = 0;

x _ y = x y xy:

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

K1 _ K2 = K1 K2 K1K2:

Для ортогональных конъюнкций равносильность примет вид:

K1 _ K2 = K1 K2:

В частности, совершенная ДНФ булевой функции f(x1; : : : ; xn) состоит из попарно ортогональных конъюнкций, значит

1	_		c1	cn		M		c1	cn
1	_		f	: : : xn =		M		f	: : : xn :
f(x1; : : : ; xn) =			x1	: : : xn =	c1	::: cn		x1	: : : xn :
c ::: cn		2	M1		c1	::: cn	2	M1
		2					2

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

Доказательство. Константа 0 это полином Жегалкина по договоренности. Любая другая булева функция f(x1; : : : ; xn) представима совершен-

ной ДНФ (С. 38), а значит, как только что было показано, и формулой

âèäà:

f(x1; : : : ; xn) = M xc11 : : : xcnn:

c1::: cn2Mf1

Эта формула не является полиномом Жегалкина, если содержит переменные с инверсиями. От инверсий можно избавиться, используя равносильность x = x 1. Раскрыв в полученной формуле скобки на основе закона

<<< < Предыдущая 1 2 3 4 5 6 7 8 9 10 11 1213 / 1713 14 15 16 17 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
21.09.201964.51 Кб0Delphi отчёт.doc
#
15.11.2019158.72 Кб3Diagramma_otchet.doc
#
29.05.20153.1 Mб51DIF_calc_2013.pdf
#
29.05.20152.58 Mб46Diplom.docx
#
29.05.20155.95 Mб19Diplom_na_pechat.doc
#
29.05.2015753.61 Кб65DisMathTPU.pdf
#
29.05.2015753.84 Кб64DisMathTPU_new.pdf
#
29.05.20158.69 Mб33dissertatsia.doc
#
25.03.2016419.15 Кб4Dokument_Microsoft_Office_Word_2.PDF
#
29.05.2015118.78 Кб20Dokument_Microsoft_Word (1).doc
#
23.12.201838.93 Кб4Dokument_Microsoft_Word_4.docx