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

Пусть В={0,1}. Элемент = (x₁,x₂,...,x_n) Î Bⁿ, где Bⁿ=B´B´...´B, называется булевым вектором.

Функция f:Bⁿ®B называется булевой функцией от n переменных x₁, x₂,..., x_n, где x_iÎ B (1 £ i £ n), и обозначается f( )=f(x₁,x₂,...,x_n). Если f( )=1, то называется единичным относительно функции f; если f( )=0, то нулевым.

Для булевой функции f(x₁,x₂,...,x_n) переменная x_i, 1£i£n, называется несущественной, если выполнено равенство: f(x₁,...,x_i-1,1,x_i+1, ...,x_n)= f(x₁,...,x_i-1,0,x_i+1, ...,x_n)

для всех значений переменных x₁,...,x_i-1,x_i+1,...,x_n. В этом случае функция f(x₁,x₂,...,x_n) фактически не зависит от переменной x_i и можно рассмотреть функцию, зависящую от n-1 переменных, которая совпадает с исходной.

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

Выпишем все возможные булевы функции одной переменной (табл. 1.1).

Для функций j₁ и j₄ х является несущественной переменной. Эти функции называются константами, соответственно 0 и 1. Функцию j₂ называют тождественной (j₂(х) = х). Функция j₃ называется отрицанием х (или функцией НЕ) и обозначается (иногда ù х).

Рассмотрим булевы функции двух переменных. Их 16 (табл. 1.2). Каждая из переменных может принимать по 2 значения, Þ, всего существует 2´2 = 4 различные пары (x₁,x₂), а значит, и строк в таблице 4. Различных векторов длины 4, состоящих из 0 и 1, можно составить 2⁴=16.

Функции y₁ и y₁₆ - константы 0 и 1, то есть функции с двумя несущественными переменными. Формально эти функции отличаются от функций j₁ и j₄, так как все функции в табл. 1.1 - унарные операции на В, а все функции в табл. 1.2 - бинарные операции на В. Однако ранее уже было принято функции, отличающиеся лишь несущественными переменными, считать равными.

Таблица 1.2

Функция y₂(x₁,x₂) называется конъюнкцией x₁ и x₂ ; ее обозначения: x₁&x₂, x₁Ùx₂, x₁×x₂, x₁x₂. Она равна 1, только если x₁=x₂=1, поэтому ее называют функцией И. Еще одно ее название - ²логическое умножение², т.к. ее таблица совпадает с таблицей обычного умножения для чисел 0 и 1.

Функция y₈(x₁,x₂) называется дизъюнкцией x₁ и x₂ ; ее обозначения: x₁Úx₂, x₁+x₂ . Она равна 1, если x₁=1 или x₂=1 (²или² здесь понимается в смысле - хотя бы одна переменная из двух). Поэтому ее часто называют функцией ИЛИ.

Заметим, что x₁&x₂= min{x₁,x₂}, а x₁Úx₂= max{x₁,x₂}.

Функция y₇(x₁,x₂) - это сложение по модулю 2. Ее обозначения: x₁Åx₂, x₁Dx₂ , x₁¹x₂ . Она равна 1, когда значения ее аргументов различны, и равна 0, когда они равны; поэтому y₇ иногда называют неравнозначностью.

Функция y₁₀(x₁,x₂) называют эквивалентностью или равнозначностью. Ее обозначения: x₁~x₂ , x₁ºx₂ , x₁«x₂. Она равна 1, когда значения ее аргументов равны, и равна 0, когда они различны. Еще 3 функции имеют свои названия:

y₁₄ (x₁,x₂) - импликация; обозначения: x₁®x₂ , x₁Éx₂ ; читается “если x₁, то x₂“;

y₉(x₁,x₂) - стрелка Пирса, обозначение: x₁­x₂ ; y₁₅(x₁,x₂) - штрих Шеффера; обозначение: x₁|x₂.

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

Определим, сколько существует булевых функций от n переменных. Число различных наборов (x₁,x₂,...,x_n) составляет 2ⁿ, поэтому таблица, описывающая функции n переменных, состоит из 2ⁿ строк. Различных векторов с 2ⁿ компонентами, состоящих из 0 и 1, а значит, и булевых функций, можно составить . Пример.При n = 3 булевых функций 256.

Функция f называется суперпозицией булевых функций f₁, f₂,..., f_k , если она получается некоторой подстановкой этих булевых функций друг в друга. Выражение, описывающее результат этой подстановки, называется логической формулой, задающей функцию f. Например, функция j₃(y₂ (x₁,x₂)) задается формулой , а функции y₈(y₁₄ (x₁,x₂), y₇ (x₁,x₂)) соответствует формула ((x₁®x₂) Ú (x₁Åx₂)). О формуле, задающей некоторую булеву функцию, говорят, что она реализует эту функцию.

Пример. Формула строится в два этапа, а формула ((x₁®x₂) Ú (x₁Åx₂)) - в три.