что такое булева алгебра

10.12.202316.04.2022 admin 0 Comments

Булева алгебра

Булевой алгеброй [1] [2] [3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

		ассоциативность
		коммутативность
		законы поглощения
		дистрибутивность
		дополнительность

Первые три аксиомы означают, что (A, , ) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

Содержание

Некоторые свойства

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:




		дополнение 0 есть 1 и наоборот
		законы де Моргана
.	инволютивность отрицания, закон снятия двойного отрицания.

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

		1 коммутативность, переместительность
		2 ассоциативность, сочетательность
3.1 конъюнкция относительно дизъюнкции	3.2 дизъюнкция относительно конъюнкции	3 дистрибутивность, распределительность
		4 комплементность, дополнительность (свойства отрицаний)
		5 законы де Моргана
		6 законы поглощения
		7 Блейка-Порецкого
		8 Идемпотентность
	9 инволютивность отрицания, закон снятия двойного отрицания
		10 свойства констант

дополнение 0 есть 1	дополнение 1 есть 0
		11 Склеивание

Примеры

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

Представления булевых алгебр

Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки.

Знаменитая теорема Стоуна утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то компактного вполне несвязного хаусдорфова топологического пространства.

Аксиоматизация

В 1933 г. американский математик Хантингтон предложил следующую аксиоматизацию для булевых алгебр:

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

Этот вопрос оставался открытым с 30-х годов и был любимым вопросом Тарского и его учеников.

В 1996 г. Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

Источник

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

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

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

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

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

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

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

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

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

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

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

Функция	Название	Обозначение
	Константа нуля
	Повторение 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

Ответить на контрольные вопросы, а затем посмотреть ответы

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

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

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

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