1 - Jazyk a sémantika predikátové logiky (termy, formule, realizace jazyka, pravdivost formulí)

Question 1

Axiomy výrokové logiky

Answer 1

1. A→(B→A)
2. (A→(B→C))→((A→B)→(A→C))
3. (¬B→¬A)→(A→B)

Question 2

Modus Ponens

Answer 2

Jestliže platí formule A a formule A→B, tak také platí B.

Question 3

Postova věta o úplnosti

Answer 3

Dokazatelné formule jsou tautologiemi (⊨A⇔⊢A).

Question 4

Gramatika - Termy, formule

Answer 4

• 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))) )

Question 5

Realizace (interpretace) jazyka L

Answer 5

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 >=,

Question 6

Formule φ je splněna v realizaci M když?

Formule φ je logicky platná (tautologie) v realizaci M když?

Formule jsou logicky ekvivalentní

Answer 6

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 ∀.

Question 7

Substituovatelná proměnná

Answer 7

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)).

Question 8

Tautologie, logicky ekvivalentní formule

Answer 8

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í.