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 15: Linia 15:
#''Wpisać, gdy osoba ubezpieczona nie posiada numerów identyfikacyjnych NIP lub PESEL.''<ref name="zus">Instrukcja wypełniania formularza ZUS ZCZA  
#''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>
(Zgłoszenie danych o członkach rodziny\dots)</ref>
#''Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o&nbsp;współczynnikach całkowitych i takiej, która nie jest.''
#''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>.''
#''Warunek zachodzi dla każdego <math>x</math> i dla pewnego <math>y</math>.''
}}
}}
Linia 27: Linia 27:


{{Cwiczenie|4||
{{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>...
}}
}}


Linia 39: Linia 39:


{{Cwiczenie|6||
{{Cwiczenie|6||
Czy zdanie '' "Liczba&nbsp;<math>a</math> nie jest kwadratem pewnej liczby  
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" ''?  
całkowitej"'' jest poprawnym zaprzeczeniem zdania ''"Liczba&nbsp;<math>a</math> jest kwadratem  pewnej liczby całkowitej"''?  
}}
}}


Linia 47: Linia 47:


#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;
#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;
#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>.
#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>.
}}
}}


Linia 64: Linia 64:
#<math><\mathbb N, +></math> i <math><\mathbb Z, +></math>;
#<math><\mathbb N, +></math> i <math><\mathbb Z, +></math>;
#<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.  
}}
}}


Linia 70: Linia 70:
Napisać takie zdania <math>\var\varphi</math> i&nbsp;<math>\psi</math>, że:  
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>\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>.
#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>.
}}
}}


{{Cwiczenie|11||
{{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||
{{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>.
}}
}}

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:

  1. ;
  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 , jeśli jest parzyste, to jest podzielne przez 3.
  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:

  1. Aby wykazać prawdziwość tezy
    "Dla dowolnego , jeśli zachodzi warunek , to zachodzi warunek "
    załóżmy, że dla dowolnego zachodzi ...
  2. 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:

  1. 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;
  2. 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  oraz dwuargumentowego symbolu funkcyjnego . Napisać (możliwie najkrótsze) zdanie, które jest prawdziwe dokładnie w tych modelach , w których:

  1. Złożenie relacji 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 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 ;
  4. Obraz przy funkcji  jest podstrukturą w ;
  5. Obraz zbioru przy funkcji  jest pusty.

Ćwiczenie 9

Dla każdej z par struktur:

  1. i ;
  2. i ;
  3. 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:

  1. zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} jest prawdziwe w modelu , ale nie w modelu ;
  2. zdanie jest prawdziwe w modelu , ale nie w modelu .

Ć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 z mnożeniem, ale nie w algebrze z dodawaniem;
  3. 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/>

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Logika_dla_informatyków/Ćwiczenia_3&oldid=61103”