\(\def\NN{\mathbb N}
\def\QQ{\mathbb Q}
\def\RR{\mathbb R}
\def\ZZ{\mathbb Z}
\def\A{{\cal A}}
\def\[{\langle}
\def\]{\rangle}
\def\oto{\leftrightarrow}\)

Logika zdaniowa

Zadanie 1

Zbadać, czy następujące formuły są tautologiami rachunku zdań i czy są spełnialne:

1. \((p\to r)\wedge(q\to s)\wedge(\neg p\vee \neg s)\to (\neg p\vee \neg q)\);
2. \(((p\to q)\vee r)\wedge(\neg p\to r)\);
3. \((p\to q)\vee(q\to r)\vee(r\to p)\);
4. \(((p\vee q)\to r)\to (p\to r)\vee(q\to r)\);
5. \((p\to q)\wedge(\neg p\to r)\to (r\to\neg q)\);
6. \(((\neg p\to q)\to r)\to \neg(p\to q)\);
7. \((((p\to q)\to r)\to \neg p)\to \neg q\);
8. \(((p\to q)\to p)\to q\);
9. \(p\vee(\neg p\wedge q)\vee(\neg p\wedge\neg q)\);
10. \((p\to q)\vee (p\to \neg q)\);
11. \((p\wedge q\to r)\to (p\wedge \neg r)\to \neg q\);
12. \(q\vee r\to (p\vee q\to p\vee r)\);
13. \((p\vee q\vee r)\wedge(q\vee(\neg p\wedge s))\wedge (\neg s\vee q\vee r)
    \to q\).

Zadanie 2

Znaleźć (o ile istnieje) taką formułę zdaniową \(\alpha\), aby następująca formuła była tautologią rachunku zdań:

1. \(((r\to (\neg q\wedge p))\to\alpha)\to (\alpha\wedge(p\to q)\wedge r)\);
2. \((\alpha\to p)\to(p\to q)\);
3. \(((p\to\alpha)\to q)\to(q\to(\neg p\to\neg\alpha))\);
4. \((\alpha\to p)\wedge(\neg\alpha\to q)\);
5. \(((\alpha\wedge q)\to\neg p)\to((\alpha\to p)\to\neg q)\);
6. \(((\neg\alpha\to p)\to q)\to(\alpha\wedge q\to \neg p)\);
7. \(((\alpha\to p)\wedge q)\to(\alpha\vee q\to p)\);
8. \(((\alpha\to p)\wedge q)\to(\alpha\vee q\to \neg p)\).

Zadanie 3

Udowodnić, że dla dowolnej funkcji \(f:\{0,1\}^k\to\{0,1\}\) istnieje formuła \(\alpha\), w której występują tylko zmienne zdaniowe ze zbioru \(\{p_1,\ldots, p_k\}\), o tej własności, że dla dowolnego wartościowania zdaniowego \(v\) zachodzi równość \(v(\alpha) = f(v(p_1),\ldots, v(p_k))\). (Inaczej mówiąc, formuła \(\alpha\) definiuje funkcję zerojedynkową \(f\).)

Logika I rzędu

Zadanie 4

W strukturze \(\A =\[\NN, P^\A, Q^\A\]\), gdzie:
\(\[a,b\]\in P^\A\) wtedy i tylko wtedy, gdy \(a+b\geq 6\);
\(\[a,b\]\in Q^\A\) wtedy i tylko wtedy, gdy \(b=a+2\),
wyznaczyć wartość formuł:

1. \(\forall x P(x,y) \to \exists x Q(x,y)\);
2. \(\forall x P(x,y) \to \forall x Q(x,y)\);
3. \(\forall x P(x,y) \to \exists x Q(x,z)\);

przy wartościowaniach \(v(y) = 7\), \(v(z) = 1\) oraz \(u(y)= 3, u(z) = 2\).

Zadanie 5

Podaj przykład modelu i wartościowania, przy którym formuła
\(P(x,f(x)) \to \forall x\exists y P(f(y),x)\)
jest: a) spełniona; b) nie spełniona.

Zadanie 6

Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):

