Алгебра логики – это раздел математики, разработанный в позапрошлом веке английским ученым Джорджем Булем

Алгебра логики – это раздел математики, разработанный в позапрошлом веке английским ученым Джорджем Булем. По этой причине существует другое название этого раздела – Булева алгебра.

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

Высказывания могут быть простыми и сложными. Простое высказывание содержит только один факт, не зависящий от других фактов, т. е. сам по себе может быть или истинным или ложным. В приведенных выше примерах высказывания - простые. Сложное высказывание содержит несколько простых высказываний.

Рассмотрим высказывание: «Автомат сработает, когда будут нажаты кнопки К1 и К2 или нажата кнопка КЗ и не нажата кнопка К4». Здесь простые высказывания (состояния кнопок) составляют сложное высказывание (срабатывание автомата) с помощью союзов - связок И, ИЛИ, НЕ; состояния кнопок играют роль аргументов (переменных), над ними эти союзы осуществляют такие функциональные преобразования, которые формируют функцию - условие срабатывания автомата.

Из изложенного следует, что булева алгебра оперирует с переменными, принимающими только два значения: истинно или ложно. Причем состояние истинно можно обозначить цифрой 1, а состояние ложно – цифрой 0, т. е. двоичными переменными.

Простое высказывание (событие) обозначим символом Х, а сложное событие, являющееся функцией простых, объединенных связками И, ИЛИ, НЕ, символом У. Выше указанные связки И, ИЛИ, НЕ называют логическими операциями. Функция двоичных переменных, принимающая то же два значения, называется логической функцией (переключательной функцией, функцией алгебры логики).

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

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

Базисные логические функции. Логическое сложение (дизъюнкция) переменных Х записывается в виде:

У = Х1 v Х2 v Х3 v…v Хi v…vХN.

Значение У = 0 имеет место только, если все аргументы Х равны = 0. Если хотя бы одно слагаемое равно единице (Хi = 1 - событие наступило), то У = 1. Сумма наступивших событий означает наступление события, т. е. при любом числе слагаемых, равных единице, сумма их равна единице: У = 1, если Х1 = l, или X2 = l, или Х1 и Х2 = 1, или и т.д., или все переменные Х равны единице. Этим и объясняется еще одно название рассматриваемой операции - операция ИЛИ.

Представление операции ИЛИ для двух переменных в виде таблицы истинности (рис.4.44).

В каждой ее строке записаны значения переменных X1 и Х2 и соответствующее им значение функции У.

Две двоичные переменные имеют четыре сочетания. В общем случае N двоичных переменных дают 2N сочетаний.

Х2 | Х1 | У
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

Рис.4.44 Таблица истинности логической операции ИЛИ для двух переменных

Кроме знака «v» дизъюнкция обозначается знаком «+»: У = Х1 + Х2 + ... +ХN.

Элемент, выполняющий дизъюнкцию, называется дизъюнктором или элементом ИЛИ.

Электрическая реализация операции ИЛИ с помощью ключей дана на рис.4.45 а.

Рис.4.45 Электрическая реализация логических операций

Замкнутое состояние ключа соответствует логической единицей (Кл = 1), разомкнутое - логическому нулю (Кл = 0). Лампочка будет светить (Л = 1), если выполняются условия: ключ Кл1 замкнут, ключ Кл2 разомкнут (первое простое высказывание) - Кл1=1, Кл2 = 0; ИЛИ: ключ Кл1 разомкнут, ключ Кл2 замкнут (второе простое высказывание); ИЛИ: ключ Кл1 замкнут, ключ Кл2 замкнут (третье простое высказывание).

Высказывание «лампочка светит, если...» может быть представлено простыми высказываниями, соединенными операцией ИЛИ:

У = X1+Х2,

где X1 соответствует состоянию ключа Кл1,Х2 - состоянию ключа Кл2, а У - состоянию лампочки.

Логическое умножение (конъюнкция) переменных записывается в виде:

У = Х1 ^ Х2 ^ ...^ Хi ^…^ ХN.

Из приведенного выражения следует, что если хотя бы одна из переменных равна нулю, то функция равна нулю. Только в том случае, если Х1 = 1, и Х2 = 1, и т.д. ..и ХN = 1, то У = 1. Поэтому данная операция называется также операцией И.

Таблица истинности операции И двух переменных (рис.4.46):

Х2 | XI | У
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1

Рис.4.46 Таблица истинности операции И для двух переменных

Кроме приведенной используются следующие формы записи конъюнкции:

У = Х1·Х·2·Х3 или просто У = Х1Х2Х3.

Элемент, выполняющий конъюнкцию, называется конъюнктором или элементом И.

На рис.4.45,б показана электрическая реализация операции И. Лампочка будет светить (У =1), если замкнуть ключ Кл1 (Х1 = l) и замкнуть ключ Кл2 (Х2 =1). Логическое уравнение, выражающее состояние лампочки, имеет вид:

У = X1X2,

где значения Х1 и Х2 соответствуют состояниям ключей Кл1 и Кл2.

Логическое отрицание (инверсия) записывается в виде У = и называется также операцией НЕ, читается «У есть НЕ Х». Таблица истинности операции НЕ (рис.4.47):

Х | У
0 | 1
1 | 0

Рис.4.47 Таблица истинности операции НЕ

Элемент, выполняющий инверсию, называется инвертором или элементом НЕ.

Электрическая реализация операции НЕ показана на рис.4.45,в. Если ключ Кл замкнут (Кл = 1), то лампочка не светит (Л = 0), если ключ разомкнут ( Кл = О), то лампочка светит ( Л = 1).

Основные законы алгебры логики, действующие при сложении и умножении переменных:

переместительный закон: Х1 + Х2 = Х2 + Х1; Х1Х2 = Х2Х1;

сочетательный закон: (X1+ Х2) + Х3 = Х1 + (Х2 + Х3); (Х1Х2)Х3 = Х1(Х2Х3);

распределительный закон: Х1(Х2 + Х3) = X1X2 + Х1Х3; Х1 + Х2Х3 =

(Х1+ Х2)(Х1 + Х3).

Закон отрицания (закон инверсии, теорема де Моргана):

+ = ;

= .

Закон отрицания отражает принцип двойственности алгебры Буля.

Эти законы справедливы для любого числа переменных.

Основные тождества алгебры логики:

Х+0 = Х; Х+1=1; Х+Х = Х; Х + = 1;

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

Их справедливость, легко установить, подставляя вместо Х значения 0 и 1.

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

Предпоследнее выражение второй строчки тождеств (Х = 0) - закон противоречия: два противоположных высказывания не могут быть одновременно истинными.

Рассмотренные выше логические операции позволяют представить логическую функцию любой сложности, поэтому их называют базисными(базисом) или функционально полными. Базисными являются также совокупности операций ИЛИ, НЕ; И, НЕ.