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. $(\mathrm{\exists }yp(y)\to \mathrm{\forall }zq(z))\to \mathrm{\forall }y\mathrm{\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 $\mathrm{\Sigma }$ składa się z symboli $r,s\in {\mathrm{\Sigma }}_1^R$, $R,S\in {\mathrm{\Sigma }}_2^R$ i $g\in {\mathrm{\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 $\mathrm{\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{\mathbb{N}},\le >$ i $<\{m-\frac{1}{n}|m,n\in \mathbb{\mathbb{N}}-\{0\}\},\le >$;
2. $<\mathbb{\mathbb{N}},+>$ i $<\mathbb{\mathbb{Z}},+>$;
3. $<\mathbb{\mathbb{N}},\le >$ i $<\mathbb{\mathbb{Z}},\le >$,

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{\mathbb{Z}},+,0>$, ale nie w modelu $\mathfrak{𝔅}=<\mathbb{\mathbb{N}},+,0>$;
2. zdanie $\psi$ jest prawdziwe w modelu $\mathfrak{𝔅}=<\mathbb{\mathbb{Z}},+,0>$, ale nie w modelu $C=<\mathbb{\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{\mathbb{N}}$ z mnożeniem, ale nie w algebrze $\mathbb{\mathbb{N}}$ z dodawaniem;
3. spełnialną w $<\{a,b{\}}^{*},\cdot ,\epsilon >$ ale nie w $<\{a,b,c{\}}^{*},\cdot ,\epsilon >$.

Ć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/>