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

Определение 1.1. Двоичной функцией от N (N ³ 1) переменных называется функция , аргументы и значения которой выбираются из множеств , т. е.

F: ,

Где

, .

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

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

.

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

Таблица 1.1

Номер набора

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.3. Число двоичных функций от N переменных равно .

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

Таблица 1.2

X1 \ F

F0

F1

F2

F3

0

0

0

1

1

1

0

1

0

1

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

0

1

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

Функций от двух переменных — шестнадцать (табл.1.3).

Таблица 1.3

,\ 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

XX2

X1

X2

XX2

XX2

Продолжение табл.1.3

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

Обозначение

XX2

X1 ~ X2

X1 ® X2

XX2

1

Важнейшими из них являются:  — конъюнкция (X1 X2, X1 & X2, X1X2),  — сложение по модулю 2 (X1X2),  — дизъюнкция (X1X2),  — функция Пирса (X1X2),  — импликация (X1X2),  — функция Шеффера (X1| X2).

Определение 1.4. Переменная 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 чрезвычайно быстро. В табл.1.4 приведена зависимость функций от своих переменных при N £ 8.

Таблица 1.4

N

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

1

2

2

16

3

256

4

65536

5

4294967296

6

> 1.8 ×1019

7

> 3.4 ×1038

8

> 1.1 ×1077

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

Определение 1.5. Множество двоичных наборов {(A1, ..., AN) Î Î| F(A1, ..., AN) = 1}, на которых функция F принимает значение 1, называется Областью истинности функции F. Мощность области истинности функции F называется Весом функции F и обозначается || ||.

Очевидно, что 0 £ || F || £ 2N, причем равенства достигаются лишь для функций-констант 0 и 1. Если || F || = 2N-1, то функция F называется Равновероятной.

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

© 2011-2024 Контрольные работы по математике и другим предметам!