ВУЗ:
Составители:
Рубрика:
b) «существует по меньшей мере два различных x, таких, что Q(x)»;
c) «существует не более двух x, таких, что Q(x)»;
d) «существует ровно два различных x, таких, что Q(x)».
Формулы логики предикатов
95. Приведите к предваренной нормальной форме:
a) ∃xF (x) ⇒ ∀xG(x);
b) ¬(∀xF (x) ⇒ ∃yG(y));
c) ∃y∃u((∃xF (x, y, z) ⇒ ∀xG(x, y)) ∧ ¬∀zF (y, u, z));
d) ∃xF (x, z) ∧ (G(x, y) ⇒ ∀zH(z, x));
e) ∀x¬∃yF (x, y, z) ∧ ∃x∃yG(y, x) ⇒ ∃zH(z);
f) ∀x∀yF (x, y) ⇒ ∃x∃yG(x, y);
g) (¬∃xF (x, y, z) ⇒ ∀xF (x, x, x)) ∨ F (x, y, z);
h) ¬(∃z¬∀x(G(x, y) ∧ F (x, z)) ⇒ ∀yH(y, z));
i) ∀x(¬F (x) ⇒ ∀y(¬F (y) ⇒ ∀z(¬F (z) ⇒ ∀uF (u))));
j) F (x, y) ∧ ∀yG(x, y, z) ∧ ¬∃xF (x, x);
k) ∀xF (x, y, z) ⇒ (∀yF (x, y, z) ⇒ (∀zF (x, y, z) ⇒ G(u))).
96. Докажите эквивалентность формул:
a) ∃x(F (x) ⇒ G(x)) ∼ ∀xF (x) ⇒ ∃xG(x);
b) ∃x∀y(F (x) ∧ G(y)) ∼ ∀y∃x(F (x) ∧ G(y));
c) ∃x∀y(F (x) ∨ G(y)) ∼ ∀y∃x(F (x) ∨ G(y)).
97. Докажите общезначимость формул:
a) ∀x(F (x) ⇒ F (x));
b) ∀xF (x) ⇒ ∃xF (x);
c) ∀xF (x) ⇒ F (y);
d) ∃y∀xF (x, y) ⇒ ∀x∃yF (x, y);
e) F (y) ⇒ ∃xF (x);
f) ∃xG(x, x) ⇒ ∃y∃zG(y, z).
98. Выполнимы ли следующие формулы:
a) ∃xF (x);
b) ∀xF (x);
c) ∃xF (x) ⇒ ∀xF (x);
d) ∃x∀y(F (x, x) ∧ ¬F (x, y));
e) ∃x∃y(F (x) ∧ ¬F (y));
f) ¬F (x) ∧ ∀yF (y).
99. Докажите невыполнимость формул:
a) ∃x(F (x) ∧ ¬F (x));
b) F (x) ∧ ¬∃xF (x);
c) ∃y∀x¬F (y, x) ∧ ∀x∃yF (x, y);
d) ∀x∀y(H(x) ⇒ H(y)) ∧ ∃xH(x) ∧ ∃x¬H(x).
100. Докажите, что следующие формулы выполнимы, но не об-
щезначимы:
a) ∀x∃yF (x, y);
b) F (y) ⇒ ∀xF (x);
c) ∃xF (x) ⇒ F (y);
d) ∀x∃yF (x, y) ⇒ ∃y∀xF (x, y);
e) ∀y∃xH(x, y) ∧ ¬∃x∀yH(x, y);
f) ∃xF (x, y) ∧ ∃xF (y, x);
18
