1-2. ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

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

Пример 1-3. Для согласно теореме 1 имеем различные функции:

В этом случае только функции и существенно зависят от , а для функций этот единственный аргумент является фиктивным.

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

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

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

Из примера 1-3 вытекает, что Применяя теорему 2, имеем:

Вместо рекуррентного соотношения (1-2) можно найти прямое выражение для значений Как показал Г. А. Крылов,

Рассмотрим одиннадцать функций, которые Играют большую роль в построении теории функций алгебры логики и ее приложениях. Эти функции мы будем называть в дальнейшем элементарными.

Рассмотрение множества элементарных функций алгебры логики мы начнем со случая . В силу теоремы 1-1 в этом случае имеются только две функции, совпадающие с константами 0 и 1:

Обе эти функции мы будем считать элементарными.

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

Эти две функции мы также причислим к элементарным и будем их записывать следующим образом:

Функцию мы будем называть функцией отрицания или просто отрицанием.

В случае в силу теоремы 1-2 имеем десять различных функций, существенно зависящих от аргументов Из этих десяти функций к элементарным функциям будем относить следующие семь функций:

Функция определяемая этой таблицей, носит название дизъюнкции и или логического

сложения Для ее обозначения применяются следующие символы:

и

Мы на протяжении всего дальнейшого изложения будем называть функцию дизъюнкцией и обозначать дизъюнкцию при помощи символа

Функция носит название конъюнкции или логическогоумножения Для ее обозначения применяется символ

Вместо этого символа часто применяют точку или вообще опускают всякий знак между т. е.

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

Функция носит название функции эквивалентности или функции равнозначности. Для ее обозначения применяются следующие два символа:

и

В дальнейшем будем называть эту функцию эквивалентностью Для ее обозначения будем употреблять второй из вышеприведенных символов.

Функция носит название импликации в Она обозначается следующим образом:

Функция носит название функции Вебба и обозначается следующим образом:

Функция называется функцией Шеффера и обозначается следующим образом:

Функция обычно называется функцией сложения по модулю 2 (реже ее называют функцией разноименности).

Для обозначения функции сложения по модулю 2 применяется символ 0:

Рассмотренные одиннадцать функций позволяют строить новые функции алгебры логики двумя основными путями:

1) путем перенумерации аргументов;

2) путем подстановки в функцию новых функций вместо аргументов.

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

Имея, например, элементарные функции отрицания, дизъюнкции, эквивалентности и импликации, можно составить следующие новые функции алгебры логики, являющиеся суперпозициями этих функций:

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

Пример 1-5. Пусть требуется представить в виде таблицы следующую функцию:

Будем строить функцию последовательно.