Задачи по математической логике. Фролов И.С. - 4 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

a) (¬A ⇒ A) ⇒ A;
b) (A ⇒ B) ∧ A ⇒ B;
c) (A ⇒ B) ⇔ (¬B ⇒ ¬A);
d) ¬(A ⇒ B) ⇔ (A ∧ ¬B);
e) (A ⇒ B) ⇒ (A ∧ C ⇒ B ∧ C);
f) (A ⇒ B) ∧ (C ⇒ D) ⇒ (A ∧ C ⇒ B ∧ D);
g) (A ⇒ B) ∨ (C ⇒ D) ⇒ (A ∧ C ⇒ B ∨ D).
8. Докажите выполнимость следующих формул, указав соответ-
ствующую модель:
a) ¬(A ⇒ ¬A);
b) (A ⇒ B) ⇒ (B ⇒ A);
c) ¬((A ⇔ ¬B) ∨ C) ∧ B;
d) A ∧ B ⇒ (C ∨ B ⇒ ¬C).
9. Покажите, что следующие формулы опровержимы, указав ин-
терпретации, при которой они ложны:
a) A ∨ B ⇒ (¬A ∧ B) ∨ (A ∧ ¬B);
b) (A ∨ B) ∨ C ⇒ (A ∨ B) ∧ (A ∨ C);
c) ((A ⇒ B ∧ C) ⇒ (¬B ⇒ ¬A)) ⇒ ¬B.
10. Определите, являются ли следующие формулы общезначимы-
ми, выполнимыми, опровержимыми или противоречивыми:
a) A ⇔ A;
b) A ⇒ ¬A;
c) A ∨ B ⇔ A ∧ B;
d) ((A ⇒ B) ⇒ B) ⇒ B;
e) (A ⇒ B) ⇒ C;
f) (A ⇒ B) ∧ (B ⇒ C) ∧ ¬(A ⇒ C).
11. Докажите эквивалентность формул:
a) A ∨ B ∼ ¬A ⇒ B;
b) A ∧ B ∼ ¬(A ⇒ ¬B);
c) (A ∨ B) ∧ (A ∨ ¬B) ∼ A;
d) A ⇔ B ∼ (¬A ∨ B) ∧ (A ∨ ¬B);
e) (A ∧ B) ⇒ C ∼ A ⇒ (B ⇒ C).
12. Докажите, что следующие пары формул не эквивалентны
друг другу:
a) A ⇒ B и ¬A ⇒ ¬B;
b) A ⇒ B и B ⇒ A;
c) A ⇒ (B ⇒ C) и (A ⇒ B) ⇒ C;
d) A ⇒ (B ⇒ C) и A ⇒ (B ⇔ C).
13. Докажите эквивалентность формул методом математической
индукции:
a) A ∧ (B
1
∨ . . . ∨ B
n
) ∼ (A ∧ B
1
) ∨ . . . ∨ (A ∧ B
n
);
b) ¬(A
1
∨ . . . ∨ A
n
) ∼ ¬A
1
∧ . . . ∧ ¬A
n
;
c) A ∨ (B
1
∧ . . . ∧ B
n
) ∼ (A ∨ B
1
) ∧ . . . ∧ (A ∨ B
n
);
d) ¬(A
1
∧ . . . ∧ A
n
) ∼ ¬A
1
∨ . . . ∨ ¬A
n
.
II. Эквивалентные преобразования формул
14. Преобразуйте формулы так, чтобы они содержали только
связки ¬ и ∨ :
a) ¬A ∧ ¬B ⇒ A ∨ B;
b) (A ⇒ B) ⇒ B ∧ C;
c) (¬A ∧ ¬B) ∨ C ⇒ C ∧ ¬B;
d) ((A ⇒ B ∧ C) ⇒ (¬B ⇒ ¬A)) ⇒ ¬B.
4

Страницы