Элементы математической логики. Фролов И.С. - 14 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

Теорема 5. Если F ∼ G, то F
A
H
∼ G
A
H
(правило подстановки).
/ Интерпретации для формул F
A
H
и G
A
H
надо задавать на множестве
всех атомов формул F и G, исключая, быть может, A. Какое бы зна-
чение ни получила формула H при этом, оно уже учтено в таблицах
значений для формул F и G (так как таблицы значений отражают все
возможные интерпретации). Поскольку эти таблицы совпадают, также
совпадают таблицы значений формул F
A
H
и G
A
H
. .
Обозначим F
G
формулу, в которой выделена некоторая подфор-
мула G. Очевидно, эта формула может быть получена подстановкой
формулы G вместо некоторого атома. Естественно в таком случае обо-
значить F
H
формулу, получаемую из F
G
заменой выделенной подфор-
мулы G на формулу H.
Теорема 6. Если G ∼ H, то F
G
∼ F
H
(правило замены).
/ В процессе построения таблицы значений для формул F
G
и F
H
колонки таблиц, соответствующие подформулам G и H, совпадут в си-
лу G ∼ H, но все дальнейшие построения в обеих таблицах совершенно
идентичны. В результате мы получим совпадение колонок таблиц для
формул F
G
и F
H
. .
Пример 6. ¬A ⇒ B ∼ ¬¬A ∨ B по правилу подстановки,
примененному к закону импликации; ¬¬A ∨ B ∼ A ∨ B по правилу
замены, примененному к закону двойного отрицания; таким образом
¬A ⇒ B ∼ A ∨ B по правилу цепи эквивалентностей.
Отметим еще ряд эквивалентностей, полезных при проведении
преобразований:
(a) A ∨ (A ∧ B) ∼ A, A ∧ (A ∨ B) ∼ A (правило поглощения)
(b) A ∨ ¬ A ∼ 1 , A ∧ ¬A ∼ 0,
(c) A ∨ 0 ∼ A, A ∧ 0 ∼ 0,
(d) A ∨ 1 ∼ 1, A ∧ 1 ∼ A,
где 1 стоит на месте тождественно истинного, а 0 — на месте тожде-
ственно ложного высказывания.
Пример 7. A ∼ A ∧ 1 ∼ A ∧ (B ∨¬B) ∼ (A ∧B) ∨ (A ∧¬B).
Упражнение 5. Докажите аналогичную эквивалентность (A∨ B)∧(A∨¬B) ∼
∼ A.
Упражнение 6. Дайте обоснование правилу поглощения.
13

Страницы