Zopakujte si základní logické operátory (spojky) a vztahy mezi nimi.
Nejjednoduššími - unárními - logickými operátory jsou negace a aserce. Aserce "nedělá nic" a zavádí se spíš z formálních důvodů. Pravdivostní tabulky tedy jsou:
$X$ $X$ (aserce X) 0 0 1 1 $X$ $\neg X$ (negace X) 0 1 1 0 V programování se logická negace obvykle značí NOT, ! apod. Často se používá jako bitový operátor, tj. provedení několika logických negací v bajtu (či několika bajtech) najednou. Například:
~ 00100101 = 11011010
(Pro přehlednost jsme vynechali prefix 0b indikující binární číslo.)
Logický součin (logické "a") $X\land Y$ výroků X a Y je pravdivý jen tehdy, jsou-li pravdivé X a Y současně. Pokud chcete studené pivo, potřebujete splnění obou podmínek současně: teplé pivo, studená kofola ani teplá kofola vám radost neudělají. Pravdivostní tabulka je tedy:
$X$ $Y$ $X\land Y$ 0 0 0 0 1 0 1 0 0 1 1 1 V programování se logický součin obvykle značí AND, && apod. Často se používá jako bitový operátor, tj. provedení několika logických součinů v bajtu (či několika bajtech) najednou. Například:
00100101 & 11111100 = 00100100
Všimněme si, že logický součin se používá pro nulování bitů: bity, které jsou v druhém operandu nulové, se ve výsledku vynulují, hodnota ostatních je nezměněna.
Logický součet (logické "nebo") $X\lor Y$ výroků X a Y je pravdivý tehdy, je-li pravdivý alespoň jeden z výroků X a Y. Pokud jste mladiství nebo silně podnapilí, v hospodě vám pivo nenatočí. Pokud přijde opilý puberťák, tím spíš nic nedostane. Pravdivostní tabulka je tedy:
$X$ $Y$ $X\lor Y$ 0 0 0 0 1 1 1 0 1 1 1 1 Měli bychom si všimnout, že v běžném jazyce se spojky "a" a "nebo" často používají jinak, než jak jsou zavedeny ve formální logice. V hospodě spíš najdete cedulku "mladistvým a podnapilým nenaléváme" než technicky správnější "mladistvým nebo podnapilým nenaléváme". Mimochodem, i tato drobnost komplikuje úlohu, jak má počítač porozumět přirozené řeči. Také proto se používání logických spojek v aplikacích "pro prostý lid" (jako třeba různé vyhledávače) spíš nedoporučuje, protože nepoučený uživatel je obvykle neumí používat.
V programování se logický součet obvykle značí OR, || apod. Často se používá jako bitový operátor, tj. provedení několika logických součtů v bajtu (či několika bajtech) najednou. Například:
00100101 | 00000011 = 00100111
Všimněme si, že logický součin se používá pro nastavení bitů na 1: bity, které jsou v druhém operandu jedničkové, se nastaví na 1, hodnota ostatních je nezměněna.
Implikace (vyplývání) $X\implies Y$ je spojka, jejíž pravdivostní tabulka činí nejvíc problémů. Zkusme si proto rozebrat pravdivost výroku "pokud prší, je mokro"; zanedbejme přitom nedokonalosti přirozené řeči, tj. nebudeme řešit, zda tři kapky znamená "prší" a podobně.
Označme si výrok "prší" jako $X$, výrok "je mokro" jako $Y$. Pravdivost výroku $X\implies Y$ posoudíme následovně: když někdo řekne "pokud prší, je mokro", označíme ho za lháře a výrok za nepravdivý, nebo ne?
Pokud prší ($X=1$) a zjistíme, že je mokro ($Y=1$), nemůžeme o mluvčímu říct, že se mýlí. Výrok $X\implies Y$ považujeme za pravdivý.
Pokud prší ($X=1$), ale jindy zjistíme, že je sucho ($Y=0$), musel se mluvčí zmýlit. Výrok $X\implies Y$ považujeme za nepravdivý.
Až potud nebývají problémy. Otázkou je, jak vyhodnotit pravdivost výroku $X\implies Y$ v případě, že $X$ neplatí, tj. zrovna neprší. Zkusme si proto vyjádřit tvrzení jinak.
Výrok "pokud prší, je mokro" můžeme alternativně formulovat jako "nemůže se stát, že by pršelo a současně bylo sucho", tj. výrok $X\implies Y$ jsme vyjádřili jako $\neg(X\land \neg Y)$. Pravdivostní tabulku totoho výroku budeme považovat za pravdivostní tabulku implikace:
$X$ $Y$ $X\implies Y$
$=\neg(X\land \neg Y)$0 0 1 0 1 1 1 0 0 1 1 1 Logická implikace je pouhou spojkou mezi dvěma výroky. Na rozdíl od přirozeného jazyka ale $X\implies Y$ neznamená, že by z $X$ šlo odvodit $Y$, nebo že by mezi nimi byla jakákoliv souvislost. Ještě tak nejlépe se implikace a její pravdivostní ohodnocení dá přirovnat k sázce: "($X$) jestli sníš za hodinu padesát vajec, $(Y)$ je tahle hromada peněz tvoje". Jen v případě nevyplacení výhry ($X=1$, $Y=0$) označíme autora výroku za lháře.
V běžném imperativním programování se logická implikace obvykle nevyužívá.
-
Ekvivalence $X\iff Y$ je pravdivá tehdy, je-li pravdivost $X$ i $Y$ stejná. Z pohledu logiky jsou výroky $X$ a $Y$ zaměnitelné; neříká se ale, že jsou stejné. Pravdivostní tabulka je tedy:
$X$ $Y$ $X\iff Y$ 0 0 1 0 1 0 1 0 0 1 1 1 Znak ekvivalence $\iff$ je jen zkratkou za "$\implies$ a současně $\impliedby$", čili $(X\implies Y)\land(Y\implies X)$. Také se říká "$X$ platí tehdy a jen tehdy, když platí $Y$".
V běžném imperativním programování se logická ekvivalence obvykle nevyužívá.
Nonekvivalence $X\kern8pt\not\kern-8pt\iff Y$ je pouhou negací ekvivalence, tj. pravdivostní tabulka je:
$X$ $Y$ $X\kern8pt\not\kern-8pt\iff Y$ 0 0 0 0 1 1 1 0 1 1 1 0 Nonekvivalenci se někdy říká exkluzivní součet, přičemž slovo "exkluzivní" neznamená ani tak "výjimečný", jako opak "inkluzivní" - funguje stejně jako logický součet až na případ, kdy jsou $X$ i $Y$ pravdivé současně. V přirozeném jazyce se nonekvivalence používá často: když požádáte "přineste mi kávu nebo čaj", asi se budete divit, když dostanete obojí.
Rovněž si můžeme všimnout, že pravdivostní tabulka je stejná jako operace sčítání v tělesu $\mathbb{Z}_2$, tj. v aritmetice modulo 2.
V programování se nonekvivalence obvykle značí XOR. Často se používá jako bitový operátor, tj. provedení několika logických nonekvivalencí v bajtu (či několika bajtech) najednou. Například:
00100101 | 00000011 = 00100110
Všimněme si, že nonekvivalence se používá pro negování bitů: bity, které jsou v druhém operandu jedničkové, se negují, hodnota ostatních je nezměněna.
- V praxi jsou velmi důležité funkce "negace logického součtu" (NOR) a "negace logického součinu" (NAND), protože se s nimi snadno konstruují složité logické výrazy. Používají se zejména v elektronice, proto jsou logické obvody NAND a NOR asi ty nejobvyklejší. V běžném programování se s nimi obvykle nesetkáme.
Pro logický součet a logický součin platí De Morganova pravidla:
- $\neg(X \land Y) = \neg X \lor \neg Y$
- $\neg(X \lor Y) = \neg X \land \neg Y$
V praxi se De Morganova pravidla využivají často - například tehdy, potřebujeme-li zpřehlednit zápis komplikované podmínky.
Ukázka: dejme tomu, že hodnota reálného čísla "x" může být libovolná, a pokud není z intervalu 0 až 5 ani z intervalu 10 až 15, má se provést nějaký příkaz. Obvykle je pohodlnější napsat pozitivní podmínku (je z intervalu 0 až 5 nebo z intervalu 10 až 15) a poté ji znegovat:
if (!((x >= 0 && x <= 5) || (x >= 10 && x <= 15))) { ... }Podmínku přepíšeme na logický výraz
$$\neg((A \land B) \lor (C \land D))$$
Použijeme druhé De Morganovo pravidlo:
$$\neg(A \land B) \land \neg(C \land D)$$
Na závorky použijeme první De Morganovo pravidlo:
$$(\neg A \lor \neg B) \land (\neg C \lor \neg D)$$
Protože negace výrazu
x<=yje za normálních okolnostíx>y, můžeme podmínku přepsat naif ((x < 0 || x > 5) && (x < 10 || x > 15)) { ... }Upravený výraz čteme "x není v intervalu 0 až 5 a současně není v intervalu 10 až 15", což jsme potřebovali.
Za zvláštní zmínku stojí urychlení vyhodnocení podmínky. Všimněme si, že při vyhodnocení výrazu
$$X_1\land X_2\land \cdots \land X_N,$$
stačí jediná nepravda (false), aby byl výsledek celý nepravdivý. Mnohé překladače toho využívají: vyhodnocují postupně $X_1$, $X_2$ atd. tak dlouho, dokud nenarazí na nepravdu (false); pak okamžitě vyhodnocení končí s výsledkem nepravda (false).
Proto je obvykle možné psát třeba
if ( x != 0 && y/x > 10 ) { ... }protože při nulovém x se výraz y/x vůbec nebude vyhodnocovat, tj. nedojde k dělení nulou.
Obdobně, pokud vyhodnocujeme výraz
$$X_1\lor X_2\lor \cdots \lor X_N,$$
stačí jediná pravda (true), aby byl výsledek celý pravdivý.
Rozhodněte, zda z formulí $\mathcal{A}_1: \lnot A \implies B$ a $\mathcal{A}_2: \lnot B \iff C$ logicky vyplývá formule $\mathcal{B}: C \implies A$.
Řešení 1: Aby formule $\mathcal{B}$ vyplývala z formulí $\mathcal{A}_1$, $\mathcal{A}_2$, musí být formule $(\mathcal{A}_1 \land \mathcal{A}_2) \implies B$ tautologií, tj. musí být pravdivá pro libovolné pravdivostní ohodnocení výroků $A$, $B$, $C$. O tom se snadno přesvědčíme pravdivostní tabulkou:
| $A$ | $B$ | $C$ | $\mathcal{A}_1:$ $\lnot A \implies B$ |
$\mathcal{A}_2:$ $\lnot B \iff C$ |
$\mathcal{A}_1 \land \mathcal{A}_2$ | $\mathcal{B}:$ $C \implies A$ |
$(\mathcal{A}_1 \land \mathcal{A}_2)\implies B$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
Řešení 2: Aby formule $\mathcal{B}$ vyplývala z formulí $\mathcal{A}_1$, $\mathcal{A}_2$, musí být formule $(\mathcal{A}_1 \land \mathcal{A}_2 \land \neg B)$ kontradikcí, tj. musí být nepravdivá pro libovolné pravdivostní ohodnocení výroků $A$, $B$, $C$. O tom se snadno přesvědčíme pravdivostní tabulkou:
| $A$ | $B$ | $C$ | $\mathcal{A}_1:$ $\lnot A \implies B$ |
$\mathcal{A}_2:$ $\lnot B \iff C$ |
$\mathcal{B}:$ $C \implies A$ |
$\neg\mathcal{B}$ | $(\mathcal{A}_1 \land \mathcal{A}_2 \land \neg B)$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Řešení 3: Připomeňme, že implikace $X\implies Y$ se ekvivalentně vyjádří tzv. nepřímou implikací $\neg Y\implies\neg X$ (princip nepřímého důkazu). Formuli $\mathcal{A}_1$ tedy můžeme přepsat do ekvivalentní podoby nepřímé implikace:
$$\neg B \implies A.$$
Formule $\mathcal{A}_2$ říká, že výroky $\neg B$ a $C$ mají stejnou pravdivostní hodnotu, čili za $\neg B$ můžeme dosadit $C$:
$$C \implies A.$$
To je pochopitelně výrok, který jsme měli prověřit. Ukázeli jsme, že logicky plyne z výroků $\mathcal{A}_1$ a $\mathcal{A}_2$.