18 PL druheho radu

  1. V PL2 jsou na rozdíl od PL1 povoleny i ... proměnné.
    • predikátové (např. znaky M, N, O, R, S)
    • - jejich hodnotami jsou nějaké množiny, jmenovitě podmnožiny univerza nebo podmnožiny kartézského součinu univerza (tj. relace).
    • - Navíc tyto predikátové proměnné mohou být kvantifikovány
  2. df Leibnizoův zákon identity nerozlišitelných entit
    - kvantifikace predikátové proměnné v PL2

    • ∀x∀y (x=y) ↔ ∀P (P(x)↔P(y)),
    • = pro všechna individua x a y platí, že x a y jsou identická právě tehdy, když mají všechny vlastnosti stejné (P je zde proměnná pro vlastnosti).
  3. Předmětem PL2 jsou zejména vlastnosti ....
    binárních relací (tj. množiny prvků)

    • Jak už bylo naznačeno, v našich zápisech jsou znaky M, N, O, R, S proměnné pro množiny/třídy či relace. (Jsou to objektové proměnné, nikoli metajazykové proměnné zastupující predikátové symboly.)
    • V našich definicích se proměnné jako např. M (či R) vyskytují ve formulích po obou stranách definičního znaku „=df“ volně; předpokládá se přitom, že celá definice je z objektového hlediska formulí tvaru ekvivalence (kdy „=df“ zastupuje „↔“), jež je uzavřena příslušným obecným kvantifikátorem  ∀M (či ∀R).
  4. co je to logika vyšších řádů?
    • Kromě logiky druhého řádu se někdy hovoří o logice vyšších řádů (než 2), někdy se tím míní všech řádů včetně řádu 2.
    • Pod logikou vyššího řádů je tedy myšlena logika umožňující kvantifikaci přes třídy tříd (množiny množin), resp. logika umožňující kvantifikovat přes entity jakéhokoli řádu.
    • Obory proměnných jsou přitom omezovány na entity určitého druhu, na tzv. sorty (sorta individuí, sorta tříd individuí, sorta tříd tříd individuí, atd.)
  5. srovnej notační prostředky jazyka PL a jazyka teorie množin:
    ¬ ∧ ∨ → ↔
    Image Upload 1

    Vzhledová podobnost operátorů daných dvou jazyků bude vyšší, když si připomeneme, že „MC“ bývá mnohdy značeno např. „–M“, a dále že „→“ a „↔“ bývají značeny i „⊃“ a „☰“.
  6. co je to logika tříd?
    • V logice se, zčásti z historických důvodů, množinám říká třídy (angl. „classes“).
    • Problematika ukazovaná v této sekci pak bývá někdy nazývána logika tříd. V jistém smyslu se nejedná o nic jiného než o překlad jazyka teorie množin, a v ní uváděných poznatků, do jazyka PL.
    • Například si ukážeme, že „M∩N“ lze prostředky PL vyjádřit s pomocí „(M(x)∧N(x))“. Z jiného úhlu pohledu, operátor ∩ se dá definovat (proto níže „=df“) s  pomocí „(M(x)∧N(x))“.
    • Všimněme si, že „M∩N“ je infixním zápisem, prefi xní „∩(M,N)“ se neužívá. Připomeňme si ještě, že M, N, O jsou libovolné podmnožiny U.
  7. Jak lze interpretovat zápis jako (M∩N)(x)?
    • (M∩N)je nějaká množina O a my proto vlastně zapisujeme, že x patří do O.
    • (Při užití lambda-notace se těmto komplikacím můžeme vyhnout díky λ-operátoru, protože můžeme psát jednoduše např. ∅ =df λx (M(x)∧¬M(x)); v  PL se naproti tomu vždy musí po  stranách „=df“ vyskytovat formule, např. „∅(x) =df
    • (M(x)∧¬M(x))“.)
  8. Principy stavby tříd (definice třídových operátorů) - vyjmenuj
    Image Upload 2
  9. Principy stavby tříd (defi nice třídových operátorů) - definuj
    Image Upload 3
    Image Upload 4
  10. vyjmenuj základní zákony pro operace se třídami vyjadřující rovnost mezi množinami
    • operace se třídami (= je proto rovnost mezi třídami), čemuž se někdy říká algebra tříd, v logice pak obvykle kalkul tříd.
    • Image Upload 5
  11. Vyjmenuj další zákony tříd (mimo rovnosti mezi množinami)
    • zákon reflexivity
    • zákon (slabé) antisymetrie
    • zákon tranzitivity
  12. df zákon dvojitého komplementu
    (MC)C = M
  13. df zákony komutativity
    • M ∩ N = N ∩ M
    • M ∪ N = N ∪ M
  14. df zákony asociativity
    • (M ∩ N) ∩ O = M ∩ (N ∩ O)
    • (M ∪ N) ∪ O = M ∪ (N ∪ O)
  15. df zákony distributivity
    • M ∩ (N ∪ O) = (M ∩ N) ∪ (M ∩ O)
    • M ∪ (N ∩ O) = (M ∪ N) ∩ (M ∪ O)
  16. df zákony idempotence
    • M ∩ M = M
    • M ∪ M = M
  17. df De Morganovy zákony tříd
    • M ∩ N = (MC ∪ NC)C
    • M ∪ N = (MC ∩ NC)C
  18. M ∩ ∅ = ...
    M ∪ ∅ = ...
    M ∩ U = ...
    M ∪ U = ...
    • M ∩ ∅ = ∅
    • M ∪ ∅ = M
    • M ∩ U = M
    • M ∪ U = U
  19. df zákon reflexivity
    ∀M(M ⊆ M)
  20. df zákon (slabé) antisymetrie
    ∀M∀N((M ⊂ N) ∧ (N ⊂ M) → (M = N))
  21. df zákon tranzitivity
    ∀M∀N∀O((M ⊂ N) ∧ (N ⊂ O)) → (M ⊂ O)
  22. v teorii tříd lze ověřovat platnost kategorických sylogismů (nejen díky Boolově způsobu formalizace). Například důkaz sylogismu druhu barbara, jehož premisy a závěr jsou formalizovatelné ∀x(M ⊆ P)(x), ∀x(S ⊆ M)(x) ∴ ∀x(S ⊆ P)(x) využívá kromě univerzální instanciace kterého zákonu?
    tranzitivity S ⊆ M ⊆ P
  23. df n-ární relace
    n-ární relace nad univerzem U jsou podmnožinami kartézského součinu Un. Protože jsou relace množiny, většina principů jejich stavby je shodná s principy stavby obyčejných množin.

    • V  našem zápisu relací neužíváme mnohdy používanou infixní notaci (např. „xRy“), používáme notaci výše zavedenou v gramatice PL1 pro binární predikátové symboly. Přidáváme druhořádové proměnné pro binární relace, „R“ a  „S“. Z  daných kontextů jako např. „∅(x,y)“, je zřejmé, že „∅“ označuje prázdnou množinou dvojic.
    • V principech stavby se relace liší od obyčejných množin jen tím, že navíc existují inverzní relace a dále kompozice (skládání) relací.
  24. jaké znáš Principy stavby binárních relací (definice relačních operátorů)? vyjmenuj
    Image Upload 6
  25. df Doplněk relace
    RC2(x, y) =df ¬R(x, y)
  26. df Inverzní relace
    R−1(x, y) =df R(y, x)

    • Inverzní relace je někdy zvána konverzní relace.
    • Příkladem k sobě inverzních relací je ‚být potomkem (někoho)‘ –‚být předkem (někoho)‘ nebo ‚být rodič (někoho)‘–‚být dítě (někoho)‘.
  27. df Prázdná relace
    ∅(x, y) =df R(x, y) ∧ ¬R(x, y)

    Příkladem prázdné relace je ‚nebýt identický se sebou‘ (pro žádné x totiž neplatí x≠x).
  28. df Univerzální relace
    U2(x, y) =df R(x, y) ∨ ¬R(x, y)

    Příkladem univerzální relace je ‚být v nějakém vztahu k (něčemu)‘ (každá entita je alespoň v nějakém vztahu k něčemu).
  29. df Inkluze relací
    R⊆S(x, y) =df R(x, y) → S(x, y)

    Příkladem relace v inkluzi je ‚být bratr (někoho)‘ vzhledem k ‚být příbuzný (někoho)‘.
  30. df Rovnost relací
    R=S(x, y) =df R(x, y) ↔ S(x, y)
  31. df Průnik relací
    R∩S(x, y) =df R(x, y) ∧ S(x, y)
  32. df Sjednocení relací
    R∪S(x, y) =df R(x, y) ∨ S(x, y)
  33. df Kompozice relací
    R◦S(x, y) =df ∃z(R(x, z) ∧ S(z, y))

    Kompozici relací si nepleťme s relačním součinem a relačním součtem, což jsou starší názvy pro průnik a sjednocení relací (když ale někteří autoři hovoří jen o součinu relací, mohou uvažovat kompozici relací

    Relace ‚být strýc‘ je definovatelná jako kompozice relací ‚být rodič‘ a ‚být bratr‘; relace ‚být prarodič‘ je definovatelná jako kompozice relací ‚být rodič‘ a ‚být rodič‘.
  34. vlastnosti binárních relací - jen omrkni:)
    Image Upload 7

    • Dané vlastnosti vymezují druhy relací, například vlastnost reflexivity vymezuje druh reflexivních relací.
    • Tranzitivitu lze alternativně definovat např. pomocí ∀x∀y∀z ((R(x,y)→(R(y,z)→R(x,z))) kvůli zákonu exportace (VL).
    • Konexnost lze alternativně definovat např. pomocí ∀x∀y ((x=y)∨R(x,y)∨R(y,x)) (na základě tautologie VL).
    • Některé relace autoři nazývají jinak. Například totální relace bývá zvána lineární relace. Ba co víc, například ∀x R(x,x) je někdy považována za definici úplné reflexivity, přičemž za vlastní definici reflexivity je považována až ∀x∀y (R(x,y)→R(x,x)).
    • Všimněme si, že dané druhy relací nejsou navzájem disjunktní. Například každá asymetrická relace je též antisymetrická (asymetrie navíc zahrnuje ireflexitivitu). Polosymetrie je konjunkcí negace symetrie a negace asymetrie. Pod sériové relace zas spadají reflexivní relace. Atd.

    • příklady relací:
    • - reflexivní: ‚být identický (se sebou)‘, ‚narcistně se obdivovat‘
    • – poloreflexivní: ‚milovat (někoho)‘ (někdo nemiluje sám sebe, někdo ano)
    • – ireflexivní: ‚být ženatý (s někým)‘, ‚být potomkem (někoho)‘
    • symetrický: ‚mít se rád navzájem s (někým)‘, ‚být sourozenec (někoho)‘
    • – polosymetrický: ‚znát (někoho)‘, ‚mít rád (někoho)‘
    • – antisymetrický: ‚být dělitelný‘ (v oboru přirozených čísel)
    • – asymetrický: ‚platonicky milovat (někoho)‘, ‚být otcem (někoho)‘
    • tranzitivní: ‚být potomkem (někoho)‘, ‚být vyšší než (něco)‘, ‚být podmnožinou‘, ≤
    • – polotranzitivní: ‚být kořist‘ (v  potravním řetězci někteří predátoři nejsou kořist)
    • – antitranzitivní: ‚porazit (někoho) v turnaji‘ (když x porazil y a y porazil z, x neporazil z)
    • – intranzitivní: ‚být otcem (někoho)‘
    • – euklidovská: ‚věci y a z, které se rovnají stejnému x, jsou si rovny‘
    • – sériová: ‚mít předka
  35. Vyjmenuj tři hlavní vlastnosti binárních relací, které musíš znát a definuj je
    • Reflexivita Refl (R) =df ∀x R(x,x)
    • Symetrie Sym(R) =df ∀x∀y (R(x,y)→R(y,x))
    • Tranzitivita Trans(R) =df ∀x∀y∀z ((R(x,y)∧R(y,z))→R(x,z))
  36. Vyjmenuj a definuj Speciální druhy binárních relací
    • Relace typu ekvivalence (R) =df Refl (R) ∧ Sym(R) ∧ Trans(R)
    • Částečné parciální uspořádání (R) =df Refl (R) ∧ Antisym(R) ∧ Trans(R)
    • Ostré uspořádání (R) =df Total(R) ∧ Antisym (R) ∧ Trans(R)

    • Částečné parciální uspořádání (angl. „weak partial order“) je někdy nazýváno kvazi uspořádání. Příkladem takové relace je relace ≤ na množině přirozených čísel, anebo relace dělení přirozených čísel m a n beze zbytku. (Relace < se od ≤ liší tím, že < je ireflexivní, v důsledku čehož je < ostrým uspořádáním.)
    • Druhů uspořádání je v literatuře definováno více, zde jsme se dále omezili už jen na jednu definici ostrého uspořádání.
  37. Binární relace jsou někdy vyobrazovány šipkovými diagramy. Objasni
    • Relace R je zobrazena množinou šipek, z nichž každá šipka ukazuje první a druhý člen nějaké dvojice obsažené v R.
    • Pokud nějaká šipka propojuje nějakou dvojici individuí, ale je přeškrtnuta, daná dvojice nepatří do dané relace.
    • Pokud nějaká šipka nějakou dvojici individuí nepropojuje, daná dvojice v relaci může být, ale nemusí.
    • Šipka propojující tři individua jako např. α, β, γ reprezentuje dvě dvojice 〈α,β〉, 〈β,γ〉. Někdy se používá obousměrná šipka, jež nahrazuje dvě jednosměrné šipky vedoucí opačnými směry. 

    Image Upload 8
Author
iren
ID
355222
Card Set
18 PL druheho radu
Description
predikatova logika
Updated