Výroková logika


Výroky

Výrok = každé tvrzení, o kterém má smysl prohlásit, zda je, či není pravdivé

Značíme malými písmeny: v,v1,v2,...v, v_1, v_2, ...

Hypotéza = výrok, o kterém zatím nevíme, zda je pravdivý

Pravdivostní hodnota výroku:

  • Pravdivý výrok p(v)=1\Rightarrow p(v) = 1
  • Nepravdivý výrok p(v)=0\Rightarrow p(v) = 0

Např.

v1: Cˇıˊslo 17 je sudeˊ.  p(v1)=0  v2: Rovnice x2+5x=0 maˊ v R rˇesˇenıˊ.  p(v2)=1v_1 \mathord: \space \text{Číslo 17 je sudé.} \\~\\~ p(v_1) = 0 \\~\\~ v_2 \mathord: \space \text{Rovnice } x^2 + 5x = 0 \text{ má v } \R \text{ řešení.} \\~\\~ p(v_2) = 1

Negace

Negace výroku vv = výrok, který vylučuje platnost vv

Značka: ¬\neg

Např.

v1: Venku prsˇıˊ.  ¬v1: Venku neprsˇıˊ.  v2: 2+2=4  ¬v2: 2+24  v3: 2+2<4  ¬v3: 2+24v_1 \mathord: \space \text{Venku prší.} \\~\\~ \neg v_1 \mathord: \space \text{Venku neprší.} \\~\\~ v_2 \mathord: \space 2 + 2 = 4 \\~\\~ \neg v_2 \mathord: \space 2 + 2 \neq 4 \\~\\~ v_3 \mathord: \space 2 + 2 < 4 \\~\\~ \neg v_3 \mathord: \space 2 + 2 \geq 4

Výrok a jeho negace mají vždy opačné pravdivostní hodnoty

vv¬v\neg v
1100
0011

Složené výroky

Složený výrok = výrok, který vznikne spojením dvou a více výroků logickými spojkami

KonjunkceDisjunkceImplikaceEkvivalence
\land\lor    \implies    \iff
a (zároveň)nebo (nevylučovací)jestliže ..., pakprávě tehdy, když
uuvvuvu \land vuvu \lor vu    vu \implies vu    vu \iff v
111111111111
110000110000
001100111100
000000001111

Tautologie = vždy pravdivý výrok
Kontradikce = vždy nepravdivý výrok

Obměněná implikace:

ab  ¬b¬aa \Rightarrow b \\~\\~ \neg b \Rightarrow \neg a

Obrácená implikace:

ab  baa \Rightarrow b \\~\\~ b \Rightarrow a

Negace složených výroků

¬(ab)    (¬a¬b)  ¬(ab)    (¬a¬b)  ¬(a    b)    (a¬b)  ¬(a    b)    (¬a    b)    (a    ¬b)    (¬ab)(a¬b)\neg (a \land b) \iff (\neg a \lor \neg b) \\~\\~ \neg (a \lor b) \iff (\neg a \land \neg b) \\~\\~ \neg (a \implies b) \iff (a \land \neg b) \\~\\~ \neg (a \iff b) \iff (\neg a \iff b) \iff (a \iff \neg b) \iff (\neg a \land b) \lor (a \land \neg b)

Kvantifikované výroky

Kvantum (lat.) = množství

Udávají množství objektů, kterých se výrok týká

Použití kvantifikátorů

Kvantifikátory

  1. Obecný výrok
    \rightarrow Každý, všechno, pro každý, pro všechna, ...
     xM: V\forall \space x \in M{:} \space V
    = Pro každé xx z množiny MM platí VV
    Např.

     xR: x20   nN: 9n    3n\forall \space x \in \R{:} \space x^2 \ge 0 \\~\\~ \forall \space n \in \N{:} \space 9 \mid n \implies 3 \mid n
  2. Existenční výrok
    \rightarrow existuje aspoň jeden, ...
     xM: V\exists \space x \in M{:} \space V
    = Existuje xx z množiny MM, pro které platí VV
    Např.

     xN: xN   aZ: a+3N\exists \space x \in \N{:} \space \sqrt{x} \notin \N \\~\\~ \exists \space a \in \Z{:} \space a + 3 \in \N

Negace kvantifikovaných výroků

¬( xM: V)    ( xM: ¬V)  ¬( xM: V)    ( xM: ¬V)\neg (\forall \space x \in M{:} \space V) \iff (\exists \space x \in M{:} \space \neg V) \\~\\~ \neg (\exists \space x \in M{:} \space V) \iff (\forall \space x \in M{:} \space \neg V)

Ostatní kvantifikované výroky

Pro právě kk prvků z množiny MM platí VV.
Pro nejvýše kk prvků z množiny MM platí VV.
Pro alespoň kk prvků z množiny MM platí VV.

Např.

Rovnice x216=0 maˊ praˊveˇ 2 korˇeny.  V libovolneˊ je nejvyˊsˇe 1 uˊhel pravyˊ.  Existujıˊ alesponˇ 3 lichaˊ cˇıˊsla, kteraˊ jsou deˇliteli cˇıˊsla 100.\text{Rovnice } x^2 - 16 = 0 \text{ má právě 2 kořeny.} \\~\\~ \text{V libovolném } \triangle \text{ je nejvýše 1 úhel pravý.} \\~\\~ \text{Existují alespoň 3 lichá čísla, která jsou děliteli čísla 100.}

Negace:

Nejvýše kk \to alespoň k+1k + 1
Alespoň kk \to nejvýše k1k - 1
Právě kk \to nejvýše k1k - 1 nebo alespoň k+1k + 1