Eksklusjon (logikk)

Eksklusjon er en grunnleggende sannhetsfunksjon i setningslogikken (latin exclusio = «utestengning»). Eksklusjonen av to utsagn er sann hvis og bare hvis minst ett av disse utsagnene er falske. Den symbolske skrivemåten for eksklusjonen av to utsagn A og B bruker den såkalte Sheffer-streken:

$\mathbf A \mid \mathbf B$

og kan uttales som følger:

• «høyst én av A og B,»
• «ikke begge av A og B,»
• «A og B utelukker hverandre.»

I noen programmeringsspråk eller andre sammenhenger der særtegn ikke kan brukes, skrives også «NAND» istedenfor «|». «NAND» er avledet av det engelske uttrykket not and. Dette kommer av at eksklusjonen er negasjonen av en «logisk og»:
$(\mathbf A \mid \mathbf{B}) \Leftrightarrow \neg (\mathbf B \land \mathbf{A})$.

Sheffer-streken er oppkalt etter logikeren Henry Maurice Sheffer, som beskrev noen av eksklusjonens interessante egenskaper. Blant annet kan alle andre sannhetsfunksjonene uttrykkes gjennom eksklusjonen:

• negasjon («ikke»), $\neg \mathbf A \Leftrightarrow (\mathbf A \mid \mathbf{A})$;
• inklusiv disjunksjon («eller»), $(\mathbf A \lor \mathbf{B}) \Leftrightarrow (\neg \mathbf A \mid \neg \mathbf{B}) \Leftrightarrow ((\mathbf A \mid \mathbf{A}) \mid (\mathbf B \mid \mathbf{B}))$;
• konjunksjon («og»), $(\mathbf A \land \mathbf{B}) \Leftrightarrow \neg (\mathbf A \mid \mathbf{B}) \Leftrightarrow ((\mathbf A \mid \mathbf{B}) \mid (\mathbf A \mid \mathbf{B}))$;
• subjunksjon («hvis»), $(\mathbf A \rightarrow \mathbf{B}) \Leftrightarrow (\mathbf A \mid \neg \mathbf{B}) \Leftrightarrow (\mathbf A \mid (\mathbf B \mid \mathbf{B}))$;
• bisubjunksjon («hvis og bare hvis»), $(\mathbf A \leftrightarrow \mathbf{B}) \Leftrightarrow ((\mathbf A \mid \mathbf{B}) \mid ((\mathbf A \mid \mathbf{B}) \mid (\mathbf B \mid \mathbf{B})))$;
• eksklusiv disjunksjon («enten–eller»), $(\mathbf A$$\mathbf{B}) \Leftrightarrow ((\mathbf A \mid (\mathbf B \mid \mathbf{B})) \mid ((\mathbf A \mid \mathbf{A}) \mid \mathbf{B}))$;
• tilsvarende fungerer for de resterende sannhetsfunksjonene.