Arytmetyka Peano (PA)
Operacje arytmetyki Peano:
1. Operacja następnika S: y = S(x), gdzie S(x) =df x + 1
2. Dodawanie ·: z = ·(x, y)
3. Mnożenie +: z = +(x, y)
Aksjomaty arytmetyki Peano
A1: ∀x [0 ≠ S(x)]
A2: ∀x ∀y [S(x) = S(y) ⇒ x = y]
A3: ∀x (0 + x = x)
A4: ∀x ∀y [S(x) + y = S(x + y)]
A5: ∀x (0 · x = 0)
A6: ∀x ∀y [S(x) · y = x · y + y]
A7: Schemat aksjomatu indukcji - dla dowolnej formuły φ(x) ze zmienną wolną x:
{φ(0) ∧ ∀x [φ(x) ⇒ φ(S(x))]} ⇒ ∀x φ(x)
Reguły wnioskowania dla identyczności
R1: ∀x x = x (zwrotność identyczności)
R2: ∀x ∀y (x = y ⇒ y = x) (symetryczność identyczności)
R3: ∀x ∀y ∀z [(x = y ∧ y = z) ⇒ x = z] (przechodniość identyczności)
Reguły kongruencji
R4: Dla dowolnego n-argumentowego symbolu funkcyjnego F:
∀x1 ... ∀xn ∀y1 ... ∀yn [(x1 = y1) ∧ ... ∧ (xn = yn) ⇒ F(x1, ... , xn) = F(y1, … , yn)]
R5: Dla dowolnego n-argumentowego predykatu P:
∀x1 ... ∀xn ∀y1 ... ∀yn [(x1 = y1) ∧ ... ∧ (xn = yn) ∧ P(x1, ... , xn) ⇒ P(y1, … , yn)]
R4 (a = b ∧ c = d) ⇒ a + c = b + d
R5 (a = b ∧ c = d ∧ a c) ⇒ b d
Gödel udowodnił, że PA jest niezupełna i nierozstrzygalna. Arytmetyki analogiczne do PA, pozbawione operacji + lub · są zupełne i rozstrzygalne.
Definicje rekurencyjne symboli funkcyjnych w arytmetyce Peano
Symbole pierwotne - S i 0
Definicja dodawania (+)
0 + t = t
S(x) + t = S(x + t)
Definicja mnożenia (·)
0 · t = 0
S(x) · t = x · t + t
Definicja potęgowania
t0 = 1
tS(x) = tx · 1
Definicja silni (!)
0! = 1
S(x)! = x! · S(x)
Przykład. Szukamy, czym jest t3. Z definicji rekurencyjnej t0 = 1, t1 = t0 · t = 1 · t = t, t2 = t1 · t = t · t, t3 = t2 · t = (t · t) · t = t · t · t.
Definicje te działają jak dodatkowe aksjomaty.
Definicja formalna definicji rekurencyjnej (definicji przez rekursję)
Niech g będzie funkcją k-argumentową g: ωk → ω z liczb naturalnych. Niech h będzie funkcją k+2-argumentową h: ωk+2 → ω. Definiujemy k+1-argumentową funkcję ƒ: ωk+1 → ω w następujący sposób:
1° ƒ(0, t1, ... , tk) = g(t1, ... , tk)
2° ƒ(S(x), t1, ... , tk) = h(x, t1, ... , tk, ƒ(x, t1, ... , tk))
Definicja rekurencyjna podaje algorytm znajdowania wyników działań.
(…)
… przez przypadki - niech świat będzie 2-elementowy:
φ(1) ∨ φ(2), φ(1) ⇒ ξ ∧ φ(2) ⇒ ξ || ξ
Poprawność reguły wnioskowania R'
a ∉ ξ
Przypuśćmy, że
1. ∃x φ(x),
2. ∀x [φ(x) ⇒ ξ],
3. ~ ξ
Twierdzimy, że ∀x ~ φ(x).
Dowód. Niech a ustalone. Chcemy pokazać, że ~ φ(a). Załóżmy niewprost, że φ(a). Z 2. otrzymujemy ξ. Sprzeczność z 3.
Mamy więc ~ ∃x φ(x) (z prawa De Morgana). Sprzeczność z 1.
Aksjomaty możemy traktować…
… odpowiedzi o praktycznej złożoności obliczeniowej.
Algorytm - przepis na obliczanie.
Chcemy sprawdzić, czy formuła rachunku zdań φ jest tautologią.
1. Wypisujemy wszystkie zmienne zdaniowe p1, ... , pn występujące w φ.
2. Wypisujemy wszystkie pozostałe podformuły β1, ... , βk formuły φ tak, aby wszystkie podformuły βi wystąpiły pomiędzy p1, ... , pn, β1, ... , βi - 1, dla i = 1, ... , k.
3. Konstruujemy…
… rośnie wykładniczo, ilość kolumn rośnie (liniowo?).
Wartości każdej funkcji wykładniczej przekraczają kiedyś wartości każdej funkcji wielomianowej.
Teza Edmondsa (1965) - problemy praktycznie obliczalne (realizowalne za pomocą algorytmów komputerowych) są to dokładnie problemy, dla których mamy algorytmy o wielomianowej złożoności obliczeniowej (PTIME) - istnieje stała c taka, że dla pytania rozmiaru n…
… fałszywy.
Skuteczną metodą zagwarantowania poprawności dowodu jest to, aby kolejne stwierdzenia wynikały z wcześniejszych na mocy poprawnych reguł wnioskowania.
Ważniejsze reguły wnioskowania dla kwantyfikatorów
1. Dictum de omni
∀x φ(x) || φ(t), gdzie x - zmienna typu T, t - wyrażenie nazwowe typu T.
Wywnioskowanie dowolnego przykładu ze zdania ogólnego.
→ - wnioskowanie: reguła wyciągania wniosków…
... zobacz całą notatkę
Komentarze użytkowników (0)