Výroková a predikátová logika

Vyřešíme pomocí pravdivostní tabulky 2, ve které ověřujeme první vztah. Druhý se dokáže obdobně. Zobecnění vztahů pro konečnou množinu výroků $\set{B, A_1, \dots, A_n}$ mají tvar

$$\left( \bigwedge_{ i = 1 }^n A_i \right) \vee B \iff \bigwedge_{i=1}^n \left( A_i \vee B \right), \qquad \left( \bigvee_{ i = 1 }^n A_i \right) \wedge B \iff \bigvee_{i=1}^n \left( A_i \wedge B \right).$$

$A$	$B$	$C$	$B \wedge C$	$A \vee B$	$A \vee C$	$A \vee (B \wedge C)$	$(A \vee B) \wedge (A \vee C)$
$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$

Tabulka 2: Pravdivostní tabulka pro příklad 2.1.

□

Vyřešíme pomocí pravdivostní tabulky 3, ve které ověřujeme první vztah. Druhý se dokáže obdobně. Zobecnění vztahů pro konečnou množinu výroků $\set{A_1, \dots, A_n}$ mají tvar

$$\neg \left( \bigwedge_{i=1}^n A_i \right) \iff \bigvee_{i=1}^n \neg A_i, \qquad \neg \left( \bigvee_{i=1}^n A_i \right) \iff \bigwedge_{i=1}^n \neg A_i.$$

$A$	$B$	$\neg A$	$\neg B$	$A \wedge B$	$\neg (A \wedge B)$	$(\neg A \vee \neg B)$
$0$	$0$	$1$	$1$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$0$	$1$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$1$
$1$	$1$	$0$	$0$	$1$	$0$	$0$

Tabulka 3: Pravdivostní tabulka pro příklad 2.2.

□

Vyřešíme pravdivostní tabulkou 4.

$A$	$B$	$\neg A$	$\neg B$	$A\wedge \neg B$	$A \implies B$	$\neg B \implies \neg A$	$\neg (A \wedge \neg B)$	$\neg A \vee B$
$0$	$0$	$1$	$1$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$1$	$1$	$1$	$1$

Tabulka 4: Pravdivostní tabulka pro příklad 2.3.

□

Na uzávorkování záleží. Kdybychom závorky rozmístili jinak, například $A \wedge (B \vee \neg A) \wedge \neg B$, dostali bychom kontradikci: muselo by platit $A$ i $\neg B$, jenže pak je prostřední závorka nepravdivá.

Výsledek plyne z následující série úprav

$$\begin{aligned} (A \wedge B) \vee (\neg A \wedge \neg B) & \iff [A \vee (\neg A \wedge \neg B)] \wedge [B \vee (\neg A \wedge \neg B)] \iff \\ & \iff [(A \vee \neg A) \wedge (A \vee \neg B)] \wedge [(B \vee \neg A) \wedge (B \vee \neg B)] \iff \\ & \iff (A \vee \neg B) \wedge (B \vee \neg A) \iff \\ & \iff (B \implies A) \wedge (A \implies B) \iff \\ & \iff (A \iff B), \end{aligned}$$

kde první dvě ekvivalence plynou z distributivního zákona, třetí je důsledek toho, že $(A \vee \neg A)$ a $(B \vee \neg B)$ jsou tautologie, čtvrtá je přepis implikace a pátá definice ekvivalence.

□

Pomocí distributivního zákona:

$$\begin{aligned} (A \wedge B) \vee \neg B \iff (A \vee \neg B) \wedge (B \vee \neg B) \iff (A \vee \neg B) \iff (B \implies A). \end{aligned}$$

Druhá ekvivalence plyne z faktu, že $(B \vee \neg B)$ je tautologie, a poslední ekvivalence je definicí implikace.

□

• Vyřešíme tranzitivitu implikace, tj. ptáme se, zda je tautologií výrok

  $$\left[(A \implies B) \wedge (B \implies C) \right] \implies (A \implies C) .$$

  Celou implikaci přepíšeme podle vztahu $(P \implies Q) \iff (\neg P \vee Q)$, kde $P$ je hranatá závorka a $Q$ je $(A \implies C)$. Použijeme-li ještě De Morganovo pravidlo a negaci implikace, dostaneme

  $$\left[ (A \wedge \neg B) \vee (B \wedge \neg C) \right] \vee (\neg A \vee C),$$

  neboli bez hranatých závorek

  $$(A \wedge \neg B) \vee (B \wedge \neg C) \vee \neg A \vee C.$$

  Tento výrok je vždy pravdivý (jde tedy o tautologii), protože aspoň jeden ze čtyř členů disjunkce vyjde vždy pravdivý, viz pravdivostní tabulka 5. Poslední sloupec tabulky je výsledná disjunkce. Lze to dokázat i jinak, další aplikací distributivního zákona.

  $A$	$B$	$C$	$\neg B$	$\neg C$	$A \wedge \neg B$	$B \wedge \neg C$	$\neg A \lor C$	celkem
  $0$	$0$	$0$	$1$	$1$	$0$	$0$	$1$	$1$
  $0$	$0$	$1$	$1$	$0$	$0$	$0$	$1$	$1$
  $0$	$1$	$0$	$0$	$1$	$0$	$1$	$1$	$1$
  $0$	$1$	$1$	$0$	$0$	$0$	$0$	$1$	$1$
  $1$	$0$	$0$	$1$	$1$	$1$	$0$	$0$	$1$
  $1$	$0$	$1$	$1$	$0$	$1$	$0$	$1$	$1$
  $1$	$1$	$0$	$0$	$1$	$0$	$1$	$0$	$1$
  $1$	$1$	$1$	$0$	$0$	$0$	$0$	$1$	$1$

  Tabulka 5: Pravdivostní tabulka pro příklad 2.6.

