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

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

 

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

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

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

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

Если n = 1, то => N = 4:
у1 = 0,
у2 = 1,
у3 = х,
у4 = /х.

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

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

х1	х2	у1	у2	у3	у4

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

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

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

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

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

х1	х2	у=х1·х2

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

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

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

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

х1	х2	у=х1+х2

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

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

Рис.2-3

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

х	у=

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

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

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

5) Сумма по модулю 2 - функция равна 1,когда нечетное число переменных равно 1, функция равна 0, когда четное число переменных равно 1. Функция обозначается: в виде у = Σmod2 = х1 х2 ... х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.

 

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