03 Jazyk VL

  1. vzjmenuj subdisciplíny sémiotiky
    • syntax: zkoumá jen znaky jako takové
    • sémantika: zkoumá vztahy jazykových znaků a jejich významů (denotátů, referentů).
    • pragmatika: zvažuje záměr uživatelů daného jazyka

    syntax vlastně vymezuje, které znaky se počítají do onoho jazyka, zatímco  sémantika vymezuje, jak těmto výrazům rozumět
  2. vyjmenuj základní pojmy spadající do syntaxe VL
    • abeceda 
    • gramatika
    • pod/formule, s.u.f., výroková forma
    • výrokový symbol
  3. vyjmenuj základní pojmy spadající do sémantiky jazyka VL
    valuace, interpretace, splnitelnost, tautologie, kontradikce, ekvivalence, pravdivostní fce
  4. k čemu slouží abeceda VL?
    plán: v části zvané abeceda určujeme základní stavební jednotky tohoto  znakového systému x v části zvané gramatika generujeme z abecedy slova nad  abecedou, tj. znakové řetězce; v případě jazyka VL se významuplná slova  nad abecedou nazývají správně (ev. dobře) utvořené formule, s.u.f (ev  d.u.f.; angl. ,,wff'')

    • abecedu tvoří:
    • Image Upload 1
  5. k čemu slouží gramatika VL?
    • Image Upload 2
    • Image Upload 3
  6. definuj podformuli
    Image Upload 4

    • syntaktické stromy podformulí:
    • Image Upload 5
  7. úkolem sémantiky VL je...
    přiřadit k správně utvořeným formulím jazyka VL význam (tedy pravdivostní hodnotu 1 a 0)
  8. co je to valuace?
    • = pravdivostní ohodnocení
    • každá jednotlivá valuace v je funkce zobrazující všechny proměnné na pravdivostní hodnoty 1 a 0
    •    protože každá valuace je funkce, v(A) dává pravdivostní hodnotu pro  formuli A (podmínka- A je atomická formule, tj. výroková proměnná)
  9. definuj interpretaci
    • Image Upload 6
    • Image Upload 7
    • Image Upload 8

    • někteří autoři v rámci VL valuaci a interpretaci neodlišují a jednoduše říkají, že formule A je pravdivá na základě valuace
    • - naše valuace složené formule nijak neohodnocuje
    • - někteří autoři pak rozeznávají v v našem smyslu a w, kdy w je rozšíření v v souladu s podmínkami 1.--6.

    • definice Image Upload 9 je rekurzivní, protože nám pro libovolnou formuli daného jazyka umožnuje určit její sémantickou (rozuměj pravdivostní) hodnotu
    • body 2.--6. vycházejí z definic pravdivostních funkcí ¬, ∧, atd., jež jsme si formou pravdivostních tabulek uvedli výše

    výpočet pravdivostních hodnot dodávaných funkcí Image Upload 10 :

    Image Upload 11
  10. k čemu slouží pojem splnitelnost?
    • sémantika alternativně formulová na na základě teorie modelů 
    • - využívá pojmu splnitelnosti (angl. ,,satisfaction"), jež se opírá o pojem  interpretace; model je pak to, co splňuje formuli

    Image Upload 12

    Image Upload 13
  11. definuj pojem splnitelná formule
    formule A je splnitelná právě tehdy, když je splňována aspoň jednou interpretací
  12. definuj pojem model formule
    • každou valuaci v, při níž je formule splňována, nazýváme model formule A
    • Image Upload 14
  13. kdy mluvíme o splnění a slnitelnosti systému formulí?
    Systém formulí T je splněn nějakou interpretaci Image Upload 15 právě tehdy, když každá z formulí systému T je při této interpretaci Image Upload 16 pravdivá.

    Systém formulí T je splnitelný právě tehdy, když existuje interpretace Image Upload 17  taková, že systém T je splněn tou interpretaci Image Upload 18 .

    někdy se pak říká, že systém formulí T je logicky pravdivý právě tehdy,  když je splněn každou interpretaci Image Upload 19
  14. definuj větu o kompaktnosti
    Věta o kompaktnosti: Libovolný systém formulí T je splnitelný právě tehdy, když každá konečná část T je splnitelná.
  15. o čem je Problem SAT / Problem booleovské splnitelnosti?
    otázka , zda pro danou formuli existuje ohodnocení jejích proměnných , při němž je pravdivá
  16. definuj tautologii
    výrokově-logickou tautologií je formule, která nabývá hodnoty 1 při každém ohodnocení výrokových proměnných, tj. při každé valuaci. Je to tedy formule, která je každou interpretací splňována
  17. jiným názvem pro tautologie je...
    logicky platná formule
  18. definuj kontradikci
    výrokově-logickou kontradikcí je formule, která nabývá hodnoty 0 při každém ohodnocení výrokových proměnných, tj. při každé valuaci. Je to tedy formule, která naní žádnou interpretací splňována, jsou to nesplnitelné formule
  19. definuj ekvivalenci formulí
    formule A je ekvivalentní formuli B právě tehdy když jsou obě splňovány pouze a právě týmiž interpretacemi, tj. Image Upload 20 při všech valuacích v.
  20. co je to duální formule a věta o dualitě?
    • duální formule: dvě formule A a B jsou k sobě duální právě tehdy, kdyžImage Upload 21
    • Image Upload 22
    • věta o dualitě: A je ekvivalentní B, jež se od A liší záměnou duálních spojek ∧ a ∨ a tím, že namísto atomických formulí (proměnných) obsahují jejich negace
  21. definuj tautologický důsledek formulí
    formule A je tautologickým důsledkem systému formulí T, psáno T I= A, právě tehdy, když Image Upload 23 pro každou formuli B, jež je prvkem T. V případě T I= A pro prázdný soubor T píšeme krátce I= A.

    množina tautologických důsledků množiny T se obvykle označuje  Cn(T), kde ,,Cn" je zkratkou za ,,consequence" (tj. důsledek) nebo se  používá CI, což zkracuje ,,closure" (tj. uzávěr)
  22. namísto tautologický důsledek lze použít pojem ...
    logický důsledek systému formulí
  23. definuj pravidlo substituce
    nahradíme li ve VL-tautologii každý výskyt určité proměnné určitou jednou a toutéž formulí, zůstane VL-tautologií

    • např. do tautologie p ⇒ p můžeme substituovat (tj.dosadit) za p například q anebo třeba q ∨ r, a výsledky těchto substitucí, totiž q ⇒
    •  q i (q ∨ r) ⇒ (q ∨ r) jsou rovněž tautologie
  24. definuj pravidlo ekvivalentního nahrazení VL
    Nechť A je formule, která obsahuje alespoň na jednom místě podformuli B. Jestliže platí, že B je ekvivalentní s C, a jestliže formule A' vznikne  nahrazením libovolného počtu výskytů formule B formulí C ve formuli A, pak A' je ekvivalentní s A.

    například ve formuli (p V q) ⇒ p lze namísto prvního výskytu p dát formuli p ∧ p, neboť je ekvivalentní p; výsledek nahrazení,  ((p ∧ p) V q) ⇒ p, je ekvivalentní (p V q) ⇒p
Author
iren
ID
353890
Card Set
03 Jazyk VL
Description
FILOSOFIE, VÝROKOVÁ LOGIKA
Updated