LOGIKA
ROK AK. 2010/2011
Program.
Język klasycznego rachunku zdań (język k.r.z.). Struktura formuł k.r.z. Twierdze-
nia strukturalne. Interpretacja semantyczna formuł k.r.z. Konsekwencje seman-
tyczne, tautologie. Podstawienia. Przykłady podstawowych tautologii. Równo-
ważność semantyczna formuł k.r.z. Boole owska interpretacje formuł k.r.z. Postacie
normalne formuł k.r.z. Zastępowanie spójników. Wielomianowa zupełność. Teorie
formalne. Konsekwencje syntaktyczne w teoriach formalnych. Klasyczny rachunek
zdań jako teoria. Niesprzeczność i niezależność aksjomatyki k.r.z. Pełność k.r.z.
Dowody formalne na gruncie k.r.z. Różne systemy aksjomatyczne k.r.z. Struktury.
Systemy relacyjne. Algebry. Język klasycznego rachunku k.r.p. Struktura formuł
k.r.p. Twierdzenia strukturalne. Konsekwencje semantyczne. Równoważność se-
mantyczna formuł k.r.p. Teorie elementarne. Aksjomatyka. Dowody formalne na
gruncie teorii elementarnych. Przykłady teorii elementarnych. Pełność klasycz-
nego rachunku predykatów. Teoria mnogości. Wybrane aksjomatyki - informacja.
Formalna teoria liczb. Funkcje pierwotnie rekurencyjne i rekurencyjne. Teorie re-
kurencyjnie aksjomatyzowalne. Teza Churcha.
Literatura
[1] Z. Adamowicz, P. Zbierski, Logika matematyczna. Państwowe Wydawnictwo Naukowe, War-
szawa, 1991.
[2] J. Barwise (Ed.) Handbook of Mathematical Logic. North-Holland, Amsterdam, New York,
Oxford, 1977.
[3] M. Ben-Ari, Mathematical Logic for Computer Science, (istn. tłum. na język polski: Logika
matematyczna w informatyce. Wydawnictwa Naukowo-Techniczne, Warszawa, 2005).
[4] S. Bilaniuk, A Problem Course in Mathematical Logic, (książka dostępna w Internecie).
[5] J.W. Bremer, Wprowadzenie do logiki. Wydawnictwo WAM, Kraków, 2004.
[6] S.N. Burris, Logic for Mathematics and Computer Science. Prentice Hall Inc., New Jer-
sey,1998.
[7] P.J. Cameron, Sets, Logic and Categories. Springer-Verlag, London, 1999.
[8] D. van Dalen, Logic and Structure. Springer-Verlag, 1994.
[9] A. Grzegorczyk, Zarys logiki matematycznej. Państwowe Wydawnictwo Naukowe, Warszawa,
1984.
[10] S.C. Kleene, Mathematical Logic. John Wiley & Sons, Inc. New York, London, Sydney, 1967.
[11] R. Kowalski, Logika w roawiazywaniu zadań. Wyadawnictwa Naukowo-Techniczne, Warsz-
zawa 1989.
[12] K. Kuratowski, Wstęp do teorii mnogości i topologii. Wydawnictwo Naukowe PWN, War-
szawa, 2004.
[13] R.C. Lyndon, Notes on Logic. Van Nostrand Company, Inc. 1966. (Istn. tłum. na język polski:
O logice matematycznej. Państwowe Wydawnictwo Naukowe, Warszawa, 1978.)
[14] E. Mendelson, Introduction to Mathematical Logic. Chapman & Hall, 1997.
[15] A. Mostowski, Logika matematyczna. Warszawa  Wrocław, 1948.
[16] A. Mostowski, K. Kuratowski, Teoria mnogości, Państwowe Wydawnictwo Naukowe, War-
szawa, 1978.
[17] R. Murawski, K. Świrydowicz Podstawy logiki i teorii mnogości. Wydawnictwo Naukowe
UAM, Poznań 2006.
[18] W. Ostasiewicz, Logika dla informatyków. Wydawnictwo Akademii Ekonomicznej im. Oskara
Langego we Wrocławiu, Wrocław, 2001.
[19] W. van Quine, Tłum. polskie: Logika matematyczna. Państwowe Wydawnictwo Naukowe,
Warszawa, 1974.
[20] W. Sierpiński, Wstęp do teorii mnogości i topologii. Państwowe Zakłady Wydawnictw Szkol-
nych, Warszawa, 1947.
[21] J. Słupecki, K. Hałkowska, K. Piróg-Rzepecka, Logika matematyczna. Wydawnictwo Na-
ukowe PWN, Warszawa, 1999.
[22] K. Świrydowicz, Podstawy logiki modalnej. Wydawnictwo Naukowe UAM, Poznań, 2004.
[23] K. Trzęsicki, Logika i teoria mnogości. Ujęcie systematyczno-historyczne. Akademicka Oficyna
Wydawnicza EXIT, Warszawa 2003.
[24] A. Wojciechowska, Elementy logiki i teorii mnogości. Państwowe Wydawnictwo Naukowe,
Warszawa, 1979.
Zbiory zadań
[25] I.A. A
awrow, A
.L. Maksimowa, Zada%0Å„i po teorii mno~
estv, matemati%0ńeskoj logikę, (istn. tłum.
na język polski: Zadania z teorii mnogości, logiki matematycznej i teorii algorytmów. Wy-
dawnictwo Naukowe PWN, Warszawa, 2004.)
[26] W. Marek, J. Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach. Wydawnictwo
Naukowe PWN, Warszawa, 1998. (Istnieje kilka wydań.)
[27] B. Stanosz, Ćwiczenia z logiki. Państwowe Wydawnictwo Naukowe, Warszawa, 1980. (Istnieje
kilka wydań.)
Ćwiczenia i materiały uzupełniające
Ćwiczenie 1. [25, rozdz. 2, par. 2.1, zad. 1].
Ćwiczenie 2. Zapisać w odwrotnej notacji beznawiasowej formuły występujące w
ćwiczeniach [26, 1.10  1.61].
Ćwiczenie 3. Ćwiczenia [27, 1 6].
Ćwiczenie 4. Znalez
ć ciągi tworzące formuł występujące w 1.10  1.61 ze zbioru
zadań [26] (dla każdej formuły po kilka różnych ciągów). W każdym przypadku
znalez
ć ciąg minimalny tj. ciąg o możliwie najmniejszej długości.
Ćwiczenie 5.
(i) Dla każdej z formuł występujących w 1.10  1.61 ze zbioru zadań [26] wskazać
wszystkie jej podformuły.
(ii) [25], rozdz. 2, par. 2.1, zad. 3.
(iii) Intuicyjnie jasne jest pojęcie pierwszego, drugiego etc. wystąpienia danego
symbolu alfabetu w danej formule (np.  pierwsze wystÄ…pienie zmiennej p0 w
formule Õ ). SformuÅ‚ować definicjÄ™ n-tego wystÄ…pienia symbolu a w formule
Õ.
(iv) Analogicznie jak w poprzednim punkcie sformułować definicję n-tego wystą-
pienia podformuÅ‚y È w formule Õ.
Ćwiczenie 6. Wykazać, że:
(1) Õ È Ð!Ò! Õ È.
Twierdzenie 1.
Cn : P(FormL ) - P(FormL ) ( x Cn (x) )
0 0
jest operatorem domknięcia.
Dowód. Ćwiczenie.
Ćwiczenie 7. Opisać rodzinę domknięć wyznaczoną przez operator Cn .
Wybrane tautologie k.r.z.
(2) Õ (" Õ "! Õ;
(3) Õ '" Õ "! Õ;
(4) (Õ (" È) (" Ç "! Õ (" (È (" Ç);
(5) (Õ '" È) '" Ç "! Õ '" (È '" Ç);
(6) Õ (" È "! È (" Õ;
(7) Õ '" È "! È '" Õ;
(8) Õ (" (È '" Ç) "! (Õ (" È) '" (Õ (" Ç);
(9) Õ '" (È (" Ç) "! (Õ '" È) (" (Õ '" Ç);
(10) Ź(Õ (" È) "! ŹÕ '" ŹÈ;
(11) Ź(Õ '" È) "! ŹÕ (" ŹÈ;
(12) ŹŹÕ "! Õ;
(13) (Õ "! È) "! (Õ È) '" (È Õ);
(14) (Õ È) "! ŹÕ (" È;
(15) (Õ È) "! Ź(Õ '" ŹÈ);
(16) Õ (" È "! (ŹÕ È);
(17) Õ (" È "! Ź(ŹÕ '" ŹÈ);
(18) Õ '" È "! Ź(Õ ŹÈ);
(19) Õ '" È "! Ź(ŹÕ (" ŹÈ);
(20) ŹÕ "! (Õ Ä„");
(21) Ä„" "! Õ '" ŹÕ;
def
(22) "! Õ (" ŹÕ ( gdzie = ŹĄ");
(23) (ŹÕ Õ) Õ;
(24) ŹÕ (Õ Ç);
(25) Õ (È Õ);
(26) (Õ È) '" Õ È;
(27) (Õ È) '" ŹÈ ŹÕ;
(28) (Õ È) ((È Ç) (Õ Ç));
(29) (Õ '" È Ç) (Õ (È Ç));
(30) (Õ (È Ç)) (Õ '" È Ç);
(31) (Õ (È Ç)) ((Õ È) (Õ Ç));
(32) (Õ È) ((ŹÕ È) È);
(33) (Õ È) ((Õ ŹÈ) ŹÕ);
Terminologia:
" (2), (3)  prawa idempotentności;
" (4), (5)  prawa łączności;
" (6), (7)  prawa przemienności;
" (8), (9)  prawa rozdzielności (dystrybutywności);
" (10), (11)  prawa de Morgana;
" (12)  prawo podwójnego przeczenia;
" (21)  prawo redukcji do absurdu;
" (22)  prawo wyłączonego środka.
" (23)  prawo Claviusa;
" (24)  prawo Dunsa Szkota;
" (25)  prawo symplikacji;
" (26)  modus ponens;
" (27)  modus tollens;
" (28)  sylogizm hipotetyczny;
" (29)  prawo eksportacji;
" (30)  prawo importacji;
" (31)  sylogizm Fregego;
" (32)  dylemat konstrukcyjny;
" (33)  dylemat destrukcyjny;
Ćwiczenie 8. Wykazać, że (2)  (33) są schematami tautologii.
Ćwiczenie 9.
(i) [26, zad. 1.10  1.61].
(ii) [27, zad. 26, 48  57].
Ćwiczenie 10. Niech Õ, È, Ç " FL . Wykazać, że
0
Õ H" Õ;
Õ H" È Ò! È H" Õ;
Õ H" È, È H" Ç Ò! Õ H" Ç.
Ćwiczenie 11. [25, rozdz. 2, par. 2.1, zad. 14  20].
Ćwiczenie 12. Niech Õ1, . . . , Õn, È1, . . . , Èm, È " FL . Wtedy
0
n n

(34) È '" ( Õi) H" (È '" Õi);
i=1 i=1
n n

(35) È (" ( Õi) H" (È (" Õi);
i=1 i=1
n n

(36) Õi H" ÕÃ(i) Ã " Sn;
i=1 i=1
n n

(37) Õi H" ÕÃ(i) Ã " Sn;
i=1 i=1
n m n m

(38) {Õ1, . . . , Õn} = {È1, . . . , Èm} Ò! Õi H" Èi, Õi H" Èi.
i=1 i=1 i=1 i=1
Ćwiczenie 13. Znalez
ć interpretację boole owską dla formuł [26, zad. 1.33  1.61]
Ćwiczenie 14.
(i) [25, rozdz. 2, par. 2.1, zad. 24].
(ii) [26, zad. 1.83, 1.84].
Ćwiczenie 15. Dla każdej z formuł (2)  (33) znalez
ć równoważną formułę zbu-
dowaną wyłącznie przy pomocy zmiennych zdaniowych i spójników {Ź, ("} ({Ź, '"},
{Ź, }, {|}, {“!}).
Ćwiczenie 16. Czy zbiory {, Ą"}, {, }, {(", Ą"}, {(", }, {'", Ą"}, {'", }, { },
{ , Ź} są zupełne?
Ćwiczenie 17. Wykazać, że | oraz “! sÄ… jedynymi spójnikami 2-argumentowymi zu-
peÅ‚nymi (tj. {|} oraz {“!} sÄ… zupeÅ‚nymi zbiorami spójników).
Twierdzenie 2. Niech T będzie teorią. Wtedy
Cn : P(F ormT) - P(F ormT) ( x Cn (x) )
T T
jest algebraicznym operatorem domknięcia.
Dowód. Ćwiczenie.
Twierdzenie 3. Niech T będzie teorią. Wtedy
(39) " Ä…" Cn (“) Ò! Cn (") Ä…" Cn (“)
T T T
Dowód. Ćwiczenie.
Ćwiczenie 18.
(i) Oznaczmy przez
Cn = (im Cn ; Ä…").
T T
(a) Czy Cn jest kratÄ…?
T
(b) Jeśli Cn jest kratą, to czy jest to krata zupełna?
T
(c) Jeśli Cn jest kratą, to czy jest podkratą kraty (P(F ormT), ą")?
T
(ii) Rozważmy zbiór
IndT def {x | x ą" F ormT, x  niezależny}
=
Czy
IndT = (IndT; Ä…")
jest kratÄ…?
Z
Wybrane tezy i konsekwencje teorii Z
Z
(T1) Õ Õ,
(T2) (ŹÕ Õ) Õ,
(T3) Õ (È Ç), È Õ Ç.
(T4) Õ È, È Ç Õ Ç,
(T5) Õ (È Ç) È (Õ Ç),
(T6) ŹŹÕ Õ,
(T7) Õ ŹŹÕ.
(T8) ŹÕ (Õ È),
(T9) (ŹÈ ŹÕ) (Õ È),
(T10) (Õ È) (ŹÈ ŹÕ),
(T11) Õ (ŹÈ Ź(Õ È)),
(T12) (Õ È) ((ŹÕ È) È).
(T13) Õ Õ (" È,
(T14) Õ È (" Õ,
(T15) Õ (" È È (" Õ,
(T16) Õ '" È Õ,
(T17) Õ '" È È,
(T18) Õ '" È È '" Õ.
(T19) Õ, È Õ '" È,
(T20) Õ È, È Õ Õ "! È,
(T21) Ä„" Õ,
(T22) (Õ (È Ç)) (Õ '" È Ç),
(T23) Õ (" ŹÕ,
(T24) (Õ Ä„") ŹÕ,
(T25) Ź(Õ (" È) ŹÕ '" ŹÈ,
(T26) Ź(Õ '" È) ŹÕ (" ŹÈ.
Dowód. Dowody formalne  ćwiczenie.