Výroková logika - základne pojmy

Ciele

  1. Naštudovať potrebné pojmy z formálneho aparátu výrokovej logiky.
  2. Preštudovať vzorové príklady prezentované v rámci teoretickej časti.
  3. Vypracovať zadané úlohy.

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.

Príklad

Majme dané nasledujúce logické tvrdenie (P1) v prirodzenom jazyku.

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.

V tomto logickom tvrdení sa vyskytujú tri atomické výroky:

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

Jednotlivé premisy (P1) reprezentujú vzťahy medzi atomickými výrokmi. Skutočnosť, že tieto výroky (1-3) považujeme za atomické, nesúvisí s tým, že sa jedná o holé vety.

Pri pohľade na jednotlivé výroky sa zaujímame o výrokové (logické) spojky a pri atomických výrokoch nás nezaujíma ich vnútorná štruktúra. Na základe toho môžeme atomické výroky abstrahovať a nahradiť výrokovými premennými:

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

Vzhľadom na logické spojky v príklade (P1) je možné dané tvrdenie prepísať nasledovne:

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

Poznámka

V závere predchádzajúceho príkladu sa vo výrokoch stále vyskytujú slová a slovné spojenia prirodzeného jazyka ako napríklad "nie je pravda, že"…. V ďalších kapitolách bude uvedené ako prepísať takéto slovné spojenia do jazyka výrokovej logiky.

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:

Logická spojka Priorita
¬ 1
2
3
4

Poznámka

Pokiaľ máte pochybnosti ohľadom priority a asociativity logických operátorov (a nie len pri nich), vždy platí zlaté pravidlo: "zátvorkuj!".

Príklad

Na základe uvedeného je možné logické tvrdenie z príkladu (P1) prepísať do jazyka výrokovej logiky nasledovne:

¬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} $$

Príklad

Majme výrokovú formulu $φ = ¬p ∧ r ⇒ q \vee s$. Nájdite všetky podformuly $φ$.

Riešenie

Na základe vyššie definovanej priority a asociativity operátorov môžeme do $φ$ pridať zátvorky nasledovne: $$(¬p ∧ r) ⇒ (q \vee s).$$ Aplikujeme funkciu $subf$ na upravenú formulu:

$$ \begin{array} ~subf((¬p ∧ r) ⇒ (q \vee s)) = \{(¬p ∧ r) ⇒ (q \vee s)\} ∪ subf(¬p ∧ r) ∪ subf(q \vee s) = \\ = \{(¬p ∧ r) ⇒ (q \vee s)\} ∪ \{¬p ∧ r\} ∪ subf(¬p) ∪ subf(r) ∪ \{q \vee s\} ∪ subf(q) ∪ subf(s) = \\ = \{(¬p ∧ r) ⇒ (q \vee s)\} ∪ \{¬p ∧ r\} ∪ \{¬p\} ∪ subf(p) ∪ \{r\} ∪ \{q \vee s\} ∪ \{q\} ∪ \{s\} = \\ = \{(¬p ∧ r) ⇒ (q \vee s)\} ∪ \{¬p ∧ r\} ∪ \{¬p\} ∪ \{p\} ∪ \{r\} ∪ \{q \vee s\} ∪ \{q\} ∪ \{s\} \end{array} $$

Poznámka


Prvý krok pridania zátvoriek nie nutný, avšak zvyšuje prehľadnosť.

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:


Poznámka


Intuitívne, $Trees$ v špecifikácii funkcie $ast$ je množina stromov, ktorú nedefinujeme formálne.

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.

Príklad

Majme výrokovú formulu $φ = ¬p ∧ r ⇒ q \vee s$. Nájdite jej abstraktný syntaktický strom $φ$.

Riešenie

Aplikujeme funkciu $ast$ na formulu $φ$:


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} $$

Príklad

Majme výrokovú formulu $φ = ¬p ∧ r ⇒ q \vee s$. Zistite veľkosť formuly $φ$.

Riešenie

Aplikujeme funkciu $size$ na formulu $φ$:

$$ \begin{array} ~size(¬p ∧ r ⇒ q \vee s) = 1 + size(¬p ∧ r) + size(q \vee s) = \\ = 1 + 1 + size(¬p) + size(r) + 1 + size(q) + size(s) =\\ = 1 + 1 + 1 + size(p) + 1 + 1 + 1 + 1 =\\ = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8 \end{array} $$

Poznámka


Funkcie $subf, ast, size$štrukturálne rekurzívne.

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} $$

Poznámka


Namiesto pravdivostných hodnôt 1, 0 reprezentujúcich pravdu, nepravdu sa niekedy používajú označenia T, F (z ang. true, false).

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.

ϕ ψ ¬ϕ ϕ ∧ ψ ϕ ∨ ψ ϕ ⇒ ψ
1 1 0 1 1 1
1 0 0 0 1 0
0 1 1 0 1 1
0 0 1 0 0 1

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: $$ ((ϕ ⇒ ψ) ∧ ¬ ψ) ⇒ ¬ ϕ $$

Poznámka

