03 Jazyk VL

• 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

• abeceda 
• gramatika
• pod/formule, s.u.f., výroková forma
• výrokový symbol

valuace, interpretace, splnitelnost, tautologie, kontradikce, ekvivalence, pravdivostní fce

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ří:
• 

• 
• 

• syntaktické stromy podformulí:
• 

přiřadit k správně utvořeným formulím jazyka VL význam (tedy pravdivostní hodnotu 1 a 0)

• = 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á)

• 
• 
• 

• 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  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í :

• 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

formule A je splnitelná právě tehdy, když je splňována aspoň jednou interpretací

• každou valuaci v, při níž je formule splňována, nazýváme model formule A
• 

Systém formulí T je splněn nějakou interpretaci  právě tehdy, když každá z formulí systému T je při této interpretaci  pravdivá.

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

někdy se pak říká, že systém formulí T je logicky pravdivý právě tehdy,  když je splněn každou interpretaci 

Věta o kompaktnosti: Libovolný systém formulí T je splnitelný právě tehdy, když každá konečná část T je splnitelná.

otázka , zda pro danou formuli existuje ohodnocení jejích proměnných , při němž je pravdivá

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

logicky platná formule

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

formule A je ekvivalentní formuli B právě tehdy když jsou obě splňovány pouze a právě týmiž interpretacemi, tj.  při všech valuacích v.

• duální formule: dvě formule A a B jsou k sobě duální právě tehdy, když
• - 
• 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

formule A je tautologickým důsledkem systému formulí T, psáno T I= A, právě tehdy, když  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)

logický důsledek systému formulí

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

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