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 6` ϕ.

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 ∃x

1

. . .

∃x

n

ϕ

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

∀x

1

. . .

∀x

n

∃y

1

. . .

∃y

m

ϕ

(ϕ nie zawiera kwantyfikatorów) jest tautologią? Liczą się też częściowe odpowiedzi.