Краткий конспект: властивфункційості булевих

Операція

Позначення

НЕ (NOT)

¬x

И (AND)

x ∧ y; xy; x · y

ИЛИ (OR)

x ∨ y; x + y

XOR

x ⊕ y

Закони нуля та одиниці

Ідемпотентність

x ∧ 0 = 0

x ∧ x = x

x ∨ 1 = 1

x ∨ x = x

x ∧ 1 = x

Протилежність

x ∨ 0 = x

x ∧ ¬x = 0

Подвійне заперечення

x ∨ ¬x = 1

¬(¬x) = x

Комутативність

Асоціативність

x ∧ y = y ∧ x

(x ∧ y) ∧ z = x ∧ (y ∧ z)

x ∨ y = y ∨ x

(x ∨ y) ∨ z = x ∨ (y ∨ z)

x ⊕ y = y ⊕ x

(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)

Дистрибутивність

Поглинання

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

x ∨ (x ∧ y) = x

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

x ∧ (x ∨ y) = x

Закони де Моргана

XOR — основні тотожності

¬(x ∧ y) = ¬x ∨ ¬y

x ⊕ 0 = x

¬(x ∨ y) = ¬x ∧ ¬y

x ⊕ 1 = ¬x

Зв’язок XOR з базовими операціями

x ⊕ x = 0

x ⊕ y = (x ∧ ¬y) ∨ (¬x ∧ y)

x ⊕ ¬x = 1

x ⊕ y = (x ∨ y) ∧ ¬(x ∧ y)

Оборотність XOR

Корисні спрощення

x ⊕ y = z

x ⊕ x ⊕ y = y

x = y ⊕ z

(x ⊕ y) ⊕ y = x

y = x ⊕ z

(x ∧ y) ∨ (x ∧ ¬y) = x