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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 1 wersji utworzonej przez jednego użytkownika)
Linia 1: Linia 1:
Ćwiczenie 1<br>
+
{{Cwiczenie|1||
 
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:
 
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 \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||
Ćwiczenie 2<br>
 
 
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 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>.''
 +
}}
  
 
+
{{Cwiczenie|3||
Ćwiczenie 3<br>
 
 
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:
 +
#''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>...
 +
}}
  
Ćwiczenie 4<br>
+
{{Cwiczenie|5||
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>...
 
 
 
 
 
Ćwiczenie 5<br>
 
 
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&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"''?
 +
}}
  
Ćwiczenie 6<br>
+
{{Cwiczenie|7||
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" ''?
 
 
 
 
 
Ćwiczenie 7<br>
 
 
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:
 
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:
  
 
#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>.
 +
}}
  
 
+
{{Cwiczenie|8||
Ćwiczenie 8<br>
 
 
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:
 
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>;
 
#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&nbsp;<math>f^A</math> jest podstrukturą 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.  
 
#Obraz zbioru <math>A\times A</math> przy funkcji&nbsp;<math>f^A</math> jest pusty.  
 +
}}
  
 
+
{{Cwiczenie|9||
Ćwiczenie 9<br>
 
 
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>;
 
#<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.  
 +
}}
  
 
+
{{Cwiczenie|10||
Ćwiczenie 10<br>
 
 
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>.
 
+
}}
  
Ćwiczenie 11<br>
+
{{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>.
 
+
}}
  
Ćwiczenie 12<br>
+
{{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||
Ćwiczenie 13<br>
 
 
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.  
 
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.  
 
+
}}
  
  
 
<references/>
 
<references/>

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/>