В булевой алгебре

основное множество В = {0, 1};

набор операций (сигнатура) W = { },

где – логическое сложение – дизъюнкция,

– логическое умножение – конъюнкция,

– отрицание – инверсия;

аксиомы:

1. Каждая переменная x может принимать одно из двух значений 0 или 1:

x = 0, если x не равно 1, или x = 1, если x не равно 0 (третьего не дано).

2. , .

3. 0 0 = 0; 1 1 = 1; 1 0 = 0 1 = 0;

0 0 = 0; 0 1 = 1 0 = 1; 1 1 = 1.

Аксиома 1 определяет возможные значения переменных, аксиомы 2 и 3 определяют правила выполнения операций отрицания ( ) – инверсии, логического умножения ( ) – конъюнкции и логического сложения ( ) – дизъюнкции.

Из аксиом также видим, что в булевой алгебре задано отношение эквивалентности, обозначаемое символом =.

Отношение эквивалентности обладает свойствами

– рефлексивности: x = x,

– симметричности: если есть x₁ = x₂, то есть и x₂ = x₁,

– транзитивности: если есть x₁ = x₂ и x₂ = x₃, то x₁ = x₃.

Из этих свойств следует принцип подстановки: если x₁ = x₂, то в любом логическом выражении, содержащем x₁, вместо x₁ можно подставить x₂ и в результате будет получено эквивалентное правильное выражение.

Правильным логическим выражением является

– логическая переменная, например, x;

– логическая переменная с символом отрицания ;

– выражение типа или ;

– выражение типа или , где A и B – выражения.

Совокупность конкретных значений логических входных переменных называется входным набором. Если число входных переменных n, то число возможных входных наборов будет 2ⁿ (у одной переменной два набора: 0 и 1, у двух переменных – четыре набора: 00, 01, 10, 11 и т.д.).

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

Для входных наборов можно установить также отношение предшествования (разновидность отношения порядка): Входной набор предшествует набору (обозначается это так ), если .

Наборы, которые находятся в отношении , называются сравнимыми. Например, наборы 00 и 10, 00 и 01, 01 и 11, 10 и 11, 00 и 11 сравнимы, а наборы 01 и 10 не сравнимы, поэтому наборы в отношении предшествования являются лишь частично упорядоченными. (При определении монотонности логических функций (см. п. 3.1.4) рассматривают только последовательности наборов, удовлетворяющих отношению предшествования 00, 10, 11 и 00, 01, 11.)

Если функция задана на всех 2ⁿ входных наборах, то она полностью определена, иначе (т.е. если она задана не на всех наборах) она называется частично определенной функцией.

Различные логические функции должны отличаться друг от друга хотя бы на одном входном наборе, а различных символов в булевой алгебре всего 2, поэтому при n переменных может быть полностью определенных функций. например, при n = 1 их будет 2² = 4, при n = 2, 2⁴ = 16, при n = 3, 2⁸ = 256.

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

Суперпозицией логических функций f₀ и f₁, f₂,…, f_n называется функция

где либо совпадает с одной из переменных x_i, либо с одной из функций f₁, f₂,…, f_n .

Пример: .

Здесь функция есть суперпозиция функций НЕ, И, ИЛИ (обозначения функций см. ниже).