Алгебра логики

Материал из Википедии — свободной энциклопедии

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

Содержание

1 Определение
2 Аксиомы
3 Логические операции
4 Свойства логических операций
5 История

[править] Определение

Высказывания строятся над множеством {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$ ).

[править] Аксиомы

1. ¬(¬x)=x, x=¬(¬x);
2. x*(¬x)=0;
3. x+1=1;
4. x+x=x, x=x+x+x;
5. x+0=x;
6. x*x=x, x=x*x*x;
7. x*0=0;
8. x*1=x;
9. x+(¬x)=1.

Унарные логические операции
x	g₁ ( $\lnot$ )	g₂ (=)	g₃ (1)	g₄ (0)
0	1	0	1	0
1	0	1	1	0

g₁(x) — отрицание/негация (g₁(x) = $\neg$ x = x')

g₂(x) — тождественная функция (g₂(x) = x)

Бинарные логические операции
x	y	f₁ ( $\land$ )	f₂ ( $\lor$ )	f₃ ( $\equiv$ )	f₄ ( $\oplus$ )	f₅ ( $\subset$ )	f₆ ( $\supset$ )	f₇ ( $\downarrow$ )	f₈ ( $\mid$ )
0	0	0	0	1	0	1	1	1	1
0	1	0	1	0	1	0	1	0	1
1	0	0	1	0	1	1	0	0	1
1	1	1	1	1	0	1	1	0	0
x	y	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅	f₁₆
0	0	0	0	1	1	0	0	1	0
0	1	0	1	1	0	0	1	1	0
1	0	1	0	0	1	1	0	1	0
1	1	0	0	0	0	1	1	1	0

Здесь 0 и 1 — тождественные нуль и единица соответственно,

f₁(x, y) — конъюнкция (f₁(x, y) = x&y = x $\cdot$ y = x $\land$ y = min(x, y)),

f₂(x, y) — дизъюнкция (f₂(x, y) = x $\lor$ y = max(x, y)),

f₃(x, y) — эквивалентность (f₃(x, y) = x $\sim$ y = x $\equiv$ y = x $\leftrightarrow$ y),

f₄(x, y) — сумма по модулю два (f₄(x, y) = x $\oplus$ y),

f₅(x, y) — импликация от y к x (f₅(x, y) = x $\leftarrow$ y = x $\subset$ y),

f₆(x, y) — импликация от x к y (f₆(x, y) = x $\rightarrow$ y = x $\supset$ y),

f₇(x, y) — стрелка Пи́рса = функция Да́ггера = функция Ве́бба
(«антидизъюнкция») (f₇(x, y) = x $\downarrow$ y).

f₈(x, y) — штрих Ше́ффера («антиконъюнкция») (f₈(x, y) = x $\mid$ y),

f₉(x, y), f₁₀(x, y) — инверсии импликаций f₅ и f₆,

f₁₁—f₁₄ — функции только одного аргумента,

f₁₅, f₁₆ — тождества.

Все вышеперечисленные функции называются логическими связками.

[править] Логические операции

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество 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).
Законы де Мо́ргана:
- $\neg$ (x $\land$ y) = ( $\neg$ x) $\lor$ ( $\neg$ y),
- $\neg$ (x $\lor$ y) = ( $\neg$ x) $\land$ ( $\neg$ y).
Законы поглощения:
- x $\land$ (x $\lor$ y) = x,
- x $\lor$ (x $\land$ y) = x.
Другие (1):
- x $\land$ ( $\neg$ x) = x $\land$ 0 = x $\oplus$ x = 0.
- x $\lor$ ( $\neg$ x) = x $\lor$ 1 = x $\sim$ x = x $\rightarrow$ x = 1.
- x $\lor$ x = x $\land$ x = x $\land$ 1 = x $\lor$ 0 = x $\oplus$ 0 = x.
- x $\oplus$ 1 = x $\rightarrow$ 0 = x $\sim$ 0 = x $\mid$ x = x $\downarrow$ x = $\neg$ x.
- $\bar\bar x = x$ .
Другие (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}$ = $(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$ .
Другие (3) (Дополнение законов де Мо́ргана):
- $x\mid y$ = $\neg (x\land y)$ = $\neg x\lor\neg y$ .
- $x\downarrow y$ = $\neg (x\lor y)$ = $\neg x\land\neg y$ .

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

[править] История

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

Источник — «http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B8»