Мы уже видели связки c нулевой арностью: логическое константы 0 (ложь) и 1 (истина).
Двойной соединитель равенства между логическими выражениями пишется ⇔ и назвается эквивалентностью: A ⇔ B читается как «A эквивалентно B».
Вот наиболее полезные связки в порядке арности n > 0 по своим свойствам для всех значений логических переменных (заменяемых формулами A, B, C).
Отрицание
отрицание ¬ обменивает булевы выражения (¬A читается «не A»):
| ¬1 ¬0 ¬(¬A) |
⇔ 0 ⇔ 1 ⇔ A |
Обозначается также корнем из аргумента (формируя другой символ в том же формате)):
| x ≠ y x ∉ E (A ⇎ B) (A ⇎ B) |
⇔ ¬(x=y) ⇔ ¬(x ∈ E) ⇔ ¬(A ⇔ B) ⇔ (A ⇔ ¬B)) |
(x отличается y) (x не принадлежит к E) (Неэквивалентность) |
Конъюкция, дизъюнкции
Соединение ∧ означает «и», будучи истинным только тогда, когда оба аргумента являются истинными;
Дизъюнкция ∨ означает «или», будучи истинным всегда, за исключением, когда оба аргумента являются ложными.
Каждый из них может быть:
| Идемпотентным (A ∧ A) ⇔ A (A ∨ A) ⇔ A |
Коммутативным (B ∧ A) ⇔ (A ∧ B)
(B ∨ A) ⇔ (A ∨ B) |
Ассоциативным ((A ∧ B) ∧ C) ⇔ (A
∧ (B ∧ C))
((A ∨ B) ∨ C) ⇔ (A ∨ (B ∨ C)) |
Дистрибутивным (A ∧ (B ∨ C)) ⇔ ((A
∧ B) ∨ (A ∧ C))
(A ∨ (B ∧ C)) ⇔ ((A ∨ B) ∧ (A ∨ C)) |
Симметрия между ними происходит от того, что они обмениваются отрицаниями:
(A ∨ B)
⇎ (¬A ∧ ¬B)
(A ∧ B) ⇎ (¬A ∨ ¬B)
Строки союзов, таких как (A ∧ B ∧ C), сокращают любую формулу с большим количеством скобок, например, ((A ∧ B) ∧ C), которые эквивалентны друг другу, благодаря ассоциативности; и схожи строки дизъюнкций такие как (A ∨ B ∨ C).
Утверждение конъюнкции формул составляет все эти формулы.
Его отрицание A ⇎ B можно также прочитать как отрицание аргумента (A ⇎ B), либо как «исключающее или» ((A ∨ B) ∧ ¬(A ∧ B)).
Импликация
Бинарный соединитель импликаци ⇒ определяется как (A ⇒ B) ⇔ ((¬A) ∨ B). Это можно прочитать как «из A следует B», «A является достаточным условием для B», или «B является необходимым условием для A». Это верно всегда, за исключением когда A - ложь, так как из-за лжи не может вытекать правда.
К тому же,
| (A ⇒ B) ⇎ (A ⇒ B) ⇔ |
(A ∧ ¬B) (¬B ⇒ ¬A) |
Формула ¬B ⇒ ¬A называется контрапозитивной из A ⇒ B, и эквивалентна ей.
Эквивалентность также может быть рассмотрена, как
⇔ (эквивалент), равенство логических значений: (A ⇔ B) ⇔ ((A ⇒ B) ∧ (B ⇒ A)).
Доказательство, что A ⇔ B может быть получено из импликации (A ⇒ B), то другой (B ⇒ A), называется его обратным.
Формула (A ∧ (A ⇒ B)) будет сокращенна как A ∴ B, которая означает «из A следует В». Это эквивалентно (A ∧ B), но с указанием, что она выведена из истин A и (A ⇒ B).
Это превращает свойства ассоциативности и дистрибутивности в различные формулы:
Наконец,
Последовательности импликаций и эквивалентностей
В различных видах аббревиатур, любая строка формул связанная с помощью ⇔ и / или ⇒ будет означать конъюнкцию всех этих импликаций и эквивалентностей между соседними формулам:
(A ⇒ B
⇒ C) ⇔ ((A ⇒ B) ∧ (B ⇒ C)) ⇒
(A ⇒ C)
(A ⇔ B ⇔ C) ⇔ ((A ⇔ B) ∧ (B
⇔ C)) ⇒ (A ⇔ C)
0 ⇒ A ⇒ A ⇒ 1
(¬A) ⇔ (A ⇒ 0) ⇔ (A ⇔ 0)
(A ∧ 1) ⇔ A ⇔ (A ∨ 0) ⇔ (1 ⇒ A) ⇔ (A
⇔ 1)
(A ∧ B) ⇒ A
⇒ (A ∨ B)
Аксиомы равенства
Для любого функтора T и объектов x, y (что может символизировать элементы с параметрами)
| x = y ⇒ x = y ⇒ |
x = x T(x) = T(y) (A(x) ⇔ A(y)) |
Последняя формула может быть записана: (A(x) ∧ x = y) ⇒ A(y), так как обратное A(y) ⇒ A(x) может быть выведено либо из контрапозиции (замена ¬A) или из симметрии равенства (x = y ⇒ y = x) , полученные путем использования в качестве A(z) формулы (z = x).
Это также верно для всех x, y, z, (x = y ∧ y = z) ⇒ x = z. Формула (x = y ∧ y = z) будет сокращена как x = y = z.
Вероятность
Будем говорить, что A доказуема в T и будем писать T⊢ A, если существует доказательство A в T.
Опять же, опровержение формулы A в T является доказательством ¬A. Если существует (T⊢ ¬A), формула называется опровержимой (в T).
Формула называется неразрешимой (в T), если она не является ни доказуемой, ни опровергнутой.
Если формула доказуема и опровержима одновременно, это означает, что теория противоречива:
(A ∧
¬A) ⇔ 0
((T⊢ A)∧(T⊢ ¬A))⇔(T⊢ 0).
Теория T называется противоречивой, если T ⊢ 0, в противном - совместной. В противоречивой теории, каждая формула доказуема. Такая теория не имеет модели.
Доказательства, как правило, последовательность формул, каждая которая истинна благодаря предыдущей и благодаря свойствам связок и равенства. Могут появиться новые соединения в языке особенно при работе с кванторами (см. 1.9) и вводя символы определенные выражениями.
В частности, равенство между элементами x = y позволяет заменить любое вхождение х на у в любом выражении, не влияя на результат; когда символы, определеные элементами, равны, они могут быть заменены друг с другом в любом выражении. Аксиомы и другие правила, выраженные символами переменных, могут использовать вместо этих переменных элементы.
Доказуемые формулы с известным доказательством могут быть по-разному называны в обычном языке в зависимости от степени их важности: теорема является важнее, чем утверждение; любое из них может быть выведено из не менее важной леммы, и из этого может легко выводиться следствие.