KRZ - klasyczny rachunek zdan !

Syntaktyka

S - najmniejszy w sensie inkluzji zbiór spełniający

następujące warunki:

i) ဢp჎V p჎S

ii) ၡ჎S პ იၡ჎S

iii) ၡ, ၢ჎S პ ၡლၢ, ၡკၢ, ၡႮၢ ჎S

Semantyka

Semantyką KRZ jest dwuwartościowa algebra Boole`a

Jeśli p jest zmienną zdaniową (formułą atomową), to v(p) jest interpretacją formuły p

(wartością logiczną formuły p w interpretacji v).

Implikacja i równoważność semantyczna

Wyrażenie ၡႫၢ jest formułą KRZ, która może być ale nie musi być tautologią

Wyrażenie ၡმၢ jest stwierdzeniem o formułach ၡ, ၢ mówiącym, że są one logicznie

równoważne, tzn, że formuła ၡႫၢ jest tautologią

Wyrażenie ၡპၢ oznacza, że ၡ implikuje logicznie ၢ, tzn. ၡპၢ wtedy i tylko

wtedy, gdy ၡႮၢ jest tautologią.

Tautologia

Definicja

Formułę ၡ nazywamy tautologią (twierdzeniem) wttw ဢv h^v(ၡ)=1 (dla każdego wartościowania wartość logiczna formuły równa jest 1)

DefinicjeFormuła ၡ jest spełniona przy interpretacji v wttw h^v(ၡ)=1 (v spełnia ၡ; v jest modelem dla ၡ)

Aksjomaty i teoria

Niech X, będzie zbiorem formuł, zbiór T(X)={ၡ: X |= ၡ} nazywamy teorią zbioru formuł X, a formuły należące do zbioru X nazywamy aksjomatami

Metoda zero-jedynkowa

polega na rozważeniu wszystkich możliwych przypadków wartości zdań składowych formuły i policzeniu w każdym przypadku wartości formuły.

Metoda kosztowna obliczeniowo ze względu na liczbę formuł składowych

Postacie normalne formuł

Atomem (formułą atomową) nazywać będziemy zmienną zdaniową (zdanie)

Atom nazywamy również literałem pozytywnym

Negację atomu nazywamy literałem negatywnym

Literały ၡ i იၡ nazywamy komplementarnymi

Definicja

Formuła ၡ jest w koniunkcyjnej postaci normalnej - CNF wtw jest ona postaci:ၡ=ၡ₁კၡ₂კ..კၡ_n gdzie każde ၡ_i jest alternatywą literałów. Koniunkcją alternatyw (składniami każdej alternatywy muszą być literały)

Definicja

Formuła ၡ jest w alternatywnej postaci normalnej - DNF wtw jest ona postaci:ၡ=ၡ=ၡ₁ლၡ₂ლ..ლၡ_n gdzie każde ၡ_i jest koniunkcją literałów . Alternatywą koniunkcji (składniami każdej koniunkcji muszą być literały)

ADT - dla KRZ

Twierdzenie

Dla dowolnej formuły ၡ istnieją formuły ၡ` i ၡ” równoważne ၡ, będące

(odpowiednio) w postaciach CNF i DNF

Jeśli formuła jest w postaci CNF, to jest tautologią wttw każda z alternatyw zawiera

parę literałów komplementarnych

Jeśli formuła jest w postaci DNF, to jest kontrtautologią wttw każda z koniunkcji

zawiera parę literałów komplementarnych

Przykłady tautologii (praw) KRZ

Przykłady tautologii

1. prawa przemienności (კ, ლ )

2. prawa łączności

3. prawa rozdzielności

4. iv) ი(pლq) მ (იpკიq) (pლq) მ ი(იpკიq) prawa De Morgana

5. v) dla iloczynu analogicznie

6. vi) pႮq მ (იqႮ იp) prawo kontrapozycji

7. vii) pႮq მ [(p კ იq)Ⴎ c] reductio ad absurdum (c zdanie sprzeczne)

8. viii) pკp მ p pლp მ p prawa idempotentności

9. ix) [(pკq)Ⴎr ] მ [pႮ(qႮr)] prawo eksportacji

10. x) (p ლ იp) prawo wyłączonego środka

System formalny tzw. (system dowodzenia)

Wnioskowanie:

Proces polegający na uznaniu pewnych zdań zwanych wnioskami na podstawie innych zdań zwanych przesłankami.

Definicja

Dwójkę <R, X> w której R jest zbiorem formuł wnioskowania,X zbiorem formuł (aksjomatów) nazywamy systemem formalnym.

Reguła wnioskowania - zapis

Znaczenie - jeśli przesłanki są prawdziwe, to konkluzja też jest prawdziwa.

UWAGA: KRZ podaje się dwa systemy dowodzenia Hilbertowski i Gentzenowski. Systemy te mają różną liczbę aksjomatów i różne reguły wnioskowania .

Jeżeli formuła zbudowana ze zmiennych zdaniowych p₁,..., p_n jest tautologią, to wstawiając na miejsce zmiennych dowolne zdania otrzymamy zdanie prawdziwe.

Reguła podstawiania

Jeśli na miejsce zmiennych wstawimy dowolne formuły (schematy), to otrzymana formuła dalej będzie tautologią.

Przykłady systemów formalnych system hilbertowski H

System składa się z trzech aksjomatów i jednej reguły dowodzenia (modus ponens)

W celu ułatwienia wnioskowania wprowadza się wiele reguł pochodnych(które oczywiście najpierw się udowadnia) jedną z nich jest reguła dedukcji Inne reguły to reguła kontrapozycji, przechodniości, podwójnego zaprzeczenia itd.

Twierdzenie

KRZ jest rozstrzygalny tzn. można obliczyć wartość logiczną każdej formuły .

---