Výroková logika - základne pojmy

Teoretické základy výrokovej logiky, jej jazyk a sémantika

Výroková logika (VL) sa zaoberá výrokmi, ich pravdivosťou a odvodzovaním. Pojem výrok je možné chápať ako tvrdenie v tvare oznamovacej vety, pri ktorej má zmysel sa pýtať, či je pravdivá alebo nie.

Atomický výrok je jednoduché tvrdenie, ktoré nie je možné deliť. Takéto tvrdenia označujeme pomocou výrokových premenných p, q, r... .

Zložený výrok je tvrdenie, v ktorom sú atomické výroky prepojené logickými spojkami.

Ak Ivan nepôjde študovať matematiku, pôjde študovať informatiku.
Ak Ivan nepôjde študovať informatiku, začne podnikať.
Ivan nebude zároveň študovať matematiku aj podnikať.
----------------------------------------------------------------
Ivan pôjde študovať informatiku.

1. Ivan pôjde študovať matematiku.
2. Ivan pôjde študovať informatiku.
3. Ivan začne podnikať.

p = "Ivan pôjde študovať matematiku."
q = "Ivan pôjde študovať informatiku."
r = "Ivan začne podnikať."

Ak nie je pravda, že p, tak q.
Ak nie je pravda, že q, tak r.
Nie je pravda, že p a r.
------------------------------
q

Jazyk výrokovej logiky

Jazyk výrokovej logiky definujeme pomocou jeho abecedy a syntaxe v Backus-Naurovej forme (BNF).

Abecedu výrokovej logiky tvoria nasledujúce symboly:

1. Výrokové premenné: sú to atomické výroky, podľa konvencie označované malými písmenami latinskej abecedy p, q, r...,
2. Výrokové formuly: zložené výroky (aj atomické), podľa konvencie označované malými písmenami gréckej abecedy ψ, ϕ, ϴ …,
3. Základné logické spojky:
   • konštanty: ⊤, ⊥, reprezentujúce vždy pravdivý resp. vždy nepravdivý výrok, nazývané verum, absurdum,
   • negácia ¬, vyslovuje sa ako "nie je pravda, že",
   • konjunkcia ∧, vyslovuje sa ako "a",
   • disjunkcia ∨, vyslovuje sa ako "alebo",
   • implikácia ⇒, vyslovuje sa ako "ak, …, tak …".
4. Pomocné symboly: zátvorky.

Syntax výrokovej logiky v BNF:

je definovaná produkčným pravidlom v Backus-Naurovej forme, prostredníctvom ktorého je možné konštruovať všetky prípustné tvary formúl: \begin{equation} \varphi ::= p \mid \top \mid \bot \mid \neg\varphi \mid \varphi \land \psi \mid \varphi \lor \psi \mid \varphi \Rightarrow \psi, \end{equation} kde p je množina atomických výrokov. Množinu všetkých formúl jazyka výrokovej logiky, ktoré je možné skonštruovať pomocou vyššie uvedeného BNF označíme ako Prop.

Priorita a asociativita logických spojok

Pre úplnosť je potrebné uviesť asociativitu a prioritu jednotlivých logických spojok. Pokiaľ zátvorky nie sú použité, platí nasledujúca asociativita:

• Logické spojky ∧, ∨ sú (ne)asociatívne t.j.: $$ ϕ ∧ (ψ ∧ ϴ) ≡ (ϕ ∧ ψ) ∧ ϴ  ϕ ∨ (ψ ∨ ϴ) ≡ (ϕ ∨ ψ) ∨ ϴ $$
• Logická spojka ⇒ je asociatívna sprava t.j.: $$ ϕ ⇒ ψ ⇒ ϴ ≡ (ϕ ⇒ (ψ ⇒ ϴ))$$

Zároveň platia nasledujúce konvencie priority logických spojok:

¬p ⇒ q
¬q ⇒ r
¬(p ∧ r)
---------
q

Priama podformula formuly VL

Majme dané formuly VL ϕ, ψ. Nech U je ľubovoľná unárna logická spojka a B ľubovoľná binárna logická spojka, potom platí:

• Ak ϕ je atomický výrok, tak ϕ nemá žiadnu priamu podformulu.
• Formula Uϕ, má jednu priamu podformulu: ϕ.
• Formula ϕ B ψ, má dve priame podformuly: ϕ, ψ.