Vyššie je uvedených len niekoľko zákonov a ekvivalencií platných vo výrokovej logike, potrebných pre zvládnutie úloh v rámci cvičení (viď odporúčaná literatúra).

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

Poznámka

Logické vyplývanie sa taktiež nazýva aj sylogizmus.

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$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.

Príklad

Tvrdenia z príkladu (P1)

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

je možne základe schémy uvedenej vyššie prepísať do nasledujúcej formuly výrokovej logiky: \begin{equation} (¬p ⇒ q) ∧ (¬ q ⇒ r) ∧ ¬(p ∧ r) ⇒ q. \end{equation}

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.

Poznámka

Boolova algebra a výroková logika sú izomorfické systémy. V rámci týchto učebných textov nebudú tieto systémy považované za rozdielne. Z dôvodu prehľadnosti bude v niektorých prípadoch v nasledujúcich kapitolách vypožičaná syntax boolovej algebry.

Príklad

Prostredníctvom tabuľkovej metódy je možné zistiť či je formula (2) tautológiou, kontradikciou, alebo splniteľná. Nech je formula (2) nazvaná ϕ: $$ φ = (¬p ⇒ q) ∧ (¬ q ⇒ r) ∧ ¬(p ∧ r) ⇒ q.$$ Potom formula ϕ(p,q,r) je Boolova funkcia, obsahujúca tri atomické výroky, čo vytvára 2³ jej možných kombinácií pravdivostných ohodnotení. Pri výtvarní pravdivostnej tabuľky zloženej formuly, je potrebné formulu vhodne rozložiť na základe jej priamych podformúl a zistiť ich ohodnotenie. V našom prípade sa jedná o nasledujúce podformuly.

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

Vytvoríme pravdivostnú tabuľku:

p q r ¬p ¬q ¬p⇒q ¬q⇒r p ∧ r ¬(p ∧ r) (¬p ⇒ q) ∧ (¬ q ⇒ r) ∧ ¬(p ∧ r) ⇒ q
1 1 1 0 0 1 1 1 0 1
1 1 0 0 0 1 1 0 1 1
1 0 1 0 1 1 1 1 0 1
1 0 0 0 1 1 0 0 1 1
0 1 1 1 0 1 1 0 1 1
0 1 0 1 0 1 1 0 1 1
0 0 1 1 1 0 1 0 1 1
0 0 0 1 1 0 0 0 1 1

Na základe posledného stĺpca pravdivostnej tabuľky je možné tvrdiť, že formula ϕ je tautológia.

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). $$

Poznámka

Pojem ekvivalencia je označovaný dvomi symbolmi ⇔ ≡. Avšak ich kontext je rozdielny. V prvom prípade sa jedná o odvodenú logickú spojku výrokovej logiky (⇔) a v druhom prípade o matematický metasymbol jazyka (≡) používaný na napr. pre vyjadrenie dvoch (sémanticky) ekvivalentných tvrdení.

Postup

Krok 1: Prepíšte nasledujúce vety v prirodzenom jazyku do formúl jazyka výrokovej logiky.

Úloha 1.1

  Jana pôjde do kina a Eva pôjde do kina.
  1. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a implikácie.
  2. Negujte formulu.

Riešenie

Určíme atomické výroky. Výrok:

  Jana pôjde do kina.

Označíme ako j.

  Eva pôjde do kina.

Označíme ako e.

Potom výsledná formula má nasledujúci tvar: $$j ∧ e$$

  1. V prvom kroku prepíšeme formulu využitím De Morganovho pravidla a zákonu dvojitej negácie: $$ ¬(¬(j ∧ e)) ≡ ¬(¬j ∨ ¬e) $$ V druhom kroku prepíšeme formulu využitím zákonu nahradenia implikácie: $$ ¬(¬j ∨ ¬e) ≡ ¬(j ⇒ ¬e) $$
  2. Formulu negujeme podľa De Morganovho pravidla: $$ ¬(j ∧ e) ≡ ¬j ∨ ¬e $$

Úloha 1.2

  Jana pôjde do kina alebo Eva nepôjde do kina.
  1. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a implikácie.
  2. Negujte formulu.

Výsledok

$$ j ∨ ¬e $$

  1. $$ j ∨ ¬e ≡ ¬j ⇒ ¬e $$
  2. $$ ¬(j ∨ ¬e ) ≡ (¬j ∧ e ) $$

Úloha 1.3

  Jana pôjde do kina a Eva nepôjde do kina.
  1. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a implikácie.
  2. Negujte formulu.

Úloha 1.4

  Ak Jana pôjde do kina, potom Eva nepôjde do kina.
  1. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a disjunkcie.
  2. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a konjunkcie.
  3. Negujte formulu.

Úloha 1.5

  Ak Jana alebo Eva pôjde, potom Peter pôjde a Jozef nepôjde.
  1. Využitím zákonov výrokovej logiky, prepíšte formulu do tvaru negácie a disjunkcie.
  2. Prepíšte formulu do disjnktívneho normálneho tvaru.
  3. Prepíšte formulu do konjunktívneho normálneho tvaru.
  4. Negujte formulu.

Poznámka

