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. Ławrow, Ł.L. Maksimowa, Zadači po teorii množestv, matematič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. Znaleźć 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

znaleźć 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 p

0

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(Form

L

0

) −→ P(Form

L

0

)

( x 7→ Cn



(x) )

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)

 > ↔ ϕ ∨ ¬ϕ ( gdzie >

def

= ¬⊥);

(22)

 (¬ϕ → ϕ) → ϕ;

(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 ϕ, ψ, χ ∈ F

L

0

. Wykazać, że

ϕ ≈ ϕ;

ϕ ≈ ψ ⇒ ψ ≈ ϕ;

ϕ ≈ ψ, ψ ≈ χ ⇒ ϕ ≈ χ.

Ćwiczenie 11. [

25

, rozdz. 2, par. 2.1, zad. 14 – 20].

Ćwiczenie 12. Niech ϕ

1

, . . . , ϕ

n

, ψ

1

, . . . , ψ

m

, ψ ∈ F

L

0

. Wtedy

ψ ∧ (

n

_

i=1

ϕ

i

) ≈

n

_

i=1

(ψ ∧ ϕ

i

);

(34)

ψ ∨ (

n

^

i=1

ϕ

i

) ≈

n

^

i=1

(ψ ∨ ϕ

i

);

(35)

n

_

i=1

ϕ

i

≈

n

_

i=1

ϕ

σ(i)

σ ∈ S

n

;

(36)

n

^

i=1

ϕ

i

≈

n

^

i=1

ϕ

σ(i)

σ ∈ S

n

;

(37)

{ϕ

1

, . . . , ϕ

n

} = {ψ

1

, . . . , ψ

m

} ⇒

n

_

i=1

ϕ

i

≈

m

_

i=1

ψ

i

,

n

^

i=1

ϕ

i

≈

m

^

i=1

ψ

i

.

(38)

Ćwiczenie 13. Znaleźć 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

) znaleźć równoważną formułę zbu-

dowaną wyłącznie przy pomocy zmiennych zdaniowych i spójników {¬, ∨} ({¬, ∧},
{¬, →}, {|}, {↓}).

Ćwiczenie 16. Czy zbiory {→, ⊥}, {→, >}, {∨, ⊥}, {∨, >}, {∧, ⊥}, {∧, >}, {Y},
{Y, ¬} 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

`

T

: P(F orm

T

) −→ P(F orm

T

)

( x 7→ Cn

`

T

(x) )

jest algebraicznym operatorem domknięcia.

Dowód. Ćwiczenie.



Twierdzenie 3. Niech T będzie teorią. Wtedy

∆ ⊆ Cn

`

T

(Γ) ⇒ Cn

`

T

(∆) ⊆ Cn

`

T

(Γ)

(39)

Dowód. Ćwiczenie.



Ćwiczenie 18.

(i) Oznaczmy przez

Cn

`

T

= (im Cn

`

T

; ⊆).

(a) Czy Cn

`

T

jest kratą?

(b) Jeśli Cn

`

T

jest kratą, to czy jest to krata zupełna?

(c) Jeśli Cn

`

T

jest kratą, to czy jest podkratą kraty (P(F orm

T

), ⊆)?

(ii) Rozważmy zbiór

Ind

T

def

= {x | x ⊆ F orm

T

,

x — niezależny}

Czy

Ind

T

= (Ind

T

; ⊆)

jest kratą?

Wybrane tezy i konsekwencje teorii Z

Z

Z

` ϕ → ϕ,

(T

1

)

` (¬ϕ → ϕ) → ϕ,

(T

2

)

ϕ → (ψ → χ), ψ ` ϕ → χ.

(T

3

)

ϕ → ψ, ψ → χ ` ϕ → χ,

(T

4

)

ϕ → (ψ → χ) ` ψ → (ϕ → χ),

(T

5

)

` ¬¬ϕ → ϕ,

(T

6

)

` ϕ → ¬¬ϕ.

(T

7

)

` ¬ϕ → (ϕ → ψ),

(T

8

)

` (¬ψ → ¬ϕ) → (ϕ → ψ),

(T

9

)

` (ϕ → ψ) → (¬ψ → ¬ϕ),

(T

10

)

` ϕ → (¬ψ → ¬(ϕ → ψ)),

(T

11

)

` (ϕ → ψ) → ((¬ϕ → ψ) → ψ).

(T

12

)

` ϕ → ϕ ∨ ψ,

(T

13

)

` ϕ → ψ ∨ ϕ,

(T

14

)

` ϕ ∨ ψ → ψ ∨ ϕ,

(T

15

)

` ϕ ∧ ψ → ϕ,

(T

16

)

` ϕ ∧ ψ → ψ,

(T

17

)

` ϕ ∧ ψ → ψ ∧ ϕ.

(T

18

)

ϕ, ψ ` ϕ ∧ ψ,

(T

19

)

ϕ → ψ, ψ → ϕ ` ϕ ↔ ψ,

(T

20

)

⊥ ` ϕ,

(T

21

)

` (ϕ → (ψ → χ)) → (ϕ ∧ ψ → χ),

(T

22

)

` ϕ ∨ ¬ϕ,

(T

23

)

` (ϕ → ⊥) → ¬ϕ,

(T

24

)

` ¬(ϕ ∨ ψ) → ¬ϕ ∧ ¬ψ,

(T

25

)

` ¬(ϕ ∧ ψ) → ¬ϕ ∨ ¬ψ.

(T

26

)

Dowód. Dowody formalne — ćwiczenie.