6. Основы булевой алгебры

Математический аппарат, описывающий действия дискретных устройств, базируется на алгебре логики, или, как ее еще называют по имени автора – английского математика Джорджа Буля (1815–1864 г.), булевой алгебре. В практических целях первым применил его американский ученых Клод Шеннон в 1938 г. при исследовании электрических цепей с контактными выключателями.

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

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

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

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

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

Таблица 2.1 Таблица 2.2

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),(константа 0).

Два аргумента дают 16 значений функций (таблица 2.3).

Таблица 2.3

	0	0	1	1	Функция	Название функции
	0	1	0	1
	0	0	0	0		Константа 0
	0	0	0	1		Конъюнкция, операция И
	0	0	1	0		Запрет по
	0	0	1	1		Тождественность (тавтология)
	0	1	0	0		Запрет по
	0	1	0	1		Тождественность (тавтология)
	0	1	1	0		Исключающее ИЛИ (сумма по модулю 2)
	0	1	1	1		Дизъюнкция, операция ИЛИ
	1	0	0	0		Стрелка Пирса (операция ИЛИ–НЕ)
	1	0	0	1		Равнозначность, эквивалентность
	1	0	1	0		Инверсия
	1	0	1	1		Импликация от к
	1	1	0	0		Инверсия
	1	1	0	1		Импликация от к
	1	1	1	0		Штрих Шеффера (операция И–НЕ)
	1	1	1	1		Константа 1