lec02

Пример. 2.3. Способы задания булевой функции: геометрически.

Звездочкой обозначены единичные вершины. Носитель:

Nf : = { Вn ( ) = 1} = { (001), (100),(101) }

x3

x2

x1

31

Вес булевой функции.

Весом wt булевой функции (x1, x2, … xi, … xn) называется количество единичных наборов при которых (x1, x2, … xi, … xn) принимает значение 1.

Т.е. если БФ (x1, x2, … xi, … xn) размерности n задана вектором= ( 1, 2, … i …, N) длины N=2n, то

Пример 2.4. Для (x1,x2,x3) = (01001100) – носитель Nf = { (001), (100), (101) }

его вес – wt( (x1,x2,x3)) = | Nf | = 3.

32

Расстояния между БФ.

Расстоянием (числом Хемминга) ρ между двумя булевыми функциями f и g (размерности n), заданных векторами

= ( 1, 2, … i …, N) и = ( 1, 2, … i …, N) длины N=2n

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

=1

33

Расстояние между БФ. Пример.

Пример 2.5. БФ заданы векторами.

(x1,x2,x3): = (11101001), g(x1,x2,x3): = (00101111).

Расстояние между и g - ρ( , )=4 (различия в 1-м, 2-м, 6-м и 7-м разрядах).

Вектора и называются соседними, если ρ( , )=1.

Вектора и называются противоположными, если ρ( , )=N.

Можно связать операциями противоположные и ?

ρ( , )=N =

34

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

(x); n=1;

22 = 4 – всего 4 булевых функции

f1(x) 0; f2(x) x; f3(x) ; f4(x) 1.

Булевы функции: константы, тождество и отрицание.

35

Булева функция двух переменных.

Пусть задана (x1, x2, … xi, … xn). xn называется фиктивным переменным, если его значения не влияют на значение функции:

(x1, … xi, … xn-1, 0) = (x1, … xi, … xn-1, 1);

(x1, … xi, … xn-1).

xn называется существенным переменным, если вариация его значения влияет на значение функции:

(x1, … xi, … xn-1, 0) ≠ (x1, … xi, … xn-1, 1);

(x1, … xi, … xn-1).

36

Булева функция двух переменных.

В частности, (x) входит в перечень функций от 2 переменных (которыми и задается).

(x1,x2) (x1). (x1,x2) (x2). также (x1,x2) ().

(x1,x2); n = 2; 222 = 16

Из них 2 константы (без переменных), 4 функции одного переменного, а 10 функций существенно зависят от двух переменных.

37

Булева функция двух переменных.

Основные функции:

( x) = ; (x1 ∩ x2) = x1 & x2; (x1 x2) = x1 x2.

Новые функции через основные:

Импликация: x1 x2 = 1 x2.

Штрих Шеффера (отрицание конъюнкции): x1 | x2 = 1 & 2;

x1 x2 = 1 2; x1 x2 = 1· 2 x1·x2;

x1 x2 = 1·x2 x1· 2;

Элементарные функции: константы, тождество, основные функции и: , , , ,

38

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

39

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

40