Введение в логику

Функции многих переменных

Показывать лекцию целиком
Записаться

Понятно, что кроме унарных и бинарных функций существуют функции многих переменных – произвольной арности. Унарных функций – 4, бинарных – 16. А сколько функций от n переменных? Докажем следующую теорему:

Теорема о числе логических функций:

Число логических функций от n переменных С задается соотношением:

$$C=2^{2^n}$$

Доказательство. Ранее мы установили, что кортежей в области определения функции $$2^n$$. Для каждого из них нужно задать значение функции. Определение каждой функции можно рассматривать как двоичное слово длины $$2^n$$. Применяя лемму о числе слов в двоичном алфавите, получаем требуемое соотношение.

Функций от одного аргумента - $$ 2^{2^1} = 4$$. Функций от двух аргументов - $$ 2^{2^2} = 16$$. Функций от трех аргументов - $$ 2^{2^3} = 256$$. С ростом числа аргументов число различных функций стремительно возрастает.

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^