Аксиомы и основные свойства алгебры логики

Основные понятия

Алгебра логики – один израздел математической логики. Её создателем является англичанин Джорж Буль (1815г - 1864г), поэтому алгебру логики называют булевой алгеброй.

Начальным понятием булевой алгебры является высказывание.

Высказывание - это некоторое предложение, о котором можно утверждать истинно оно или ложно. Высказывание обозначают буквой (идентификатором). Например, два высказывания

X₁ = < Москва - столица России > X₁ = 1 – истина

X₂ = < Солнце - меньше Земли > X₂ = 0 – ложь

Если высказывание истинно, то его обозначают единицей, если ложно – нулём.

Логическая переменная – некоторая переменная величина X, которая может принимать одно из двух значений 0 или 1, то есть быть ложной или истинной X={0, 1}.

Логическая функция (булева функция, переключательная функция, функция алгебры логики) n переменных - это функция, которая может принимать одно из двух значений 0 или 1 на некотором наборе этих переменных F (X₁, X₂, …, X_n) ={0, 1}

Логическая функция задается таблицей истинности.

Таблица истинности – это совокупность всех возможных наборов (комбинаций) логических переменных и значений функции на этих наборах.

Например, логические функции одной переменной n = 1 – тривиальные функции.

Таблица 1 – Логические функции одной переменной

Реализация этих функций показана на рисунке 1.1.

Рисунок 1.1 – Реализация функций одной переменной

Функция F₁ всегда ложна (рис.1.1а), функция F_2, есть сама переменная икс (рис 1.1б), функция F ₃ реализуется инвертором (рис.1.1в), функция F₄ всегда истинна (рис.1.1г).

В общем случае, если имеем n независимых логических переменных, то можно составить 2ⁿ = N наборов этих переменных, а так как на каждом из наборов функция может принимать значение 0 или 1, то общее возможное число функций равно L=2^N. Так, при n = 1 число наборов N =2, а число функций L = 4.

Рассмотрим логические функции двух переменных n = 2. Они относятся к элементарным функциям. Число наборов переменных равно N = 2² = 4, а число функций - L =16.

На практике имеют простую техническую реализацию и используются не все элементарныe функции, а только основные (базисные) функции. Рассмотрим их.

1. Логическое умножение, операция “ И ” – конъюнкция. Выполняется элементом – конъюнктором (рис 1.2).

Рисунок 1.2 -Конъюнктор

Его таблица истинности

Рисунок 1.3 – Таблица истинности конъюнктора

2. Операция Шеффера “ И – НЕ” – отрицание конъюнкции. Выполняется элементом Шеффера (рис. 1.4).

Рисунок 1.4 – Элемент Шеффера

Его таблица истинности

Рисунок 1.5 -Таблица истинности элемента Шеффера

3. Логическое сложение, операция “ ИЛИ” – дизъюнкция. Выполняется элементом – дизъюнктором (рис.1.6).

Рисунок 1.6 – Дизъюнктор

Его таблица истинности

Рисунок 1.7 – Таблица истинности дизъюнктора

4. Операция Пирса - отрицание дизъюнкции. Логическое “ ИЛИ – НЕ”. Выполняется элементом Пирса (рис. 1.8).

Рисунок 1.8 – Элемент Пирса

Его таблица истинности

Рисунок 1.9 – Таблица истинности элемента Пирса

5. Логическая неравнозначность или сумма по модулю два - М2.

Выполняется сумматором по “модулю два” (рис. 1.10). Функция истинна на тех наборах, где число единиц нечетно.

Рисунок 1.10 – Сумматор по модулю два

Его таблица истинности

Рисунок 1.11 – Таблица истинности сумматора по модулю два

Вместе с тем, в литературе встречается функция, так называемая, “исключающее ИЛИ”, которая истинна, на тех наборах, где присутствует исключительно одна единица. Операция выполняется элементом “исключающее ИЛИ” (рис.1.11)

Рисунок 1.11 – Элемент “исключающее ИЛИ”

Его таблица истинности

Рисунок 1.12 – Таблица истинности элемента “исключающее ИЛИ”

Видно, что таблицы истинности совпадают. Значит для двух переменных функции M2 и =1 – эквивалентны.

Составим таблицу истинности этих функций при числе переменных n=3

Рисунок 1.13 – Таблица истинности элементов М2 и =1

для трёх переменных

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

Графическое изображение и условное обозначение логических элементов регламентируются ГОСТ 2.743-91 ЕСКД. Этот ГОСТ устанавливает следующие геометрические размеры (рис. 1.14):

Рисунок 1.14 – Условное изображение логических элементов

Других ограничений на размеры логических элементов ГОСТ не накладывает.

Аксиомы и основные свойства алгебры логики

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

АКСИОМЫ алгебры логики:

0 * 0 = 0 0 + 0 = 0

0 * 1 = 0 0 + 1 = 1

1 * 0 = 0 1 + 0 = 1

1 * 1 = 1 1 + 1 = 1

ЗАКОНЫ алгебры логики:

1. Закон одинарных элементов

1 * X = X 0 * X = 0

1 + X = 1 0 + X = X

2. Законы отрицания

а) Закон дополнительных элементов.

б) Двойное отрицание

поэтому отрицание можно переносить из одной части равенства в другую.

в) Закон двойственности (правилоМоргана).

Отрицание дизъюнкции есть конъюнкция отрицаний и наоборот - отрицание конъюнкции есть дизъюнкция отрицаний:

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

3. Комбинационные законы.

Они во многом соответствуют обычной алгебре, но есть и отличия.

а) тавтологии ( многократное повторение )

б) переместительности

A+B+C+D=A+C+B+D

в) сочетательности

A+B+C+D=A+(B+C)+D=A+B+(C+D)

г) распределительности

X₁(X₂+X₃)= X₁X₂ + X₁X₃

X₁+X₂X₃=(X₁+X₂)(X₁+X₃)=/ докажем это путём раскрытия скобок/=

= X₁X₁+ X₁X₃+ X₁X₂+ X₂X₃= X₁(1+X₃+X₂)+ X₂X₃= X₁+X₂X₃

д) правило поглощения (одна переменная поглощает другие )

X₁+X₁X₂ X₃ =X₁(1+X₂ X₃ )=X₁

е) правило склеивания ( выполняется только по одной переменной )

Также как в обычной математике имеется старшинство операций:

1) Действие в скобках

2) Операция с одним операндом (одноместная операция) –НЕ

3) Конъюнкция - И

4) Дизъюнкция - ИЛИ

5) Сумма по модулю два.

Операции одного ранга выполняются слева направо в порядке написания.