1 - Jazyk a sémantika predikátové logiky (termy, formule, realizace jazyka, pravdivost formulí) Flashcards
Axiomy výrokové logiky
- A→(B→A)
- (A→(B→C))→((A→B)→(A→C))
- (¬B→¬A)→(A→B)
Modus Ponens
Jestliže platí formule A a formule A→B, tak také platí B.
Postova věta o úplnosti
Dokazatelné formule jsou tautologiemi (⊨A⇔⊢A).
Gramatika - Termy, formule
- Termy jsou tvrzení sestavená pomocí proměnných, konstant a funkčních symbolů. (např. x.(y + z))
- Atomické formule jsou tvrzení sestavená pomocí termů a predikátových symbolů. (např. x.(y + z) = (x.y) + (x.z))
- Formule jsou tvrzení sestavená pomocí atomických formulí (termy + predikátové symboly), logických spojek a kvantifikátorů. (např. ∀x(x≠→∃y(x=S(y))) )
Realizace (interpretace) jazyka L
je algebraická struktura \ M, složená z:
• univerzum M - neprázdná množina objektů (tj. množina (obor) hodnot)
○ Například univerzum M může být množina všech nezáporných čísel {0,1,2,3,…}
• funkční zobrazení f_M:M^n→M (tj. definice funkcí) pro každý symbol f četnosti n ○ Prostě n-tici se přiřazuje právě jedno individuum: M×…×M do M ○ Je-li n=0, pak se jedná o nulární funkční symbol, tedy o individuovou konstantu, které je přiřazen prvek univerza - individuum. Napříkad 1,2, true, false, … ○ Je-li n=1, pak se jedná o unární funkční symbol, kterému je přiřazena funkce o jednom argumentu (např. nad množinou čísel x^2, x1, nad množinou individuí otec (x), matka (x), atd.) ○ Je-li n=2, pak se jedná o binární funkční symbol, kterému je přiřazena binární funkce se dvěma argumenty (např. nad množinou čísel x+y, x⋅y, atd.) • predikátová relace p_M⊆M^n (tj. definice predikátových relací) pro každý predikátový symbol p četnosti n (kromě rovnosti) ○ Tedy jedná se o zobrazení:M×…×M do {0,1} ○ Je-li n=0, pak se jedná o nulární predikátový symbol, kterému je přiřazena hodnota 1 nebo 0 (pravda, nepravda) tak, jak to již známe z výrokové logiky. ○ Je-li n=1, pak se jedná o unární predikátový symbol, kterému je přiřazena podmnožina univerza M. (Vlastnosti tedy v predikátové logice vyjadřujeme jako podmnožiny univerza.) Je-li n=2, pak se jedná o binární predikátový symbol, kterému je přiřazena binární relace nad univerzem (např. relace >=,
Formule φ je splněna v realizaci M když?
Formule φ je logicky platná (tautologie) v realizaci M když?
Formule jsou logicky ekvivalentní
Formule φ je splněna v realizaci M, pokud je pravdivá při každém ohodnocení e. Píšeme M⊨φ. Je-li φ uzavřená, pak říkáme, že φ je pravdivá v M.
Formule φ je logicky platná (tautologie), pokud pro každou realizaci M jazyka L platí M⊨φ. Píšeme ⊨φ.
Formule φ a ψ (psi) jsou logicky ekvivalentní, pokud při libovolné realizaci M a libovolném ohodnocení e je M⊨φ[e] právě když M⊨ψ[e]. (φ≡ψ je logicky platná formule)
aneb. Logicky ekvivalentní formule mají stejné pravdivostní ohodnocení při libovolném ohodnocení jejich částí.
Každá formule φ je ekvivalentní nějaké formuli ψ, ve které se nevyskytuje jeden kvantifikátor, popř. takové, ve které se vyskytují pouze spojky ¬ a → a kvantifikátor ∀.
Substituovatelná proměnná
substituovatelná proměnná x je taková, že žádný její volný výskyt neleží v oboru kvantifikátoru proměnné y, která je obsažená v substituovaném termu. Např. term S(y) není substituovatelný za term x ve formuli x→∃y(x=S(y)).
Tautologie, logicky ekvivalentní formule
Tautologie jsou formule, které jsou pravdivé při libovolném ohodnocení, píšeme ⊨, např.:
• zákon vyloučení třetího: A∨¬A
• zákon dvojí negace: ¬¬A≡A
• zákon vyloučení sporu: ¬(A∧¬A)
Logicky ekvivalentní formule mají stejné pravdivostní ohodnocení při libovolném ohodnocení jejich částí.