imported>Pipian82: отмена правки 152168999 участника 92.100.39.125 (обс.) Вандализм

2026-03-11T17:48:56Z

отмена правки 152168999 участника 92.100.39.125 (обс.) Вандализм

Новая страница

{{не путать|булева алгебра|булевой алгеброй}}
{{Нужна статья|Двоичная логика}}
'''Алгебра логики''' ('''алгебра высказываний''') — раздел [[математическая логика|математической логики]], в котором изучаются логические операции над [[логическое высказывание|высказываниями]]<ref>{{БСЭ3|заглавие=Алгебра логики}}</ref>. Обычно используется ''двоичная'' (''бинарная'') логика (предполагается, что высказывания могут быть только истинными или ложными), однако возможно [[Многозначная_логика|расширение]] (например до [[троичная логика|троичной логики]] в языке [[Аймара_(язык)#Уникальные_особенности|Аймара]], с использованием которой например задача поиска отличной монеты взвешиванием решается быстрее).

Основоположником её является [[Буль, Джордж|Дж. Буль]], английский [[математик]] и [[логика|логик]], положивший в основу своего логического учения аналогию между алгеброй и логикой.
Алгебра логики стала первой системой математической логики, в которой алгебраическая символика стала применяться к логическим выводам в операциях с понятиями, рассматриваемыми со стороны их объёмов. Буль ставил перед собой задачу решить логические задачи с помощью методов, применяемых в [[алгебра|алгебре]]. Любое [[суждение]] он пытался выразить в виде уравнений с символами, в которых действуют логические законы, подобные законам алгебры.

Впоследствии усовершенствованием алгебры логики занимались [[Джевонс, Уильям Стенли|У. С. Джевонс]], [[Шрёдер, Эрнст|Э. Шрёдер]], [[Порецкий, Платон Сергеевич|П. С. Порецкий]], [[Пирс, Чарльз Сандерс|Ч. Пирс]], [[Фреге, Готлоб|Г. Фреге]], разработавший теорию исчисления высказываний, [[Гильберт, Давид|Д. Гильберт]], добившийся успехов в области применения метода формализации в операциях с логическими высказываниями. Внесли свой вклад [[Рассел, Бертран|Б. Рассел]], придавший вместе с [[Уайтхед, Альфред Норт|А. Уайтхедом]], математической логике современный вид; [[Жегалкин, Иван Иванович|И. И. Жегалкин]], заслугой которого явилась дальнейшая разработка исчисления классов и значительное упрощение теории операций логического сложения; [[Гливенко, Валерий Иванович|В. И. Гливенко]] вынес предмет алгебры логики далеко за рамки изучения объёмных операций с понятиями.

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

== Определение ==
Базовыми элементами, которыми оперирует алгебра логики, являются [[Высказывание (логика)|высказывания]].

Высказывания строятся над [[множество]]м {<math>B</math>, <math>\lnot</math>, <math>\land</math>, <math>\lor</math>, <math>0</math>, <math>1</math>}, где <math>B</math> — непустое множество, над элементами которого определены три [[операция (математика)|операции]]:
: '''<math>\lnot</math>''' ''[[отрицание]]'' ([[унарная операция]]),
: '''<math>\land</math>''' ''[[конъюнкция]]'' ([[бинарная операция|бинарная]]),
: '''<math>\lor</math>''' ''[[дизъюнкция]]'' ([[бинарная операция|бинарная]]),
а логический ноль '''0''' и логическая единица '''1''' — [[постоянная|константы]].

Также используются названия:
* ''Дизъю́нкт'' — [[пропозициональная формула]], являющаяся [[дизъюнкция|дизъюнкцией]] одного или более [[Литерал (математическая логика)|литералов]] (например <math>x_1 \lor \neg x_2 \lor x_4</math>).
* ''Конъюнкт'' — [[пропозициональная формула]], являющаяся [[конъюнкция|конъюнкцией]] одного или более литералов (например <math>x_1 \land \neg x_2 \land x_4</math>).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (<math>\lnot x</math>) либо в виде черты над операндом (<math>\bar x</math>), что компактнее, но в целом менее заметно.

== [[Аксиома|Аксиомы]] ==
# <math>\bar {\bar x}=x</math>, [[Инволюция (математика)|инволютивность отрицания]], [[Закон двойного отрицания|закон снятия двойного отрицания]]
# <math>x\lor\bar x=1</math>
# <math>\ x\lor1=1</math>
# <math>\ x\lor x=x</math>
# <math>\ x\lor0=x</math>
# <math>\ x\land\bar x=0</math>
# <math>\ x\land x=x</math>
# <math>\ x\land0=0</math>
# <math>\ x\land1=x</math>

== [[Логическая операция|Логические операции]] ==
Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:
: <math>B</math> = { Ложь, Истина }
Как правило, в математических выражениях '''Ложь''' отождествляется с логическим нулём, а '''Истина''' — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, [[логика высказываний]] изучает [[Высказывание (логика)|высказывания]] и [[предикат]]ы. Также вводятся дополнительные операции, такие как [[эквиваленция]] <math>\leftrightarrow</math> («тогда и только тогда, когда»), [[импликация]] <math>\rightarrow</math> («следовательно»), сложение по модулю два <math>\oplus</math> («[[исключающее или]]»), [[штрих Шеффера]] <math>\mid</math>, [[стрелка Пирса]] <math>\downarrow</math> и другие.

[[Логика высказываний]] послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в [[бит]]овую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция <math>\neg</math> приобретает смысл вычитания из единицы; <math>\lor</math> — немодульного сложения; & — умножения; <math>\leftrightarrow</math> — равенства; <math>\oplus</math> — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); <math>\mid</math> — не превосходства суммы над 1 (то есть <math>A</math> <math>\mid</math> <math>B</math> = <math>(A + B) <= 1</math>).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом. Это позволило рассматривать, например, логику [[кубит]]ов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено»), комплексную логику и др.

== Свойства логических операций ==
# [[Коммутативность]]: <math>x\circ y = y\circ x ,\circ\in \{ \land, \lor, \oplus, \sim, \mid, \downarrow \}</math>.
# [[Идемпотентность]]: <math>x\circ x=x, \circ\in \{\land, \lor \}</math>.
# [[Ассоциативность (математика)|Ассоциативность]]: <math>(x\circ y)\circ z = x\circ(y\circ z), \circ\in \{\land, \lor, \oplus, \sim \}</math>.
# [[Дистрибутивность]] конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
#* <math>x\land (y\lor z) = (x\land y)\lor (x\land z)</math>,
#* <math>x\lor (y\land z) = (x\lor y)\land (x\lor z)</math>,
#* <math>x\land (y\oplus z) = (x\land y)\oplus (x\land z)</math>.
# [[Законы де Моргана|Законы де Мо́ргана]]:
#* <math>\overline{x\land y} = \bar x \lor \bar y</math>,
#* <math>\overline{x\lor y} = \bar x\land \bar y</math>.
# Законы поглощения:
#* <math>x\land (x\lor y) = x</math>,
#* <math>x\lor (x\land y) = x</math>.
# Другие (1):
#* <math>x\land \bar x = x\land 0 = x\oplus x = 0</math>.
#* <math>x\lor \bar x = x\lor 1 = x\sim x = x\rightarrow x = 1</math>.
#* <math>x\lor x = x\land x = x\land 1 = x\lor 0 = x\oplus 0 = x</math>.
#* <math>x\oplus 1 = x\rightarrow 0 = x\sim 0 = x\mid x = x\downarrow x = \bar x</math>.
#* <math>\bar{\bar x} = x</math>, [[Инволюция (математика)|инволютивность отрицания]], [[Закон двойного отрицания|закон снятия двойного отрицания]].
# Другие (2):
#* <math>x\oplus y = x\land \bar y \lor \bar x\land y = (x\lor y)\land (\bar x\lor \bar y)</math>.
#* <math>x\sim y = \overline{x\oplus y} = 1\oplus x\oplus y = x\land y\lor \bar x \land \bar y = (x\lor \bar y)\land (\bar x\lor y)</math>.
#* <math>x\rightarrow y = \bar x \lor y = x\land y\oplus x\oplus 1</math>.
#* <math>x \lor y = x \oplus y \oplus x\land y</math>.
# Другие (3) (Дополнение законов [[Морган, Огастес де|де Мо́ргана]]):
#* <math>x\mid y = \overline {x\land y} = \bar x \lor \bar y</math>.
#* <math>x\downarrow y = \overline {x\lor y}= \bar x\land \bar y</math>.

Существуют методы упрощения логической функции: например, [[Карта Карно]], [[метод Куайна - Мак-Класки]]

== История ==
Своим существованием наука «алгебра логики» обязана английскому математику [[Буль, Джордж|Джорджу Булю]], который исследовал '''[[логика высказываний|логику высказываний]]'''. Первый в России курс по алгебре логики был прочитан [[Порецкий, Платон Сергеевич|П. С. Порецким]] в [[Казанский государственный университет|Казанском государственном университете]].

== См. также ==
* [[Булева алгебра]]
* [[Булева функция]]
* [[Битовые операции]]
* [[Логика высказываний]]
* [[Функциональная полнота]]

== Примечания ==
{{примечания}}

{{вс}}
{{Логика}}
{{Нет источников |дата=2010-08-04}}

[[Категория:Алгебра]]
[[Категория:Математическая логика]]

Алгебра логики - История изменений

imported>Pipian82: отмена правки 152168999 участника 92.100.39.125 (обс.) Вандализм