Алгебра логики | это... Что такое Алгебра логики? (original) (raw)

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

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B, $\lnot$ , $\land$ , $\lor$ , 0, 1}, где B — непустое множество, над элементами которого определены три операции:

$\lnot$ отрицание (унарная операция),

$\land$ конъюнкция (бинарная),

$\lor$ дизъюнкция (бинарная),

а также константы — логический ноль 0 и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например $x_1 \lor \neg x_2 \lor x_4$ ). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например $x_1 \land \neg x_2 \land x_4$ ).

Аксиомы

$\bar {\bar x}=x$ , инволютивность отрицания, закон снятия двойного отрицания
$x\lor\bar x=1$
$\ x\lor1=1$
$\ x\lor x=x$
$\ x\lor0=x$
$\ x\land\bar x=0$
$\ x\land x=x$
$\ x\land0=0$
$\ x\land1=x$

Логические операции

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество B, состоящее всего из двух элементов:

B = { Ложь, Истина }

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

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

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

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

Свойства логических операций

Коммутативность: x $\circ$ y = y $\circ$ x, $\circ\in$ {&, $\lor, \oplus, \sim, \mid, \downarrow$ }.
Идемпотентность: x $\circ$ x = x, $\circ\in$ {&, $\lor$ }.
Ассоциативность: (x $\circ$ y) $\circ$ z = x $\circ$ (y $\circ$ z), $\circ\in$ {&, $\lor, \oplus, \sim$ }.
Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
- $x\land (y\lor z) = x\land y\lor x\land z$ ,
- $x\lor y\land z = (x\lor y)\land (x\lor z)$ ,
- $x\land (y\oplus z) = x\land y\oplus x\land z$ .
Законы де Мо́ргана:
- $\overline{x\land y} = \bar x \lor \bar y$ ,
- $\overline{x\lor y} = \bar x\land \bar y$ .
Законы поглощения:
- $x\land (x\lor y) = x$ ,
- $x\lor x\land y = x$ .
Другие (1):
Другие (2):
- $x\oplus y = x\land \bar y \lor \bar x\land y = (x\lor y)\land (\bar x\lor \bar y)$ .
- $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)$ .
- $x\rightarrow y = \bar x \lor y = x\land y\oplus x\oplus 1$ .
- $x \lor y = x \oplus y \oplus x\land y$ .
Другие (3) (Дополнение законов де Мо́ргана):
- $x\mid y = \overline {x\land y} = \bar x \lor \bar y$ .
- $x\downarrow y = \overline {x\lor y}= \bar x\land \bar y$ .

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

История

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

См. также

Примечания

↑ Алгебра логики — статья из Большой советской энциклопедии

Логика
Формальная	Логические операции с понятиями Изменение содержания понятия: отрицание • ограничение • обобщение • деление Изменение объёма понятия: сложение • умножение • вычитаниеТипы: Многозначная логика • Бинарная логикаЗаконы: Закон обратного отношения между содержанием и объёмом понятия
Математическая (теоретическая, символическая)	Логические связки (операции) над высказываниями Высказывание - построение над множеством {B, $\lnot$ , $\land$ , $\lor$ , 0, 1}В - непустое множество, над элементами которого определены три операции: конъюнкция ( $\land$ или &,бинарная) • дизъюнкция ( $\lor$ ,бинарная) • отрицание ( $\neg$ ,унарная) 2 константы: импликация ( $\to$ ) • Круги Эйлера/Диаграмма Венна • Теория множеств

Логика

Формальная

Логические операции с понятиями Изменение содержания понятия: отрицание • ограничение • обобщение • деление Изменение объёма понятия: сложение • умножение • вычитаниеТипы: Многозначная логика • Бинарная логикаЗаконы: Закон обратного отношения между содержанием и объёмом понятия

Математическая (теоретическая, символическая)

Логические связки (операции) над высказываниями Высказывание - построение над множеством {B, $\lnot$ , $\land$ , $\lor$ , 0, 1}В - непустое множество, над элементами которого определены три операции: конъюнкция ( $\land$ или &,бинарная) • дизъюнкция ( $\lor$ ,бинарная) • отрицание ( $\neg$ ,унарная) 2 константы: импликация ( $\to$ ) • Круги Эйлера/Диаграмма Венна • Теория множеств