03a Jazyk PL

  1. Jaký je rozdíl mezi PL 1.řádu a PL 2.řádu? + Vyjmenuj hlavní vlastnosti PL
    • - PL1 umožňuje kvantifikaci pouze přes individua
    • - v minulosti i současnosti rozmanité názvy – k historickým patří „functional calculus“, „calculus of propostional functions“, k soudobým patří „predicate logic“, „predicate calculus“, „first-order logic“, ovšem v češtině se užívá jen „predikátová logika“, popř. „predikátový kalkul“, „predikátový počet“.
    • - PL1 je poměrně dosti expresivní logický aparát. z praktických důvodů je často obohacována zejména o znak identity („=“), popř. i symboly funkcí (např. „+“).
    • - PL1= bývá někdy chápána jako ‚kanonický jazyk vědy‘.
    • - Kromě PL1 existuje i PL druhého řádu, jež umožňuje kvantifikaci přes množiny/relace, obsahuje totiž proměnné predikátové symboly a příslušné kvantifikátory 
    • - Klasická PL prvního i vyšších řádů je kompozicionální – sémantická hodnota složeného výrazu je funkcí sémantických hodnot podvýrazů daného výrazu, a je též dvouhodnotová – každá formule je pravdivá, nebo nepravdivá.
    • - Podobně jako ve VL je definice jak syntaxe, tak sémantiky jazyka PL rekurzivní. Na základě konečného množství specifikací umožňuje o každém výrazu ověřit (vyhledat), zda je výrazem PL a co je jeho sémantickou hodnotou.
  2. Co tvoří syntax PL?
    • Abeceda
    • Gramatika
    • Podformule
    • Volnost proměnných

    • - Jazyk PL lze zadat různými abecedami a zčásti i jinými gramatikami
    • - Možná poněkud překvapivě nemají v gramatice vyhrazeno svébytné místo predikátové symboly, ty v ní vystupují jen v kontextu formulí.
  3. Co tvoří abecedu PL?
    • Abeceda:
    • i. individuové proměnné x, y, z, …, x1, y1, z1, …
    • ii. individuové konstanty a1, …, an, b1, …, bn, …
    • iii. predikátové symboly (k značí aritu predikátu; 1 ≤ k) Pk, Qk, Rk, …, P1k,P2k, …
    • iv. výrokové spojky (jakožto symboly) ¬, ∧, ∨, →, ↔, …
    • v. kvantifikátory ∀ a ∃
    • vi. pomocné symboly (,), příp. [, ].

    • - Všechny výrazy uváděné v abecedě jsou znaky. Například proměnná x je znak, konstanta c rovněž.
    • - Zvláště individuových proměnných se obvykle uvažuje nekonečný počet
  4. Co to jsou funkční termy?
    • Někdy jsou v jazyce (a tedy už v abecedě) zaváděny funkční termy (či funkční symboly) fk, gk, …
    • - ty mají rovněž aritu (např. „+“ má aritu 2;
    • - namísto např. „+(2,3)“ se píše všeobecně známé „2+3“).

    Pokud jsou zaváděny funkční termy, tak se do gramatiky přidává, že je-li fk k-ární funkční term a t1,..., tk jsou termy, tak fk(t1,...,tk) je term (kde „k“ je arita); tyto termy jsou tedy složené.
  5. Df monadické + binární predikáty
    predikáty arity 1 jsou zvány monadické predikáty, predikáty arity 2 jsou binární (vzácně: dyadické) predikáty,..., predikáty arity n jsou n-ární (tedy polyadické) predikáty.
  6. Df kvantifikátory
    • Kvantifikujících výrazů, tedy kvantifikátorů či zcela obecně tzv. determinátorů, je v jazyce přítomna celá řada- „některý“, „nanejvýše jedno“, „právě dva“, atd. Mnohé tyto kvantifikátory jsou vyjádřitelné prostředky PL, a to dokonce jen s pomocí dvou nejzákladnějších (klasických) kvantifikátorů ∀ a ∃.
    • je obecný kvantifikátor; odpovídá jazykovým kvantifikátorům jako například „všichni“ a „každý“.
    • -někdy nazývaný univerzální či velký, je značen podle prvního písmene německého slova "Alle"
    • - někdy je značen pomocí "(x)", "Π", ev. "Λ"
    • je existenční kvantifikátor; odpovídá jazykovým kvantifikátorům jako např. „někteří“ a „někdo“ či „existuje alespoň jeden“.
    • - někdy nazývaný částečný nebo malý, je značen podle prvního písmene německého slova "exists"
    • - někdy je značen pomocí "(Ex)", "Σ", ev. "V"
    • Formule jako „∀x D(x)“ a „∃x D(x)“ chápeme jako formalizace výroků „Vše je dívka“ a „Existují dívky“.
    • Image Upload 1
  7. v případě (nekonečného) univerza je ∀xP(x) ekvivalentní ..., ∃xP(x) je zase ekvivalentní ...
    • ... nekonečné konjunkci P(a1) ∧ ... ∧ P(an)
    • ... nekonečné disjunkci P(a1) ∨ ... ∨ P(an)
  8. Počet kvantifikátorů lze zmenšit kvůli vzájemné definovatelnosti kvantifikátorů, totiž
    ∀x A =df ... nebo ∃x A =df ...
    Někdy se o těchto dvou kvantifikátorech mluví jako o klasických kvantifikátorech.
    • ∀x A =df ¬∃x ¬A
    • ∃x A =df ¬∀x ¬A
  9. Někdy se však setkáme i s omezenými kvantifikátory („restricted quantifiers“), jmenovitě „(∀x∊A)“ a „(∃x∊A)“, kde A je podmnožinou U; celá formule se pak píše třeba „(∀x∈A)¬B“. Omezené kvantifikátory jsou ovšem definovatelné následovně:
    Image Upload 2
  10. Na rozdíl od VL, jež disponovala jen VL-formulemi, gramatika PL odlišuje formule PL – níže jen „formule“ – a termy. Jaký je mezi nimi rozdíl a co to termy jsou?
    Zatímco formule sémanticky vzato označují pravdivostní hodnoty, termy označují individua.

    • Termy
    • i. Každá individuová proměnná je term.
    • ii. Každá individuová konstanta je term.
    • iii. Nic jiného není term.
  11. Df formule PL
    • i. Jestliže Pk je k-místný predikátový symbol a jestliže t1,..., tk jsou termy, pak Pk(t1,...,tk) je (správně utvořená) formule.
    • ii. Jestliže A a B jsou formule, pak ¬A, (A∗B) (kde ∗ je ∧, ∨, →, nebo ↔) jsou formule.
    • iii. Jestliže x je proměnná a A je formule, pak ∃x A a ∀x A jsou formule.
    • iv. Nic jiného není formule.
  12. Co tvoří gramatiku PL?
    termy, formule

    - v gramatice nemají vyhrazeno svébytné místo predikátové symboly, ty v ní vystupují jen v kontextu formulí
  13. co to jsou atomické a složené formule formule?
    • atomické formule splňují definici formulí:
    • i. Jestliže Pk je k-místný predikátový symbol a jestliže t1,..., tk jsou termy, pak Pk(t1,...,tk) je (správně utvořená) formule.

    • složené formule splňují definici formulí:
    • ii. Jestliže A a B jsou formule, pak ¬A, (A∗B) (kde ∗ je ∧, ∨, →, nebo ↔) jsou formule.
    • iii. Jestliže x je proměnná a A je formule, pak ∃x A a ∀x A jsou formule.
  14. df duální formule
    • pouze u formulí, jejichž operátory jsou jen ∀, ∃, ¬,∨, ∧.
    • Formuli Aδ, která vznikne systematickou záměnou ∀ a ∃, ∧ a ∨, nazýváme duální formulí k formuli A. Formule A a Aδ jsou k sobě vzájemně duální.
    • Image Upload 3
  15. Platí, že ¬A↔Aδ právě tehdy, když ...
    • všechny atomické podformule jsou v právě jedné z těchto formulí negovány.
    • Například jsou takto ekvivalentní ¬∀x P(x)a ∃x ¬P(x).
  16. Df podformule
    • i. Každá formule A je (tzv. nevlastní) podformulí A.
    • ii. Je-li formule A tvaru ¬B, tak B je (tzv. vlastní) podformulí A.
    • iii. Je-li formule A tvaru (B∗C), tak B a C jsou (tzv. vlastními) podformulemi A.
    • iv. Je-li formule A tvaru ∃x B a ∀x B, tak B je (tzv. vlastní) podformulí A.
    • v. Nic jiného není podformulí formule A.
  17. v jazyce s funkčními termy lze definovat podtermy: ...
    je-li f(t1, ..., tk) term, tak t1, ..., tk jsou podtermy f(t1, ..., tk)
  18. df složitost formule
    = číslo, jež je počtem výrokových spojek a kvantifikátorů.
  19. df řád formule
    • (angl. „rank“)
    • = číslo úměrné množství zanořených kvantifikátorů
    • i. formule bez kvantifikátoru má řád 0,
    • ii. řád formule složené pomocí výrokových spojek je roven nejvyššímu řádu formulí spojených těmito spojkami,
    • iii. řád formule ∃x B nebo ∀x B je roven řádu B plus 1; například P(a)∧∃y ∀x R(x,y) má řád 2.
  20. Popiš výstavbu formulí a její čtení
    • O výstavbě formulí můžeme rovněž uvažovat v tom smyslu, že tu jsou tyto formule vytvářející posloupnosti.
    • Ty získáme, když čteme odspodu (od listů) směrem ke kořeni syntaktické stromy (pod)formulí, poněvadž v kořeni stromu je sama formule, v uzlech větví jsou složené podformule a listy jsou tvořeny atomickými formulemi

    Image Upload 4

    • a totéž úsporněji
    • Image Upload 5

    V souladu s výstavbou formulí podle gramatiky se hovoří o tom, že nějaká definice či nějaký důkaz jsou vystavěny indukcí podle složitosti formule, což je pojem, který zužitkovává pojem podformule.
  21. Kdy je výskyt proměnné x volný a kdy vázaný?
    • i. Výskyt proměnné x je volný ve formuli ¬A právě tehdy, když je volný v A. Výskyt proměnné x je volný ve formuli (A∗B) právě tehdy, když je volný v A nebo v B.
    • ii. Výskyt proměnné x je volný ve formuli tvaru ∃y B a ∀y B právě tehdy, když je volný v B a proměnná x je odlišná od proměnné y.
    • iii. Výskyt proměnné x je vázaný ve formuli tvaru ∃y B a ∀y B právě tehdy, když je volný v B a zároveň je proměnná x totožná s proměnnou y.

    • Pro ilustraci, každý první výskyt x v následujících formulích je volný- P(x), ∃y P(x), P(x)→∃x P(x).
    • Na druhou stranu výskyt x v ∃x P(x) je vázaný; proto je vázaný poslední výskyt x v P(x)→∃x P(x).
    • Ne příliš často uváděná podmínka iii. nám ukazuje, že ten výskyt x, který je vázaný v ∃x P(x) je výskyt x v její podformuli P(x). Zda je výskyt x vyskytující se bezprostředně za ∃ volný nebo vázaný, definice nijak nestanovuje
  22. Někdy je v diskusi dostatečné anebo žádoucí abstrahovat od volnosti či vázanosti výskytu proměnné a stručně se vyjadřovat jen k volnosti anebo vázanosti proměnné:
    Proměnná x je volná ...
    Proměnná x je vázaná ...
    • i. Proměnná x je volná ve formuli A právě tehdy, když x má v A alespoň jeden výskyt volný.
    • ii. Proměnná x je vázaná v A právě tehdy, když jsou všechny výskyty x v A vázané.
    • (O volných proměnných se kdysi mluvilo jako o skutečných proměnných, kdežto o vázaných proměnných jako o fiktivních či zdánlivých proměnných.)
  23. co to jsou otevřené a uzavřené formule?
    • užíváno analogicky k volnosti a vázanosti proměnných
    • i. Formule A je uzavřená právě tehdy, když jsou v A všechny proměnné vázány.
    • ii. Formule A je otevřená právě tehdy, když je v A alespoň jeden výskyt nějaké proměnné volný.
    • Uzavřené formule jsou někdy v literatuře nazývány sentence.
    • V prostředí matematické logiky se pak setkáváme s (univerzálními) uzávěry formule A (angl. „closure“), což jsou formule tvaru ∀x1∀x2...∀xn A, kde na pořadí kvantifikátorů vážících volné proměnné x1, x2,..., xn formule A nezáleží, neboť všechny uzávěry A (jež se tedy liší právě jen pořadím kvantifikátorů vázajících proměnné) jsou ekvivalentní.
    • Uvědomme si tedy, že formule jako například ∃x (P(x)∧Q(x)) a ∃xP(x)∧Q(x) se závažným způsobem liší.
    • V první formuli jsou oba výskyty x vázány existenčním kvantifikátorem. Druhá formule je však konjunkcí dvou podformulí, přičemž pouze v druhé z nich, totiž v Q(x), má x volný výskyt. První formule je tedy uzavřená, kdežto druhá otevřená (bez ohledu na to, že obsahuje uzavřenou podformuli).
    • To, které výskyty proměnných jsou daným kvantifikátorem vázány, ukazuje dosah kvantifikátoru (angl. „scope“). Říkáme, že nějaká proměnná, přesněji její výskyt, je či není v dosahu daného kvantifkátoru, což znamená, že je tímto kvantifkátorem vázána. (Někdy bývá definováno, že dosahem kvantifkátoru jako ∃ ve formuli ∃x A je A.) Například poslední výskyt x v ∃x (P(x)∧Q(x)) je v dosahu ∃; ve formuli ∃x P(x)∧Q(x) je však poslední výskyt x mimo dosah ∃.
    • V následujícím příkladu jsou všechny výskyty x v ∃x (P(x)∧∃y Q(x)) vázány vepředu stojícím kvantifikátorem ∃, druhý kvantifikátor ∃ ovšem neváže žádný výskyt nějaké proměnné.
    • Vázání výskytů proměnných má tedy dopad na možnost korektního přejmenování proměnných a obecněji dosazování termů za proměnnou.
  24. df Substituovatelnost termu za proměnnou
    Term t je substituovatelný za proměnnou x ve formuli A právě tehdy, když term t je individuová konstanta anebo individuová proměnná taková, že po dosazení do formule A není v dosahu žádného kvantifikátoru, který váže proměnnou x. Značíme A[t/x].

Author
iren
ID
354840
Card Set
03a Jazyk PL
Description
predikatova logika
Updated