Функции алгебры логики


Пусть E2 = {0,1} есть двухэлементное множество. Набор длины n из 0 и 1 есть последовательность длины n, состоящая из 0 и 1.

Пример: (0), (1) – набор длины 1.
(0,0), (0,1), (1,0), (1,1) – длины 2.
(0,0,…,0), (0,0,…,1), …, (1,1,…,1) – набор длины n.

Теорема: Число h(n) всех наборов длины n из 0 и 1 равно 2n.
Доказательство: Индукцией по n.
Базис: n=1, h(1) = 2 =21.
Предположение индукции: Допустим h(n) = 2n.
Шаг индукции: покажем, h(n+1) = 2n+1. Разобьем все наборы длины n+1 на 2 класса: класс наборов, начиная с 0, и класс наборов, начинающихся с 1.
0, 0,0,…,0,0 1, 1,0,…,0,0
0, 0,0,…,0,1 1, 1,0,…,0,1

0, 0,1,…,1,1 1, 1,1,…,1,1

Длины n, их 2n Длины n, их 2n

Все наборы их 2n+1
h(n+1) = 2n+2n = 2 * 2n = 2n+1 доказано.

Определение: Функция алгебры логики(булева функция) есть функция, аргументы и значения которой есть лишь 0 или 1.

Пусть P2 – множество всех функций алгебры логики.

Теорема: Число всех n-местных (n-аргументных) функций алгебры логики f(x1, x2,…,xn) равно 22n.

Доказательство: Перечислим все n местные функции следующим образом:
X1 X2 Xn-1 Xn F0 F1 … Fк
0 0 … 0 0 0 0 … 1
0 0 … 0 1 0 0 … 1
… … … … … … … … …
1 1 … 1 0 0 0 … 1
1 1 … 1 1 0 1 … 1

Число строк = 2n, т.е. число всех наборов длины n из 0 и 1. Число всех n-местных функций 22n, т.е. число всех наборов длины 2n из 0 и 1. чтд.


Комментарии запрещены.




Статистика