Logika i teoria mnogości

Język, w którym zapisana jest cała reszta matematyki: zdania i ich prawdziwość, zbiory i działania na nich, relacje między elementami, zasada indukcji i to, że nie wszystkie nieskończoności są sobie równe.

TAUTOLOGIE

Zdania i kwantyfikatory

Tabele prawdy na żywo, prawa de Morgana, ∀ i ∃ na konkretnym zbiorze

¬(p∧q) ⇔ ¬p∨¬q
DIAGRAM VENNA

Zbiory

Suma, przecięcie, różnica i dopełnienie — z konkretnymi liczbami w każdym obszarze

A∪B, A∩B, A\B, A'
GRAF RELACJI

Relacje

Zbuduj własną relację i sprawdź na żywo: zwrotność, symetria, przechodniość

R ⊆ X × X
DOMINO

Indukcja matematyczna

Dowód wzoru na sumę przez podwojenie schodków do prostokąta

1+2+…+n = n(n+1)/2
CANTOR

Moc zbiorów

Dlaczego ℤ da się ponumerować, a zbiór ciągów binarnych — już nie

|ℕ| = |ℤ| < |{0,1}^ℕ|

Zdania i kwantyfikatory

Tabela prawdy sprawdza wartość logiczną formuły dla wszystkich możliwych wartości p i q (0=fałsz, 1=prawda). Jeśli wynik jest zawsze 1 — to tautologia (prawo logiczne).

Działania na zbiorach

U = {1,…,12}. A = liczby parzyste. B = liczby podzielne przez 3.

Relacje na zbiorze X={1,2,3,4}

Kliknij komórkę (i,j), żeby przełączyć, czy i R j. Wiersz = „od”, kolumna = „do”.

Zasada indukcji matematycznej

Jeśli (baza) zdanie jest prawdziwe dla n=1, oraz (krok) z prawdziwości dla n=k wynika prawdziwość dla n=k+1 — to zdanie jest prawdziwe dla wszystkich n≥1. Jak kostki domina: jeśli pierwsza przewraca się i każda przewraca następną, to przewrócą się wszystkie.
1+2+…+n = n(n+1)/2 — dowód „podwojenia schodków”

Moc zbiorów (przeliczalność)

Zbiór ℤ jest przeliczalny — da się go ustawić w ciąg i ponumerować liczbami naturalnymi. Dowód: jawna bijekcja f(n) = n/2 dla n parzystych, −(n+1)/2 dla n nieparzystych.

Przykład 1 — prawo de Morgana przez tabelę prawdy

Udowodnij, że ¬(p∧q) ⇔ ¬p∨¬q dla dowolnych zdań p, q.

1. Wypisujemy wszystkie 4 kombinacje wartości p,q i liczymy obie strony:
p=1,q=1: p∧q=1, ¬(p∧q)=0 | ¬p=0,¬q=0, ¬p∨¬q=0 → zgadza się
p=1,q=0: p∧q=0, ¬(p∧q)=1 | ¬p=0,¬q=1, ¬p∨¬q=1 → zgadza się
p=0,q=1: p∧q=0, ¬(p∧q)=1 | ¬p=1,¬q=0, ¬p∨¬q=1 → zgadza się
p=0,q=0: p∧q=0, ¬(p∧q)=1 | ¬p=1,¬q=1, ¬p∨¬q=1 → zgadza się
2. Kolumny ¬(p∧q) i ¬p∨¬q są identyczne we wszystkich 4 wierszach.
3. Zatem formuła ¬(p∧q) ⇔ (¬p∨¬q) jest tautologią — obie strony są zawsze równoważne. ∎

Przykład 2 — działania na konkretnych zbiorach

Dla A={1,2,3,4,5}, B={4,5,6,7} oblicz A∪B, A∩B, A\B oraz różnicę symetryczną A△B.

1. A∪B = {1,2,3,4,5,6,7} — wszystkie elementy z A lub z B (bez powtórzeń).
2. A∩B = {4,5} — elementy wspólne dla obu zbiorów.
3. A\B = {1,2,3} — elementy A, których nie ma w B.
4. A△B = (A∪B)\(A∩B) = {1,2,3,4,5,6,7}\{4,5} = {1,2,3,6,7}. Sprawdzenie: to samo co (A\B)∪(B\A) = {1,2,3}∪{6,7} = {1,2,3,6,7}. ✓

Przykład 3 — dowód indukcyjny: suma liczb nieparzystych

Udowodnij, że dla każdego n≥1: 1+3+5+…+(2n−1) = n².

1. Baza (n=1): lewa strona = 1, prawa strona = 1² = 1. Zgadza się.
2. Założenie indukcyjne: zakładamy, że dla pewnego k zachodzi 1+3+…+(2k−1) = k².
3. Krok indukcyjny (n=k+1): 1+3+…+(2k−1)+(2k+1) = k²+(2k+1) [z założenia] = (k+1)² [bo (k+1)²=k²+2k+1].
4. Teza zachodzi dla k+1, więc na mocy zasady indukcji matematycznej zachodzi dla wszystkich n≥1. ∎