• Nyní se podíváme na tranzitivitu ekvivalence, kterou můžeme zapsat následovně:

  $$\left[ (A \iff B) \wedge (B \iff C) \right] \implies (A \iff C).$$

  Stačí ukázat, že kdykoli je pravdivá levá strana, je pravdivá i pravá. Předpokládejme tedy, že platí obě ekvivalence. Každou z nich rozepíšeme na dvojici implikací, platí tedy všechny čtyři implikace

  $$\textcolor{red}{(A \implies B)} \wedge \textcolor{blue}{(B \implies A)} \wedge \textcolor{red}{(B \implies C)} \wedge \textcolor{blue}{(C \implies B)}.$$

  Z červeně vyznačených implikací $A \implies B$ a $B \implies C$ plyne podle právě dokázané tranzitivity implikace $A \implies C$. Stejně z modře vyznačených implikací $C \implies B$ a $B \implies A$ plyne $C \implies A$. Platí tedy

  $$(A \implies C) \wedge (C \implies A),$$

  což je přesně ekvivalence $A \iff C$. Tím je důkaz hotov.

□

Negujeme vždy podle toho, co je ve výroku hlavní spojkou nebo kvantifikátorem.

1. Výrok má tvar implikace $(A \wedge B) \implies C$. Negací implikace není implikace, ale konjunkce:

   $$\neg (X \implies Y) \quad\iff\quad X \wedge \neg Y.$$

   Předpoklad tedy zůstává a závěr se neguje: „Bude hezky a budu mít čas a nepůjdu si zaběhat.“

2. Hlavní je existenční kvantifikátor. Jeho negací je kvantifikátor obecný s negovaným vnitřkem, tedy „Každý člověk je vysoký jinak než 2 metry“, jinými slovy „Žádný člověk není vysoký 2 metry“.

3. Postupujeme zleva doprava, každý kvantifikátor nahradíme opačným a nakonec znegujeme vnitřní nerovnost:

   $$(\exists \varepsilon > 0)(\forall n_0 \in \N)(\exists n \in \N, n>n_0)\,(|a_n-a| \geq \varepsilon).$$

   Všimněte si, že podmínky u kvantifikátorů, tedy $\varepsilon > 0$ a $n > n_0$, se nemění. Negujeme samotný výrok, nikoli obor, přes který se kvantifikuje.

□

První tři výroky jsou přímočarým přepisem, u negace vždy jen vyměníme každý kvantifikátor za opačný a znegujeme vnitřní výrok. U třetího bodu si uvědomte, že „existují dvě čísla“ nevylučuje, aby byla stejná.

Zajímavější je poslední bod. Kvantifikátor $\exists!$ („existuje právě jedno“) totiž není základní, a než ho začneme negovat, musíme ho rozepsat na existenci a jednoznačnost:

$$(\exists! m \in \N)\,\big(V(m)\big) \quad\iff\quad (\exists m \in \N)\,\Big( V(m) \wedge (\forall k \in \N)\,\big(V(k) \implies k = m\big) \Big).$$

Teprve tento tvar umíme znegovat běžnými pravidly. Výsledkem je disjunkce dvou situací: buď žádné vyhovující $m$ neexistuje, nebo naopak existují aspoň dvě různá.

Dodejme, že samotné tvrzení ze čtvrtého bodu neplatí. Například pro $n = 10$ už žádné přirozené $m$ se součtem $10$ neexistuje.

□

1. Slovo „i“ spojuje dvě tvrzení o témže čísle, jde tedy o konjunkci. Její negací je disjunkce s negovanými členy.
2. Výrok obsahuje tři kvantifikátory za sebou a při negaci se všechny obrátí. Pořadí přitom zůstává zachováno.
3. Spojení „je-li liché“ je předpokladem implikace, lichost zapisujeme jako $2 \nmid n$. Negace implikace opět dá konjunkci předpokladu a negovaného závěru.
4. Zde je potřeba dát pozor na to, že v české větě nejsou proměnné vidět. Vystupují v ní tři, $a$, $b$ i násobek, který musíme zapsat jako $cb$ pro libovolné celé $c$. Všechny tři je nutné okvantifikovat. Přesněji řečeno věta říká $(\forall a, b \in \Z)\,\big(a \mid b \implies (\forall c \in \Z)\,(a \mid cb)\big)$. Výrok $a \mid b$ ale proměnnou $c$ neobsahuje, a kvantifikátor $\forall c$ proto můžeme podle pravidel pro kvantifikaci složených výroků vytknout před celou implikaci.

