Логические функции способы описания логических функций

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

Понятие алгебры логики

На этом уроке знакомимся с алгеброй логики (булевой алгеброй). Одним из её основателей стал английский математик Джордж Буль (1815-1864), который был из довольно бедной семьи, а в юности зарабатывал переводами сочинений древнегреческих философов. За этим занятием его и посетила мысль о том, что высказываниям можно присваивать значения 1 («истина») и 0 «ложь».

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

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

Пусть функция от n переменных и любой из её аргументов могут принимать значения только из множества <0, 1>. Тогда эта функция называется логической, или булевой, или переключательной, или функцией алгебры логики. Описанную функцию часто называют также булевым вектором. Количество функций от n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая «1») или сигнал отсутствует (логический «0»).

На логических элементах, реализующих булевы функции, строятся логические схемы электронных устройств.

Законы булевой алгебры применяются и в программировании — при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён здесь (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример — применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.

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

Логические функции

Логические функции одной переменной

Функция	Название	Обозначение
	Константа нуля
	Повторение x
	Логическое отрицание, инверсия, «НЕ»
	Константа единицы

Переменная	Логические функции
x
0	0	0	1	1
1	0	1	0	1

Логические функции двух переменных

Функция	Название	Обозначение
	Константа нуля	или False
	Логическое умножение, конъюнкция, «И»	или или или
	Запрет по	или
	Переменная
	Запрет по	или
	Переменная
	Сложение по модулю 2, отрицание эквивалентности, исключающее «ИЛИ»	или или
	Логическое сложение, дизъюнкция, «ИЛИ»	или или или
	Функция Пирса (Вебба), «ИЛИ-НЕ»	или или
	Логическая равнозначность, эквиваленция	или или или
	Отрицание
	Правая импликация	или
	Отрицание
	Левая импликация	или
	Функция Шеффера, «И-НЕ»	или или
	Константа единицы	или True

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

X1	0	0	1	1
X2	0	1	0	1
	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
	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. Даны две переменные x 1 и x 2 . Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:

Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):

• отрицание и сложение по модулю два
• эквивалентность и повторение x
• отрицание и импликация
• функция Шеффера и эквивалентность
• запрет по x 2 и отрицание

Булев базис (логический базис)

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

Инверсия (логическое отрицание, «НЕ»)

.

0	1
1	0

Конъюнкция (логическое умножение, «И»)

.

0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция (логическое сложение, «ИЛИ»)

.

0	0	0
0	1	1
1	0	1
1	1	1

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

Аналитическое представление логических функций

В качестве исходного описания сложных логических функций обычно используется таблица истинности, однако упрощение функций удобнее производить в аналитической форме. При аналитической записи функция алгебры логики представляется либо в виде логической суммы элементарных логических произведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элементарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи имеет название дизъюнктивной нормальной формы (ДНФ), вторая — конъюнктивной нормальной формы (КНФ). В этих названиях термин «нормальная» означает отсутствие общей инверсии (отрицания) над несколькими перемнными сразу.

Дизъюнктивная нормальная форма

.

X1	X2	f
0	0	1
0	1	1
1	0	1
1	1	0

Конъюнктивная нормальная форма

.

X1	X2	f
0	0	0
0	1	0
1	0	1
1	1	0

Способы описания логических функций

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

• словесный;
• табличный;
• числовой;
• аналитический;
• координатный;
• графический.

Пример табличного описания функций алгебры логики. В верхней таблице под набором подразумевается набор значений логических переменных (1 или 0), а f — это значение функции алгебры логики, заданной определённой формулой. Нижняя таблица несёт в себе более подробную информацию о наборах, поскольку в ней указаны значения переменных.

Номер набора	f
0	0
1	1
2	0
3	0
4	1
5	1
6	0
7	1

X1	X2	X3	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

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

Пример числового описания логических функций

или .

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

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

Пример графического описания логических функций

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

Аксиомы конъюнкции

.

Аксиомы дизъюнкции

.

Аксиомы отрицания

если , то ; если , то .

Теоремы алгебры логики

Теоремы исключения констант

.

Теоремы идемпотентности (тавтологии, повторения)

.

для n переменных

.

Теорема противоречия

.

Теорема «исключённого третьего»

.

Теорема двойного отрицания (инволюции)

.

Законы алгебры логики

Ассоциативный (сочетательный) закон

.

Коммутативный (переместительный) закон

.

Дистибутивный (распределительный) закон

.

.

Законы де Моргана (законы общей инверсии или дуальности)

.

.

Закон поглощения (элиминации)

.

Закон склеивания (исключения)

.

Источник