Двоичная логика. Булевая функция одной и двух переменных. Количество булевых функций n-переменных. Суперпозиция булевых функций

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

Логическая переменная в алгебре логики может принимать одно из двух возможных значений: TRUE - истина, FALSE - ложь. Эти значения в цифровой технике принято рассматривать как логическую "1" (TRUE) и логический "0" (FALSE), или как двоичные числа 1 и 0. Физически это может означать присутствие или отсутствие некоторого сигнала (замкнуто, разомкнуто), уровень потенциала на электронном элементе (высокий, низкий), протекание или отсутствие тока в некоторой цепи и т.п. Логические переменные позволяют легко описать состояние таких объектов, как тумблеры, кнопки, реле, триггеры и других, которые могут находиться в двух четко различимых состояниях: включено - выключено.Рассмотрение понятия функции в алгебре логики (АЛ) можно начать с функций одной переменной. Нетрудно видеть, что таких функций можно построить четыре:

Содержательный смысл этих функций: g1 - константа нуля, g2 - повторение x, g3 - инверсия x, g4 - константа единицы.

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

Логическая функция определяется как n-местная функция, определенная на множестве истинных значений <Истина (True), Ложь(False)> и принимающая значения в этом множестве.  Если последовательность логических переменных обозначить как X=(x1, x2, ..., xn) и назвать двоичным набором, то под функцией алгебры логики следует понимать однозначное отображение множества всевозможных наборов * на множествоY=<0,1>. Если две функции алгебры логики f1(x1, x2, ..., xn) и f2(x1, x2, ..., xn) принимают на всех возможных наборах одинаковые значения, то они называются равными (эквивалентными).
К элементарным функциям обычно относят: функцию инверсии (отрицания), конъюнкцию, дизъюнкцию, импликацию, штрих Шеффера и стрелку Пирса. Новые функции АЛ можно получить из известных функций либо путем перенумерации аргументов, либо путем подстановки в функцию новых функций вместо аргументов. Функция АЛ, полученная из функций f1, f2, ..., fk с помощью этих правил, называется суперпозицией функций f1, f2, ..., fk. В табл. приведено представление различных функций через суперпозицию конъюнкции, дизъюнкции и отрицания.