1. \(\[\QQ,+,\cdot,0,1\]\) i \(\[\RR,+,\cdot,0,1\]\);
2. \(\[\NN,+,0\]\) i \(\[\NN, \cdot, 1\]\);
3. \(\[P_2, \parallel\]\) i \(\[P_2, \bot\]\), gdzie \(P_2\) oznacza zbiór wszystkich prostych w \(\RR^2\);
4. \(\[P_2, \bot\]\) i \(\[P_3, \bot\]\), gdzie \(P_2\) i \(P_3\) to odpowiednio zbiory wszystkich prostych w \(\RR^2\);
5. \(\[\RR, +, \cdot, 0,1\]\) i \(\[P(\NN), \cup, \cap, \emptyset, \NN\]\);
6. \(\[\NN,\leq,0\]\) i \(\[\ZZ, \leq, 0\]\);
7. \(\[\NN,+,0\]\) i \(\[\{a,b\}^*,\cdot,\varepsilon\]\),
8. \(\[\NN,+,0\]\) i \(\[\NN^2, \#, \[0,0\]\]\), gdzie operacja \(\#\) jest określona tak: \(\[a,b\]\#\[c,d\] = \[a+c, b+d\]\).

Zadanie 7

Sygnatura \(\Sigma\) składa się z symbolu równości, jednoargumentowych symboli relacyjnych \(R, S\) i jednego jednoargumentowego symbolu funkcyjnego \(f\). Napisać takie zdania \(\varphi\) i \(\psi\), że:

1. zdanie \(\varphi\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^{\A}, S^{\A}, f^{\A}\]\), w których obraz zbioru \(R^{\A}\) przy funkcji \(f^\A\) zawiera się w zbiorze \(S^{\A}\).
2. zdanie \(\psi\) jest prawdziwe dokładnie w tych modelach \(\A = \[A, R^{\A}, S^{\A}, f^{\A}\]\), w których zbiór \(S^{\A}\) jest przeciwobrazem zbioru \(R^{\A}\) przy przekształceniu \(f\).

Zadanie 8

Sygnatura \(\Sigma\) składa się z dwóch symbolu równości i dwuargumentowych symboli relacyjnych \(R\) i \(S\). Napisać takie zdania \(\varphi_1\), \(\varphi_2\) i \(\varphi_3\), że

1. zdanie \(\varphi_1\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^\A, S^\A\]\), w których \(R^\A\) jest relacją równoważności o dokładnie trzech klasach abstrakcji.
2. zdanie \(\varphi_2\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^\A, S^\A\]\), w których złożenie relacji \(R^\A\) z relacją \(S^\A\) jest identyczne ze złożeniem relacji \(S^\A\) z relacją \(R^\A\).
3. zdanie \(\varphi_3\) jest prawdziwe dokładnie w tych modelach \(\A = \[A, R^\A, S^\A\]\), w których relacja \(S^\A\) jest najmniejszą relacją symetryczną zawierajacą \(R^\A\).

Zadanie 9

Wskazać (o ile istnieje) model i wartościowanie spełniające daną formułę i nie spełniające tej formuły:

1. \(\forall y(r(x)\to r(y))\);
2. \(\forall y(r(x)\wedge r(y) \to r(f(x,y))\);
3. \(\forall x(q(x,y)\to q(f(x),y)\);
4. \(\forall x\forall y(r(x)\wedge r(y) \to r(f(x,y))\);
5. \(\forall x(r(x)\vee p(x))\to (\forall x r(x)\vee \forall x p(x))\);
6. \(\forall x\exists y(q(x,y)\vee \forall y\neg q(x,y))\);
7. \(\exists x\forall y\exists z(q(x,z)\wedge\neg q(x,y))\);
8. \(\forall x\forall y(\neg(x=y)\to \exists z(P(x,z)\wedge P(y,z))\);
9. \(\forall x\exists y\exists z(\neg(y=z)\wedge P(x,y)\wedge P(x,z))\);
10. \((\forall x P(x) \to Q(y)) \oto \exists x (P(x) \to Q(y))\);
11. \((\forall x P(x) \to Q(x)) \oto \exists x (P(x) \to Q(x))\).

Zadanie 10

Udowodnij w systemie naturalnej dedukcji:

1. \(\vdash (p\to \neg q)\to\neg(p\wedge q)\);
2. \(\vdash (p\to q\vee r)\to((p\to q)\vee(p\to r))\);
3. \(\vdash \forall x(P(x)\to Q(y))\to(\exists x P(x)\to Q(y))\);
4. \(\forall x(P(x) \to P(f(x)))\vdash \exists x P(x) \to \exists x P(f(f(x)))\).