Logika dla informatyków/Ćwiczenia 3

Ćwiczenie 1

Stosując schematy (6-9) z Faktu 3.1, pokazać, że następujące formuły są tautologiami:

1. $(\exists yp(y)\to \forall zq(z))\to \forall y\forall z(p(y)\to q(z))$;
2. </math>(\forall x\exists y r(x,y) \to \exists x\forall y r(y,x))\to\exists x\forall y(r(x,y) \to r(y,x))</math>;
3. </math>\forall x\exists y((p(x)\to q(y))\to r(y)) \to ((\forall x p(x)\to \forall y q(y))\to \exists y r(y))</math>;
4. </math>\forall x(p(x)\to \exists y q(y))\to\exists y(\exists x p(x)\to q(y))</math>.% 110a

Ćwiczenie 2

{{{3}}}

Ćwiczenie 3

Czy następujące definicje można lepiej sformułować?

1. Zbiór A jest dobry, jeśli ma co najmniej 2 elementy.
2. Zbiór A jest dobry, jeśli dla każdego $x\in A$, jeśli $x$ jest parzyste, to $x$ jest podzielne przez 3.
3. Zbiór A jest dobry, jeśli dla pewnego $x\in A$, jeśli $x$ jest parzyste, to $x$ jest podzielne przez 3.

Ćwiczenie 4

Wskazać błąd w rozumowaniu:

1. Aby wykazać prawdziwość tezy
   "Dla dowolnego $n$, jeśli zachodzi warunek $W(n)$, to zachodzi warunek $U(n)$"
   załóżmy, że dla dowolnego $n$ zachodzi $W(n)$...
2. Aby wykazać prawdziwość tezy
   "Dla pewnego $n$, jeśli zachodzi warunek $W(n)$, to zachodzi warunek $U(n)$
   załóżmy, że dla pewnego $n$ zachodzi $W(n)$...

Ćwiczenie 5

Sformułować poprawnie zaprzeczenia stwierdzeń:

• Liczby $m$ i $n$ są pierwsze.
• Liczby $m$ i $n$ są względnie pierwsze.

Ćwiczenie 6

Czy zdanie "Liczba $a$ nie jest kwadratem pewnej liczby całkowitej" jest poprawnym zaprzeczeniem zdania "Liczba $a$ jest kwadratem pewnej liczby całkowitej"?

Ćwiczenie 7

Sygnatura $\Sigma$ składa się z symboli $r,s\in \Sigma _{1}^{R}$, $R,S\in \Sigma _{2}^{R}$ i $g\in \Sigma _{2}^{F}$. Napisać takie zdania Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi}  i $\psi$, że:

1. zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest prawdziwe dokładnie w tych modelach $A=<A,R^{A},S^{A},r^{A},s^{A},g^{A}>$, w których obie relacje $R^{A}$, $S^{A}$ są przechodnie, ale ich suma nie jest przechodnia;
2. zdanie $\psi$ jest prawdziwe dokładnie w tych modelach $A=<A,R^{A},S^{A},r^{A},s^{A},g^{A}>$, w których $s^{A}$ jest obrazem iloczynu kartezjańskiego $r^{A}\times r^{A}$ przy funkcji $g^{A}$.

Ćwiczenie 8

Sygnatura $\Sigma$ składa się z dwuargumentowych symboli relacyjnych $r$ i $s$ oraz dwuargumentowego symbolu funkcyjnego $f$. Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w tych modelach $A=<A,r^{A},s^{A},f^{A}>$, w których:

1. Złożenie relacji $r^{A}$ i $s^{A}$ zawiera się w ich iloczynie $r^{A}\cap s^{A}$;
2. Zbiór wartości funkcji $f^{A}$ jest rzutem sumy $r^{A}\cup s^{A}$ na pierwszą współrzędną;
3. Relacja $r^{A}$ nie jest funkcją z $A$ w $A$;
4. Obraz $r^{A}$ przy funkcji $f^{A}$ jest podstrukturą w $A$;
5. Obraz zbioru $A\times A$ przy funkcji $f^{A}$ jest pusty.

Ćwiczenie 9

Dla każdej z par struktur:

1. $<\mathbb {N} ,\leq >$ i $<\{m-{1 \over n}\ |\ m,n\in \mathbb {N} -\{0\}\},\leq >$;
2. $<\mathbb {N} ,+>$ i $<\mathbb {Z} ,+>$;
3. $<\mathbb {N} ,\leq >$ i $<\mathbb {Z} ,\leq >$,

wskaż zdanie prawdziwe w jednej z nich, a w drugiej nie.

Ćwiczenie 10

Napisać takie zdania Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} i $\psi$, że:

1. zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest prawdziwe w modelu $A=<\mathbb {Z} ,+,0>$, ale nie w modelu ${\mathfrak {B}}=<\mathbb {N} ,+,0>$;
2. zdanie $\psi$ jest prawdziwe w modelu ${\mathfrak {B}}=<\mathbb {Z} ,+,0>$, ale nie w modelu $C=<\mathbb {Q} ,+,0>$.

Ćwiczenie 11

Wskazać formułę pierwszego rzędu:

1. spełnialną w ciele liczb rzeczywistych, ale nie w ciele liczb wymiernych;
2. spełnialną w algebrze $\mathbb {N}$ z mnożeniem, ale nie w algebrze $\mathbb {N}$ z dodawaniem;
3. spełnialną w $<\{a,b\}^{*},\cdot ,\varepsilon >$, ale nie w $<\{a,b,c\}^{*},\cdot ,\varepsilon >$.

Ćwiczenie 12

Zmodyfikować konstrukcję z dowodu Twierdzenia 3.8 w ten sposób, aby w formule $\psi _{M}$ nie występował symbol równości ani stała $c$.

Ćwiczenie 13

Zmodyfikować konstrukcję z dowodu Twierdzenia 3.8 w ten sposób, aby $\psi _{M}$ była zawsze formułą ustalonej sygnatury (niezależnej od maszyny $M$). Wywnioskować stąd, że logika pierwszego rzędu nad tą ustaloną sygnaturą jest nierozstrzygalna.

<references/>