Disjunktívny a konjunktívny normálny tvar je definováný v cvičení 2.

Krok 2: Prepíšte nasledujúce vety v prirodzenom jazyku do formúl jazyka výrokovej logiky. Výsledné formuly negujte.

Úloha 2.1

  Pôjdem na prechádzku alebo do kina.

Úloha 2.2

  Nechcem spievať ani tancovať.

Úloha 2.3

  Ak sa budem učiť, urobím skúšku.

Úloha 2.4

  Ak je streda, potom mám cvičenie.

Úloha 2.5

  Ak sa budem učiť a budem mať šťastie, potom urobím skúšku.

Úloha 2.6

  Ak bude jasno a nepokazí sa auto, potom pôjdeme na výlet a budeme sa kúpať.

Krok 3: Zostrojte syntaktické stromy formúl, zistite ich velkosť a pomocou pravdivostných tabuliek zistite či sa jedná o tautológie, kontradikcie alebo splniteľné formuly.

Úloha 3.1

$$ p ⇒ (q ⇒ r) $$

Úloha 3.2

$$ p ⇒ q ⇒ r $$

Úloha 3.3

$$ (p ⇒ q) ⇒ r $$

Úloha 3.4

$$ ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)$$

Úloha 3.5

$$ (p ⇒ q) ⇒ (¬q ⇒ ¬p) $$

Úloha 3.6

$$ p ⇒ (¬p ⇒ ¬q) $$

Úloha 3.7

$$ ((p ⇒ q) ⇒ p) ⇒ q $$

Úloha 3.8

$$ ((p ∨ q) ⇒ r) ∧ (¬r ⇒ p) $$

Úloha 3.9

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

Úloha 3.10

$$(a ⇒ b) ∧ ( b ⇒ c ) ∧ ( c ⇒ ¬ d ) ⇒ ( a ⇒ ¬ d )$$

Krok 4: Dokážte, či platia nasledujúce ekvivalencie.

Úloha 4.1

$$ (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) $$

Úloha 4.2

$$ (p ⇒ q) ⇒ r ≡ p ⇒ (q ⇒ r) $$

Úloha 4.3

$$ (p ∧ q) ≡ (p ↓ p) ↓ (q ↓ q) $$

Úloha 4.4

$$ (p ∨ q) ≡ (p ↓ q) ↓ (p ↓ q) $$

Úloha 4.5

$$ (p ∧ q) ≡ (p ↑ q) ↑ (p ↑ q) $$

Úloha 4.6

$$ (p ∨ q) ≡ (p ↑ p) ↑ (q ↑ q) $$

Krok 5: Prepíšte nasledujúce tvrdenia v prirodzenom jazyku do formúl výrokovej logiky a rozhodnite či formula pod čiarou je dôsledkom formúl nad čiarou.

Úloha 5.1

  Ak mám peniaze, tak si kúpim auto. 
  Peniaze mám. 
  ----------------------------------------------
  Kúpim si auto.

Úloha 5.2

  Ak je Svätopluk učiteľ, tak je múdry. 
  Svätopluk je múdry. 
  ----------------------------------------------
  Svätopluk je učiteľ.

Úloha 5.3

  Ak je zamračené a nezoberiem si dáždnik, zmoknem. 
  Nezoberiem si dáždnik. 
  ----------------------------------------------
  Zmoknem.

Úloha 5.4

  Budem inžinier z informatiky ak urobím skúšku. 
  Urobím skúšku ak urobím zápočet
  Urobím zápočet ak nebudem lenivý. 
  ----------------------------------------------
  Budem inžinier ak nebudem lenivý.

Úloha 5.5

  Ak budem veľa cestovať, tak navštívim veľa krajín. 
  Ak navštívim veľa krajín, tak spoznám veľa ľudí. 
  Ak spoznám veľa ľudí, tak budem mať veľa priateľov.
  ----------------------------------------------
  Ak budem veľa cestovať, budem mať veľa priateľov.

Úloha 5.6

  Ak sa Argentína pripojí k aliancii, potom Brazília alebo Chile ju budú bojkotovať.
  Ak sa Ekvádor pripojí k aliancii, potom Chile alebo Peru ju budú bojkotovať.
  Chile nebojkotuje alianciu.
  ----------------------------------------------
  Ak ani Brazília ani Peru nebojkotujú alianciu, tak sa ani Argentína ani Ekvádor nepripoja k aliancii.

Krok 6: Úloha: štyria priatelia.

Úloha 6.1

Štyria priatelia sa rozhodli, že strávia spoločne deň. Keďže sú pohádaní, každý si začal klásť podmienky.

  1. Vasil: "Pôjdem, ak nepôjde Ľudovít a pôjde František a zároveň pôjdem práve vtedy, keď nepôjde Konrád."

  2. František: "Pôjdem, ak nepôjde Konrád alebo pôjdem, ak pôjde Vasil."

  3. Ľudovít: "Ak pôjdem, musí ísť Vasil a František."

  4. Konrád: "Ak nepôjde František, tak pôjdem, ak pôjde Ľudovít."

Rozhodnite v akých zloženiach môžu stráviť deň.