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

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

Номер аксиомы	Формулировка	Пояснения
A₁	x=0, если x¹1	Булева переменная всегда равна нулю либо единице
A₂	x=1, если x¹0
A₃	x=0, если =1	Инверсное значение переменной x противоположно ее прямому значению
A₄	x=1, если =0
A₅	0×0=0	Правила выполнения логического умножения (конъюнкции)
A₆	1×1=1
A₇	0×1=1×0=0
A₈	0Ú0=0	Правила выполнения логического сложения (дизъюнкции)
A₉	1Ú1=1
A₁₀	0Ú1=1Ú0=1

Полученная система аксиом непосредственно следует из определения функций НЕ, И и ИЛИ.

№	Формулировка	Пояснения
1. Идентичность
T₁	x Ú 0 = x	Доказательство теоремы T₁ следует из аксиом A₈ и A₁₀, в которых первое слагаемое заменено на x. Теорема T₁ говорит, что из булева выражения можно удалить часть, равную нулю и связанную с остальным выражением операцией дизъюнкция.
T₂	x × 1 = x	Теорема T₂ доказывается на основе аксиом A₆ и A₇ и говорит, что из булева выражения можно удалить часть, равную единице и связанную с остальным выражением операцией конъюнкция.
2. Наличие нулевых элементов
T₃	x Ú 1 = 1	Теорема T₃ следует из A₉ и A₁₀, свидетельствуя о том, что если какая-то часть булева выражения, связанная с остальным выражением операцией дизъюнкция, равна единице, то и все выражение равно единице.
T₄	x × 0 = 0	Теорема T₄ следует из A₅ и A₅, свидетельствуя о том, что если какая-то часть булева выражения, связанная с остальным выражением операцией конъюнкция, равна нулю, то и все выражение равно нулю.
3. Идемпотентность
T₅	x Ú x = x x Ú x Ú...Ú x = x	Теорема T₅ следует из A₅ и A₉ и свидетельствует, что добавление или удаление идентичных частей булева выражения, связанных операцией дизъюнкция с остальной частью выражения, не меняет значения булева выражения.
T₆	x × x ×... × x = x	Теорема T₆ следует из A₅ и A₆ и свидетельствует о том, что умножение булева выражения на само себя не меняет значения булева выражения.
4. Эволюция (двойное отрицание)
T₇	= x	Теорема T₇ доказывается последовательным применением аксиом A₃ и A₄. Из T₇ следует, что двойное отрицание булева выражения не меняет его значения. Таким образом, любое четное число отрицаний булева выражения может быть введено или удалено без изменения значения выражения.
5. Дополняемость
T₈	x Ú = 1	Дизъюнкция двух взаимообратных выражений всегда равна единице независимо от значений выражений. Если x=0, то =1 и xÚ=0Ú1=1; если x=1, то =0 и xÚ=1Ú0=1.
T₉	x × = 0	Конъюнкция двух взаимообратных выражений всегда равна нулю независимо от значений выражений. Если x=0, то =1 и x&=0&1=0; если x=1, то =0 и xÚ=1&0=0.
6. Ассоциативность
T₁₀	(aÚb)Úc = aÚ(bÚc)	Теоремы T₁₀ и T₁₁ аналогичны теоремам обычной алгебры и свидетельствуют о том, что значение булева выражения не зависит от порядка вычисления значений его частей.
T₁₁	(a×b)×c = a×(b×c)
7. Коммутативность
T₁₂	a Ú b = b Ú a	Теоремы T₁₂ и T₁₃ свидетельствуют о том, что перестановка членов булева выражения не меняет его значения. Эти теоремы аналогичны теоремам обычной алгебры.
T₁₃	a × b = b × a
8. Дистрибутивность
T₁₄	a×b Ú a×c = a×(bÚc)	Теорема T₁₄ представляет собой процесс вынесения общей переменной за скобки.
T₁₅	(aÚb)×(aÚc) = a Ú b×c	Теорема T₁₅ не имеет своего аналога в обычной алгебре, но ее справедливость может быть доказана на основе рассмотренных выше аксиом и теорем.
9. Поглощение
T₁₆	a Ú a×b = a	Теоремы T₁₆ и T₁₇ позволяют уменьшить число членов булева выражения.
T₁₇	a×(aÚb) = a
10. Склеивание
T₁₈	a×b Ú a×= a	Теоремы T₁₈ и T₁₉ также позволяют уменьшить число членов булева выражения.
T₁₉	(aÚb) × (aÚ) = a
11. Законы Де Моргана
T₂₀		Теоремы Де Моргана имеют важнейшее значение в алгебре логики. Их суть заключается в замене одной операции на другую: операции дизъюнкция на операцию конъюнкция, или наоборот. Понятно, что просто так подобную замену сделать нельзя, поскольку операции совершенно разные и результирующее выражение будет отличаться от исходного. Поэтому для сохранения эквивалентности выражений после замены одной операции на другую над каждым элементом выражения должна быть поставлена инверсия, и над всем выражением также должна быть поставлена инверсия.
T₂₁