Пусть 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 равно 2ⁿ.
Доказательство: Индукцией по n.
Базис: n=1, h(1) = 2 =2¹.
Предположение индукции: Допустим h(n) = 2n.
Шаг индукции: покажем, h(n+1) = 2ⁿ⁺¹. Разобьем все наборы длины 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) = 2ⁿ+2ⁿ = 2 * 2ⁿ = 2ⁿ⁺¹ доказано.

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

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

Теорема: Число всех n-местных (n-аргументных) функций алгебры логики f(x₁, x₂,…,x_n) равно 2²ⁿ.

Доказательство: Перечислим все n местные функции следующим образом:
X₁ X₂ X_n-1 X_n F₀ F₁ … 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

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

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