Bewijzen in de wiskunde 9 september 2024

Logica

Beweringen

Een bewering is een zin die waar ( $T$ ) is of niet waar ( $F$ ) is, maar niet allebei. Beweringen worden vaak opgeschreven met $P, Q, R, P_1, P_2, ..., P_n$ . Voorbeelden van beweringen zijn:

Het getal $3$ is oneven ( $T$ )
Het getal $57$ is priem ( $F$ )

Een open bewering $P(x)$ over een domein $S$ is een bewering voor iedere $x$ in $S$ .

Voorbeeld

Gegeven is de bewering $P(x): (x-3)^2 \leq 1$ over $S=\Z$ .

Dan geldt bijvoorbeeld $P(2)$ is waar, $P(3)$ is waar, $P(4)$ is waar, maar $P(5)$ is niet waar.

Waarheidstabellen

Een waarheidstabel is een tabel met alle mogelijke waar/niet waar-waardes voor de beweringen. Een waarheidstabel voor $n$ beweringen heeft $2^n$ rijen.

Voorbeeld

Voor beweringen $P$ en $Q$ ziet de waarheidstabel er als volgt uit:

$P$	$Q$
$T$	$T$
$T$	$F$
$F$	$T$
$F$	$F$

Samengestelde beweringen

Beweringen kun je samenvoegen tot een nieuwe bewering.

Negatie ("niet")

De negatie van een bewering $P$ is een nieuwe bewering, notatie $\lnot P$ ("niet- $P$ "). De bewering $\lnot P$ is alleen waar als de bewering $P$ niet waar is.

De waarheidstabel ziet er dan zo uit:

$P$	$\lnot P$
$T$	$F$
$F$	$T$

Disjunctie ("of")

De disjunctie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $P \lor Q$ (" $P$ of $Q$ "). De bewering $P \lor Q$ is waar wanneer minstens één van $P$ en $Q$ waar is.

De waarheidstabel ziet er dan zo uit:

$P$	$Q$	$P \lor Q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Conjunctie ("en")

De conjunctie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $P \land Q$ (" $P$ en $Q$ "). De bewering $P \land Q$ is waar wanneer zowel $P$ als $Q$ waar is.

De waarheidstabel ziet er dan zo uit:

$P$	$Q$	$P \land Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Implicatie ("als, dan")

De implicatie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $P \implies Q$ ("als $P$ , dan $Q$ "). De bewering $P \implies Q$ is waar wanneer zowel $P$ als $Q$ waar is, of $P$ niet waar is.

In de implicatie $P \implies Q$ heet $P$ de voowaarde en $Q$ de conclusie. De implicatie $Q \implies P$ is de omkering van $P \implies Q$ .

De waarheidstabel ziet er dan zo uit:

$P$	$Q$	$P \implies Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Voorbeeld

Gegeven zijn de beweringen $P(x): x = -3$ en $Q(x): |x| = 3$ over $S=\Z$ .

Nu zijn $Q(-3) \implies P(-3)$ en $Q(2) \implies P(2)$ waar, maar $Q(3) \implies P(3)$ is niet waar.

Verder geldt voor iedere $x$ dat $P(x) \implies Q(x)$ waar is.

Bi-implicatie

Voor beweringen $P$ en $Q$ heet de conjunctie $(P \implies Q) \land (Q \implies P)$ de bi-implicatie, notatie $P \iff Q$ . Deze bi-implicatie is alleen waar als $P$ en $Q$ allebei waar of allebei niet waar zijn.

De waarheidstabel ziet er dan zo uit:

$P$	$Q$	$P \iff Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

Tautologie en tegenspraak

Een tautologie is een bewering die altijd waar is.

Voorbeeld

De bewering $P \lor \lnot P$ is een tautologie, wat volgt uit de waarheidstabel:

$P$	$\lnot P$	$P \lor \lnot P$
$T$	$F$	$T$
$F$	$T$	$T$

Een tegenspraak is een bewering die nooit waar is.

Voorbeeld

De bewering $P \land \lnot P$ is een tegenspraak, wat volgt uit de waarheidstabel:

$P$	$\lnot P$	$P \land \lnot P$
$T$	$F$	$F$
$F$	$T$	$F$

Er geldt: als $P$ een tautologie is, dan is $\lnot P$ een tegenspraak.

Logische equivalentie

Samengestelde beweringen $P$ en $Q$ zijn logisch equivalent als ze precies dezelfde waarheidstabellen hebben. We noteren dat als $P \equiv Q$ .

Er geldt: $P$ en $Q$ zijn logisch equivalent dan en slechts dan als $P \iff Q$ een tautologie is.

Eigenschappen van samengestelde beweringen

Met deze definitie van logische equivalentie kunnen we een paar eigenschappen opschrijven over beweringen $P$ , $Q$ en $R$ :

$P \lor Q \equiv Q \lor P$ en $P \land Q \equiv Q \land P$
$P \lor (Q \lor R) \equiv (P \lor Q) \lor R$ en $P \land (Q \land R) \equiv (P \land Q) \land R$
$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ en $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$
$\lnot (P \lor Q) \equiv \lnot P \land \lnot Q$ en $\lnot (P \land Q) \equiv \lnot P \lor \lnot Q$

Al deze eigenschappen kunnen bewezen worden met waarheidstabellen.

Quantoren

Een quantor maakt van een open bewering een gesloten bewering.

Universele quantor

De universele quantor, notatie $\forall$ , betekent dat iets waar is voor ieder element uit het domein. Zo betekent $\forall x \in S : P(x)$ dat voor iedere $x$ uit $S$ , $P(x)$ waar is.

Voorbeeld

Gegeven is de open bewering $P(x): x^2 > 0$ . Nu geldt dat de bewering $\forall x \in \{1,2,3,...\}:P(x)$ waar is. Maar de bewering $\forall x \in \{0, 1, 2, 3, ...\}:P(x)$ is niet waar, omdat deze niet waar is voor $x=0$ .

Existentiële quantor

De existentiële quantor, notatie $\exists$ , betekent dat iets waar is voor minimaal één element uit het domein. Zo betekent $\exists x \in S : P(x)$ dat er minstens één element $x$ bestaat in $S$ , zodat $P(x)$ waar is.

Voorbeeld

Gegeven is de open bewering $P(x): x^2 > 0$ . Nu geldt dat de bewering $\exists x \in \{0,1,2,3,...\}:P(x)$ waar is. Bijvoorbeeld voor $x=1$ .

Let op dat het domein belangrijk is:

Voorbeeld

Gegeven is de open bewering $P(x): x^2 = 3$ . Nu is de bewering $\exists x \in \R : P(x)$ waar, bijvoorbeeld voor $x=\sqrt3$ .

De bewering $\exists x \in \Z : P(x)$ daarentegen is niet waar.

Negatie van quantoren

Voor de negatie van quantoren gelden de volgende regels:

$\lnot \big(\forall x \in S: P(x)\big) \equiv \exists x \in S : \lnot P(x)$
$\lnot \big(\exists x \in S: P(x)\big) \equiv \forall x \in S : \lnot P(x)$

In het algemeen wissel je bij negatie de $\forall$ - en $\exists$ -symbolen om, en trek je het $\lnot$ -symbool "naar binnen".

Voorbeeld

$\lnot \big(\forall x \in S : \exists y \in T : P(x, y)\big) \equiv \exists x \in S : \forall y \in T : \lnot P(x, y)$