Основные понятия алгебры логики

Существует не более чем 2^к (где к=2ⁿ) различных булевых функций n переменных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из 2ⁿ наборов функции могут принимать два значения.

Функций от одной переменной четыре: это константа 0 (f₀), константа 1 (f₁), тождественная функция (f₂), то есть функция, значение которой совпадает с аргументом, и функция отрицания (f₃), значение которой противоположно значению аргумента. Отрицание будем обозначать x.

x f₀ f₁ f₂ f₃

0 0 1 0 1

1 0 1 1 0

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

Переменная x_i называется фиктивной (несущественной) переменной функции f(x₁,···,x_n), если

f(x₁,···,x_i-1,0,x_i+1,···,x_n) = f(x₁,···,x_i-1,1,x_i+1,···,x_n)

для любых значений x₁,···,x_i-1,x_i+1,···,x_n. Иначе переменная x_i называется существенной.

Функции двух переменных представлены в табл. 9.

Таблица 9

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

f₀ (x1, x2) = 0 - тождественный ноль (константа 0);

f₁ (x1, x2) = x₁ ∙ x₂ – конъюнкция (логическое произведение, И). Иногда употребляется знак & или /\;

f₃ (x1, х2) = x₁ − повторение x₁;

f₅ (x1, x2) = x_{2 −} повторение x₂;

f₆ (x1, x2) = x₁  x₂ − сложение по модулю 2 или mod 2;

f₇ (х1, х2) = x₁ + x₂ − дизъюнкция (логическое сложение, ИЛИ или V);

f₈ (x1, x2) = x₁ ↓ x₂ − функция Вебба (стрелка Пирса, ИЛИ-НЕ);

f₉ (х1, х2) = x₁ ~ x₂ − эквивалентность;

f₁₃(x1, x2) = x₁ → x₂ − импликация;

f₁₄(x1, x2) = x₁ \ x₂ − штрих Шеффера (И-НЕ);

f₁₅(x1, x2) = 1 − тождественная единица (константа 1).

Основными операциями булевой алгебры являются: отрицание, логическое сложение и логическое умножение. В булевой алгебре возведение в степень и извлечение корня являются вырожденными логическими операциями, поскольку значения, принимаемые аргументами при возведении в степень и извлечении корня, остаются неизменными, если принять справедливость равенств 1·1= 1 и 0·0= 0. Операции вычитания и деления не рассматриваются и не допускаются.

Логическое отрицание (функция НЕ). Логическим отрицанием высказывания x называется такое сложное высказывание f(x), которое истинно, когда x ложно, и наоборот. Функция НЕ записывается следующим образом: f₁=x. Условное изображение элемента реализующего функцию НЕ приведено на

рис. 13,а.

Логическое умножение (конъюнкция). Конъюнкция (функция И) двух переменных x₁ и x₂ − это сложное высказывание, которое истинно только тогда, когда истинны x₁ и x₂, и ложно для всех остальных наборов переменных. Логическая функция конъюнкции имеет вид f=x₁·x₂. Для обозначения операции конъюнкции используются также символы & и Λ. Функция логического умножения (И) от n переменных имеет вид f₂=(x₁, x₂, …, x_n)= x₁·x₂· … ·x_n = Λ x_i. Условное изображение элемента, реализующего операцию логического умножения, приведено на рис.13,б.

Логическое сложение (дизъюнкция). Дизъюнкция (функция ИЛИ) двух переменных x₁ и x₂ – это сложное высказывание, которое истинно тогда, когда истинна хотя бы одна из переменных x₁ и x₂, и ложно, когда они обе ложны. Логическая функция дизъюнкции имеет вид f=x₁+x₂. Для обозначения операции дизъюнкции используется также символ V. Функция логического сложения (ИЛИ) от n переменных имеет вид f₂=(x₁, x₂, …, x_n)= x₁+x₂+ … +x_n = V x_i. Условное изображение элемента, реализующего операцию логического сложения, изображено на рис.13,в.

Отрицание конъюнкции (операция Шеффера). Отрицание конъюнкции (функция И-НЕ) двух переменных x₁ и x₂ – сложное высказывание, ложное только при истинности обоих аргументов x₁ и x₂. Логическая функция И-НЕ имеет вид f=x₁·x₂. Условное изображение элемента реализующего указанную операцию, изображено на рис. 13,г и называется элементом Шеффера или элементом И-НЕ.

Отрицание дизъюнкции (операция Пирса (Вебба)). Отрицание дизъюнкции (функция ИЛИ-НЕ) двух переменных x₁ и x₂ – сложное высказывание, истинное только тогда, когда оба аргумента принимают ложное значение. Логическая функция ИЛИ-НЕ имеет вид f=x₁+x₂. Условное изображение элемента, реализующего указанную операцию, приведено на рис.13,д и называется элементом Пирса или элементом ИЛИ-НЕ.

Сложение по модулю 2 (исключающее ИЛИ). Сложение по модулю

2 − это сложное высказывание, которое истинно только тогда, когда истинна только одна из переменных x₁ и x₂. Логическая функция ”сумма по модулю 2” имеет вид f=x₁x₂. Если число переменных n>2, то функция истинна на тех наборах, в которых число единиц нечетно. Условное изображение элемента, реализующего операцию сумма по модулю два, изображено на рис. 13,е.

а б в г д е

Рис. 13. Схемы логических элементов

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

Суперпозицией булевых функций f₀ и f₁,...,f_n называется функция f(x₁,...,x_m)= f₀(g₁(x₁,...,x_m),...,g_k(x₁,...,x_m)), где каждая из функций g_i(x₁, ...,x_m) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f₁,...,f_n.

Функция f(x,y) = (x & y) является суперпозицией функций и &. Функция g(x,y) = x  (x  y) является суперпозицией функций  и . Функция h(x,y,z) =

= (x & y)  z − суперпозиция функций  и &.

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

• одна и та же функция может быть представлена разными формулами;

• каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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