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

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

Двоичные переменныемогут принимать только два значения: 0 (ложь) и 1 (истина) − и обозначаются символамиx₁,x₂, … ,x_n. Двоичные (логические, булевы) переменные являются аргументами булевых (переключательных) функций.

Функция f, зависящая от n переменных x₁, x₂, ...., x_n, называетсябулевой, или переключательной, если функция f и любой из ее аргументовx_i, (i = 1...n) принимают значения только из множества {0, 1}.

Или булева функция– это функция, и аргументы и значение которой принадлежат множеству { 0, 1 }. Множество { 0, 1 } обозначим черезB.

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

x₁x₂...x_n-1 x_nf

0 0 ... 0 0 f(0,0,...,0,0)

... ... ... ... ... ...

1 1 ... 1 1 f(1,1,...,1,1)

Для того чтобы задать функцию, достаточно выписать значения f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),...,f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1). Этот набор называютвектором значений функции.

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

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

0 0 0 1 1

1 0 1 0 1

Переменная 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называетсясущественной.

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

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

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

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

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

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

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

Импликация. Это высказывание, принимающее ложное значение только в случае, еслиx₁истинно, аx₂ложно.

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

Однако следует отметить:

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

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

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