Предикатски рачун

Помоћна табела: квантификатори на бројевним скуповима

У задацима често треба „решити“ квантификатор у једнакости \(x = y \circ z\), где је \(\circ\) једна од четири рачунске операције. Табела даје услов на слободне променљиве под којим је формула тачна (1 — увек тачна, 0 — никад). Све променљиве узимају вредности из наведеног скупа, \(\mathbb{N}_0 = \mathbb{N} \cup \{0\}\), а релација дељивости дефинисана је са \[ a \mid b \ \overset{\text{деф}}{\Longleftrightarrow}\ (\exists k \in \mathbb{Z})\, b = a \cdot k. \]

Егзистенцијални квантификатор
Формула Тачна када
\((\exists x \in \mathbb{N}, \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y + z\) 1
\((\exists y \in \mathbb{N})\ x = y + z\) \(x > z\)
\((\exists y \in \mathbb{N}_0)\ x = y + z\) \(x \ge z\)
\((\exists y \in \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y + z\) 1
\((\exists x \in \mathbb{N})\ x = y - z\) \(y > z\)
\((\exists x \in \mathbb{N}_0)\ x = y - z\) \(y \ge z\)
\((\exists x \in \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y - z\) 1
\((\exists y \in \mathbb{N}, \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y - z\) 1
\((\exists z \in \mathbb{N})\ x = y - z\) \(y > x\)
\((\exists z \in \mathbb{N}_0)\ x = y - z\) \(y \ge x\)
\((\exists z \in \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y - z\) 1
\((\exists x \in \mathbb{N}, \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y \cdot z\) 1
\((\exists y \in \mathbb{N}, \mathbb{N}_0, \mathbb{Z})\ x = y \cdot z\) \(z \mid x\)
\((\exists y \in \mathbb{Q}, \mathbb{R})\ x = y \cdot z\) \(x = 0 \lor z \ne 0\)
\((\exists x \in \mathbb{N})\ x = y : z\) \(z \mid y\)
\((\exists x \in \mathbb{N}_0, \mathbb{Z})\ x = y : z\) \(z \mid y \land z \ne 0\)
\((\exists x \in \mathbb{Q}, \mathbb{R})\ x = y : z\) \(z \ne 0\)
\((\exists y \in \mathbb{N})\ x = y : z\) 1
\((\exists y \in \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y : z\) \(z \ne 0\)
\((\exists z \in \mathbb{N})\ x = y : z\) \(x \mid y\)
\((\exists z \in \mathbb{N}_0, \mathbb{Z})\ x = y : z\) \(x \mid y \land \neg(x \ne 0 \land y = 0)\)
\((\exists z \in \mathbb{Q}, \mathbb{R})\ x = y : z\) \(x = 0 \Leftrightarrow y = 0\)
Универзални квантификатор
Формула Тачна када
\((\forall x)\ x = y + z\), \(\ (\forall y)\ x = y + z\), \(\ (\forall z)\ x = y + z\) (сви скупови) 0
\((\forall x)\ x = y - z\), \(\ (\forall y)\ x = y - z\), \(\ (\forall z)\ x = y - z\) (сви скупови) 0
\((\forall x \in \mathbb{N}, \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y \cdot z\) 0
\((\forall y \in \mathbb{N})\ x = y \cdot z\), \(\ (\forall z \in \mathbb{N})\ x = y \cdot z\) 0
\((\forall y \in \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y \cdot z\) \(x = 0 \land z = 0\)
\((\forall z \in \mathbb{N}_0, \mathbb{Z}, \mathbb{Q}, \mathbb{R})\ x = y \cdot z\) \(x = 0 \land y = 0\)
\((\forall x)\ x = y : z\), \(\ (\forall y)\ x = y : z\), \(\ (\forall z)\ x = y : z\) (сви скупови) 0

Код \(\exists\) једначину решавамо по везаној променљивој и питамо се да ли решење припада скупу; на пример, \((\exists y \in \mathbb{N})\, x = y + z\) јер је \(y = x - z \in \mathbb{N}\) тачно када је \(x > z\). Код \(\forall\) једнакост мора да важи за све вредности везане променљиве, што је могуће само у изузетним случајевима: \((\forall y)\, x = y \cdot z\) за \(y = 0\) даје \(x = 0\), а за \(y = 1\) даје \(x = z\).

Задатак 1 Одредити истинитост следећих исказа на доменима \(\mathbb{N}\), \(\mathbb{Z}\) и \(\mathbb{R}\):

(а) \((\forall x)\, x^2 \ge x\)

(б) \((\exists x)\, x^2 = 2\)

(в) \((\forall x)(\exists y)\, y < x\)

(г) \((\exists x)(\forall y)\, x \le y\)

\(\mathbb{N}\) \(\mathbb{Z}\) \(\mathbb{R}\)
(а) \((\forall x)\, x^2 \ge x\) тачно тачно нетачно, \(x = \frac{1}{2}\)
(б) \((\exists x)\, x^2 = 2\) нетачно нетачно тачно, \(x = \sqrt{2}\)
(в) \((\forall x)(\exists y)\, y < x\) нетачно, \(x = 1\) тачно, \(y = x - 1\) тачно, \(y = x - 1\)
(г) \((\exists x)(\forall y)\, x \le y\) тачно, \(x = 1\) нетачно нетачно

У (а) на \(\mathbb{Z}\): за \(x \le 0\) је \(x^2 \ge 0 \ge x\), а за \(x \ge 1\) је \(x^2 = x \cdot x \ge x\). Исказ (г) тврди да постоји најмањи елемент, а исказ (в) да најмањи елемент не постоји — зато су на сваком од ова три домена међусобно супротни.

Задатак 2 Записати одговарајућу формулу и одредити њену истинитосну вредност:

(а) Постоји објекат једнак самом себи.

(б) Сваки природан број је и реалан.

(в) Неки цели бројеви су већи од 8.

(г) Квадрат произвољног реалног броја је негативан.

(д) Једначина \(x^2 = 1\) има решења у скупу природних бројева.

(ђ) Разлика било која два природна броја је природан број.

(е) Не постоји највећи природан број. Негацију у овој формули провући до елементарних формула и добијену формулу прочитати.

(а) \((\exists x)\, x = x\) — тачно, свако \(x\) је сведок.

(б) \((\forall x)(x \in \mathbb{N} \Rightarrow x \in \mathbb{R})\), краће \((\forall x \in \mathbb{N})\, x \in \mathbb{R}\) — тачно, јер је \(\mathbb{N} \subseteq \mathbb{R}\).

(в) \((\exists x)(x \in \mathbb{Z} \land x > 8)\), краће \((\exists x \in \mathbb{Z})\, x > 8\) — тачно, сведок је \(x = 9\).

(г) \((\forall x)(x \in \mathbb{R} \Rightarrow x^2 < 0)\), краће \((\forall x \in \mathbb{R})\, x^2 < 0\) — нетачно, контрапример је \(x = 1\): \(1^2 = 1 < 0\) не важи.

(д) \((\exists x)(x \in \mathbb{N} \land x^2 = 1)\), краће \((\exists x \in \mathbb{N})\, x^2 = 1\) — тачно, сведок је \(x = 1\) (иако друго решење, \(-1\), није природан број).

(ђ) \((\forall x)(\forall y)(x \in \mathbb{N} \land y \in \mathbb{N} \Rightarrow x - y \in \mathbb{N})\), краће \((\forall x, y \in \mathbb{N})\, x - y \in \mathbb{N}\) — нетачно, контрапример је \(x = 2\), \(y = 5\): \(2 - 5 = -3 \notin \mathbb{N}\).

(е) \(\neg (\exists x)\big(x \in \mathbb{N} \land (\forall y)(y \in \mathbb{N} \Rightarrow y \le x)\big)\), краће \(\neg (\exists x \in \mathbb{N})(\forall y \in \mathbb{N})\, y \le x\) — тачно. Формула у загради је нетачна: ни за једно \(x\) не важи \((\forall y \in \mathbb{N})\, y \le x\), јер је \(y = x + 1\) контрапример.

Негацију провлачимо Де Моргановим законима за квантификаторе: \[ \begin{aligned} & \neg (\exists x)\big(x \in \mathbb{N} \land (\forall y)(y \in \mathbb{N} \Rightarrow y \le x)\big) \\ \equiv {} & (\forall x)\, \neg\big(x \in \mathbb{N} \land (\forall y)(y \in \mathbb{N} \Rightarrow y \le x)\big) \\ \equiv {} & (\forall x)\big(\neg(x \in \mathbb{N}) \lor \neg (\forall y)(y \in \mathbb{N} \Rightarrow y \le x)\big) \\ \equiv {} & (\forall x)\big(\neg(x \in \mathbb{N}) \lor (\exists y)\, \neg(y \in \mathbb{N} \Rightarrow y \le x)\big) \\ \equiv {} & (\forall x)\big(\neg(x \in \mathbb{N}) \lor (\exists y)(y \in \mathbb{N} \land y > x)\big) \\ \equiv {} & (\forall x)\big(x \in \mathbb{N} \Rightarrow (\exists y)(y \in \mathbb{N} \land y > x)\big), \end{aligned} \] краће \((\forall x \in \mathbb{N})(\exists y \in \mathbb{N})\, y > x\): „За сваки природан број постоји природан број већи од њега.“

Задатак 3 Одредити истинитосну вредност формула:

(а) \((\exists x)(x \in \mathbb{Z} \land 3x = 8)\)

(б) \((\exists x)(x \in \mathbb{Q} \land 3x = 8)\)

(в) \((\forall x \in \mathbb{N})(\exists y \in \mathbb{N})\, x \le y\)

(г) \((\exists y \in \mathbb{N})(\forall x \in \mathbb{N})\, x \le y\)

(д) \((\forall x, y, z \in \mathbb{R})(x = y \Rightarrow xz = yz)\)

(ђ) \((\forall x, y, z \in \mathbb{R})(xz = yz \Rightarrow x = y)\)

(а) Нетачно: једино решење једначине је \(x = \frac{8}{3} \notin \mathbb{Z}\).

(б) Тачно: \(x = \frac{8}{3} \in \mathbb{Q}\).

(в) Тачно: „за сваки природан број постоји природан број већи или једнак од њега“, сведок је, на пример, \(y = x + 1\) (или \(y = x\)).

(г) Нетачно: формула тврди да постоји највећи природан број, а у задатку 2 (е) видели смо да такав не постоји.

(д) Тачно: ако је \(x = y\), множењем обе стране са \(z\) добијамо \(xz = yz\).

(ђ) Нетачно. Обе стране смемо да поделимо са \(z\) само ако је \(z \ne 0\). Контрапример је \(x = 5\), \(y = 2\), \(z = 0\): \(5 \cdot 0 = 2 \cdot 0\) је тачно, а \(5 = 2\) нетачно, па импликација има вредност \(1 \Rightarrow 0 = 0\).

Формуле (в) и (г) разликују се само по редоследу квантификатора, а вредности су им различите: редослед различитих квантификатора се не сме мењати.

Задатак 4 Нека је \(D = \{1, 2, 3\}\). Записати формулу \((\forall x)(\exists y)\, \alpha(x, y)\) без квантификатора, користећи само конјункцију и дисјункцију.

Свако \(x\) из \(\{1, 2, 3\}\) даје по један конјункт, а свако \(y\) по један дисјункт у њему: \[ \big(\alpha(1,1) \lor \alpha(1,2) \lor \alpha(1,3)\big) \land \big(\alpha(2,1) \lor \alpha(2,2) \lor \alpha(2,3)\big) \land \big(\alpha(3,1) \lor \alpha(3,2) \lor \alpha(3,3)\big). \]

Задатак 5 Нека је \(S(x)\): „\(x\) је студент“, \(M(y)\): „\(y\) је предмет“ и \(P(x, y)\): „\(x\) је положио \(y\)“. Записати формулама:

(а) Сваки студент је положио бар један предмет.

(б) Постоји предмет који су положили сви студенти.

(в) Ниједан студент није положио све предмете.

Затим записати негацију реченице (а) формулом и речима.

(а) \((\forall x)\Big(S(x) \Rightarrow (\exists y)\big(M(y) \land P(x, y)\big)\Big)\).

(б) \((\exists y)\Big(M(y) \land (\forall x)\big(S(x) \Rightarrow P(x, y)\big)\Big)\).

(в) \(\neg (\exists x)\Big(S(x) \land (\forall y)\big(M(y) \Rightarrow P(x, y)\big)\Big)\), или еквивалентно \((\forall x)\Big(S(x) \Rightarrow (\exists y)\big(M(y) \land \neg P(x, y)\big)\Big)\).

Негација реченице (а) је \((\exists x)\Big(S(x) \land (\forall y)\big(M(y) \Rightarrow \neg P(x, y)\big)\Big)\): „Постоји студент који није положио ниједан предмет.“

Задатак 6 Негирати формуле и негацију провући до елементарних формула:

(а) \((\forall x)(\exists y)\big(x < y \land P(y)\big)\)

(б) \((\exists x)(\forall y)\big(P(x, y) \Rightarrow Q(y)\big)\)

(в) дефиницију инјективне функције \((\forall x_1)(\forall x_2)\big(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\big)\)

(а) \((\exists x)(\forall y)\big(x \ge y \lor \neg P(y)\big)\), што је исто што и \((\exists x)(\forall y)\big(x < y \Rightarrow \neg P(y)\big)\).

(б) \((\forall x)(\exists y)\big(P(x, y) \land \neg Q(y)\big)\).

(в) \((\exists x_1)(\exists x_2)\big(f(x_1) = f(x_2) \land x_1 \ne x_2\big)\) — постоје два различита елемента са истом сликом.

Задатак 7 Одредити слободна и везана појављивања променљивих и записати ознаку формуле (\(F(\dots)\) или „затворена“):

(а) \((\forall x)\big(\alpha(x, y) \Rightarrow (\exists y)\, \beta(y, z)\big)\)

(б) \((\exists x)\, \alpha(x, y) \land (\forall y)\, \beta(x, y)\)

(в) \((\forall x)(\exists y)\big(\alpha(x, y) \lor (\forall z)\, z = x\big)\)

(а) \(x\) је везана; прво појављивање \(y\) (у \(\alpha\)) је слободно, а друго (у \(\beta\)) везано; \(z\) је слободна. Ознака је \(F(y, z)\).

(б) Квантификатор \((\exists x)\) се односи само на \(\alpha(x, y)\), а \((\forall y)\) само на \(\beta(x, y)\). Зато је \(x\) везана у \(\alpha\), а слободна у \(\beta\), док је \(y\) слободна у \(\alpha\), а везана у \(\beta\). Ознака је \(F(x, y)\).

(в) Сва појављивања су везана — формула је затворена.

Задатак 8 Одредити вредност формуле \((\forall x)(\exists y)\, \alpha\big(x, f(y)\big)\) при интерпретацијама:

(а) \(D = \mathbb{N}\), \(\alpha\) је једнакост, \(f(y) = y + 1\)

(б) \(D = \mathbb{Z}\), \(\alpha\) је једнакост, \(f(y) = y + 1\)

(в) \(D = \mathbb{N}\), \(\alpha\) је \(\le\), \(f(y) = 2y\)

Да ли је формула ваљана? Да ли је задовољива?

(а) Формула гласи \((\forall x)(\exists y)\, x = y + 1\) на \(\mathbb{N}\) и нетачна је: за \(x = 1\) не постоји природан број \(y\) са \(y + 1 = 1\).

(б) На \(\mathbb{Z}\) је тачна, сведок је \(y = x - 1\).

(в) Формула гласи \((\forall x)(\exists y)\, x \le 2y\) и тачна је, сведок је \(y = x\).

Формула је задовољива (интерпретације (б) и (в) су њени модели), али није ваљана, јер је у интерпретацији (а) нетачна.

Следећи задаци траже вредност формуле при датој интерпретацији за све валуације слободних променљивих. Формулу прво запишемо у датој интерпретацији, затим уклонимо импликације и еквиваленције, па квантификаторе „гурамо“ ка елементарним формулама. При томе користимо, поред Де Морганових закона, и следећа правила, где \(P\) не зависи од \(x\), а \(\circ\) је \(\lor\) или \(\land\): \[ (\exists x)(P \circ Q) \equiv P \circ (\exists x)\, Q, \qquad (\forall x)(P \circ Q) \equiv P \circ (\forall x)\, Q, \] \[ (\exists x)(P \lor Q) \equiv (\exists x)\, P \lor (\exists x)\, Q, \qquad (\forall x)(P \land Q) \equiv (\forall x)\, P \land (\forall x)\, Q, \] \[ (\exists x)\big(x = t \land P(x)\big) \equiv P(t), \qquad (\forall x)\big(x = t \Rightarrow P(x)\big) \equiv P(t). \] Последња два правила кажу да квантификатор „нестаје“ када се везана променљива изједначи са термом \(t\) који не садржи \(x\).

Задатак 9 Одредити истинитосну вредност формуле \[ F(x, y, z) = \Big(\alpha(x, y) \Rightarrow \neg\big(\alpha(z, a) \lor \alpha(y, z)\big)\Big) \Rightarrow (\exists z)\, \alpha\big(y, f(x, z)\big) \] за све вредности слободних променљивих при интерпретацији \(D = \mathbb{N}_0\), \(\alpha\) је \(=\), \(f\) је \(+\), \(a\) је \(7\). При истој интерпретацији одредити и вредности формула \((\forall y)\, F(x, y, z)\), \((\forall y)(\exists x)\, F(x, y, z)\) и \((\forall x)(\exists y)\, \neg F(x, y, z)\).

На домену \(\mathbb{N}_0\) је \((\exists z)\, y = x + z \equiv x \le y\), јер је тада \(z = y - x \ge 0\). Уклањањем импликација и применом Де Морганових закона и дистрибутивности добијамо \[ \begin{aligned} F(x, y, z) &\equiv \big(x = y \Rightarrow \neg(z = 7 \lor y = z)\big) \Rightarrow x \le y \\ &\equiv \neg\big(x \ne y \lor \neg(z = 7 \lor y = z)\big) \lor x \le y \\ &\equiv \big(x = y \land (z = 7 \lor y = z)\big) \lor x \le y \\ &\equiv (x = y \lor x \le y) \land (z = 7 \lor y = z \lor x \le y) \\ &\equiv x \le y \land (z = 7 \lor y = z \lor x \le y) \equiv x \le y. \end{aligned} \] Користили смо \(x = y \lor x \le y \equiv x \le y\) и закон апсорпције. Дакле, \(F(x, y, z)\) је тачна ако је \(x \le y\), а нетачна ако је \(x > y\).

  • \((\forall y)\, F(x, y, z) \equiv (\forall y)\, x \le y \equiv x = 0\) — тачна за \(x = 0\), нетачна иначе.
  • \((\forall y)(\exists x)\, F(x, y, z) \equiv (\forall y)(\exists x)\, x \le y \equiv (\forall y)\, \top \equiv \top\) — увек тачна (сведок \(x = 0\)).
  • \((\forall x)(\exists y)\, \neg F(x, y, z) \equiv (\forall x)(\exists y)\, x > y \equiv (\forall x)\, x \ne 0 \equiv \bot\) — увек нетачна (контрапример \(x = 0\)).

Задатак 10 Решити претходни задатак за исту формулу \(F(x, y, z)\) при интерпретацији \(D = \mathbb{Z}\), \(\alpha\) је \(=\), \(f\) је \(\cdot\), \(a\) је \(-7\).

На домену \(\mathbb{Z}\) је \((\exists z)\, y = x \cdot z \equiv x \mid y\), по дефиницији дељивости. Истим трансформацијама као у задатку 9 добијамо \[ \begin{aligned} F(x, y, z) &\equiv \big(x = y \Rightarrow \neg(z = -7 \lor y = z)\big) \Rightarrow x \mid y \\ &\equiv \big(x = y \land (z = -7 \lor y = z)\big) \lor x \mid y \\ &\equiv (x = y \lor x \mid y) \land (z = -7 \lor y = z \lor x \mid y) \equiv x \mid y, \end{aligned} \] јер из \(x = y\) следи \(x \mid y\). Дакле, \(F\) је тачна ако \(x \mid y\), а нетачна ако \(x \nmid y\).

  • \((\forall y)\, F(x, y, z) \equiv (\forall y)\, x \mid y \equiv x = 1 \lor x = -1\) — само \(\pm 1\) деле сваки цео број.
  • \((\forall y)(\exists x)\, F(x, y, z) \equiv (\forall y)(\exists x)\, x \mid y \equiv \top\) — сведок \(x = 1\).
  • \((\forall x)(\exists y)\, \neg F(x, y, z) \equiv (\forall x)(\exists y)\, x \nmid y \equiv (\forall x)\, x \ne \pm 1 \equiv \bot\) — контрапример \(x = 1\).

Задатак 11 Одредити истинитосну вредност формуле \[ F(y, z) = (\forall x)\Big(\big((\exists z)\, \beta(x, y) \land \neg\big(\alpha(x, y) \Rightarrow \alpha(z, a)\big)\big) \lor (\exists y)\, \alpha\big(f(x, y), z\big)\Big) \] за све вредности слободних променљивих при интерпретацији \(D = \mathbb{R}\), \(\alpha\) је \(=\), \(\beta\) је \(\le\), \(f\) је \(\cdot\), \(a\) је \(0\). При истој интерпретацији одредити и вредности формула \((\forall y)\, F(y, z)\), \(F(0, z)\) и \(F(\sqrt{2}, z)\).

Квантификатор \((\exists z)\) односи се само на \(\beta(x, y)\), која не садржи \(z\), па је \((\exists z)\, x \le y \equiv x \le y\). Даље, \((\exists y)\, x \cdot y = z \equiv x \ne 0 \lor z = 0\): за \(x \ne 0\) сведок је \(y = \frac{z}{x}\), а за \(x = 0\) мора бити \(z = 0\). Зато је \[ \begin{aligned} F(y, z) &\equiv (\forall x)\big((x \le y \land \neg(x = y \Rightarrow z = 0)) \lor x \ne 0 \lor z = 0\big) \\ &\equiv (\forall x)\big((x \le y \land x = y \land z \ne 0) \lor z = 0 \lor x \ne 0\big) \\ &\equiv (\forall x)\big((x = y \land z \ne 0) \lor z = 0 \lor x \ne 0\big) \\ &\equiv (\forall x)(x = y \lor z = 0 \lor x \ne 0) \\ &\equiv z = 0 \lor (\forall x)(x = 0 \Rightarrow x = y) \\ &\equiv z = 0 \lor y = 0. \end{aligned} \] У четвртом кораку користили смо \((A \land \neg B) \lor B \equiv A \lor B\), у петом то што \(z = 0\) не зависи од \(x\), а у последњем правило \((\forall x)(x = t \Rightarrow P(x)) \equiv P(t)\) за \(t = 0\). Дакле, \(F(y, z)\) је тачна ако је \(y = 0\) или \(z = 0\), а нетачна ако је \(y \ne 0\) и \(z \ne 0\).

  • \((\forall y)\, F(y, z) \equiv z = 0 \lor (\forall y)\, y = 0 \equiv z = 0 \lor \bot \equiv z = 0\).
  • \(F(0, z) \equiv z = 0 \lor 0 = 0 \equiv \top\) — тачна за свако \(z\).
  • \(F(\sqrt{2}, z) \equiv z = 0 \lor \sqrt{2} = 0 \equiv z = 0\).

Задатак 12 Одредити истинитосну вредност формуле \[ F(x, y) = (\exists z)\Big(\big((\forall z)\, \alpha(x, f(y, z)) \Rightarrow \alpha(z, a)\big) \land \big(\alpha(y, z) \lor \alpha(x, z)\big)\Big) \] за све вредности слободних променљивих при интерпретацији \(D = \mathbb{R}\), \(\alpha\) је \(=\), \(f\) је \(\cdot\), \(a\) је \(3\). Колика је њена вредност за валуације у којима је \(x = y = 0\)?

Прво одредимо \((\forall z)\, x = y \cdot z\). Заменом \(z = 0\) и \(z = 1\) добијамо да су \(x = 0\) и \(y = x = 0\) потребни услови, а они су и довољни, јер \(0 = 0 \cdot z\) важи за свако \(z\). Дакле, \((\forall z)\, x = y \cdot z \equiv x = 0 \land y = 0\), па је \[ \begin{aligned} F(x, y) &\equiv (\exists z)\big((x \ne 0 \lor y \ne 0 \lor z = 3) \land (y = z \lor x = z)\big) \\ &\equiv \big((x \ne 0 \lor y \ne 0) \land (\exists z)(y = z \lor x = z)\big) \lor (\exists z)\big(z = 3 \land (y = z \lor x = z)\big) \\ &\equiv \big((x \ne 0 \lor y \ne 0) \land \top\big) \lor y = 3 \lor x = 3 \\ &\equiv x \ne 0 \lor y \ne 0. \end{aligned} \] У другом кораку смо дистрибутивношћу раздвојили \(\exists\) на две дисјункције и из прве извукли део који не зависи од \(z\), а у трећем применили правило \((\exists z)(z = t \land P(z)) \equiv P(t)\) за \(t = 3\). На крају, \(x = 3\) повлачи \(x \ne 0\), па се \(y = 3\) и \(x = 3\) апсорбују.

Дакле, \(F(x, y)\) је нетачна само ако је \(x = y = 0\), па је за те валуације њена вредност 0.

Задатак 13 Одредити истинитосну вредност формуле \[ F(x, y) = (\forall z)\Big(\big((\exists z)\, \alpha(x, f(y, z)) \land \alpha(y, z)\big) \Rightarrow \big((\alpha(z, a) \Rightarrow \alpha(x, y)) \lor \alpha(x, z)\big)\Big) \] за све вредности слободних променљивих при интерпретацији \(D = \mathbb{N}_0\), \(\alpha\) је \(=\), \(f\) је \(\cdot\), \(a\) је \(0\).

Квантификатор \((\exists z)\) односи се само на \(\alpha(x, f(y, z))\), а \((\exists z)\, x = y \cdot z \equiv y \mid x\) (дељивост се дефинише исто у \(\mathbb{N}_0\) и у \(\mathbb{Z}\)). Зато је \[ \begin{aligned} F(x, y) &\equiv (\forall z)\big((y \mid x \land y = z) \Rightarrow (z \ne 0 \lor x = y \lor x = z)\big) \\ &\equiv (\forall z)(y \nmid x \lor y \ne z \lor z \ne 0 \lor x = y \lor x = z) \\ &\equiv y \nmid x \lor x = y \lor (\forall z)(y \ne z \lor z \ne 0 \lor x = z). \end{aligned} \] Последња формула под квантификатором нетачна је само за \(z = y = 0\) и \(x \ne 0\), па је \((\forall z)(\dots) \equiv y \ne 0 \lor x = 0\). Тако је \[ F(x, y) \equiv y \nmid x \lor x = y \lor y \ne 0 \lor x = 0. \] Ова формула је увек тачна: ако би сви дисјункти били нетачни, било би \(y = 0\) и \(y \mid x\), а \(0 \mid x\) значи \(x = 0 \cdot k = 0\), што је у супротности са \(x \ne 0\). Дакле, \(F(x, y)\) је тачна за све вредности \(x\) и \(y\).

Задатак 14 Дата је формула \[ \Phi(x, y, z) = (\forall z)\, \alpha\big(f(x, z), y\big) \land \Big(\big(\alpha(z, a) \Rightarrow \alpha(x, z)\big) \Rightarrow \big(\alpha(y, z) \lor \alpha(y, x)\big)\Big). \] При интерпретацији \(D = \mathbb{N}\), \(\alpha\) је \(\ge\), \(f\) је \(\cdot\), \(a\) је \(1\), одредити истинитосне вредности формула \((\forall x)(\exists z)\, \Phi(x, 5, z)\), \((\forall x)(\exists z)\, \Phi(x, y, z)\) и \(\neg (\exists z)(\forall y)\, \Phi(x, y, z)\).

Најмањи природан број је 1, па је \((\forall z)\, x \cdot z \ge y \equiv x \ge y\) и \(z \ge 1\) увек тачно, тј. \((z \ge 1 \Rightarrow x \ge z) \equiv x \ge z\). Зато је \[ \Phi(x, y, z) \equiv x \ge y \land (x < z \lor y \ge z \lor y \ge x). \]

  • \((\forall x)(\exists z)\, \Phi(x, y, z) \equiv (\forall x)\big(x \ge y \land ((\exists z)\, x < z \lor (\exists z)\, y \ge z \lor y \ge x)\big) \equiv (\forall x)\, x \ge y \equiv y = 1\), јер је \((\exists z)\, x < z\) тачно. Формула је тачна за \(y = 1\), а нетачна за \(y \ne 1\).
  • \((\forall x)(\exists z)\, \Phi(x, 5, z)\) је зато нетачна (контрапример \(x = 1\)).
  • \(\neg (\exists z)(\forall y)\, \Phi(x, y, z) \equiv \neg (\exists z)\big((\forall y)\, x \ge y \land (\forall y)(x < z \lor y \ge z \lor y \ge x)\big) \equiv \neg (\exists z)\, \bot \equiv \top\), јер ниједан природан број није већи или једнак од свих. Формула је увек тачна.

Задатак 15 Одредити истинитосну вредност формуле \[ \Phi(z) = (\forall x)(\exists y)\Big(\big((x = z \Rightarrow x = y) \Rightarrow z = 0\big) \land (\exists z)\, x = y + z\Big) \] за све вредности слободне променљиве на домену \(D = \mathbb{N}_0\).

Унутрашњи квантификатор \((\exists z)\) везује своје \(z\), па је \((\exists z)\, x = y + z \equiv x \ge y\). Како је \((A \Rightarrow B) \Rightarrow C \equiv (A \land \neg B) \lor C\), добијамо \[ \begin{aligned} \Phi(z) &\equiv (\forall x)(\exists y)\big(((x = z \land x \ne y) \lor z = 0) \land x \ge y\big) \\ &\equiv (\forall x)\big((x = z \land (\exists y)\, x > y) \lor (z = 0 \land (\exists y)\, x \ge y)\big) \\ &\equiv (\forall x)\big((x = z \land x \ne 0) \lor z = 0\big) \\ &\equiv (\forall x)(x = z \land x \ne 0) \lor z = 0 \equiv z = 0, \end{aligned} \] јер \((\exists y)\, x > y\) значи \(x \ne 0\), \((\exists y)\, x \ge y\) је увек тачно, а \((\forall x)\, x = z\) увек нетачно. Дакле, \(\Phi(z)\) је тачна за \(z = 0\), а нетачна за \(z \ne 0\).

Задатак 16 Дата је формула \[ \Phi(x, y, z) = (\forall z)\, \alpha\big(f(y, z), x\big) \lor \neg\Big(\alpha(y, z) \land \big(\alpha(z, a) \Rightarrow \alpha(x, y)\big)\Big). \] При интерпретацији \(D = [0, \infty)\), \(\alpha\) је \(\ge\), \(f\) је \(\cdot\), \(a\) је \(0\), одредити истинитосне вредности формула \(\Phi(3, 2, z)\), \((\forall x)\, \Phi(x, y, z)\) и \((\exists x)\, \Phi(x, y, z)\).

За \(z = 0\) из \(y \cdot z \ge x\) следи \(0 \ge x\), па је \((\forall z)\, y \cdot z \ge x \equiv x = 0\) (за \(x = 0\) неједнакост важи увек). Како је \(z \ge 0\) увек тачно, \((z \ge 0 \Rightarrow x \ge y) \equiv x \ge y\). Зато је \[ \Phi(x, y, z) \equiv x = 0 \lor \neg(y \ge z \land x \ge y) \equiv x = 0 \lor y < z \lor x < y. \]

  • \(\Phi(3, 2, z) \equiv 3 = 0 \lor 2 < z \lor 3 < 2 \equiv z > 2\) — тачна за \(z > 2\), нетачна за \(z \le 2\).
  • \((\forall x)\, \Phi(x, y, z)\) је тачна ако и само ако је \(y < z\): ако је \(y < z\), сваки \(x\) задовољава формулу, а ако је \(y \ge z\), контрапример је било које \(x \ge y\) различито од 0.
  • \((\exists x)\, \Phi(x, y, z)\) је увек тачна, сведок је \(x = 0\).

Задатак 17 Дата је формула \[ \Phi(x, y, z) = \big(\alpha(x, y) \land \alpha(z, y) \land \neg\alpha(y, x) \land \neg\alpha(y, z)\big) \Rightarrow \alpha(z, x). \] При интерпретацији \(D = \mathbb{N}\), \(\alpha\) је \(\le\), одредити истинитосне вредности формула \(\Phi(3, 5, z)\), \((\forall z)\, \Phi(3, 5, z)\), \((\forall z)\, \Phi(x, y, z)\), \((\exists z)\, \Phi(3, 5, z)\) и \((\exists z)\, \Phi(x, y, z)\).

Како је \(x \le y \land \neg(y \le x) \equiv x < y\), формула гласи \((x < y \land z < y) \Rightarrow z \le x\), тј. \[ \Phi(x, y, z) \equiv y \le x \lor y \le z \lor z \le x \equiv y \le z \lor z \le x. \] Дисјункт \(y \le x\) је сувишан: ако је \(y \le x\), онда је или \(z \le x\), или \(z > x \ge y\). Формула је, дакле, нетачна тачно када је \(x < z < y\).

  • \(\Phi(3, 5, z) \equiv 5 \le z \lor z \le 3\) — нетачна само за \(z = 4\).
  • \((\forall z)\, \Phi(3, 5, z)\) је нетачна (контрапример \(z = 4\)).
  • \((\forall z)\, \Phi(x, y, z)\) је тачна ако и само ако не постоји природан број строго између \(x\) и \(y\), тј. ако је \(y \le x + 1\).
  • \((\exists z)\, \Phi(3, 5, z)\) је тачна (сведок \(z = 5\)), а \((\exists z)\, \Phi(x, y, z)\) је увек тачна (сведок \(z = y\)).

Задатак 18 Показати да формула \((\forall x)\big(P(x) \lor Q(x)\big) \Rightarrow (\forall x)\, P(x) \lor (\forall x)\, Q(x)\) није ваљана, а да обрнута импликација јесте.

Контрамодел: \(D = \mathbb{N}\), \(P(x)\): „\(x\) је паран“, \(Q(x)\): „\(x\) је непаран“. Претпоставка \((\forall x)\big(P(x) \lor Q(x)\big)\) је тачна, а оба дисјункта закључка нетачна (контрапримери \(x = 1\) и \(x = 2\)).

Обрнута импликација \((\forall x)\, P(x) \lor (\forall x)\, Q(x) \Rightarrow (\forall x)\big(P(x) \lor Q(x)\big)\) је ваљана: ако је тачно, на пример, \((\forall x)\, P(x)\), онда за свако \(x\) важи \(P(x)\), па и \(P(x) \lor Q(x)\); исто и ако је тачно \((\forall x)\, Q(x)\).

Задатак 19 Да ли је закључак исправан? „Сви програмери знају логику. Неки студенти знају логику. Дакле, неки студенти су програмери.“ Записати га формулама и, ако није исправан, навести контрамодел.

Нека је \(P(x)\): „\(x\) је програмер“, \(L(x)\): „\(x\) зна логику“ и \(S(x)\): „\(x\) је студент“. Питање је да ли \[ (\forall x)\big(P(x) \Rightarrow L(x)\big),\ (\exists x)\big(S(x) \land L(x)\big) \models (\exists x)\big(S(x) \land P(x)\big). \] Не важи. Контрамодел: домен \(\{1, 2\}\), где је 1 програмер који зна логику и није студент, а 2 студент који зна логику и није програмер. Обе претпоставке су тачне, а закључак нетачан — ниједан студент није програмер.

Задатак 20 Помоћу функција all и any проверити на домену \(D = \{1, 2, \dots, 50\}\) формулу \((\forall x)(\exists y)\big(x < y \land \text{Прост}(y)\big)\) и одредити све контрапримере. Да ли је формула тачна на домену \(\mathbb{N}\)? Затим проверити Голдбахову хипотезу за парне бројеве од 4 до 100: сваки такав број је збир два проста броја.

D = range(1, 51)

def prost(n):
    return n > 1 and all(n % d != 0 for d in range(2, n))

print(all(any(x < y and prost(y) for y in D) for x in D))        # False
print([x for x in D if not any(x < y and prost(y) for y in D)])  # [47, 48, 49, 50]

print(all(any(prost(p) and prost(n - p) for p in range(2, n - 1))
          for n in range(4, 101, 2)))                            # True

На домену \(\{1, \dots, 50\}\) формула је нетачна: највећи прост број у домену је 47, па за \(x \ge 47\) нема већег простог броја у домену. На домену \(\mathbb{N}\) формула је тачна, јер простих бројева има бесконачно много (Еуклидова теорема). Голдбахова хипотеза је проверена за све парне бројеве до \(4 \cdot 10^{18}\), али још увек није доказана — провера коначно много случајева није доказ тврђења са \(\forall\).