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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
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 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 zawiera się w ich iloczynie ;
  2. Zbiór wartości funkcji  jest rzutem sumy na pierwszą współrzędną;
  3. Relacja nie jest funkcją z ;
  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}, ż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/>