Lista zadań z matematycznych podstaw informatyki nr 2.
Zad. 1. Niech T bÄ™dzie teoriÄ… niesprzecznÄ… i zupeÅ‚nÄ…, a Õ i È  zdaniami. Pokaż, że T Õ (" È
wtedy i tylko wtedy, gdy albo T Õ, albo T È. Pokaż też, że T ŹÕ wtedy i tylko wtedy,
gdy T Õ.
Zad. 2. Udowodnij, że jeżeli A jest strukturą, to teoria struktury A, czyli teoria
{Õ : Õ jest zdaniem oraz A |= Õ},
jest niesprzeczna i zupełna.
Zad. 3. Udowodnij, że teoria grup nie jest zupełna. Teoria grup jest tu rozumiana tak, jak w
części pierwszej notatek.
Zad. 4. Udowodnij, że każda struktura ma przeliczalną podstrukturę o tej samej teorii. Pojęcie
podstruktury jest uogólnieniem pojęcia podalgebry. Jeżeli mamy strukturę A i podzbiór B jej
uniwersum, to czasem może okazać się funkcje ze struktury A (interpretacje symboli funk-
cyjnych) można obiąć do zbioru B. Wtedy strukturę B o uniwersum B, z obięciami funkcji i
relacji ze struktury A do zbioru B nazywamy podstrukturą struktury A. Oczywiście, musimy
założyć, że język struktury ma przeliczalnie wiele symboli. Wynika stąd w szczególności, że
dowolna formuła jest tautologią wtedy i tylko wtedy, gdy jest spełniona we wszystkich prze-
liczalnych strukturach. Wskazówka. Można podjąć próbę dowodu równoważności, że dowolna
formuła jest spełniona przy wartościowaniu h w podstrukturze wtedy i tylko wtedy, gdy jest
spełniona w całej strukturze. Dowód powinien się zaciąć, a kłopoty usuwa konstrukcja podobna
do  henkinizacji z dowodu twierdzenia o pełności.
Zad. 5. Niech Ś oznacza formułę
"x"y"z((A(x, y) Ò! A(y, z) '" A(z, z)) '" (A(x, y) '" B(x, y) Ò! B(x, z) '" B(z, z)))
(jest to formuła wykorzystywana do testowania programu Gilmora). Udowodnij, że Ś jest
tautologią (prawem logiki). Zrób to wprost oraz korzystając z algorytmu Herbranda.
Zad. 6. Rozważamy formuÅ‚y bez staÅ‚ych i symboli funkcyjnych, formuÅ‚a Õ nie zawiera po-
nadto kwantyfikatorów. Udowodnij, że zdanie "x1 . . . "xn Õ jest tautologiÄ… wtedy i tylko
wtedy, gdy formuÅ‚a Õ jest speÅ‚niona przy każdym (jedynym możliwym) wartoÅ›ciowaniu w
każdej strukturze o jednoelementowym uniwersum. Jak sprawdzić warunek z prawej strony tej
równoważności posługując się metodą zerojedynkową? Zbadaj, czy formuła
"x "y "z ((F (x, y) Ò! F (y, z) '" F (z, z)) '" (F (x, y) '" G(x, y) Ò! G(x, z) '" G(z, z)))
jest tautologiÄ….
Zad. 7. Zmodyfikuj równoważność z poprzedniego zadania tak, aby była prawdziwa dla formuł
Õ, w których mogÄ… dodatkowo wystÄ™pować staÅ‚e.
Zad. 8. Czy istnieje algorytm, który odpowiada na pytanie, czy zdanie
"x1 . . . "xn "y1 . . . "ym Õ
(Õ nie zawiera kwantyfikatorów) jest tautologiÄ…? LiczÄ… siÄ™ też częściowe odpowiedzi.