Аксиомы алгебры логики

Цифровая электроника

Алгебра логики (алгебра Буля)

Алгебра логики изучает связь между переменными, принимающими только значения "1" и "0".

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

Закон исключенного третьего

Если х ≠ 1, то х = 0, если х ≠ 0, то х = 1.

Логическая функция у = f(х₁,х₂,...,х_n) задана, когда каждому набору х однозначно сопоставляется у. Количество функций, образуемых n переменными равно:

Если n = 1, то => N = 4:
у₁ = 0,
у₂ = 1,
у₃ = х,
у₄ = /х.

Для двух переменных n = 2 и N= 16.

В таблице 1 приведены некоторые из возможных функций при n=2.

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

Элементарные логические функции

1) Конъюнкция (операция "и", логическое умножение). Конъюнкция нескольких переменных равна 1 лишь тогда, когда все переменные равны 1.Конъюнкция обозначается в виде произведения у = х₁·х₂, или у = х₁х₂, или у = х₁Λх₂. Обозначение элемента в схеме приведено на рис 2-1.

Рис.2-1 Конъюнктор

Таблица соответствия для конъюнкции

Таблица 2 Конъюнкция

2) Дизъюнкция (операция "или", логическое сложение). Дизъюнкция нескольких переменных равна 1, если хотя бы одна из переменных равна 1. Дизъюнкция обозначается в виде суммы: у = х₁+х₂, или у = х₁Vх₂. Обозначение элемента в схеме приведено на рис.2-2.

Рис.2-2Дизъюнктор

Таблица соответствия для дизъюнкции

Таблица 3 Дизъюнкция

3) Инверсия (операция "не", логическое отрицание). Обозначение элемента в схеме приведено на рис 2-3.

Рис.2-3

Таблица соответствия для инверсии

х	у=

Возможны комбинированные операции. Примеры элементов,выполняющих такие действия приведены на рис.2-4.

Рис. 2-4 Комбинированные логические элементы

4) Исключающее "или" – функция равна 1,когда только одна переменная равна 1. Обозначается значком

5) Сумма по модулю 2 - функция равна 1,когда нечетное число переменных равно 1, функция равна 0, когда четное число переменных равно 1. Функция обозначается: в виде у = Σ_mod2 = х₁ х₂ ... х_n. Для двух переменных Σ_mod2 совпадает с функцией исключающее "или". Для трех переменных в таблице 4 приведены данные для функций "исключающее или" и "сумма по модулю 2". Они уже неполностью совпадают.

х1	х2	х3	у1=х1 х2 х3	у2=х1 х2 х3
				1 !!!

Таблица 4 Сравнение функций

Система логических функций называется функционально полной, если используя только эти функции можно реализовать любые другие. Функционально полными являются системы:
1) "и", "или", "не";
2) "и", "не";
3) "или", "не".

Порядок выполнения логических операций: "не","и","или" (если нет скобок).

Аксиомы алгебры логики

х+0=х	х×0=0	х 0=х
х+1=1	х×1=х	х 1=х
х+х=х	х×х=х	х х=0
х+х=1	х×х=0	х х=1

Их можно проверить подставляя вместо х 0 или 1.

Правила Де-Моргана

Правила Де-Моргана позволяют переходить от конъюнкции к дизъюнкции и наоборот.

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

Закон поглощения

х₁+х₁×х₂ = х₁(1+х₂) = х₁×1 = х₁х₁ "поглощает" х₂