2. Основы алгебры логики

Наибольшее применение из-за простоты построения структурных схем ПК нашел двоичный структурный алфавит. Элементарные сигналы, составляющие этот алфавит, представляются импульсами электрического напряжения (тока), уровнями электрического напряжения (тока) или их комбинацией.

В связи с двоичным представлением структурного алфавита в качестве математического аппарата для целей анализа и синтеза цифровых схем оказалось удобным применять аппарат алгебры логики.

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Логическое высказывание — любое повествовательное пpедлoжение, в oтнoшении кoтopoгo мoжно oднoзначнo сказать, истинно oнo или лoжнo. Например, предложение «6 — четное число» следует считать высказыванием, так как оно истинное. Предложение «Рим — столица Франции» тоже высказывание, так как оно ложное.

Создателем алгебры логики является живший в ХIХ в. английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Понятия двоичной переменной и двоичной функции

Двоичными (логическими, булевыми) переменными х₁, х₂,..., х_n называются переменные, которые могут принимать только два значения: 0 и 1. Совокупность значений таких переменных называют набором.

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

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

Любая булева функция может быть задана с помощью таблицы, в левой части которой выписываются все наборы значений двоичных переменных, а в правой — соответствующие им значения функции. Такая таблица называется таблицей истинности. Пример таблицы истинности:

Таблица 1

Таблицы истинности логической функции

x1	x2	x3	f(x1, x2, x3)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Общее число различных булевых функций от n переменных равно .

Для анализа и синтеза схем ПК широко используются булевы функции одной и двух переменных.

Для одной булевой переменной имеются четыре различные булевы функции (табл. 2).

Таблица 2

Таблицы истинности для логических функций одной переменной

Обозначение функции	х		Название функции
	0	1
f0 = 0	0	0	Константа «0»
f1 = х	0	1	Переменная х
f2 =	1	0	Инверсия х
f3 = 1	1	1	Константа «1»

Число всех булевых функций двух переменных равно 16 (табл. 3).

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

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

Таблица 3

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

Обозначение функции и выражение через операции И, ИЛИ, НЕ	х1	0	0	1	1	Название	Специальное обозначение	Чтение
	х2	0	1	0	1
f0 = 0		0	0	0	0	Константа «0»	0	Всегда «0»
f1 = х1х2		0	0	0	1	Конъюнкция	х1х2	х1 и х2
f2 =		0	0	1	0	Запрет по х2		Неверно, что если х1, то х2
f3 = х1		0	0	1	1	Переменная х1	х1
f4 =		0	1	0	0	Запрет по х1		Неверно, что если х2, то х1
f5 = х2		0	1	0	1	Переменная х2	х2
f6 = 		0	1	1	0	Сложение по модулю 2	х1х2	х1 неравнозначно х2
f7 = х1х2		0	1	1	1	Дизъюнкция	х1х2	х1 или х2
f8 =		1	0	0	0	Функция (стрелка) Пирса	x1x2	Ни х1, ни х2
f9 = 		1	0	0	1	Эквивалентность	x1x2	х1 равнозначно х2
f10 =		1	0	1	0	Инверсия х2		Не х2
f11 = 		1	0	1	1	Импликация	x2x1	Если х2, то х1
f12 =		1	1	0	0	Инверсия х1		Не х1
f13 = 		1	1	0	1	Импликация	x1x2	Если х1, то х2
f14 = 		1	1	1	0	Функция (штрих) Шеффера	x1/x2	Неверно, что х1 и х2
f15 = 1		1	1	1	1	Константа «1»	1	Всегда «1»