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
Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie budziły wątpliwości?

1. Nie wolno pić i grać w karty.
2. Nie wolno pluć i łapać.
3. Zabrania się zaśmiecania i zanieczyszczania drogi.<ref name="kodeks1">Kodeks Drogowy przed nowelizacją w roku 1997.</ref>
4. Zabrania się zaśmiecania lub zanieczyszczania drogi. <ref name="kodeks2">Kodeks Drogowy po nowelizacji w roku 1997.</ref>
5. Wpisać, gdy osoba ubezpieczona nie posiada numerów identyfikacyjnych NIP lub PESEL.<ref name="zus">Instrukcja wypełniania formularza ZUS ZCZA

(Zgłoszenie danych o członkach rodziny\dots)</ref>

1. Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o współczynnikach całkowitych i takiej, która nie jest.
2. Warunek zachodzi dla każdego $x$ i dla pewnego $y$.

Ć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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle r, s \in \Sigma^R_1} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle R, S \in \Sigma^R_2} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle g\in \Sigma_2^F} . Napisać takie zdania Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi}  i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \psi} , że:

1. zdanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} jest prawdziwe dokładnie w tych modelach Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A = <A, R^A, S^A, r^A, s^A, g^A>} , w których obie relacje Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle R^A} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S^A} są przechodnie, ale ich suma nie jest przechodnia;
2. zdanie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \psi} jest prawdziwe dokładnie w tych modelach Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A = <A, R^A, S^A, r^A, s^A, g^A>} , w których Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s^A} jest obrazem iloczynu kartezjańskiego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle r^A\times r^A} przy funkcji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle g^A} .

Ćwiczenie 8
Sygnatura Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Sigma} składa się z dwuargumentowych symboli relacyjnych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle r} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s} oraz dwuargumentowego symbolu funkcyjnego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle f} . Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w tych modelach Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A = <A, r^A, s^A, f^A>} , w których:

1. Złożenie relacji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle r^A} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle s^A} zawiera się w ich iloczynie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle r^A\cap s^A} ;
2. Zbiór wartości funkcji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle f^A} jest rzutem sumy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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/>