Logika dla informatyków/Ćwiczenia 3

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ć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
Jak rozumiesz następujące zdania? Jak je sformułować, żeby nie budziły wątpliwości?

  1. Nie wolno pić i grać w karty.
  2. Nie wolno pluć i łapać.
  3. Zabrania się zaśmiecania i zanieczyszczania drogi.<ref name="kodeks1">Kodeks Drogowy przed nowelizacją w roku 1997.</ref>
  4. Zabrania się zaśmiecania lub zanieczyszczania drogi. <ref name="kodeks2">Kodeks Drogowy po nowelizacji w roku 1997.</ref>
  5. 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>

  1. Podaj przykład liczby, która jest pierwiastkiem pewnego równania kwadratowego o współczynnikach całkowitych i takiej, która nie jest.
  2. Warunek zachodzi dla każdego i dla pewnego .


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