Logika dla informatyków/Ćwiczenia 3

\subsection*{Ćwiczenia}\begin{small}

1. Stosując schematy (#trk6--#9) z Faktu #teerka,

pokazać, że następujące formuły są tautologiami:

1. 1. </math>(\exists y p(y) \to \forall z q(z)) \to

\forall y\forall z(p(y)\to q(z))</math>; %95b

1. 1. </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>; %99a

1. 1. </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>; %109a

1. 1. </math>\forall x(p(x)\to \exists y q(y))\to

\exists y(\exists x p(x)\to q(y))</math>.% 110a

\item 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.\footnote{Kodeks

Drogowy przed nowelizacją w roku 1997.}

1. {\it Zabrania się zaśmiecania lub zanieczyszczania

drogi.}\footnote{Kodeks Drogowy po nowelizacji w roku 1997.}

1. {\it Wpisać, gdy osoba\boldsymbol{s}}\def\blank{\hbox{\sf Bbezpieczona nie posiada numerów identyfikacyjnych

NIP lub \mbox{PESEL}.}\footnote{Instrukcja wypełniania formularza ZUS ZCZA (Zgłoszenie danych o członkach rodziny\dots)}

1. {\it Podaj przykład liczby, która jest pierwiastkiem pewnego

równania kwadratowego o współczynnikach całkowitych i takiej, która nie jest.}

1. Warunek zachodzi dla każdego $x$ i dla pewnego $y$.\/

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

1. Zbiór $A$ jest {\sf dobry}, jeśli ma co najmniej 2elementy.
2. Zbiór $A$ jest {\sf dobry, jeśli dla każdego $x\in A$,

jeśli $x$ jest parzyste, to $x$ jest podzielne przez $3$.}

1. Zbiór $A$ jest {\sf dobry, jeśli dla pewnego $x\in A$,

jeśli $x$ jest parzyste, to $x$ jest podzielne przez $3$.}

\item Wskazać błąd w rozumowaniu:

1. {\it Aby wykazać prawdziwość tezy\\

{\sf ,,Dla dowolnego $n$, jeśli zachodzi warunek $W(n)$ to zachodzi warunek $U(n)$}\\ załóżmy, że dla dowolnego $n$ zachodzi $W(n)$\dots}

1. {\it Aby wykazać prawdziwość tezy\\

{\sf ,,Dla pewnego $n$, jeśli zachodzi warunek $W(n)$ to zachodzi warunek $U(n)$}\\ załóżmy, że dla pewnego $n$ zachodzi $W(n)$\dots}

\item Sformułować poprawnie zaprzeczenia stwierdzeń:

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

\item Czy zdanie {\it ,,Liczba $a$ nie jest kwadratem pewnej liczby całkowitej\/} jest poprawnym zaprzeczeniem zdania {\it ,,Liczba $a$ jest kwadratem pewnej liczby całkowitej\/}?

\item 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:%61 jest rozwiazanie

1. zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest prawdziwe dokładnie w tych modelach

Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle \A = \<A, R^\A, S^\A, r^\A, s^\A, g^\A\>} , w których obie relacje Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle R^\A} , Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle S^\A} są przechodnie, ale ich suma nie jest przechodnia;

1. zdanie $\psi$ jest prawdziwe dokładnie w tych modelach

Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle \A = \<A, R^\A, S^\A, r^\A, s^\A, g^\A\>} , w których Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle s^\A} jest obrazem iloczynu kartezjańskiego Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^\A\times r^\A} przy funkcji Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle g^\A} .

\item 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%77 jest rozwiazanie Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle \A = \<A, r^{\A}, s^{\A}, f^{\A}\>} , w których:

1. Złożenie relacji Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^{\A}} i Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle s^{\A}} zawiera się w ich iloczynie

Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^\A\cap s^\A} ;

1. Zbiór wartości funkcji Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle f^{\A}} jest rzutem sumy Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^\A\cup s^\A} na

pierwszą współrzędną;

1. Relacja Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^\A} nie jest funkcją z $A$ w $A$;
2. Obraz Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle r^\A} przy funkcji Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle f^\A} jest podstrukturą w Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle \A} ;
3. Obraz zbioru $A\times A$ przy funkcji Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle f^\A} jest pusty.

\item Dla każdej z par struktur:

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\NN,\leq\>} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{m-{1\over n}\ |\ m,n\in\NN-\{0\}\}, \leq\>} ;
2. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\NN, +\>} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\ZZ, +\>} ;
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\NN, \leq\>} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\ZZ, \leq\>} ,

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

\item 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 Parser nie mógł rozpoznać (nieznana funkcja „\A”): {\displaystyle \A = \<\ZZ, +, 0 \>} ,

ale nie w modelu Parser nie mógł rozpoznać (nieznana funkcja „\B”): {\displaystyle \B = \<\NN, +, 0 \>} ;

1. zdanie $\psi$ jest prawdziwe w modelu Parser nie mógł rozpoznać (nieznana funkcja „\B”): {\displaystyle \B = \<\ZZ, +, 0 \>} ,

ale nie w modelu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \C = \<\QQ, +, 0 \>} .

\item Wskazać formułę pierwszego rzędu:

1. spełnialną w

ciele liczb rzeczywistych ale nie w ciele liczb wymiernych;

1. spełnialną w algebrze Parser nie mógł rozpoznać (nieznana funkcja „\NN”): {\displaystyle \NN} z mnożeniem,

ale nie w algebrze Parser nie mógł rozpoznać (nieznana funkcja „\NN”): {\displaystyle \NN} z dodawaniem;

1. spełnialną w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{a,b\}^*,\cdot,\varepsilon\>}

ale nie w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{a,b,c\}^*,\cdot,\varepsilon\>} .

\item Zmodyfikować konstrukcję z dowodu Twierdzenia #entscheidungsproblem w ten sposób, aby w formule Parser nie mógł rozpoznać (nieznana funkcja „\M”): {\displaystyle \psi_\M} nie występował symbol równości ani stała </math>cParser nie mógł rozpoznać (błąd składni): {\displaystyle . %%{1. Napisać } \forall x\forall y\forall z(G(x,y)\wedge \item Zmodyfikować konstrukcję z dowodu Twierdzenia #entscheidungsproblem w ten sposób, aby Parser nie mógł rozpoznać (nieznana funkcja „\M”): {\displaystyle \psi_\M} była zawsze formułą\boldsymbol{s}}\def\blank{\hbox{\sf Bstalonej sygnatury (niezależnej od maszyny Parser nie mógł rozpoznać (nieznana funkcja „\M”): {\displaystyle \M} ). Wywnioskować stąd, że logika pierwszego rzędu nad tą\boldsymbol{s}}\def\blank{\hbox{\sf Bstaloną sygnaturą jest nierozstrzygalna.

\end{small}