04 Logicky pravdive formule

  1. df logicky pravdivá formule
    • logicky pravdivé formule (či platné formule, ev. logické zákony) = jsou formule pravdivé v každé interpretaci (a to při jakémkoli ohodnocení).
    • Určitou část z logicky pravdivých formulí tvoří formule, jež mají tvar výrokově-logických tautologií, tj. tautologie
  2. df tautologie PL
    • Tautologie PL je logicky platná formule, jež má tvar tautologie VL.
    • Platí tedy, že každá tautologie je logicky platnou formulí, avšak existuje mnoho logicky platných formulí, jež nejsou tautologiemi.
  3. Příklady tautologií, jež lze získat patřičnou úpravou výrokově-logické tautologie p∨¬p (zákon vyloučeného třetího), jsou:
    • ∀xP(x) ∨ ¬∀xP(x)
    • P(x) ∨ ¬P(x)
    • ∃xR(x, y) ∨ ¬∃xR(x, y)
  4. Nejdůležitější logicky pravdivé formule: De Morganovy zákony (DM)
    • Image Upload 1
    • Všimněme si, že negátory jsou v každé formuli vždy dva, přičemž jeden negátor se vztahuje na  celou formuli (stojí před kvantifikátorem), zatímco druhý se vztahuje na zbývající část, tedy na část za kvantifikátorem.
  5. Nejdůležitější logicky pravdivé formule: zákony distributivity kvantifikátorů
    Image Upload 2
    • Image Upload 3
    • v první skupině jsou uvedeny vybrané zákony distributivnosti kvantifikátorů, jde o formule tvaru ekvivalence
    • Ve druhé skupině jsou další takové zákony,
    • nicméně nejde o ekvivalence, ale jen o implikace
  6. Nejdůležitější logicky pravdivé formule: zákony distributivity kvantifikátorů ALE s podmínkou - přesunem kvantifikátoru se žádná proměnná v A nestane v antecedentu volná
    Image Upload 4
    • Image Upload 5
    • vybrané zákony pro vsunutí kvantifikátoru dovnitř ekvivalence, pokud tento kvantifikátor v antecedentu nic neváže
  7. Nejdůležitější logicky pravdivé formule: zákony distributivity kvantifikátorů ALE s podmínkou - přesunem kvantifikátoru se žádná proměnná v nekvantifikované formuli A nebo B nestane napravo od ↔ volná
    Image Upload 6
    • Image Upload 7
    • vybrané zákony pro vsunutí kvantifikátoru dovnitř ekvivalence, pokud tento kvantifikátor v antecedentu nic neváže
  8. Nejdůležitější logicky pravdivé formule: zákony záměny pořadí kvantifikátorů
    Image Upload 8
    • Image Upload 9
    • Tato skupina obsahuje základní zákony pro záměnu pořadí kvantifikátorů pro formule s binárním predikátem. Namísto „A“ tam píšeme „R(x,y)“, aby si čtenář mohl snáze promyslet jejich platnost.
  9. Nejdůležitější logicky pravdivé formule: zákon konkretizace („univerzální instanciace“)
    ∀xA → A[t/x]
  10. Nejdůležitější logicky pravdivé formule: zákon abstrakce („existenční generalizace“)
    A[t/x] → ∃xA
  11. Nejdůležitější logicky pravdivé formule: zákon partikularizace
    ∀xA → ∃xA
  12. A[t/x] značí, že ...
    term t je substituovatelný za proměnnou x ve formuli A, je-li term individuová konstanta nebo individuová proměnná x taková, že po dosazení do formule A není v dosahu kvantifikátoru, který váže proměnnou x.
Author
iren
ID
354915
Card Set
04 Logicky pravdive formule
Description
predikatova logika
Updated