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

1
Q

Axiomy výrokové logiky

A
  1. A→(B→A)
  2. (A→(B→C))→((A→B)→(A→C))
  3. (¬B→¬A)→(A→B)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Modus Ponens

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Postova věta o úplnosti

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Gramatika - Termy, formule

A
  • 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))) )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Realizace (interpretace) jazyka L

A

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 >=,
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

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

Formule jsou logicky ekvivalentní

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Substituovatelná proměnná

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Tautologie, logicky ekvivalentní formule

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly