Основные определения. Рассмотрим набор (x1, x2,, xn), (4.9)

Рассмотрим набор

в котором переменные х_i могут принимать значения 0 или 1. При этом число различных числовых наборов такого вида конечно и равно 2^п (см. таблицу 4.2).

Определение 1. Функция, определенная на наборах вида (4.9) и принимающая в качестве своих значений на этих наборах 0 или 1, называется функцией алгебры логики (ФАЛ).

Так как число различных наборов значений аргументов является конечным, то любая функция алгебры логики может быть полностью задана конечной таблицей с 2 ^п строками (таблица 4.2). В левой части этой таблицы перечислены все наборы значений аргументов этой функции, а в правой части - значения функции на этих наборах.

Таблица 4.2 - Состояние (истинность)
логической функции f (х₁, х₂)

Определение 2. Если две функции алгебры логики f₁ (x₁, x₂,..., x_n) и
f₂ (x₁, x₂,..., x_n) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f_l и f₂ называются равными (эквивалентными).

Факт равенства функций f_l и f₂ записывается обычным образом:

f₁ (x₁, x₂,..., x_n) = f₂ (x₁, x₂,..., x_n).

Определение 3. Функция f (x₁,…, x_{i - 1}, x_i, x_{i + 1},..., x_n) существенно зависит от аргумента x_i, если имеет место соотношение

f (x₁,…, x_{i - 1}, 0, x_{i + 1},..., x_n) ≠ f (x₁,…, x_{i - 1}, 1, x_{i + 1},..., x_n).

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

Пусть функция задана в виде таблицы 4.3.

Таблица 4.3 – Пример задания функции

Покажем, что аргумент x₄ для этой функции является фиктивным. Для этого убедимся, что f (x₁, x₂, x₃, 0 ) = f (x₁, x₂, x₃, 1 ). Составим таблицу 4.4, определяющую функции f (x₁, x₂, x₃, 0 ) и f (x₁, x₂, x₃, 1 ).

Таблица 4.4 - Значение функций f (x₁, x₂, x₃, 0 ) и f (x₁, x₂, x₃, 1)

На основании определений 2 и 3 можно сделать вывод о фиктивности аргумента х₄.

Теорема 1. Число различных функций алгебры логики, зависящих от п аргументов, конечно и равно .

Для доказательства теоремы составим таблицу 4.5.

Таблица 4.5 – Функция алгебры логики

В этой таблице справа стоит одна из возможных функций алгебры логики (е₁ ,…, е_j,…, ), зависящая от n аргументов. Задавая тот или иной двоичный набор (е₁ ,…, е_j,…, ), мы будем тем самым задавать одну из возможных функций алгебры логики. Но набор (е₁ ,…, е_j,…, ) является набором вида (4.9) с 2ⁿ переменными. Различное число таких наборов равно . Теорема доказана.