□

Klíčové je rozlišit, přes co se kvantifikuje.

1. „Obsahuje jen druhé mocniny“ je tvrzení o prvcích množiny $M$: každý z nich musí být druhou mocninou. Kvantifikujeme proto přes $M$. Neříká se nic o tom, že by v $M$ musely být všechny, podmínku tak splňuje i prázdná množina.
2. „Obsahuje všechny druhé mocniny“ je naopak tvrzení o přirozených číslech: ke každému $n$ musí $n^2$ v $M$ ležet. Kvantifikujeme tedy přes $\N$. Množina $M$ přitom může obsahovat i další prvky.
3. „Právě jen všechny“ znamená obojí zároveň, jde tedy o konjunkci obou předchozích tvrzení.
4. Čtvrtý bod říká přesně totéž co třetí, jen jinými slovy. Můžeme ho proto zapsat rovnou pomocí množinového zápisu jako $M = \set{n^2 \mid n \in \N}$.

□

1. Věta sice mluví o jediném $a$, ve skutečnosti jde ale o tvrzení o všech reálných číslech, proměnnou je proto potřeba okvantifikovat. Hlavní spojkou je implikace a její negací je konjunkce předpokladu s negovaným závěrem.

2. Ekvivalenci zapíšeme jako dvojici implikací,

   $$X \iff Y \quad\iff\quad (X \implies Y) \wedge (Y \implies X).$$

   Negací konjunkce je disjunkce, dostaneme tedy dvě možnosti: buď platí $X$ a neplatí $Y$, nebo naopak.

3. Slovní popis stačí přepisovat kvantifikátor po kvantifikátoru přesně v tom pořadí, v jakém je ve větě. Jde o definici konvergence posloupnosti, jejíž negaci jste už psali dříve v této kapitole.

□

Žádný z výroků neplatí.

1. $(\exists x,y \in \R)\,(x^2 + y^2 \leq 0)$, platí negace pro $x = y = 0$.
2. $(\exists x \in \R)(\forall y \in \N)\,( (y > x) \vee (y+1 \leq x) )$, platí negace například pro $x = -1$. Nebo si stačí uvědomit, že $y$ je přirozené číslo, takže pokud zvolíme $x <1$, pak výrok $(y \leq x)$ nebude platit nikdy, a musí tedy platit jeho negace.
3. $(\exists \varepsilon > 0)(\forall \delta >0)(\exists x \in \R)\,(0 < |x-1| < \delta \wedge |x-3| \geq \varepsilon)$.

Dokázat negaci třetího výroku je obtížnější. Zkusme např. $\varepsilon = 1$. Výrok přejde na tvar

$$(\forall \delta > 0)(\exists x \in \R)\,(0 < |x-1 | < \delta \wedge |x-3| \geq 1).$$

Důležité je uvědomit si geometrický význam absolutní hodnoty, viz obrázek 3. Obecně pro $a,b,c \in \R$ výraz $|a-b| > c$ znamená, že číslo $a$ je od $b$ vzdáleno o více než $c$. V našem případě máme $|x-3| \geq 1$, tedy číslo $x$ musí být od $3$ vzdáleno alespoň o $1$. Lze tedy psát

$$\begin{aligned} |x-3| \geq 1 \iff x \in (-\infty,2\rangle \cup \langle4,+\infty). \end{aligned}$$

Výrok tedy můžeme přepsat na

$$\begin{aligned} (\forall \delta > 0)(\exists x \in \R)\,(0 < |x-1 | < \delta \wedge x \in (-\infty,2 \rangle \cup \langle 4,+\infty)) \end{aligned}$$

či na

$$\begin{aligned} (\forall \delta > 0)(\exists x \in (-\infty,2 \rangle \cup \langle 4,+\infty))\,(x \in (1-\delta, 1+\delta) \setminus \set{1}). \end{aligned}$$

Nyní již přejdeme k volbě $x$. Nepřítel předhodí libovolné $\delta > 0$. Pro každé jeho $\delta$ můžeme zvolit $x = 1-\frac{\delta}{2}$. Ověříme, zda jsme zvolili dobře. Zřejmě máme

$$\begin{aligned} 1-\frac{\delta}{2} \in (1-\delta, 1+\delta) \setminus \set{1} & \text{, protože } (\forall \delta > 0)\,\left(0< \frac{\delta}{2} < {\delta}\right), \\ 1-\frac{\delta}{2} \in (-\infty,2 \rangle \cup \langle 4,+\infty) & \text{, protože } (\forall \delta > 0)\,\left(1 - \frac{\delta}{2} < 2\right). \end{aligned}$$

Obrázek 3: Geometrický význam třetího výroku v příkladu 2.12. Z obrázku je patrné, že lze volit $\varepsilon \in (0,2)$, neboť pro taková zůstane bod $x = 3-\varepsilon$ napravo od $1$.

□