litceysel.ru
добавить свой файл
1 2 3 4
Лекция №1


Основные способы задания двоичных функций



§1.1 Табличный способ задания


Определение 1.1.1 Двоичной функцией от n (n 1) переменных называется функция f(x1, ..., xn), аргументы и значения которой выбираются из множества F2={0;1}, т.е. f:
F2, где = {a=(a1, ... ,an) | aiF2, i(1,... ,n)}


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


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


определим его номер


N(a) = a12n-1 + a22n-2 +...+ an-121 + an20


Тогда двоичная функция однозначно может быть задана следующей таблицей

таблица 1.1.3

Номер набора


x1 ... xn-1 xn

f(x1, ..., xn)

0

0...0 0

f(0, ..., 0,0)

1

0...0 1

f(0, ..., 0,1)

.

.

.

.

.

.

.

.

.

2n-2

1...1 0

f(1, ..., 1,0)

2n-1

1...1 1

f(1, ..., 1,1)


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


Утверждение 1.1.4 Число двоичных функций от n переменных

равно



Перечислим все двоичные функции от одной и двух переменных. Имеется четыре функции от одной переменной

Таблица 1.1.5

x1 \ f

f0

f1

f2

f3

0

0

0

1

1

1

0

1

0

1

Условное обозначение

0

x1



1

Функции f0 и f3 не зависят от значения переменной x1 и называются константными ( f0(x1) 0, f3(x1) 1). Функция f1(x1) = x1 называется тождественной функцией, а функция f2(x1) =

называется отрицанием.


Функций от двух переменных – шестнадцать.

Таблица 1.1.6

x1, x2\ f

f0

f1

f2

f3

f4

f5

f6

f7

0 0

0

0

0

0

0

0

0

0

0 1

0

0

0

0

1

1

1

1

1 0

0

0

1

1


0

0

1

1

1 1

0

1

0

1

0

1

0

1

Обозначение

0

x1 x2




x1




x2

x1 x2

x1 x2



x1, x2\ f

f8

f9

f10


f11

f12

f13

f14

f15

0 0

1

1

1

1

1

1

1

1

0 1

0

0

0

0

1

1

1

1

1 0

0

0

1

1

0

0

1

1

1 1

0

1

0

1

0

1

0

1

Обозначение


x1x2

x1~x2








x1 x2

x1| x2

1




Важнейшими из них являются:


f1 - конъюнкция (x1 x2, x1 & x2, x1x2)

f6 - сложение по модулю 2 (x1 x2 )

f7 - дизъюнкция(x1 x2)

f8 - функция Пирса (x1x2)


f13 - импликация (x1 x2)

f14 - функция Шеффера (x1| x2)


Определение 1.1.7 Переменная xi , или i-ая переменная двоичной функции f(x1,... , xn) называется существенной переменной функции f(т.е. функция f существенно зависит от xi), если существует набор

(a1,..., ai-1, ai+1,..., an) такой, что

f (a1,..., ai-1,0, ai+1,..., an) f (a1,..., ai-1,1, ai+1,..., an)

В противном случае переменная xi называется несущественной (фиктивной) переменной функции f.


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

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


Таблица 1.1.8


n

число функций от n переменных

1


2

2

16

3

256

4

65536

5

4294967296

6

> 1.8 1019

7

> 3.4 1038

8

> 1.1 1077


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



следующая страница >>