U výroků nás přirozeně zajíma jejich pravdivostní hodnota – tedy zda jsou pravdivé, nebo nepravdivé. Pravdivost složených (složitějších) výroků vyhodnocujeme v závislosti na pravdivostním ohodnocení prvotních výroků, z nichž jsou složeny. Při vyhodnocování postupujeme od prvotních výroků, přes složené podformule, až po celou výslednou formuli („zevnitř ven“). Řídíme se při tom pravidly pro určování pravdivosti výroků, které vznikly spojením jednodušších výroků pomocí logických spojek, jejich negací, nebo přidáním kvantifikátorů.
V závislosti na pravdivostním ohodnocení prvotních výroků $A$ a $B$ jsou pravdivostní hodnoty výroků $\neg A$, $A \wedge B$, $A \vee B$, $A \Rightarrow B$ a $A \Leftrightarrow B$ dány následující tabulkou (symbol $1$ standardně označuje pravdivost a $0$ nepravdivost).
| \(A\) | \(B\) | \(\neg A\) | \(A \wedge B\) | \(A \vee B\) | \(A \Rightarrow B\) | \(A \Leftrightarrow B\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Pokud je $A(x)$ výrok závisející na proměnné $x$ z jisté množiny, potom výrok
$(\forall x)\,A(x)$ je pravdivý právě tehdy když je výrok $A(x)$ pravdivý po dosazení libovolné (každé) hodnoty za $x$ z dané množiny,
$(\exists x)\,A(x)$ je pravdivý právě tehdy když existuje (alespoň jedna) hodnota v dané množině, jejímž dosazením za $x$ se stane výrok $A(x)$ pravdivý.
Tato pravidla demonstrujeme na velmi jednoduchých příkladech:
$(\forall x\in\R)((x\geq 0)\wedge (x\leq 0))$ – nepravdivý výrok (stačí dosadit jakékoli nenulové reálné číslo),
$(\exists x\in\R)((x\geq 0)\wedge (x\leq 0))$ – pravdivý výrok (platí pro nulu),
$(\forall x\in\R)((x\geq 0)\vee (x\leq 0))$ – pravdivý výrok (pro nenulové reálné číslo platí vždy jedna z možností, pro nulu obě).
Mnohá tvrzení lze vyjádřit různými výroky, tj. syntakticky různými formulemi. Například výroky „Číslo $m$ je kladné a sudé“ a „Číslo $m$ je sudé a kladné“ mají odlišnou formu, ale stejný obsah. Nebo výroky „Světlo svítí právě tehdy když je vypínač nahoře“ a „Světlo nesvítí právě tehdy když je vypínač dole“ jsou zjevně významově stejné. Jak tento fakt vystihnout? Řekneme, že dva výroky jsou logicky ekvivalentní právě tehdy když jeden je pravdivý tehdy a jen tehdy (tj. pro stejné pravdivostní ohodnocení obsažených prvotních výroků) když je pravdivý ten druhý. Vyšetřování logické ekvivalence výroků je důležitá část logiky a podrobněji se jí budeme věnovat v kurzu BI DML.21. Umožňuje ověřit sémantickou shodu dvou výroků, najít nejstručnější zápis tvrzení, nebo takovou jeho formulaci, ze které se snadno určí, zda je pravdivé. Často využívané logické ekvivalence jsou vysloveny v tzv. logických zákonech. Nyní si uvedeme pouze jeden:
Nechť $A$ a $B$ jsou libovolné výroky. Potom výrok $A\Rightarrow B$ je logicky ekvivalentní výroku $\neg B\Rightarrow \neg A$.
Potřebujeme ověřit, že pro každé pravdivostní ohodnocení výroků $A$ a $B$ budou mít výroky $A\Rightarrow B$ a $\neg B\Rightarrow \neg A$ navzájem stejnou pravdivostní hodnotu. Provedeme to zapsáním všech pravdivostných hodnot do tzv. pravdivostní tabulky a porovnáním hodnot v posledních dvou sloupcích:
| \(A\) | \(B\) | \(\neg A\) | \(\neg B\) | \(A \Rightarrow B\) | \(\neg B \Rightarrow \neg A\) |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 |
$\square$
Nahrazení formule $A\Rightarrow B$ formulí $\neg B\Rightarrow \neg A$ také nazýváme obměna implikace. Tento postup se používá při nepřímém důkazu tvrzení, které je v podobě implikace (viz Poznámka 3.5).