Tieto pojmy slúžia pre potreby identifikácie štruktúry formuly VL, ktorú opisuje abstraktný syntaktický strom.

Výpočet všetkých podformúl výrokovej formuly $φ$ je možné vyjadriť pomocou funkcie $subf$ nasledovne:

• Špecifikácie funkcie: $$subf:Prop → \mathcal{P}(Prop).$$
• Definícia funkcie: $$ subf(φ)= \begin{cases} \{p\}, \quad \text{ak}~φ=p,~\text{a}~p~\text{je výroková premenná},\\ \{⊤\}, \quad \text{ak}~φ=⊤,\\ \{⊥\}, \quad \text{ak}~φ=⊤,\\ \{φ\} ∪ subf(φ'), \quad \text{ak}~\varphi = ¬φ', ~\text{a}~ φ'∈ Prop,\\ \{φ\} ∪ subf(φ_1) ∪ subf(φ_2), \quad \text{ak}~\varphi = φ_1 ∧ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop,\\ \{φ\} ∪ subf(φ_1) ∪ subf(φ_2), \quad \text{ak}~\varphi = φ_1 ∨ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop,\\ \{φ\} ∪ subf(φ_1) ∪ subf(φ_2), \quad \text{ak}~\varphi = φ_1 ⇒ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop. \end{cases} $$

Abstraktný syntaktický strom

Abstraktný syntaktický strom (AST) je možné formálne zadefinovať ako funkciu $ast$, ktorej parameter je výroková formula $\varphi$ a výsledkom je AST danej formuly $φ$ nasledovne:

• Špecifikácia funkcie: $$ast:Prop \rightarrow Trees$$
• Definícia funkcie:

  
  

Všimnite si, že abstraktné syntaktické stromy sú veľmi dôležité. V skutočnosti je výroková formula jej abstraktným syntaktickým stromom. Avšak v kreslenie AST je ťažkopádne, preto je vhodnejšie definovať funkcie, prostredníctvom ktorých je možné získať vlastnosti AST danej formuly bez potreby kreslenia príslušného AST.

Veľkosť formuly

Veľkosť formuly $φ$ vyjadruje počet uzlov jej abstraktného syntaktického stromu. Funkciu $size$, ktorá vráti veľkosť výrokovej formuly je možné vyjadriť nasledovne:

• Špecifikácie funkcie: $$size:Prop → \mathbb{N}.$$
• Definícia funkcie: $$ size(φ)= \begin{cases} 1, \quad \text{ak}~φ=p,~\text{a}~p~\text{je výroková premenná},\\ 1, \quad \text{ak}~φ=⊤,\\ 1, \quad \text{ak}~φ=⊤,\\ 1 + size(φ'), \quad \text{ak}~\varphi = ¬φ', ~\text{a}~ φ'∈ Prop,\\ 1 + size(φ_1) ∪ size(φ_2), \quad \text{ak}~\varphi = φ_1 ∧ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop,\\ 1 + size(φ_1) ∪ size(φ_2), \quad \text{ak}~\varphi = φ_1 ∨ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop,\\ 1 + size(φ_1) ∪ size(φ_2), \quad \text{ak}~\varphi = φ_1 ⇒ φ_2, ~\text{a}~ φ_1, φ_2∈ Prop. \end{cases} $$

Sémantika výrokovej logiky

Sémantika výrokovej logiky definuje význam jednotlivých formúl, teda či je dané tvrdenie pravdivé alebo nie. Táto vlastnosť sa nazýva pravdivostná hodnota výroku. Je definovaná ako jednoznačné zobrazenie z množiny Prop všetkých formúl VL do množiny {1,0}, ktorá kóduje množinu {pravda, nepravda}. Na základne konvencie sa zvyčajne pravdivostná hodnota pravda označuje číslicou 1 a pravdivostná hodnota nepravda číslicou 0.

Túto vlastnosť je možné modelovať prostredníctvom sémantickej funkcie, ktorá je špecifikovaná ako $$v: Prop → \{1, 0\}$$ a je definovaná pre všetky prvky produkčného pravidla (1) nasledovne:

$$ \begin{array}{l} v(p) = 1, \text{ak}~p ∈ A,~\text{kde}~A~\text{je množina všetkých pravdivých atomických výrokov,}\\ ~ \\ v(⊤) = 1 \\ ~ \\ v(⊥) = 0 \\ ~ \\ v(¬φ) = 1~\text{ak}~v(φ) = 0 \\ ~ \\ v(φ ∧ ψ) = \left\lbrace\begin{array}{ll} 1, & \text{ak}~ v(φ) = 1 ~\text{a}~ v(ψ) = 1\\ 0, & \hbox{inak} \end{array}\right. \\ ~ \\ v(φ ∨ ψ) = \left\lbrace\begin{array}{ll} 1, & \text{ak}~ v(φ) = 1 ~\text{alebo}~ v(ψ) = 1\\ 0, & \hbox{inak} \end{array}\right. \\ ~ \\ v(φ ⇒ ψ) = \left\lbrace\begin{array}{ll} 0, & \text{ak}~ v(φ) = 1 ~\text{a}~ v(ψ) = 0\\ 1, & \hbox{inak} \end{array}\right. \end{array} $$

Pravdivostné ohodnotenie formuly VL

Pravdivostné ohodnotenie $v(ϕ)$ formuly výrokovej logiky $ϕ$ pri ohodnotení $v$ atomických výrokov je priradenie hodnoty z množiny {0, 1} formule $ϕ$ na základe definície vyššie uvedenej sémantickej funkcie.

Tabuľková metóda

Pre zápis pravdivostného ohodnotenia formúl sa vo všeobecnosti používa metóda nazývaná pravdivostná tabuľka. Nižšie je uvedený príklad pravdivostnej tabuľky zložených formúl výrokovej logiky využitím základných logických spojok.

Tautológia, kontradikcia, splniteľnosť formuly:

• Formula sa nazýva tautológia označujeme ⊤ práve vtedy, ak je pravdivá pri každom ohodnotení výrokových premenných.
• Formulu sa nazýva kontradikcia označujeme ⊥ práve vtedy, keď je nepravdivá pri každom ohodnotení výrokových premenných.
• Formula sa nazýva splniteľná práve vtedy, keď existuje aspoň jedno ohodnotenie jej výrokových premenných, pri ktorom je pravdivá.
• Pravdivostné ohodnotenie pri ktorom je formula pravdivá nazývame model formuly.

Zákony výrokovej logiky:

Pre ľubovoľné formuly výrokovej logiky ϕ, ψ, ϴ platia nasledujúce ekvivalencie:

1. Idempotentnosť konjunkcie a disjunkcie: $$ϕ ∧ ϕ ≣ ϕ,   ϕ ∨ ϕ ≡ ϕ.$$

2. Komutatívnosť konjunkcie a disjunkcie: $$ ϕ ∧ ψ ≡ ψ ∧ ϕ, ϕ ∨ ψ ≡ ψ ∨ ϕ. $$

3. Asociatívnosť konjunkcie a disjunkcie: $$ϕ ∧ (ψ ∧ ϴ) ≡ (ϕ ∧ ψ) ∧ ϴ,   ϕ ∨ (ψ ∨ ϴ) ≡ (ϕ ∨ ψ) ∨ ϴ.$$

4. Absorpcia konjunkcie a disjunkcie: $$ϕ ∧ (ψ ∨ ϕ) ≡ ϕ,   ϕ ∨ (ψ ∧ ϕ) ≡ ϕ. $$

5. Zákon dvojitej negácie: $$¬¬ϕ ≡ ϕ$$

6. De Morganovo pravidlo pre konjunkciu a disjunkciu: $$¬(ϕ ∧ ψ) ≡ (¬ ϕ ∨ ¬ ψ),   ¬(ϕ ∨ ψ) ≡ (¬ ϕ ∧ ¬ ψ).$$

7. Distributívnosť konjunkcie a disjunkcie: $$ϕ ∨ (ψ ∧ ϴ) ≡ (ϕ ∨ ψ) ∧ (ϕ ∨ ϴ),   ϕ ∧ (ψ ∨ ϴ) ≡ (ϕ ∧ ψ) ∨ (ϕ ∧ ϴ).$$

8. Zákon nahradenia implikácie: $$ϕ ⇒ ψ ≡ ¬ ϕ ∨ ψ$$

9. Nech ⊤ je ľubovoľná tautológia a ⊥ je ľubovoľná kontradikcia, tak platí:
   $$⊤ ∧ ϕ ≡ ϕ,   ⊥ ∧~ϕ ≡ ⊥,   ⊤ ∨ ϕ ≡ ⊤,   ⊥ ∨~ϕ ≡ ϕ,   ϕ ∧ ¬ ϕ ≡ ⊥,   ϕ ∨ ¬ ϕ ≡ ⊤.$$

10. Zákon identity: $$ ϕ ⇒ ϕ ≡ ⊤ $$

11. Zákon modus ponens: $$ ((ϕ ⇒ ψ) ∧ ϕ) ⇒ ψ $$

12. Zákon modus tollens: $$ ((ϕ ⇒ ψ) ∧ ¬ ψ) ⇒ ¬ ϕ $$

Logické vyplývanie

Ako je možné si všimnúť, tvrdenia v príklade (P1) sú zapísane v tvare logického vyplývania, ktoré má nasledujúci všeobecný tvar:

φ1 = Tvrdenie 1
...
φn = Tvrdenie n
----------------------------------------------------------------
ψ = Záver

Takéto tvrdenia je možné na základe zákonov výrokovej logiky prepísať do jej jazyka v tvarej nasledujúcej formuly: $$φ_1 ∧ … ∧ φ_n ⇒ ψ,$$ kde výroky $φ_1 , …, φ_n$ sú predpokladom/predpoklady (premisy) a výrok $ψ$ je záverom formuly (v niektorej literatúre uvádzané ako antecedent a konzekvent). Hovoríme, že formula pod čiarou je dôsledkom formuly/formúl nad čiarou, práve vtedy ak pri každom pravdivostnom ohodnotení, pri ktorom je pravdivá každá z formúl premís, je pravdivý aj záver.

Zároveň namiesto zápisu

φ1
...
φn 
----
ψ 

prijmeme nasledujúcu konvenciu zápisu schém logického vyplývania $$ φ_1, ..., φ_n \models ψ,$$ kde symbol $\models$ je možné prečítať aj ako vyplýva, teda zápis $p, ..., q \models r$ je možné prečítať ako skutočnosť, že "výrok $ψ$ vyplýva z výrokov $φ_1, ..., φ_n$".

Množiny formúl budeme označovať veľkými písmenami gréckej abecedy $Γ, Δ,...$. Taktiež prijmeme konvenciu zápisu premís $φ_1, ..., φ_2$ ako množiny formúl $Γ$ nasledovne: $$Γ \models ψ.$$

Množina formúl $Δ$ vyplýva z množiny formúl $Γ$, ak $$Γ \models Δ.$$

Nech $φ, ψ \in Prop$ a nech $Γ \models φ$. Ak množina formúl $Γ$ je jednoprvková resp. prázdna, budeme používať nasledujúce zápisy:

• $ψ \models φ$ namiesto $\{ψ\} \models φ$,
• $\models φ$ namiesto $\emptyset \models φ$.

Zároveň platia nasledujúce tvrdenia:

• $Γ \models ψ$ vtedy a len vtedy ak $\{¬ψ\}∪Γ$ je kontradikcia.
• Ak $Γ$ je nesplniteľné, potom $Γ \models ψ$ pre všetky $ψ$. To znamená, že z kontradikcie je možné odvodiť čokoľvek ($φ ∧ ¬φ ⇒ ⊥$).
• $\models φ$ vtedy a len vtedy ak $\{¬φ\}$ je kontradikcia.

¬p ⇒ q
¬ q ⇒ r
¬(p ∧ r)
---------
q

Boolove funkcie

• Formulu ktorá obsahuje jeden atomický výrok x označíme ϕ(x).
• Formulu ktorá obsahuje viacero atomických výrokov x₁, …, xₙ, označíme $$ϕ(x₁, …, xₙ).$$
• Takéto formuly je možné na sémantickej úrovni interpretovať ako zobrazenie n-tice pravdivostných hodnôt na pravdivostnú hodnotu: $$ϕ:\{0,1\}ⁿ→\{0,1\}.$$
• Takáto funkcia sa nazýva Boolova funkcia.

Odvodené logické spojky

Prostredníctvom už definovaných logických spojok je možné definovať ďalšie logické spojky. Medzi najčastejšie využívané patria:

• Ekvivalencia ⇔ $$ p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p). $$
• Exkluzívna disjunkcia XOR ⊕ $$ p ⊗ q ≡ ¬(p ⇔ q). $$
• Shefferova operácia NAND ↑ $$ p ↑ q ≡ ¬(p ∧ q). $$
• Peirceova operácia NOR ↓ $$ p ↓ q ≡ ¬(p ∨ q). $$