Основные определения

Функции алгебры логики и их основные свойства

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

(1.16)

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

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

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

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

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

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

.

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

.

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

Пусть функция задана следующей таблицей:

Таблица 1.3 – Пример 1

Покажем, что аргумент x₄ для этой функции является фиктивным. Для этого убедимся, что

.

Составим таблицу, определяющую функции f(x₁, x₂, x₃, 0) и f(x₁, x₂, x₃, 1).

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

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

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

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

Таблица 1.5 –

0 0 … 0 0			…………	.
0 0 … 0 1			…………	.
0 0 … 1 0			1 1 … 1 1
…………	.

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