Podle definice je negace výroku $A$ výrok $\neg A$, který je pravdivý právě tehdy když je $A$ nepravdivý. Je to tedy tvrzení, které má „opačný význam“ než tvrzení $A$ („logický opak“ tvrzení $A$). Tabulka 13.1 shrnuje, jak vypadá negace výroku $F$ získaného spojením výroků $A$ a $B$ pomocí jednotlivých logických spojek.
| $F$ | $\neg F$ |
|---|---|
| $A\wedge B$ | $\neg A\vee \neg B$ |
| $A\vee B$ | $\neg A\wedge \neg B$ |
| $A\Rightarrow B$ | $A\wedge \neg B$ |
| $A\Leftrightarrow B$ | $\neg A\Leftrightarrow B$ |
| $\neg A$ | $A$ |
Tabulka 13.1: Negace.
Podobně jako v důkazu Věty 13.1 se platnost vztahů uvedených v tabulce snadno ověří pomocí pravdivostní tabulky. Stačí ukázat, že pro všechna možná pravdivostní ohodnocení výroků $A$ a $B$ mají výroky $F$ a $\neg F$ opačnou pravdivostní hodnotu. Výroky v tabulce lze samozřejmě nahradit logicky ekvivalentními výroky.
Dále si připomeneme, jaká je negace výroků s kvantifikátory. To, že nějaké tvrzení $A(x)$ platí pro všechna $x$ (z množiny $M$) není pravda právě tehdy když existuje nějaké $x$ (z množiny $M$), pro které $A(x)$ neplatí. Naopak, to, že nějaké tvrzení $A(x)$ platí pro alespoň jedno $x$ (z množiny $M$) není pravda právě tehdy když $A(x)$ neplatí pro žádné $x$ (z množiny $M$). Symbolicky tyto vztahy popisuje tabulka 13.2.
| $F$ | $\neg F$ |
|---|---|
| $(\forall x)A(x)$ | $(\exists x)\neg A(x)$ |
| $(\exists x)A(x)$ | $(\forall x)\neg A(x)$ |
Tabulka 13.2: Negace s kvantifikátory.
Když chceme najít takovou formuli negace složeného výroku, kde symbol negace stojí pouze (případně) před prvotními výroky, postupujeme „z vnějšku dovnitř“ – od celého výroku postupně přes podformule k prvotním výrokům. Ukážeme si to na příkladě.
Uvažujme výrok „Každé přirozené číslo, které je ostře větší než $1$, má prvočíselného dělitele“. Označíme-li $p(m)$ predikát „$m$ je prvočíslo“, potom tento výrok můžeme zapsat formulí
Nyní vyjádříme jeho negaci několika (logicky ekvivalentními) výroky. Na uvedené posloupnosti výroků demonstrujeme, jak postupně aplikovat pravidla pro negaci od výsledného složeného výroku až po prvotní:
$\neg\,(\forall m\in \N)\,(m>1\Rightarrow (\exists k\in\N)(p(k)\wedge k|m))$
$(\exists m\in \N)\,\neg\,(m>1\Rightarrow (\exists k\in\N)(p(k)\wedge k|m))$
$(\exists m\in \N)\,(m>1\,\wedge\, \neg\, (\exists k\in\N)(p(k)\wedge k|m))$
$(\exists m\in \N)\,(m>1\,\wedge\, (\forall k\in\N)\, \neg\, (p(k)\wedge k|m))$
$(\exists m\in \N)\,(m>1\,\wedge\, (\forall k\in\N)\, (\neg p(k)\vee k\nmid m))$
kde $k\nmid m$ značí predikát $k$ nedělí $m$. V přirozeném jazyce bychom tedy negaci přečetli jako „Existuje přirozené číslo $m$ ostře větší než $1$ takové, že každé přirozené číslo není prvočíslo nebo nedělí $m$“. Pokud si navíc uvědomíme, že $\neg\, (p(k)\wedge k|m)$ je logicky ekvivalentní výroku $\neg\,\neg\, (p(k)\Rightarrow k\nmid m)$, a tedy i výroku $p(k)\Rightarrow k\nmid m$, získáme ještě přirozenější formulaci „Existuje přirozené číslo ostře větší než $1$ takové, že ho nedělí žádné prvočíslo“. (Toto znění negace bychom jistě uměli odvodit již z původního tvrzení bez použití formalizace.)