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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Упражнение 2. Докажите, что если формула не общезначима и не противо-
речива, то она выполнима и опровержима одновременно.
3. Логические эквивалентности
Необходимо знать простые примеры общезначимых формул и
уметь применять их для получения других общезначимых формул.
Теорема 1. Следующие формулы тождественно истинны:
(1) A ∨ B ⇔ B ∨ A
A ∧ B ⇔ B ∧ A (коммутативность)
(2) (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C)
(A ∧ B) ∧ C ⇔ A ∧ (B ∧ C) (ассоциативность)
(3) (A ∨ B) ∧ C ⇔ (A ∧ C) ∨ (B ∧ C)
(A ∧ B) ∨ C ⇔ (A ∨ C) ∧ (B ∨ C) (дистрибутивность)
(4) ¬(A ∨ B) ⇔ (¬B ∧ ¬A)
¬(A ∧ B) ⇔ (¬B ∨ ¬A) (законы Де М´органа)
(5) ¬¬A ⇔ A (закон двойного отрицания)
(6) ¬(A ∧ ¬A) (закон отрицания противоречия)
(7) A ∨ ¬A (закон исключенного третьего)
(8) A ⇔ A (закон тождества)
(9) A ∨ A ⇔ A
A ∧ A ⇔ A (законы идемпотентности)
(10) A ⇒ B ⇔ ¬A ∨ B (закон импликации)
(11) (A ⇔ B) ⇔ (A ⇒ B) ∧(B ⇒ A) (закон эквиваленции).
/ Доказательство проводится с помощью построения таблиц истин-
ности. Например, для 1-го закона Де Моргана (4):
A B A ∨ B F
1
¬A ¬B F
2
F
0 0 0 1 1 1 1 1
0 1 1 0 1 0 0 1
1 0 1 0 0 1 0 1
1 1 1 0 0 0 0 1
Обозначения F, F
1
, F
2
использованы для всей формулы и ее под-
формул, стоящих слева и справа от символа ⇔ : F
1
= ¬(A ∨ B),
F
2
= (¬B ∧ ¬A), F = ¬(A ∨ B) ⇔ (¬B ∧ ¬A). .
Формулы F и G называются (логически) эквивалентными, если
|= F ⇔ G. Будем обозначать (логическую) эквивалентность формул
следующим образом: F ∼ G. Мы уже имеем некоторый запас эквива-
лентных формул, с помощью которых можно производить эквивалент-
ные преобразования, аналогичные принятым в алгебре: переставлять
11

Страницы