Элементарные функции алгебры логики

Обозначения: E₂={0,1}; Е = E₂´E₂´...´E₂ – прямое произведение n сомножителей; (x ,..,x_n)Î E₂, | E₂| – мощность E₂, |E₂|=2, тогда |Е |=2ⁿ.

Определение 1. Функцией алгебры логики называется закон, осуществляющий отображение Е E₂, причем отображение всюду определено и функционально.

Так как множество Е конечно, то задать отображение Е Þ E₂, означает задать множество наборов из Е и для каждого набора указать его образ в Е ₂.

Пример 1. Пусть n=2, тогда Е ={(0 0),(0 1),(1 0),(1 1)}, отображение Е Þ E₂ задано, например, так: (0 0) Þ0 ; (0 1) Þ1; (1 0) Þ1 ; (1 1) Þ1.

Тем самым задана функция, для которой мы будем использовать стандартное обозначение f(x₁,x₂), записывая эту функцию в виде таблицы:

Здесь x₁ и x₂ обозначают названия столбцов, а f – символ, обозначающий отображение. Следует обратить внимание, что функции f(x₁,x₂) и f(y₁,y₂) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов.

Определение 2.Таблица, задающая функцию f(x₁,x₂,...,x_n), называется таблицей истинности для этой функции.

Рассмотрим функции одной переменной. Их будет всего 4, они задаются следующими таблицами истинности:

функция называется константой 0, записывается f₀(x) 0;

функция называется тождественной, записывается f₁(x)= x;

функция называется «не x» и записывается f₂ (x)= ;

функция записывается f₃(x) 1 и называется константой 1. Если стандартным расположением переменной x считать 0 в первой строке и 1 во второй, то функции f₀, f₁, f₂, f₃ определяются однозначно наборами значений: f₀=(0,0), f₁=(0,1), f₂=(1,0) и f₃=(1,1). Наборы значений функций составляют множество E₂´Е₂, поэтому количество функций одной переменной равно |E₂ E₂|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.

Рассмотрим функции двух переменных f(x₁,x₂). Функции двух переменных определены на множестве Е ={(0 0),(0 1),(1 0),(1 1)}, эти наборы переменных из Е можно тоже рассматривать как двоичные коды чисел 0,1,2,3, именно такой порядок расположения наборов (x₁,x₂) будем считать стандартным. Тогда функции f(x₁,x₂) определяются однозначно наборами значений (b₁, b₂, b₃, b₄), где каждое b_iÎE₂, поэтому (b₁, b₂, b₃, b₄)ÎЕ . Следовательно, число функций двух переменных равно 2⁴=16, занумеруем их числами от 0 до 15 так, чтобы двоичный код номера совпадал с набором значений функции.

Некоторые из этих функций носят специальные названия и играют такую же роль, как элементарные функции в анализе, поэтому называются элементарными функциями алгебры логики. Перечислим их.

1) f₁(x₁,x₂) = (x₁&x₂), читается «конъюнкция х₁ и х₂», иногда вместо знака & употребляют знак или вообще его опускают, пишут (х₁х₂). (х₁&х₂) совпадает с обычным произведением х₁х₂ и совпадает с min(x₁,x₂). Эту операцию называют также логическим умножением.

2) f₆(x₁,x₂) = (x₁Åx₂) – сложение х₁ и х₂ по модулю два, иногда пишут (х₁+х₂)_mod2.

3) f₇(x₁,x₂) = (x₁Úx₂), читается «х₁ дизъюнкция х₂», она совпадает с max(x₁,x₂), ее называют логическим сложением.

4) f₈(x₁,x₂) = (x₁ x₂), читается «х₁ стрелка Пирса х₂» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.

5) f₉(x₁,x₂) = (x₁~x₂), читается «х₁ эквивалентно х₂».

6) f₁₃(x₁,x₂) =( x₁ x₂), читается «х₁ импликация х₂», иногда обозначается (х₁Éх₂), т. е. х₁ влечет х₂ .

7) f₁₄(x₁,x₂) = (x₁|x₂), читается «х₁ штрих Шеффера х₂», она является отрицанием конъюнкции.

Cимволы ,&,Ú, ,~, ,Å,|, участвующие в обозначениях элементарных функций, называются логическими связками или просто связками. Переменные 0 и 1 называются логическими или булевыми переменными, причем 0 соответствует «лжи» , а 1 – «истине», а функции алгебры логики называются еще и блевыми функциями.

Рассмотрим функции f(x₁...x_n), где (x₁...x_n)Î Е , тогда число наборов (x₁...x_n),где функция f(x₁...x_n) должна быть задана, равно |Е |=2ⁿ. Обозначим множество всех функций двузначной алгебры логики Р₂. Обозначим через Р₂(n) число функций, зависящих от n переменных. Очевидно, Р₂(n)=2^{2 n}.

С ростом n число Р₂(n) быстро растет: P₂(1)=4, P₂(2)=16, P₂(3)=256, P₂(4)=65536 . При больших n табличный способ задания функций становится неприемлемым, используется формульное задание функций. Но прежде чем ввести понятие формулы, дадим определение существенной переменной.

Определение 3. Функция f(x₁,...,x_i–1,x_i,x_i+1,...,x_n) существенно зависит от х_i, если существуют такие значения a₁, ...a_i–1, a_i+1, ...a_n переменных x₁, ...x_i–1, x_i+1, ...x_n, что f(a₁, ...a_i–1, 0, a_i+1...a_n)¹f(a₁...a_i–1, 1, a_i+1...a_n) . Тогда переменная х_i называется существенной переменной. В противном случае х_i называется фиктивной переменной.