1
Lista zadań z matematycznych podstaw informatyki nr 1.
Zad. 1. Sprawdz
, że każdy term, w którym występuje najwyżej zmienna x jest podstawialny
w dowolnej formule za zmienną x.
Zad. 2. Podaj formalne dowody w systemie założeniowym (albo w wybranym systemie logicz-
nym) formuł następujących postaci:
1) ((p '" q) �! r) �! (p �! (q �! r)) (p, q, r to dowolne formuły, zmienne zdaniowe lub
zeroargumentowe symbole relacyjne),
2) p �! ŹŹp,
3) (p �! q) �! (Źq �! Źp),
4) Ź(p (" q) �! (Źp '" Źq),
5) p (" Źp,
6) (p �! r) �! ((q �! r) �! (p (" q �! r)),
7) "x(� �! �) �! ("x� �! "x�),
8) "x(� �! �) �! ("x� �! "x�),
9) "x(� �! �) �! ("x� �! �) pod warunkiem, że x nie jest wolna w �,
10) "x"y� �! "y"x�.
Zad. 3. Udowodnij, że w teorii T można dowieść formułę � wtedy i tylko wtedy, gdy w teorii T
można dowieść formułę "x�. Udowodnij, że formuły "x� �! � są twierdzeniami (że "x� �!
�). Udowodnij, że niektóre z formuł postaci � �! "x� nie dają się dowieść w rozważanych
systemach logicznych.
Zad. 4. Zbadaj, w jakim stopniu dowód twierdzenia o równoważności definicji ciągłości jest
dowodem założeniowym.
Zad. 5. Udowodnij, że zbiory twierdzeń systemów Shoenfielda i G�dla są identyczne.
Zad. 6. Niech x będzie ustaloną zmienną, a t  dowolnym termem. Dla danego wartościowa-
nia zmiennych h definiujemy wartościowanie ht przyjmując, że ht(y) = h(y) dla wszystkich
zmiennych y = x oraz ht(x) = t[h]. Udowodnij, że

1) s[x �! t][h] = s[ht] dla dowolnego termu s,
2) A |= �[x �! t][h] wtedy i tylko wtedy, gdy A |= �[ht] dla dowolnej struktury A, dowolnej
formuły � i dowolnego wartościowania zmiennych h.