104306

O! = 1

S(x)l = x! • S(x)

Przykład Szukamy, czym jest t³. Z definicji rekurencyjnej t° = 1, t* = t° • t = 1 • t = t, t² = t* • t

= t • t, t³ = t² • t = (t • t) • t = t • t • L

Definicje te działają jak dodatkowe aksjomaty.

Definicja formalna definicji rekurencyjnej (definicji przez rekursję)

Niech g będzie funkcją k-argumentową g:(o^k-wz liczb naturalnych. Niech h będzie funkcją k+2-argumentową h (o^k’² — co. Definiujemy k+1-argumentową funkcję f: <o^k’¹ — to w następujący sposób:

1° f(0, t,,..., tk) = ^(ti,..., tk)

2° /(S(x), t,,..., tk) = h(x, t_b ..., tk, f (x, t_b ..., tk))

Definicja rekurencyjna podaje algorytm znajdowania wyników działań.

Oczywistość logiczna Teza: tp ^ ip

Dowód. Załóżmy, że tp. (...) Zatem iJj. □ tp = tp_b tp_b ..., tp.. =

Przejście od tp, do tpi.i dla i = 1,..., n -1 jest oczywiste logicznie.

Wamilki oczywistości:

1.    Musi zachodzić wynikanie logiczne iji z cp.

2.    Musi istnieć ogólny algorytm (ten sam dla wszystkich inferencji) dający tylko poprawne odpowiedzi o praktycznej złożoności obliczeniowej.

Algorytm - przepis na obliczanie.

Chcemy sprawdzić, czy formuła rachunku zdań <p jest tautologią.

1.    Wypisujemy wszystkie zmienne zdaniowe p_b ..., p„ występujące w <p.

2.    Wypisujemy wszystkie pozostałe podformuły p_łt ..., Pk formuły tp tak, aby wszystkie podformuły pi wystąpiły pomiędzy p_b ..., pn, Pi,..., P, _b dla i = 1,..., k.

3.    Konstruujemy tabelę prawdziwościową.

Pierwsze n kolumn wypełniamy wszystkimi możliwymi rozkładami wartości logicznych dla zmiennych p_b ..., p^. Następne kolumny wypełniamy wartościami logicznymi zgodnie z tabelami prawdziwościowymi dla spójników.

Jeśli w ostatniej kolumnie są same 1 - „TAK”, w przeciwnym przypadku - „NIE”.

Formuła spełniał na - formuła niesprzeczna

Skonstruowana tabela ma 2° wierszy. Ilość wierszy 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ą algoiytmó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 obliczanie skończy się nie później niż po n^c krokach dla dowolnego n.

Czy istnieje algorytm PTIME dla problemu tautologiczności rachunku zdań?