Processing math: 0%
Strona główna › Podstawy matematyki › Ćwiczenia

Logika

śr., 01/16/2013 - 02:48 — chrzaszcz

\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))).