Máme danou neprázdnou množinu A tzv. atomických výroků(též jim říkáme logické proměnné). Konečnou posloupnost prvků z množinyA , logických spojek a závorek nazýváme výroková formule(zkráceně jen formule), jestliže vznikla podle následujících pravidel:
Každá logická proměnná(atomický výrok) a ∈ A je výroková formule.
Jsou-li α,βvýrokové formule, pak ¬α, (α∧β),(α∨β), (α⇒β), (α⇔β)jsou také výrokové formule.
Nic jiného než to, co vzniklo pomocí konečně mnoha použití bodů 1 a 2, není výroková formule.
Všechny formule, které vznikly z logických proměnných množinyA , značíme P(A).
Poznámka: Spojka ¬ se nazývá unární, protože vytváří novou formuli z jedné formule. Ostatní zde zavedené spojky se nazývají binární, protože vytvářejí novou formuli ze dvou formulí.
V dalším textu logické proměnné označujeme malými písmeny např. a,b,c, … nebo x,y,z, … , výrokové formule označujeme malými řeckými písmeny např. α , β , γ , … nebo ϕ , ψ , … . Také většinou nebudeme ve formulích psát ty nejvíc vnější závorky - tj. píšeme a ∨ ( b ⇒ c ) místo ( a ∨ ( b ⇒ c ) ) .
0.1.2 Syntaktický strom formule
To, jak formule vznikla podle bodů 1 a 2, si můžeme znázornit na syntaktickém stromu, též derivačním stromu dané formule. Jedná se o kořenový strom, kde každý vrchol, který není listem, je ohodnocen logickou spojkou. Jedná-li se o binární spojku, má vrchol dva následníky, jedná-li se o unární spojku, má vrchol pouze jednoho následníka. Přitom pro formule ( α ∧ β ) , ( α ∨ β ) , ( α ⇒ β ) odpovídá levý následník formuli α , pravý následník formuli β . Listy stromu jsou ohodnoceny logickými proměnnými.
0.1.3 Podformule
Ze syntaktického stromu formule α jednoduše poznáme všechny její podformule: Podformule formule α jsou všechny formule odpovídající podstromům syntaktického stromu formule α .
0.1.4 Pravdivostní ohodnocení
Pravdivostní ohodnocení, též pouze ohodnocení formulí, je zobrazení u:P( A ) → { 0,1 } , které splňuje pravidla
Negace ( ¬ α ) je pravdivá právě tehdy, když α je nepravdivá, tj. u( ¬ α ) =1 právě tehdy, když u( α ) =0 ;
Konjunkce ( α ∧ β ) je pravdivá právě tehdy, když α a β jsou obě pravdivé, tj. u( α ∧ β ) =1 právě tehdy, když u( α ) =u( β ) =1
Disjunkce ( α ∨ β ) je nepravdivá právě tehdy, když α a β jsou obě nepravdivé, tj. u( α ∨ β ) =0 právě tehdy, když u( α ) =u( β ) =0 ;
Implikace ( α ⇒ β ) je nepravdivá právě tehdy, když α je pravdivá a β nepravdivá, tj. u( α ⇒ β ) =0 právě tehdy, když u( α ) =1 a u( β ) =0 ;
Ekvivalence ( α ↔ β ) je pravdivá právě tehdy, když buď obě formule α a β jsou pravdivé nebo obě jsou nepravdivé, tj. u( α ↔ β ) =1 právě tehdy, když u( α ) =u( β ) .
0.1.5 Pravdivostní tabulky
Vlastnosti, které ohodnocení formulí musí mít, znázorňujeme též pomocí tzv. pravdivostních tabulek logických spojek. Jsou to:
α
¬ α
0
1
1
0
α
β
α ∧ β
α ∨ β
α ⇒ β
α ↔ β
0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
1
1
1
0.1.6 Věta
Každé zobrazení u 0 :A → { 0,1 } jednoznačně určuje ohodnocení u:P( A ) → { 0,1 } takové, že u 0 ( a ) =u( a ) pro všechna a ∈ A .
0.1.7 Důsledek
Dvě ohodnocení u,v:P( A ) → { 0,1 } jsou shodná právě tehdy, když pro všechny logické proměnné x ∈ A platí u( x ) =v( x ) .
0.1.8 Tautologie, kontradikce, splnitelné formule
Formule se nazývá tautologie, jestliže je pravdivá ve všech ohodnoceních formulí; nazývá se kontradikce, jestliže je nepravdivá ve všech ohodnoceních formulí. Formule je splnitelná, jestliže existuje aspoň jedno ohodnocení formulí, ve kterém je pravdivá.
0.1 Výroková logika