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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

27. Используя СКНФ, постройте формулы, принимающие значе-
ние 0 только на следующих наборах значений переменных:
a) F (0, 1) = F (1, 0) = 0 ; b) F (0, 1) = 0 ;
c) F (1, 0, 0) = F (1, 0, 1) = 0 ;
d) F (0, 1, 1) = F (0, 0, 0) = F (0, 1, 0) = 0 ;
e) F (0, 0, 0) = F (0, 1, 0) = F (1, 1, 1) = 0 ;
f) F (1, 1, 1) = F (0, 0, 1) = F (1, 1, 0) = F (1, 0, 0) = 0.
28. Найдите СДНФ и СКНФ следующих формул с помощью таб-
лицы значений:
a) A ⇒ B ;
b) (A | B) ⇒ (A ↓ B) ;
c) (A ∧ B) ∨ C ;
d) (A ⇔ C) ⇒ A ∧ ¬B ;
e) A ∧ (B ⇒ (C ⊕ (A ∧ B))) ;
f) ((A ∧ ¬B) ∨ C) ∧ D.
29. Найдите наипростейшие формулы от трех переменных, по-
следние столбцы таблиц значений которых имеют следующий вид:
a) 0 0 0 0 1 1 1 1;
b) 0 1 0 1 0 1 0 1;
c) 0 0 1 0 0 1 0 0;
d) 1 0 1 1 1 1 0 1;
e) 1 1 0 0 0 0 1 0;
f) 1 0 1 0 1 1 1 0.
30. Найдите формулы F = F (A, B), такие, чтобы имели место
следующие эквивалентности:
a) F ⇔ ¬(A ⇒ B) ∼ A ⇔ B;
b) F ∧ A ⇒ ¬B ∼ (B ⇒ ¬A) ⇒ F ;
c) (F ⇒ A) ∧ (A ⇒ B) ∼ ¬((A ∨ B) ∧ (A ⇒ F )).
31. Найдите формулы от трех переменных F (A, B, C), такие, что-
бы :
a) A ∧ F ∼ A ∧ B и A ∨ F ∼ A ∨ C;
b) A ⇒ F ∼ A ⇒ B ∧ C и F ⇒ A ∼ ¬(B ∨ C) ⇒ A;
c) A ⇒ F ∼ B ⇒ ¬A ∨ C и (C ⇒ B) ⇒ A ∼ ¬A ⇒ ¬F .
IV. Логическое следование
32. Проверьте справедливость логических следований:
a) A, A ⇒ B |= B;
b) ¬B, A ⇒ B |= ¬A;
c) A ⇒ B, B ⇒ C |= A ⇒ C;
d) A ⇒ B |= ¬B ⇒ ¬A;
e) A ⇒ C, B ⇒ C, A ∨ B |= C;
f) ¬A |= A ⇒ B;
g) (A ⇒ B) ⇒ C |= (A ⇒ B) ⇒ (A ⇒ C);
h) A ⇒ (B ⇒ C) |= (A ⇒ B) ⇒ (A ⇒ C).
33. Методом от противного выяснить, справедливо ли следующее:
a) A ⇒ B, D ⇒ ¬C, C ∨ ¬B |= A ⇒ ¬D;
b) A ⇒ B, (A ∨ D) ∧ C ⇒ E, D ⇒ C |= (A ∨ D) ∧ B ⇒ ¬E;
c) A ⇒ C, ¬B ⇒ ¬D, E ⇒ F, ¬A ⇒ ¬B, F ⇒ D |= E ⇒ C;
7

Страницы