Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.1. Операции логики Буля

Стрелка Пирса, штрих Шеффера и разность

На рис. 1.7 и 1.8 приведены диаграммы двух новых операций, которые называются, соответственно, стрелка Пирса и штрих Шеффера. Эти диаграммы дополняют объединение и пересечение до фундаментального множества V.

Рис. 1.7

Рис. 1.8

На языке логических формул этот факт выражается следующим образом: для стрелки Пирса —

(x₁ ∨ x₂) ∨ (x₁ ↓ x₂) = 1,       (x₁ ∨ x₂) ∧ (x₁ ↓ x₂) = 0,

для штриха Шеффера —

(x₁ ∧ x₂) ∨ (x₁ | x₂) = 1,       (x₁ ∧ x₂) ∧ (x₁ | x₂) = 0.

Из таблиц истинности для этих операций (табл. 1.3 и 1.4) видно, что

y = x₁ ↓ x₂ = x₁ ∧ x₂ = (x₁ ∨ x₂) ∧ (x₁ ∨ x₂) ∧ (x₁ ∨ x₂),

y = x₁ | x₂ = x₁ ∨ x₂ = (x₁ ∧ x₂) ∨ (x₁ ∧ x₂) ∨ (x₁ ∧ x₂).

Таблица 1.3

x1	x2	y = x1 ↓ x2
0	0	1
1	0	0
0	1	0
1	1	0

Таблица 1.4

x1	x2	y = x1 | x2
0	0	1
1	0	1
0	1	1
1	1	0

На множествах эти операции выглядят следующим образом:

A ↓ B = {1, 2, 4, 6} ↓ {2, 3, 4, 8, 9} = {5, 7, 10, 11} = C₀,

A | B = {1, 3, 5, 6, 7, 8, 9, 10, 11} = C₀ ∪ C₁ ∪ C₂.

Разностью между множествами A и B называется совокупность тех элементов множества A, которые не вошли во множество B:

A – B = {1, 2, 4, 6} – {2, 3, 4, 8, 9} = {1, 6} = C₁.

Диаграмма Эйлера — Венна для нее приведена на рис. 1.9.

Рис. 1.9

Дополнением к разности служит импликация. Таблицы истинности для разности и импликации представлены табл. 1.5 и табл. 1.6.

Таблица 1.5

x1	x2	y = x1 – x2
0	0	0
1	0	1
0	1	0
1	1	0

Таблица 1.6

x1	x2	y = x1 → x2
0	0	1
1	0	0
0	1	1
1	1	1

y = x₁ → x₂ = x₁ ∨ x₂ = (x₁ ∧ x₂) ∨ (x₁ ∧ x₂) ∨ (x₁ ∧ x₂),

(x₁ – x₂) ∨ (x₁ → x₂) = 1,       (x₁ – x₂) ∧ (x₁ → x₂) = 0.

На диаграмме Эйлера — Венна для импликации (рис. 1.10) показано частичное включение множества A во множество B, которое нужно отличать от полного включения (рис. 1.2).

Рис. 1.10

Если утверждается, что «элементы множества A включены во множество B», то область C₃ обязательно должна быть заштрихована, так как она соответствует истине, а область C₁ с такой же необходимостью должна быть оставлена белой, поскольку ей отвечает прямо противоположное утверждение. Относительно областей C₀ и C₁, находящихся в A, заметим следующее. Мы не имеем права оставлять их белыми, поскольку они прямо не противоречат первому утверждению; но, так как логика двухзначная, мы обязаны все же области, попадающие в A, заштриховать.