TU/e
Mike Boldy en Hans Cuypers

Tautologiën

Definitie

Een tautologie is een propositie die waar is voor iedere combinatie van waarheidswaarden van de propositieletters.

Anders gezegd: als je van een propositie de waarheidstabel berekent, staat er in de bijbehorende kolom overal 1-en. Een zeer eenvoudige tautologie is p\rightarrow p. Er zijn maar twee mogelijkheden om deze propositie te evalueren

0\rightarrow0\Leftrightarrow1
en
1\rightarrow1\Leftrightarrow1

De tegenhanger van de tautologie is de contradictie.

Definitie

Een contradictie is een propositie die onwaar is voor iedere combinatie van waarheidswaarden van de propositieletters.

Een eenvoudig voorbeeld van een contradictie is p\wedge\neg p.

Definitie

Twee proposities p en q heten equivalent als p\leftrightarrow q een tautologie is. We noteren dit als p\Leftrightarrow q.

De relatie \Leftrightarrow is een equivalentierelatie.

Logische equivalenties worden gebruikt om logische wetten mee te formuleren. Een bekende equivalentie is bijvoorbeeld p\rightarrow q\leftrightarrow\neg p\vee q.

Opmerking

Merk op dat tautologie en contradictie niet elkaars tegengestelde zijn. Als een propositie geen tautologie is betekent dat nog niet dat ze een contradictie is. Een propositie zoals p\wedge q is geen tautologie, maar ook geen contradictie.

Opmerking

Let op het verschil tussen \leftrightarrow q en \Leftrightarrow: p\leftrightarrow q is een propositie. p\Leftrightarrow q is een eigenschap van de propositie p\leftrightarrow q.

Voorbeeld

Als twee proposities logisch equivalent zijn betekent dit dat in een waarheidstabel de bijbehorende kolommen gelijk zijn.

Als voorbeeld bewijzen we de equivalentie \neg(p\wedge q)\Leftrightarrow\neg p\vee\neg q. \hline
(1) (2) (3) (4) (5) (6) (7)
p q p\wedge q \neg(p\wedge q) \neg p \neg q \neg p\vee\neg q (4)\leftrightarrow(7)
0 0 0 1 1 1 1 1
0 1 0 1 1 0 1 1
1 0 0 1 0 1 1 1
1 1 1 0 0 0 0 1
De kolommen (4) en (7) zijn gelijk, dus de proposities \neg(p\wedge q) en \neg p\vee\neg q zijn logisch equivalent.