Logika dla informatyków/Ćwiczenia 3: Różnice pomiędzy wersjami

← poprzednia edycja

WizualnieWikikod

Aktualna wersja na dzień 10:45, 1 paź 2006

Ćwiczenie 1

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

$(\exists y p (y) \to \forall z q (z)) \to \forall y \forall z (p (y) \to q (z))$ ;
</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>;
</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>;
</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ć?

Zbiór A jest dobry, jeśli ma co najmniej 2 elementy.
Zbiór A jest dobry, jeśli dla każdego $x \in A$ , jeśli $x$ jest parzyste, to $x$ jest podzielne przez 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:

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)$ ...
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 $Σ$ składa się z symboli $r, s \in Σ_{1}^{R}$ , $R, S \in Σ_{2}^{R}$ i $g \in Σ_{2}^{F}$ . Napisać takie zdania Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} i $ψ$ , że:

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;
zdanie $ψ$ 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 $Σ$ 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:

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

Ćwiczenie 9

Dla każdej z par struktur:

$< ℕ, \leq >$ i $< {m - \frac{1}{n} | m, n \in ℕ - {0}}, \leq >$ ;
$< ℕ, + >$ i $< ℤ, + >$ ;
$< ℕ, \leq >$ i $< ℤ, \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 $ψ$ , że:

zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest prawdziwe w modelu $A = < ℤ, +, 0 >$ , ale nie w modelu $𝔅 = < ℕ, +, 0 >$ ;
zdanie $ψ$ jest prawdziwe w modelu $𝔅 = < ℤ, +, 0 >$ , ale nie w modelu $C = < ℚ, +, 0 >$ .

Ćwiczenie 11

Wskazać formułę pierwszego rzędu:

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

Ćwiczenie 12

