Функции и таблицы истинности

Поскольку область определения логической функции конечна, то функцию можно задать явным образом, перечислив значение функций для каждой точки из области определения. Сколько точек в области определения логической функции от n переменных? Функция от n переменных определена на кортежах длины n. Поскольку речь идет о логических функциях, аргументы которых принимают только два значения - 0 и 1, то кортежи можно рассматривать как слова длины n в алфавите \{0, 1\}.

Справедлива следующая теорема: Область определения логической функции от $$n$$ переменных содержит $$2^n$$ кортежей, представляющих слова длины n в алфавите $$\{0, 1\}$$.

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

Таким образом, чтобы явно задать функцию, можно перечислить все возможные кортежи – их $$2^n$$, и для каждого из них задать значение функции на данном кортеже. Задать функцию можно таблицей, которую принято называть таблицей истинности. Эта таблица содержит $$2^n + 1$$ строк и $$n + 1$$ столбец. Первая строка – это строка заголовков содержит имена переменных и имя функции. В следующих строках в первых n столбцах содержатся значения кортежей, в последнем столбце – значение функции для соответствующего кортежа.

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

При построении таблицы истинности принято упорядочивать кортежи. Поскольку каждый кортеж – является двоичным словом, то его можно рассматривать как запись в двоичной системе целых чисел от 0 до числа $$2^n – 1$$. Кортежи упорядочиваются в соответствии с их числовыми значениями. Первый кортеж представляет число 0, последний - $$2^n – 1$$, $$i$$- й – число $$ i -1$$.