Logika dla informatyków/Ćwiczenia 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
{{Cwiczenie|1|| | |||
Stosując schematy (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: | Stosując schematy (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 \forall y\forall z(p(y)\to q(z))</math>; | #<math>(\exists y p(y) \to \forall z q(z)) \to \forall y\forall z(p(y)\to q(z))</math>; | ||
| Linia 5: | Linia 5: | ||
#</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\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 | #</math>\forall x(p(x)\to \exists y q(y))\to\exists y(\exists x p(x)\to q(y))</math>.% 110a | ||
}} | |||
{{Cwiczenie|2|| | |||
Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie budziły wątpliwości? | Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie budziły wątpliwości? | ||
#''Nie wolno pić i grać w karty.'' | #''Nie wolno pić i grać w karty.'' | ||
| Linia 17: | Linia 17: | ||
#''Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o współczynnikach całkowitych i takiej, która nie jest.'' | #''Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o współczynnikach całkowitych i takiej, która nie jest.'' | ||
#''Warunek zachodzi dla każdego <math>x</math> i dla pewnego <math>y</math>.'' | #''Warunek zachodzi dla każdego <math>x</math> i dla pewnego <math>y</math>.'' | ||
}} | |||
{{Cwiczenie|3|| | |||
Czy następujące definicje można lepiej sformułować? | 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 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 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.'' | #''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: | 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 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>... | #''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>... | ||
}} | |||
{{Cwiczenie|5|| | |||
Sformułować poprawnie zaprzeczenia stwierdzeń: | Sformułować poprawnie zaprzeczenia stwierdzeń: | ||
*''Liczby <math>m</math> i <math>n</math> są pierwsze.'' | *''Liczby <math>m</math> i <math>n</math> są pierwsze.'' | ||
*''Liczby <math>m</math> i <math>n</math> są względnie pierwsze.'' | *''Liczby <math>m</math> i <math>n</math> są względnie pierwsze.'' | ||
}} | |||
{{Cwiczenie|6|| | |||
Czy zdanie '' "Liczba <math>a</math> nie jest kwadratem pewnej liczby | Czy zdanie '' "Liczba <math>a</math> nie jest kwadratem pewnej liczby | ||
całkowitej" '' jest poprawnym zaprzeczeniem zdania '' "Liczba <math>a</math> jest kwadratem pewnej liczby całkowitej" ''? | całkowitej" '' jest poprawnym zaprzeczeniem zdania '' "Liczba <math>a</math> jest kwadratem pewnej liczby całkowitej" ''? | ||
}} | |||
{{Cwiczenie|7|| | |||
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> i <math>\psi</math>, że: | 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> i <math>\psi</math>, że: | ||
#zdanie <math>\var\varphi</math> jest prawdziwe dokładnie w tych modelach <math>A = <A, R^A, S^A, r^A, s^A, g^A></math>, w których obie relacje <math>R^A</math>, <math>S^A</math> są przechodnie, ale ich suma nie jest przechodnia; | #zdanie <math>\var\varphi</math> jest prawdziwe dokładnie w tych modelach <math>A = <A, R^A, S^A, r^A, s^A, g^A></math>, w 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 tych modelach <math>A = <A, R^A, S^A, r^A, s^A, g^A></math>, w których <math>s^A</math> jest obrazem iloczynu kartezjańskiego <math>r^A\times r^A</math> przy funkcji <math>g^A</math>. | #zdanie <math>\psi</math> jest prawdziwe dokładnie w tych modelach <math>A = <A, R^A, S^A, r^A, s^A, g^A></math>, w których <math>s^A</math> jest obrazem iloczynu kartezjańskiego <math>r^A\times r^A</math> przy funkcji <math>g^A</math>. | ||
}} | |||
{{Cwiczenie|8|| | |||
Sygnatura <math>\Sigma</math> składa się z dwuargumentowych symboli relacyjnych <math>r</math> i <math>s</math> oraz dwuargumentowego symbolu funkcyjnego <math>f</math>. Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w tych modelach <math>A = <A, r^A, s^A, f^A></math>, w których: | Sygnatura <math>\Sigma</math> składa się z dwuargumentowych symboli relacyjnych <math>r</math> i <math>s</math> oraz dwuargumentowego symbolu funkcyjnego <math>f</math>. Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w tych modelach <math>A = <A, r^A, s^A, f^A></math>, w 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>; | #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>; | ||
| Linia 57: | Linia 57: | ||
#Obraz <math>r^A</math> przy funkcji <math>f^A</math> jest podstrukturą w <math>A</math>; | #Obraz <math>r^A</math> przy funkcji <math>f^A</math> jest podstrukturą w <math>A</math>; | ||
#Obraz zbioru <math>A\times A</math> przy funkcji <math>f^A</math> jest pusty. | #Obraz zbioru <math>A\times A</math> przy funkcji <math>f^A</math> jest pusty. | ||
}} | |||
{{Cwiczenie|9|| | |||
Dla każdej z par struktur: | Dla każdej z par struktur: | ||
#<math><\mathbb N,\leq></math> i <math><\{m-{1\over n}\ |\ m,n\in\mathbb N-\{0\}\}, \leq></math>; | #<math><\mathbb N,\leq></math> i <math><\{m-{1\over n}\ |\ m,n\in\mathbb N-\{0\}\}, \leq></math>; | ||
| Linia 65: | Linia 65: | ||
#<math><\mathbb N, \leq></math> i <math><\mathbb Z, \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. | ||
}} | |||
{{Cwiczenie|10|| | |||
Napisać takie zdania <math>\var\varphi</math> i <math>\psi</math>, że: | Napisać takie zdania <math>\var\varphi</math> i <math>\psi</math>, że: | ||
#zdanie <math>\var\varphi</math> jest prawdziwe w modelu <math>A = <\mathbb Z, +, 0 ></math>, ale nie w modelu <math>\mathfrak B =<\mathbb N, +, 0 ></math>; | #zdanie <math>\var\varphi</math> jest prawdziwe w modelu <math>A = <\mathbb Z, +, 0 ></math>, ale nie w modelu <math>\mathfrak B =<\mathbb N, +, 0 ></math>; | ||
#zdanie <math>\psi</math> jest prawdziwe w modelu <math>\mathfrak B = <\mathbb Z, +, 0 ></math>, ale nie w modelu <math>C = <\mathbb Q, +, 0 ></math>. | #zdanie <math>\psi</math> jest prawdziwe w modelu <math>\mathfrak B = <\mathbb Z, +, 0 ></math>, ale nie w modelu <math>C = <\mathbb Q, +, 0 ></math>. | ||
}} | |||
{{Cwiczenie|11|| | |||
Wskazać formułę pierwszego rzędu: | Wskazać formułę pierwszego rzędu: | ||
#spełnialną w ciele liczb rzeczywistych ale nie w ciele liczb wymiernych; | #spełnialną w ciele liczb rzeczywistych ale nie w ciele liczb wymiernych; | ||
#spełnialną w algebrze <math>\mathbb N</math> z mnożeniem, ale nie w algebrze <math>\mathbb N</math> z dodawaniem; | #spełnialną w algebrze <math>\mathbb N</math> z mnożeniem, ale nie w algebrze <math>\mathbb N</math> z dodawaniem; | ||
#spełnialną w <math><\{a,b\}^*,\cdot,\varepsilon></math> ale nie w <math><\{a,b,c\}^*,\cdot,\varepsilon></math>. | #spełnialną w <math><\{a,b\}^*,\cdot,\varepsilon></math> ale nie w <math><\{a,b,c\}^*,\cdot,\varepsilon></math>. | ||
}} | |||
{{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 | 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>. | 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 <math>M</math>). Wywnioskować stąd, że logika pierwszego rzędu nad tą ustaloną sygnaturą jest nierozstrzygalna. | 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 <math>M</math>). Wywnioskować stąd, że logika pierwszego rzędu nad tą ustaloną sygnaturą jest nierozstrzygalna. | ||
}} | |||
<references/> | <references/> | ||
Wersja z 09:24, 29 wrz 2006
Ćwiczenie 1
Stosując schematy (6-9) z Faktu 3.1, pokazać, że następujące formuły są tautologiami:
- ;
- </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 , jeśli jest parzyste, to jest podzielne przez 3.
- Zbiór A jest dobry, jeśli dla pewnego , jeśli jest parzyste, to jest podzielne przez 3.
Ćwiczenie 4
Wskazać błąd w rozumowaniu:
- Aby wykazać prawdziwość tezy
"Dla dowolnego , jeśli zachodzi warunek to zachodzi warunek "
załóżmy, że dla dowolnego zachodzi ... - Aby wykazać prawdziwość tezy
"Dla pewnego , jeśli zachodzi warunek to zachodzi warunek
załóżmy, że dla pewnego zachodzi ...
Ćwiczenie 5
Sformułować poprawnie zaprzeczenia stwierdzeń:
- Liczby i są pierwsze.
- Liczby i są względnie pierwsze.
Ćwiczenie 6
Czy zdanie "Liczba nie jest kwadratem pewnej liczby całkowitej" jest poprawnym zaprzeczeniem zdania "Liczba jest kwadratem pewnej liczby całkowitej" ?
Ćwiczenie 7
Sygnatura składa się z symboli , i . 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 , w których obie relacje , są przechodnie, ale ich suma nie jest przechodnia;
- zdanie jest prawdziwe dokładnie w tych modelach , w których jest obrazem iloczynu kartezjańskiego przy funkcji .
Ćwiczenie 8
Sygnatura składa się z dwuargumentowych symboli relacyjnych 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:
- 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} ;
- 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ą;
- Relacja 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} nie jest funkcją z 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} w ;
- Obraz przy funkcji jest podstrukturą w ;
- Obraz zbioru przy funkcji jest pusty.
Ćwiczenie 9
Dla każdej z par struktur:
- i ;
- i ;
- i ,
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 , ale nie w modelu ;
- zdanie jest prawdziwe w modelu , ale nie w modelu .
Ć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 ale nie w .
Ćwiczenie 12
Zmodyfikować konstrukcję z dowodu Twierdzenia 3.8 w ten sposób, aby w formule nie występował symbol równości ani stała .
Ćwiczenie 13
Zmodyfikować konstrukcję z dowodu Twierdzenia 3.8 w ten sposób, aby była zawsze formułą ustalonej sygnatury (niezależnej od maszyny ). Wywnioskować stąd, że logika pierwszego rzędu nad tą ustaloną sygnaturą jest nierozstrzygalna.
<references/>