Zmodyfikować konstrukcję z dowodu Twierdzenia 3.8 w ten sposób, aby w formule $ψ_{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 $ψ_{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.

@@ Linia 1: / Linia 1: @@
-Ćwiczenie 1
+{{Cwiczenie|1||
-Stosując schematy&nbsp;(6-9) z [[Logika_dla_informatyków/Logika_pierwszego_rzędu._Sposób_użycia#teerka|Faktu 3.1]], pokazać, że następujące formuły są tautologiami:
+Stosując schematy&nbsp;(6-9) z [[Logika_dla_informatyków/Logika_pierwszego_rzędu._Sposób_użycia#trkd|Faktu 3.1]], pokazać, że następujące formuły są tautologiami:
-##</math>(\exists y p(y) \to \forall z q(z)) \to
+#<math>(\exists y p(y) \to \forall z q(z)) \to \forall y\forall z(p(y)\to q(z))</math>;
-\forall y\forall z(p(y)\to q(z))</math>; %95b
+#</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>;
-##</math>(\forall x\exists y r(x,y) \to \exists x\forall y r(y,x))\to
+#</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>;
-\exists x\forall y(r(x,y) \to r(y,x))</math>; %99a
+#</math>\forall x(p(x)\to \exists y q(y))\to\exists y(\exists x p(x)\to q(y))</math>.% 110a
-##</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
-##</math>\forall x(p(x)\to \exists y q(y))\to
-\exists y(\exists x p(x)\to q(y))</math>.% 110a
+{{Cwiczenie|2||
-\item Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie
+Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie budziły wątpliwości?
-budziły wątpliwości?
 #''Nie wolno pić i grać w karty.''
 #''Nie wolno pluć i łapać.''
-#''Zabrania się zaśmiecania i zanieczyszczania drogi.''\footnote{Kodeks
+#''Zabrania się zaśmiecania i zanieczyszczania drogi.''<ref name="kodeks1">Kodeks Drogowy przed nowelizacją w roku 1997.</ref>
-Drogowy przed nowelizacją w roku 1997.}
+#''Zabrania się zaśmiecania lub zanieczyszczania drogi.'' <ref name="kodeks2">Kodeks Drogowy po nowelizacji w roku 1997.</ref>
-#{\it Zabrania się zaśmiecania lub zanieczyszczania
+#''Wpisać, gdy osoba ubezpieczona nie posiada numerów identyfikacyjnych NIP lub PESEL.''<ref name="zus">Instrukcja wypełniania formularza ZUS ZCZA
-drogi.}\footnote{Kodeks Drogowy po nowelizacji w roku 1997.}
+(Zgłoszenie danych o członkach rodziny\dots)</ref>
-#{\it Wpisać, gdy osoba\boldsymbol{s}}\def\blank{\hbox{\sf Bbezpieczona nie posiada numerów identyfikacyjnych
+#''Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o&nbsp;współczynnikach całkowitych i takiej, która nie jest.''
-NIP lub \mbox{PESEL}.}\footnote{Instrukcja wypełniania formularza ZUS ZCZA
+#''Warunek zachodzi dla każdego <math>x</math> i dla pewnego <math>y</math>.''
-(Zgłoszenie danych o członkach rodziny\dots)}
+}}
-#{\it Podaj przykład liczby, która jest pierwiastkiem pewnego
-równania kwadratowego o&nbsp;współczynnikach
-całkowitych i takiej, która nie jest.}
-#''Warunek zachodzi dla każdego <math>x</math> i dla pewnego <math>y</math>.\/''
-\item Czy następujące definicje można lepiej sformułować?
-#''Zbiór <math>A</math> jest {\sf dobry}, jeśli ma co najmniej 2elementy.''
-#''Zbiór <math>A</math> jest {\sf dobry'', jeśli dla każdego <math>x\in A</math>,
-jeśli <math>x</math> jest parzyste, to <math>x</math> jest podzielne przez&nbsp;<math>3</math>.}
-#''Zbiór <math>A</math> jest {\sf dobry'', jeśli dla pewnego <math>x\in A</math>,
-jeśli <math>x</math> jest parzyste, to <math>x</math> jest podzielne przez&nbsp;<math>3</math>.}
-\item Wskazać  błąd w rozumowaniu:
-#{\it Aby wykazać prawdziwość tezy\\
-{\sf ,,Dla dowolnego <math>n</math>, jeśli
-zachodzi warunek <math>W(n)</math> to zachodzi warunek <math>U(n)</math>''}\\
-załóżmy, że dla
-dowolnego <math>n</math> zachodzi <math>W(n)</math>\dots}
-#{\it Aby wykazać prawdziwość tezy\\
-{\sf ,,Dla pewnego <math>n</math>, jeśli
-zachodzi warunek <math>W(n)</math> to zachodzi warunek <math>U(n)</math>''}\\
-załóżmy, że dla
-pewnego <math>n</math> zachodzi <math>W(n)</math>\dots}
+{{Cwiczenie|3||
+Czy następujące definicje można lepiej sformułować?
+#''Zbiór A jest''  dobry, ''jeśli ma co najmniej 2 elementy.''
+#''Zbiór A jest''  dobry, ''jeśli dla każdego ''<math>x\in A</math>, ''jeśli'' <math>x</math>'' jest parzyste, to ''<math>x</math>'' jest podzielne przez 3''.
+#''Zbiór A jest'' dobry, ''jeśli dla pewnego'' <math>x\in A</math>, ''jeśli'' <math>x</math>'' jest parzyste, to'' <math>x</math>'' jest podzielne przez 3.''
+}}
+{{Cwiczenie|4||
+Wskazać błąd w rozumowaniu:
+#''Aby wykazać prawdziwość tezy''<br>"Dla dowolnego <math>n</math>, jeśli zachodzi warunek <math>W(n)</math>, to zachodzi warunek <math>U(n)</math>"<br>''załóżmy, że dla dowolnego ''<math>n</math>'' zachodzi ''<math>W(n)</math>...
+#''Aby wykazać prawdziwość tezy''<br>"Dla pewnego <math>n</math>, jeśli zachodzi warunek <math>W(n)</math>, to zachodzi warunek <math>U(n)</math>''<br>''załóżmy, że dla pewnego ''<math>n</math> ''zachodzi ''<math>W(n)</math>...
+}}
-\item Sformułować poprawnie zaprzeczenia stwierdzeń:
+{{Cwiczenie|5||
+Sformułować poprawnie zaprzeczenia stwierdzeń:
 *''Liczby <math>m</math> i <math>n</math> są pierwsze.''
 *''Liczby <math>m</math> i <math>n</math> są względnie pierwsze.''
+}}
+{{Cwiczenie|6||
+Czy zdanie ''"Liczba&nbsp;<math>a</math> nie jest kwadratem pewnej liczby
+całkowitej"'' jest poprawnym zaprzeczeniem zdania ''"Liczba&nbsp;<math>a</math> jest kwadratem  pewnej liczby całkowitej"''?
+}}
-\item Czy zdanie {\it ,,Liczba&nbsp;<math>a</math> nie jest kwadratem pewnej liczby
+{{Cwiczenie|7||
-całkowitej''\/}
+Sygnatura <math>\Sigma</math> składa się z symboli <math>r, s \in \Sigma^R_1</math>, <math>R, S \in \Sigma^R_2</math> i <math>g\in \Sigma_2^F</math>. Napisać takie zdania <math>\var\varphi</math>&nbsp;i&nbsp;<math>\psi</math>,&nbsp;że:
-jest poprawnym zaprzeczeniem zdania {\it ,,Liczba&nbsp;<math>a</math> jest kwadratem
-pewnej liczby całkowitej''\/}?
-\item
+#zdanie <math>\var\varphi</math> jest prawdziwe dokładnie w&nbsp;tych modelach <math>A = <A, R^A, S^A, r^A, s^A, g^A></math>, w&nbsp;których obie relacje <math>R^A</math>, <math>S^A</math> są przechodnie, ale ich suma nie jest przechodnia;
-Sygnatura <math>\Sigma</math> składa się z symboli
+#zdanie <math>\psi</math> jest prawdziwe dokładnie w&nbsp;tych modelach <math>A = <A, R^A, S^A,  r^A, s^A, g^A></math>, w&nbsp;których <math>s^A</math> jest obrazem iloczynu kartezjańskiego <math>r^A\times r^A</math> przy funkcji <math>g^A</math>.
-<math>r, s \in \Sigma^R_1</math>, <math>R, S \in \Sigma^R_2</math> i <math>g\in \Sigma_2^F</math>.
+}}
-Napisać takie zdania <math>\var\varphi</math>&nbsp;i&nbsp;<math>\psi</math>,&nbsp;że:%61 jest rozwiazanie
+{{Cwiczenie|8||
+Sygnatura <math>\Sigma</math> składa się z dwuargumentowych symboli relacyjnych <math>r</math> i&nbsp;<math>s</math> oraz dwuargumentowego symbolu funkcyjnego&nbsp;<math>f</math>. Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w&nbsp;tych modelach <math>A = <A, r^A, s^A, f^A></math>, w&nbsp;których:
+#Złożenie relacji <math>r^A</math> i <math>s^A</math> zawiera się w ich iloczynie <math>r^A\cap s^A</math>;
+#Zbiór wartości funkcji&nbsp;<math>f^A</math> jest rzutem sumy <math>r^A\cup s^A</math> na pierwszą współrzędną;
+#Relacja <math>r^A</math> nie jest funkcją z&nbsp;<math>A</math> w&nbsp;<math>A</math>;
+#Obraz <math>r^A</math> przy funkcji&nbsp;<math>f^A</math> jest podstrukturą w&nbsp;<math>A</math>;
+#Obraz zbioru <math>A\times A</math> przy funkcji&nbsp;<math>f^A</math> jest pusty.
+}}
-#zdanie <math>\var\varphi</math> jest prawdziwe dokładnie w&nbsp;tych modelach
+{{Cwiczenie|9||
-<math>\A = \<A, R^\A, S^\A, r^\A, s^\A, g^\A\></math>,
-w&nbsp;których obie relacje <math>R^\A</math>, <math>S^\A</math>
-są przechodnie, ale ich suma nie jest przechodnia;
-#zdanie  <math>\psi</math> jest prawdziwe dokładnie w&nbsp;tych modelach
-<math>\A = \<A, R^\A, S^\A,  r^\A, s^\A, g^\A\></math>,
-w&nbsp;których <math>s^\A</math> jest obrazem iloczynu
-kartezjańskiego <math>r^\A\times r^\A</math> przy funkcji <math>g^\A</math>.
-\item  Sygnatura <math>\Sigma</math> składa się z dwuargumentowych symboli
-relacyjnych <math>r</math> i&nbsp;<math>s</math> oraz dwuargumentowego symbolu funkcyjnego&nbsp;<math>f</math>.
-Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dok{ł}adnie
-w&nbsp;tych modelach%77 jest rozwiazanie
-<math>\A = \<A, r^{\A}, s^{\A}, f^{\A}\></math>, w&nbsp;których:
-#Złożenie relacji <math>r^{\A}</math> i <math>s^{\A}</math> zawiera się w ich iloczynie
-<math>r^\A\cap s^\A</math>;
-#Zbiór wartości funkcji&nbsp;<math>f^{\A}</math> jest rzutem sumy <math>r^\A\cup s^\A</math> na
-pierwszą współrzędną;
-#Relacja <math>r^\A</math> nie jest funkcją z&nbsp;<math>A</math> w&nbsp;<math>A</math>;
-#Obraz <math>r^\A</math> przy funkcji&nbsp;<math>f^\A</math> jest podstrukturą w&nbsp;<math>\A</math>;
-#Obraz zbioru <math>A\times A</math> przy funkcji&nbsp;<math>f^\A</math> jest pusty.
-\item
 Dla każdej z par struktur:
-#<math>\<\NN,\leq\></math> i <math>\<\{m-{1\over n}\ |\ m,n\in\NN-\{0\}\}, \leq\></math>;
+#<math><\mathbb N,\leq></math> i <math><\{m-{1\over n}\ |\ m,n\in\mathbb N-\{0\}\}, \leq></math>;
-#<math>\<\NN, +\></math> i <math>\<\ZZ, +\></math>;
+#<math><\mathbb N, +></math> i <math><\mathbb Z, +></math>;
-#<math>\<\NN, \leq\></math> i <math>\<\ZZ, \leq\></math>,
+#<math><\mathbb N, \leq></math> i <math><\mathbb Z, \leq></math>,
-wskaż zdanie prawdziwe w jednej z nich a w drugiej nie.
+wskaż zdanie prawdziwe w jednej z nich, a w drugiej nie.
+}}
-\item Napisać takie zdania <math>\var\varphi</math> i&nbsp;<math>\psi</math>, że:
-#zdanie <math>\var\varphi</math> jest prawdziwe w&nbsp;modelu <math>\A = \<\ZZ, +, 0 \></math>,
-ale nie w&nbsp;modelu <math>\B = \<\NN, +, 0 \></math>;
-#zdanie  <math>\psi</math> jest prawdziwe w&nbsp;modelu <math>\B = \<\ZZ, +, 0 \></math>,
-ale nie w&nbsp;modelu <math>\C = \<\QQ, +, 0 \></math>.
-\item Wskazać formułę pierwszego rzędu:
-#spełnialną w
-ciele liczb rzeczywistych ale nie w ciele liczb wymiernych;
-#spełnialną w algebrze <math>\NN</math> z mnożeniem,
-ale nie w algebrze <math>\NN</math> z dodawaniem;
-#spełnialną w <math>\<\{a,b\}^*,\cdot,\varepsilon\></math>
-ale nie w <math>\<\{a,b,c\}^*,\cdot,\varepsilon\></math>.
+{{Cwiczenie|10||
+Napisać takie zdania <math>\var\varphi</math> i&nbsp;<math>\psi</math>, że:
+#zdanie <math>\var\varphi</math> jest prawdziwe w&nbsp;modelu <math>A = <\mathbb Z, +, 0 ></math>, ale nie w&nbsp;modelu <math>\mathfrak B =<\mathbb N, +, 0 ></math>;
+#zdanie <math>\psi</math> jest prawdziwe w&nbsp;modelu <math>\mathfrak B = <\mathbb Z, +, 0 ></math>, ale nie w&nbsp;modelu <math>C = <\mathbb Q, +, 0 ></math>.
+}}
-\item <span id="bezrownosci" \> Zmodyfikować konstrukcję
+{{Cwiczenie|11||
-z dowodu Twierdzenia&nbsp;[[#entscheidungsproblem]] w ten sposób,
+Wskazać formułę pierwszego rzędu:
-aby w formule  <math>\psi_\M</math> nie występował symbol równości
+#spełnialną w ciele liczb rzeczywistych, ale nie w ciele liczb wymiernych;
-ani stała </math>c<math>. %%{1. Napisać </math>\forall x\forall y\forall z(G(x,y)\wedge
+#spełnialną w algebrze <math>\mathbb N</math> z mnożeniem, ale nie w algebrze <math>\mathbb N</math> z dodawaniem;
-<!--%% R(y,z)\to \neg G(x,z))</math>.\quad
+#spełnialną w <math><\{a,b\}^*,\cdot,\varepsilon></math>, ale nie w <math><\{a,b,c\}^*,\cdot,\varepsilon></math>.
---><!--%% 2. Użyć wszędzie prefiksu <math>\forall x(\forall y \neg P(y,x)\to \cdots)</math>.}
+}}
--->\item <span id="stalasygnatura" \>  Zmodyfikować konstrukcję
-z dowodu Twierdzenia&nbsp;[[#entscheidungsproblem]] w ten sposób,
-aby <math>\psi_\M</math> była zawsze formułą\boldsymbol{s}}\def\blank{\hbox{\sf Bstalonej sygnatury (niezależnej
-od maszyny&nbsp;<math>\M</math>). Wywnioskować stąd, że logika pierwszego rzędu
-nad tą\boldsymbol{s}}\def\blank{\hbox{\sf Bstaloną sygnaturą jest nierozstrzygalna.
+{{Cwiczenie|12||
+Zmodyfikować konstrukcję z dowodu [[Logika dla informatyków/Logika pierwszego rzędu. Sposób użycia#entscheidungsproblem|Twierdzenia 3.8]] w ten sposób, aby w formule <math>\psi_M</math> nie występował symbol równości
+ani stała <math>c</math>.
+}}
+{{Cwiczenie|13||
+Zmodyfikować konstrukcję z dowodu [[Logika dla informatyków/Logika pierwszego rzędu. Sposób użycia#entscheidungsproblem|Twierdzenia 3.8]] w ten sposób, aby <math>\psi_M</math> była zawsze formułą ustalonej sygnatury (niezależnej od maszyny&nbsp;<math>M</math>). Wywnioskować stąd, że logika pierwszego rzędu nad tą ustaloną sygnaturą jest nierozstrzygalna.
+}}
-\end{small}
+<references/>

Logika dla informatyków/Ćwiczenia 3: Różnice pomiędzy wersjami

Aktualna wersja na dzień 10:45, 1 paź 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia