Jeroen's Studie Archief

Home

Vakken

Bewijzen in de wiskunde

7 oktober 2024
Functies

Bij bewijzen met reële getallen gebruik je vaak dat $xn≥0x^n \ge 0$ voor even, positieve $n$ . Stelling $\forall x,y \in\R : \tfrac13 x^2 + \tfrac34 y^2 \ge xy$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $2x-3y)^2 = 4x^2 - 12xy + 9y^2$ . Nu krijgen we: $(2x-3y)^2 \ge 0$ $4x^2 - 12xy + 9y^2 \ge 0$ $4x^2 + 9y^2 \ge 12xy$ $\tfrac13 x^2 + \tfrac34 y^2 \ge xy$ QED. Een belangrijke stelling over reële getallen is de driehoeksongelijkheid. Om dat te bewijzen, bewijzen we eerst een handig lemma. Lemma $\forall x \in \R : |x|^2 = x^2$ Bewijs Neem een $x∈Rx\in\R$ . We onderscheiden gevallen (1) $x≥0x\ge0$ en (2) $x < 0$ . (1) We nemen aan dat $x≥0x\ge0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = x$ en dus ook $x|^2=x^2$ . (2) We nemen aan dat $x < 0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = - x$ en daaruit volgt dat $x|^2=(-x)^2=x^2$ . QED. Dan nu de stelling. Stelling $\forall x,y \in \R : |x + y| \le |x| + |y|$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $∣x∣∣y∣≥xy|x||y|\ge xy$ . Uit het lemma en hieruit volgt: $\begin{aligned} xy &\le |x||y| \\ x^2 + 2xy + y^2 &\le x^2 + 2|x||y| + y^2 \\ x^2 + 2xy + y^2 &\le |x|^2 + 2|x||y| + |y|^2 \\ (x+y)^2 &\le (|x|+|y|)^2 \\ (|x+y|)^2 &\le (|x|+|y|)^2 \\ |x+y| &\le |x|+|y| \end{aligned}$ QED. Bij bewijzen met verzamelingen is het vaak handig om een bepaalde $x$ uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen $A$ en $B$ toon je eerst aan dat $\subseteq B$ , en daarna $\subseteq A$ . Stelling $A\B=A∩B‾ A \backslash B = A \cap \overline B$ Bewijs We bewijzen (1) $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ en (2) $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . (1) Neem een $x∈A\Bx \in A \backslash B$ . Dan geldt $\in A$ en $\notin B$ . Omdat $\notin B$ , geldt $\in \overline B$ . Er geldt dus $\in A$ en $\in \overline B$ , dus $\in A \cap \overline B$ . Uit $x∈A\B ⟹ x∈A∩B‾x \in A \backslash B \implies x \in A \cap \overline B$ concluderen we dat $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ . (2) Neem een $\in A \cap \overline B$ . Dus $\in A$ en $\in \overline B$ . Uit $\in \overline B$ volgt $\notin B$ . Er geldt dus $\in A$ en $\notin B$ , dus $x∈A\Bx \in A \backslash B$ . Uit $x∈A\Bx \in A \cap \overline B \implies x \in A \backslash B$ concluderen we dat $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . QED. Voor bewijzen met carthesische producten neem je een $(x, y)$ uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling $\subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D$ Bewijs Neem aan dat $\subseteq C$ en $\subseteq D$ . Laat $\in A \times B$ . Dan geldt dat $\in A$ . Omdat $\subseteq C$ , geldt ook dat $\in C$ . Vergelijkbaar geldt dat $\in B$ , waaruit volgt dat $\in D$ . Omdat $\in C$ en $\in D$ , geldt dat $\in C \times D$ . Uit $\in A \times B \implies (x,y) \in C \times D$ concluderen we dat $\times B \subseteq C \times D$ . QED. Van een bewering van de vorm $∀x∈S:P(x)\forall x \in S : P(x)$ is de negatie $¬(∀x∈S:P(x))≡∃x∈S:¬P(x)\lnot(\forall x \in S : P(x)) \equiv \exists x \in S : \lnot P(x)$ . Dit betekent dat, om deze bewering te ontkrachten, we maar één geval hoeven te vinden waarvoor $P (x)$ niet waar is. Let op: er kunnen meerdere gevallen zijn waarvoor $¬P(x)\lnot P(x)$ , maar minstens één geval is genoeg. Voorbeeld Gegeven is de bewering $\forall x \in \R : (x-1)^2 > 0$ . Voor $x = 0$ is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering $P$ kan contradictie gebruikt worden. Bij contradictie neem je aan dat $¬P\lnot P$ , om vervolgens $F$ (niet waar) te concluderen. Als dit lukt, is er bewezen dat $P$ waar is. Stelling Er bestaat geen kleinste $\in \R^+$ . Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste $\in \R^+$ bestaat. Dan geldt ook dat $12x∈R+\frac12 x \in \R^+$ . Maar $12x<x\frac12x < x$ , dus we hebben een contradictie. QED. Nog een voorbeeld: Stelling $∀x∈R\Q:∀r∈Q\{0}:xr∉Q \forall x \in \R \backslash \mathbb Q : \forall r \in \mathbb Q \backslash \{0\} : xr \notin \mathbb Q$ Bewijs Neem een $x∈R\Qx \in \R \backslash \mathbb Q$ en $\in \mathbb Q$ . Omdat $\in \mathbb Q$ , geldt dat er $a,b∈Za,b\in\Z$ met $a,b≠0a,b\neq0$ bestaan zodat $r=abr=\dfrac ab$ . Met bewijs uit contradictie, neem aan dat $\in \mathbb Q$ . Dan bestaan er $c,d∈Zc,d\in\Z$ met $d≠0d\neq0$ zodat $xr=cdxr=\dfrac cd$ . Dit geeft $\dfrac ab = \dfrac cd$ , waaruit volgt dat $x=bcadx=\dfrac{bc}{ad}$ . Omdat $bc,ad∈Zbc,ad\in\Z$ en $ad≠0ad\neq0$ geldt dat $x∈Qx\in\mathbb Q$ . Dit is een contradictie. QED.
2 oktober 2024
Equivalentie-relaties

Bij bewijzen met reële getallen gebruik je vaak dat $xn≥0x^n \ge 0$ voor even, positieve $n$ . Stelling $\forall x,y \in\R : \tfrac13 x^2 + \tfrac34 y^2 \ge xy$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $2x-3y)^2 = 4x^2 - 12xy + 9y^2$ . Nu krijgen we: $(2x-3y)^2 \ge 0$ $4x^2 - 12xy + 9y^2 \ge 0$ $4x^2 + 9y^2 \ge 12xy$ $\tfrac13 x^2 + \tfrac34 y^2 \ge xy$ QED. Een belangrijke stelling over reële getallen is de driehoeksongelijkheid. Om dat te bewijzen, bewijzen we eerst een handig lemma. Lemma $\forall x \in \R : |x|^2 = x^2$ Bewijs Neem een $x∈Rx\in\R$ . We onderscheiden gevallen (1) $x≥0x\ge0$ en (2) $x < 0$ . (1) We nemen aan dat $x≥0x\ge0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = x$ en dus ook $x|^2=x^2$ . (2) We nemen aan dat $x < 0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = - x$ en daaruit volgt dat $x|^2=(-x)^2=x^2$ . QED. Dan nu de stelling. Stelling $\forall x,y \in \R : |x + y| \le |x| + |y|$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $∣x∣∣y∣≥xy|x||y|\ge xy$ . Uit het lemma en hieruit volgt: $\begin{aligned} xy &\le |x||y| \\ x^2 + 2xy + y^2 &\le x^2 + 2|x||y| + y^2 \\ x^2 + 2xy + y^2 &\le |x|^2 + 2|x||y| + |y|^2 \\ (x+y)^2 &\le (|x|+|y|)^2 \\ (|x+y|)^2 &\le (|x|+|y|)^2 \\ |x+y| &\le |x|+|y| \end{aligned}$ QED. Bij bewijzen met verzamelingen is het vaak handig om een bepaalde $x$ uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen $A$ en $B$ toon je eerst aan dat $\subseteq B$ , en daarna $\subseteq A$ . Stelling $A\B=A∩B‾ A \backslash B = A \cap \overline B$ Bewijs We bewijzen (1) $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ en (2) $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . (1) Neem een $x∈A\Bx \in A \backslash B$ . Dan geldt $\in A$ en $\notin B$ . Omdat $\notin B$ , geldt $\in \overline B$ . Er geldt dus $\in A$ en $\in \overline B$ , dus $\in A \cap \overline B$ . Uit $x∈A\B ⟹ x∈A∩B‾x \in A \backslash B \implies x \in A \cap \overline B$ concluderen we dat $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ . (2) Neem een $\in A \cap \overline B$ . Dus $\in A$ en $\in \overline B$ . Uit $\in \overline B$ volgt $\notin B$ . Er geldt dus $\in A$ en $\notin B$ , dus $x∈A\Bx \in A \backslash B$ . Uit $x∈A\Bx \in A \cap \overline B \implies x \in A \backslash B$ concluderen we dat $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . QED. Voor bewijzen met carthesische producten neem je een $(x, y)$ uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling $\subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D$ Bewijs Neem aan dat $\subseteq C$ en $\subseteq D$ . Laat $\in A \times B$ . Dan geldt dat $\in A$ . Omdat $\subseteq C$ , geldt ook dat $\in C$ . Vergelijkbaar geldt dat $\in B$ , waaruit volgt dat $\in D$ . Omdat $\in C$ en $\in D$ , geldt dat $\in C \times D$ . Uit $\in A \times B \implies (x,y) \in C \times D$ concluderen we dat $\times B \subseteq C \times D$ . QED. Van een bewering van de vorm $∀x∈S:P(x)\forall x \in S : P(x)$ is de negatie $¬(∀x∈S:P(x))≡∃x∈S:¬P(x)\lnot(\forall x \in S : P(x)) \equiv \exists x \in S : \lnot P(x)$ . Dit betekent dat, om deze bewering te ontkrachten, we maar één geval hoeven te vinden waarvoor $P (x)$ niet waar is. Let op: er kunnen meerdere gevallen zijn waarvoor $¬P(x)\lnot P(x)$ , maar minstens één geval is genoeg. Voorbeeld Gegeven is de bewering $\forall x \in \R : (x-1)^2 > 0$ . Voor $x = 0$ is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering $P$ kan contradictie gebruikt worden. Bij contradictie neem je aan dat $¬P\lnot P$ , om vervolgens $F$ (niet waar) te concluderen. Als dit lukt, is er bewezen dat $P$ waar is. Stelling Er bestaat geen kleinste $\in \R^+$ . Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste $\in \R^+$ bestaat. Dan geldt ook dat $12x∈R+\frac12 x \in \R^+$ . Maar $12x<x\frac12x < x$ , dus we hebben een contradictie. QED. Nog een voorbeeld: Stelling $∀x∈R\Q:∀r∈Q\{0}:xr∉Q \forall x \in \R \backslash \mathbb Q : \forall r \in \mathbb Q \backslash \{0\} : xr \notin \mathbb Q$ Bewijs Neem een $x∈R\Qx \in \R \backslash \mathbb Q$ en $\in \mathbb Q$ . Omdat $\in \mathbb Q$ , geldt dat er $a,b∈Za,b\in\Z$ met $a,b≠0a,b\neq0$ bestaan zodat $r=abr=\dfrac ab$ . Met bewijs uit contradictie, neem aan dat $\in \mathbb Q$ . Dan bestaan er $c,d∈Zc,d\in\Z$ met $d≠0d\neq0$ zodat $xr=cdxr=\dfrac cd$ . Dit geeft $\dfrac ab = \dfrac cd$ , waaruit volgt dat $x=bcadx=\dfrac{bc}{ad}$ . Omdat $bc,ad∈Zbc,ad\in\Z$ en $ad≠0ad\neq0$ geldt dat $x∈Qx\in\mathbb Q$ . Dit is een contradictie. QED.
30 september 2024
Sterke inductie en relaties

Als je een bewering van de vorm $∀n∈N:P(n)\forall n \in N : P(n)$ wilt bewijzen, kun je gebruik maken van het minimale tegenvoorbeeld. Hierbij neem je aan dat er een kleinste getal $m∈Nm\in\N$ bestaat waarvoor $P (m)$ niet waar is. Het doel is om dan uit te komen op een contradictie. Stelling $\forall n \in \N : 6 | n^3 - n$ Bewijs Bij contradictie, neem aan dat er een $n∈Nn\in\N$ bestaat waarvoor $\nmid n^3 - n$ . Dan bestaat er een kleinste $m∈Nm\in\N$ waarvoor $\nmid m^3 - m$ . Omdat $6|1^3-1=0$ en $6|2^3-2=6$ , moet gelden dat $\ge 3$ . Dan schrijven we $m = k + 2$ voor een $k∈Nk\in\N$ met $\le k < m$ . Nu geldt: $m^3-m = (k+2)^3-(k+2) = k^3-k+6(k^2+2k+1)$ Omdat $k < m$ en $m$ het kleinste getal is waarvoor $\nmid m^3-m$ , geldt dat $6|k^3-k$ . We schrijven $k$ dus als $6 x$ voor een $x∈Zx\in\Z$ . Dit geeft: $m^3-m = 6x + 6(k^2+2k+1)$ En omdat $k^2+2k+1 \in \Z$ , concluderen we dat $6|m^3-m$ . Dit is een contradictie. QED. Sterke inductie is een uitbreiding op normale inductie, en gaat alsvolgt: Laat $P (n)$ een bewering zijn met domein $N\N$ . Als (1) $P (1)$ waar is en (2) $P(k+1)\forall k \in \N : \big(P(1) \land P(2) \land ... \land P(k)\big) \implies P(k+1)$ waar is, geldt $∀n∈N:P(n)\forall n \in \N: P(n)$ . Stelling Laat $a_n$ recursief gedefiniëerd zijn door $a_1=1$ , $a_2=3$ en $a_n = 2a_{n-1} - a_{n-2}$ voor $\ge 3$ . Dan geldt $a_n=2n-1$ voor alle $n∈Nn\in\N$ . Bewijs Met sterke inductie op $n$ , bewijzen we (1) $1 = 2 (1) - 1$ en $2 = 2 (2) - 1$ , en (2) $ak+1=2(k+1)−1\forall k \in N : (a_1=2(1)-1 \land a_2=2(2)-1 \land ... \land a_k=2k-1) \implies a_{k+1} = 2(k+1)-1$ . (1) Er geldt $2 (1) - 1 = 1$ en $2 (2) - 1 = 3$ , dus dit klopt. (2) Laat $k∈Nk\in\N$ . We nemen aan dat $a_i=2i-1$ geldt voor elke $i∈Ni\in\N$ waarvoor $i < k$ . Er geldt: $\begin{aligned} a_k &= 2a_{k-1}-a_{k-2} \\ &\stackrel{IH}= 2(2(k-1)-1) - (2(k-2)-1) \\ &= 2k-1 \end{aligned}$ QED. Voor verzamelingen $A$ en $B$ is een relatie $R$ van $A$ naar $B$ een deelverzameling van $\times B$ . Als $\in R$ , zeggen we dat $a$ gerelateerd is aan $b$ , notatie $a R b$ . Voor een relatie $R$ van $A$ naar $B$ geldt dat het domein, notatie $dom(R)\text{dom}(R)$ , en het bereik, notatie $range(R)\text{range}(R)$ , gelijk zijn aan: $\text{dom}(R) = \{ a \in A : (a, b) \in R \text{ voor een } b \in B \}$ $\text{range}(R) = \{ b \in B : (a, b) \in R \text { voor een } a \in A \}$ Voorbeeld Gegeven zijn $A=\{1,2,3\}$ , $B=\{x,y\}$ en $R=\{(2,x),(1,y),(2,y)\}$ . Er geldt $\subseteq A \times B$ , dus $R$ is een relatie van $A$ naar $B$ . Hier geldt dat $dom(R)={1,2}\text{dom}(R) = \{1,2\}$ en $range(R)={x,y}\text{range}(R) = \{x,y\}$ . De inverse van een relatie $R$ van $A$ naar $B$ , notatie $R^{-1}$ , is een relatie van $B$ naar $A$ , zodat: $R^{-1} = \{ (b,a) : (a,b) \in R \}$ Een relatie $R$ op een verzameling $A$ is een relatie van $A$ naar $A$ , oftewel $\subseteq A \times A$ . Laat $R$ een relatie zijn op $A$ . Dan is $R$ : Reflexief precies als $a R a$ voor alle $\in A$ . Symmetrisch precies als $\implies bRa$ voor alle $\in A$ . Transitief precies als $\land bRc) \implies aRc$ voor alle $\in A$ . Voorbeeld Laat $R$ de relatie zijn op $R\R$ zodat $a R b$ precies als $∣a−b∣≤1|a-b|\le1$ . Dan is $R$ wel reflexief, wel symmetrisch, maar niet transitief.
25 september 2024
Existentiële bewijzen en inductie

We willen inverse functies vinden voor de goniometrische functies $sin⁡(x)\sin(x)$ , $cos⁡(x)\cos(x)$ en $tan⁡(x)\tan(x)$ . Maar omdat deze functies niet bijectief zijn, bestaan er geen inverse functies. We kunnen wel functies definiëren die op een bepaald domein de inversen zijn. We krijgen zo $arcsin⁡(x)\arcsin(x)$ , $arccos⁡(x)\arccos(x)$ en $arctan⁡(x)\arctan(x)$ . Deze tabel geeft een overzicht van de functies: $f (x)$ Domein Bereik $sin⁡(x)\sin(x)$ $R\R$ $[- 1, 1]$ $arcsin⁡(x)\arcsin(x)$ $[- 1, 1]$ $[−12π,12π][-\frac12\pi,\frac12\pi]$ $cos⁡(x)\cos(x)$ $R\R$ $[- 1, 1]$ $arccos⁡(x)\arccos(x)$ $[- 1, 1]$ $[0,π][0,\pi]$ $tan⁡(x)\tan(x)$ $R\R$ $R\R$ $arctan⁡(x)\arctan(x)$ $R\R$ $⟨−12π,12π⟩\langle-\frac12\pi,\frac12\pi\rangle$ Op het domein van de inverse functies geldt dat $sin⁡(arcsin⁡(x))=x\sin(\arcsin(x))=x$ , $cos⁡(arccos⁡(x))=x\cos(\arccos(x))=x$ en $tan⁡(arctan⁡(x))=x\tan(\arctan(x))=x$ . We weten dat voor $−12π≤x≤12π-\frac12\pi \le x \le \frac12\pi$ geldt dat $sin⁡(arcsin⁡(x))=x\sin(\arcsin(x))=x$ . Als we dit aan beide kanten differentiëren, krijgen we: $\tfrac{d}{dx} \sin(\arcsin(x)) = \tfrac{d}{dx} x$ $\cos(\arcsin(x)) \cdot \tfrac{d}{dx} \arcsin(x) = 1$ $\tfrac{d}{dx} \arcsin(x) = \frac1{\cos(\arcsin(x))}$ Deze uitdrukking kunnen we mooier schrijven, door een rechthoekige driehoek te tekenen. We noemen $θ=arcsin⁡(x)\theta = \arcsin(x)$ , waaruit volgt dat $x=sin⁡(θ)=x1x=\sin(\theta)=\frac x1$ . Hiermee kunnen we één zijde van de driehoek $x$ noemen en een andere zijde $1$ . De overgebleven zijde is dan volgens de stelling van Pythagoras gelijk aan $1−x2\sqrt{1-x^2}$ . Hieruit volgt dat $cos⁡(θ)=1−x2=cos⁡(arcsin⁡(x))\cos(\theta)=\sqrt{1-x^2}=\cos(\arcsin(x))$ , dus: $\tfrac{d}{dx} \arcsin(x) = \frac1{\sqrt{1-x^2}}$ Op vergelijkbare wijze krijgen we ook dat: $\tfrac{d}{dx} \arccos(x) = \frac{-1}{\sqrt{1-x^2}}$ $\tfrac{d}{dx} \arctan(x) = \frac{1}{1+x^2}$
23 september 2024
Bewijzen met reële getallen, verzamelingen, tegenvoorbeelden en contradictie

Bij bewijzen met reële getallen gebruik je vaak dat $xn≥0x^n \ge 0$ voor even, positieve $n$ . Stelling $\forall x,y \in\R : \tfrac13 x^2 + \tfrac34 y^2 \ge xy$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $2x-3y)^2 = 4x^2 - 12xy + 9y^2$ . Nu krijgen we: $(2x-3y)^2 \ge 0$ $4x^2 - 12xy + 9y^2 \ge 0$ $4x^2 + 9y^2 \ge 12xy$ $\tfrac13 x^2 + \tfrac34 y^2 \ge xy$ QED. Een belangrijke stelling over reële getallen is de driehoeksongelijkheid. Om dat te bewijzen, bewijzen we eerst een handig lemma. Lemma $\forall x \in \R : |x|^2 = x^2$ Bewijs Neem een $x∈Rx\in\R$ . We onderscheiden gevallen (1) $x≥0x\ge0$ en (2) $x < 0$ . (1) We nemen aan dat $x≥0x\ge0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = x$ en dus ook $x|^2=x^2$ . (2) We nemen aan dat $x < 0$ . Dan, per definitie van de absolute waarde, geldt $∣ x ∣ = - x$ en daaruit volgt dat $x|^2=(-x)^2=x^2$ . QED. Dan nu de stelling. Stelling $\forall x,y \in \R : |x + y| \le |x| + |y|$ Bewijs Neem $x,y∈Rx,y\in\R$ . Merk op dat $∣x∣∣y∣≥xy|x||y|\ge xy$ . Uit het lemma en hieruit volgt: $\begin{aligned} xy &\le |x||y| \\ x^2 + 2xy + y^2 &\le x^2 + 2|x||y| + y^2 \\ x^2 + 2xy + y^2 &\le |x|^2 + 2|x||y| + |y|^2 \\ (x+y)^2 &\le (|x|+|y|)^2 \\ (|x+y|)^2 &\le (|x|+|y|)^2 \\ |x+y| &\le |x|+|y| \end{aligned}$ QED. Bij bewijzen met verzamelingen is het vaak handig om een bepaalde $x$ uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen $A$ en $B$ toon je eerst aan dat $\subseteq B$ , en daarna $\subseteq A$ . Stelling $A\B=A∩B‾ A \backslash B = A \cap \overline B$ Bewijs We bewijzen (1) $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ en (2) $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . (1) Neem een $x∈A\Bx \in A \backslash B$ . Dan geldt $\in A$ en $\notin B$ . Omdat $\notin B$ , geldt $\in \overline B$ . Er geldt dus $\in A$ en $\in \overline B$ , dus $\in A \cap \overline B$ . Uit $x∈A\B ⟹ x∈A∩B‾x \in A \backslash B \implies x \in A \cap \overline B$ concluderen we dat $A\B⊆A∩B‾A \backslash B \subseteq A \cap \overline B$ . (2) Neem een $\in A \cap \overline B$ . Dus $\in A$ en $\in \overline B$ . Uit $\in \overline B$ volgt $\notin B$ . Er geldt dus $\in A$ en $\notin B$ , dus $x∈A\Bx \in A \backslash B$ . Uit $x∈A\Bx \in A \cap \overline B \implies x \in A \backslash B$ concluderen we dat $A∩B‾⊆A\BA \cap \overline B \subseteq A \backslash B$ . QED. Voor bewijzen met carthesische producten neem je een $(x, y)$ uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling $\subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D$ Bewijs Neem aan dat $\subseteq C$ en $\subseteq D$ . Laat $\in A \times B$ . Dan geldt dat $\in A$ . Omdat $\subseteq C$ , geldt ook dat $\in C$ . Vergelijkbaar geldt dat $\in B$ , waaruit volgt dat $\in D$ . Omdat $\in C$ en $\in D$ , geldt dat $\in C \times D$ . Uit $\in A \times B \implies (x,y) \in C \times D$ concluderen we dat $\times B \subseteq C \times D$ . QED. Van een bewering van de vorm $∀x∈S:P(x)\forall x \in S : P(x)$ is de negatie $¬(∀x∈S:P(x))≡∃x∈S:¬P(x)\lnot(\forall x \in S : P(x)) \equiv \exists x \in S : \lnot P(x)$ . Dit betekent dat, om deze bewering te ontkrachten, we maar één geval hoeven te vinden waarvoor $P (x)$ niet waar is. Let op: er kunnen meerdere gevallen zijn waarvoor $¬P(x)\lnot P(x)$ , maar minstens één geval is genoeg. Voorbeeld Gegeven is de bewering $\forall x \in \R : (x-1)^2 > 0$ . Voor $x = 0$ is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering $P$ kan contradictie gebruikt worden. Bij contradictie neem je aan dat $¬P\lnot P$ , om vervolgens $F$ (niet waar) te concluderen. Als dit lukt, is er bewezen dat $P$ waar is. Stelling Er bestaat geen kleinste $\in \R^+$ . Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste $\in \R^+$ bestaat. Dan geldt ook dat $12x∈R+\frac12 x \in \R^+$ . Maar $12x<x\frac12x < x$ , dus we hebben een contradictie. QED. Nog een voorbeeld: Stelling $∀x∈R\Q:∀r∈Q\{0}:xr∉Q \forall x \in \R \backslash \mathbb Q : \forall r \in \mathbb Q \backslash \{0\} : xr \notin \mathbb Q$ Bewijs Neem een $x∈R\Qx \in \R \backslash \mathbb Q$ en $\in \mathbb Q$ . Omdat $\in \mathbb Q$ , geldt dat er $a,b∈Za,b\in\Z$ met $a,b≠0a,b\neq0$ bestaan zodat $r=abr=\dfrac ab$ . Met bewijs uit contradictie, neem aan dat $\in \mathbb Q$ . Dan bestaan er $c,d∈Zc,d\in\Z$ met $d≠0d\neq0$ zodat $xr=cdxr=\dfrac cd$ . Dit geeft $\dfrac ab = \dfrac cd$ , waaruit volgt dat $x=bcadx=\dfrac{bc}{ad}$ . Omdat $bc,ad∈Zbc,ad\in\Z$ en $ad≠0ad\neq0$ geldt dat $x∈Qx\in\mathbb Q$ . Dit is een contradictie. QED.
18 september 2024
Deelbaarheid van gehele getallen

Twee getallen $a,b∈Za,b\in\Z$ hebben dezelfde pariteit als $a$ en $b$ allebei even of allebei oneven zijn. Voor twee getallen $a,b∈Za,b\in\Z$ met $a≠0a\neq0$ zeggen we dat " $a$ deelt $b$ ", notatie $a ∣ b$ , precies als er een $c∈Zc\in\Z$ bestaat zodat $b = a c$ . Voor een even $n∈Zn\in\Z$ geldt dus dat $2∣ n$ . Voorbeeld Er geldt $3∣6$ , $4∣4$ en $- 2∣10$ . Als $a ∣ b$ , zeggen we dat $a$ een deler is van $b$ en $b$ een veelvoud is van $a$ . Verder, als $a$ niet $b$ deelt, schrijven we $\nmid b$ . Stelling Laat $a,b,c∈Za,b,c\in\Z$ met $a,b≠0a,b\neq0$ . Als $a ∣ b$ en $b ∣ c$ , dan $a ∣ c$ . Bewijs Neem $a,b,c∈Za,b,c\in\Z$ met $a,b≠0a,b\neq0$ zodat $a ∣ b$ en $b ∣ c$ . Dan bestaat er $x,y∈Zx,y\in\Z$ zodat $b = a x$ en $c = b y$ . Er geldt dus dat $c = a x y$ . Omdat $xy∈Zxy\in\Z$ , geldt dat $a ∣ c$ . QED. Voor $a,b,n∈Za,b,n\in\Z$ met $n≥2n\ge2$ zeggen we dat $a$ congruent is aan $b$ modulo $n$ , notatie $\equiv b \mod n$ , precies als $n ∣ a - b$ . Voorbeeld Er geldt $415\equiv7\mod4$ , want $4∣15 - 7 = 8$ . Verder geldt $93\equiv-15\mod9$ , want $9∣3 - - 15 = 18$ . Dit is een belangrijke stelling over congruenties. Stelling Laat $a,b,k,n∈Za,b,k,n\in\Z$ met $n≥2n\ge2$ . Als $\equiv b \mod n$ , dan $\equiv bk \mod n$ . Bewijs Neem $a,b,k,n∈Za,b,k,n\in\Z$ met $n≥2n\ge2$ zodat $\equiv b \mod n$ . Dan geldt $n ∣ a - b$ , dus er bestaat een $x∈Zx\in\Z$ zodat $a - b = n x$ . Nu geldt $ak - bk = nk x$ . Omdat $kx∈Zkx\in\Z$ , geldt $n ∣ ak - bk$ en dus $\equiv bk \mod n$ . QED.
16 september 2024
Bewijstechnieken

Bij het bewijzen van een stelling bewijs je meestal een implicatie van de vorm: $\forall x \in S : P(x) \implies Q(x)$ Een makkelijke manier om een implicatie te bewijzen zijn met een triviaal of met een vaculeus bewijs. Bij een triviaal bewijs toon je aan dat $Q (x)$ altijd waar is, wat de implicatie waar maakt. Bij een vaculeus bewijs toon je aan dat $P (x)$ nooit waar is, wat de implicatie ook waar maakt. Dit is een voorbeeld van een triviaal bewijs: Stelling $\forall x \in \R : x < 0 \implies x^2 + 1 > 0$ Bewijs Neem $\in R$ . Omdat $x2≥0x^2 \ge 0$ , geldt $x2+1≥1>0x^2 + 1 \ge 1 > 0$ . Dus $x^2 + 1 > 0$ . QED. En dit is een voorbeeld van een vaculeus bewijs: Stelling $\forall x \in \R : x^2-2x+2 \le 0 \implies x^3 \ge 8$ Bewijs Neem $\in \R$ . Merk op dat $x^2-2x+1=(x-1)^2$ . $x^2 - 2x + 2 = (x-1)^2 + 1 \ge 0$ Dus $x2−2x+2≤0x^2-2x+2 \le 0$ is nooit waar. QED. Bij een direct bewijs van de bewering $Q(x)\forall x \in S : P(x) \implies Q(x)$ nemen we een element $\in S$ waarvoor $P (x)$ waar is, en gebruiken we eigenschappen van $P (x)$ om aan te tonen dat $Q (x)$ waar is. Stelling Voor iedere $\in \Z$ , als $n$ oneven is, dan is $3 n + 7$ even. Bewijs Neem een oneven $\in \Z$ . Omdat $n$ oneven is, bestaat er een $\in \Z$ zodat $n = 2 k + 1$ . Dan geldt: $3 n + 7 = 3 (2 k + 1) + 7 = 6 k + 10 = 2 (3 k + 5)$ Omdat $3k+5∈Z3k+5\in\Z$ , geldt dat $2 (3 k + 5) = 3 n + 7$ even is. QED. Bij een bewijs met contrapositie van de bewering $Q(x)\forall x \in S : P(x) \implies Q(x)$ , toon je aan dat $¬P(x)\forall x \in S : \lnot Q(x) \implies \lnot P(x)$ waar is. Dit is logisch equivalent aan de eerste bewering, waarmee die dus ook bewezen is. Stelling Voor iedere $x∈Zx\in\Z$ , als $5 x - 7$ even is, dan is $x$ oneven. Bewijs Neem $x∈Zx\in\Z$ . We bewijzen dit met contrapositie, dus we nemen aan dat $x$ even is en tonen aan dat $5 x - 7$ oneven is. Er bestaat dus een $k∈Zk\in\Z$ zodat $x = 2 k$ . Dit geeft: $5 x - 7 = 5 (2 k) - 7 = 2 (5 k - 4) + 1$ Omdat $5k−4∈Z5k-4\in\Z$ , geldt dat $2 (5 k - 4) + 1 = 5 x - 7$ oneven is. QED. Een lemma is een (kleine) stelling die helpt bij het bewijzen van een grotere stelling. Het is dus eigenlijk een hulpstelling. Het kan soms handig zijn een bewering te bewijzen door verschillende gevallen te onderscheiden. Bij gevalsonderscheiding moeten de gevallen alle mogelijkheden dekken. Er mag wel overlap in zitten. Stelling Voor elke $n∈Zn\in\Z$ geldt dat $n^2+3n+5$ oneven is. Bewijs Neem $n∈Zn\in\Z$ . We onderscheiden twee gevallen: (1) $n$ is even en (2) $n$ is oneven. Geval (1): $n$ is even. Dan bestaat er een $k∈Zk\in\Z$ zodat $n = 2 k$ Dit geeft $n^2+3n+5 = (2k)^2+3(2k)+5 = 4k^2+6k+5 = 2(2k^2+3k+2)+1$ . Omdat $2k2+3k+2∈Z2k^2+3k+2\in\Z$ , geldt dat $2(2k^2+3k+2)+1=n^2+3n+5$ oneven is. Geval (2): $n$ is oneven. Dan bestaat er een $k∈Zk\in\Z$ zodat $n = 2 k + 1$ . Dit geeft $n^2+3n+5 = (2k+1)^2+3(2k+1)+5 = 4k^2+10k+9 = 2(2k^2+5k+4)+1$ . Omdat $2k2+5k+4∈Z2k^2+5k+4\in\Z$ , geldt dat $2(2k^2+5k+4)+1=n^2+3n+5$ oneven is. QED. Soms is het bij gevalsonderscheiding handig om zelfs nog deelgevallen te onderscheiden.
11 september 2024
Verzamelingenleer

Een verzameling is een collectie van objecten, die elementen heten. Verzamelingen worden vaak genoteerd met hoofdletters, elementen vaak met kleine letters. De elementen van verzamelingen kunnen zelf ook verzamelingen zijn. Als $a$ een element is van $A$ , noteren we $\in A$ . Anders $\notin A$ . De cardinaliteit van een verzameling $A$ is het aantal elementen van $A$ , notatie $∣ A ∣$ . Zo geldt bijvoorbeeld ${2,4,6,8\}|=4$ . De lege verzameling, notatie $∅\emptyset$ , is de verzameling die geen elementen bevat: $∅={}\emptyset = \{\}$ . Een verzameling $A$ kan op verschillende manieren genoteerd worden (dit is telkens dezelfde verzameling): Opsomming: $A=\{2,4,6,8,10,12,14,16,18,20\}$ Puntjes: $A=\{2,4,6,...,20\}$ Bewering: $A={2x:x∈Z∧1≤x≤10}A=\{2x : x \in \Z \land 1 \leq x \leq 10\}$ Van verzamelingen maken de volgorde en dubbele elementen niet uit. Zo is ${1,2,3} = {1,3,2} = {1,2,1,3,1}$ . Een verzameling $A$ is een deelverzameling van verzameling $B$ als alle elementen van $A$ ook elementen zijn van $B$ , notatie $\subseteq B$ . Stelling Als $\subseteq B$ en $\subseteq C$ , dan $\subseteq C$ . Twee verzamelingen $A$ en $B$ zijn gelijk, notatie $A = B$ , als $A$ en $B$ precies dezelfde elementen hebben, oftewel $\subseteq B$ en $\subseteq A$ . De verzameling $A$ is een strikte deelverzameling van $B$ als $\subseteq B$ en $\neq B$ . Dit noteer je als $\subset B$ . De machtsverzameling van $A$ , notatie $P(A)\mathcal P(A)$ , is de verzameling van alle deelverzamelingen van $A$ . Dus $P(A)={B:B⊆A}\mathcal P(A) = \{B : B \subseteq A\}$ . Voorbeeld De machtsverzameling van $A=\{1,2\}$ is gelijk aan: $\mathcal P(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\} \}$ Er geldt: $∣P(A)∣=2∣A∣|\mathcal P(A)|=2^{|A|}$ . Op twee verzamelingen $A$ en $B$ kun je operaties uitvoeren. De vereniging van $A$ en $B$ , notatie $\cup B$ , bevat alle elementen die in $A$ of in $B$ zitten (inclusief). $\cup B = \{x : x \in A \lor x \in B\}$ De doorsnede van $A$ en $B$ , notatie $\cap B$ , bevat alle elementen die in $A$ en in $B$ zitten. $\cap B = \{x : x \in A \land x \in B\}$ Verzamelingen $A$ en $B$ heten disjunct als $\cap B = \emptyset$ . Het verschil van $A$ en $B$ , notatie $A\BA \backslash B$ , bevat alle elementen die wel in $A$ zitten, maar niet in $B$ . $A\B={x:x∈A∧x∉B} A \backslash B = \{x : x \in A \land x \notin B\}$ Er geldt: $\cap B \subseteq A \cup B$ . De universele verzameling, notatie $U$ , is de verzameling waar alle verzamelingen (van interesse) deelverzameling van zijn. Het complement van $A$ , notatie $A‾\overline A$ , bevat alle elementen die wel in $U$ zitten, maar niet in $A$ . $\overline A = \{x : x \in U \land x \notin A\}$ Er geldt: $\overline{\overline A} = A$ en $A∩B‾=A\B A \cap \overline B = A \backslash B$ . Voorbeeld Gegeven zijn verzamelingen $A=\{2,5,7,8\}$ , $B=\{1,3,5,7\}$ en $U=\{1,2,...,10\}$ . Nu geldt: $\cup B = \{1,2,3,5,7,8\}$ $\cap B = \{5,7\}$ $A\B={2,8} A \backslash B = \{2,8\}$ $\overline A = \{1,3,4,6,9,10\}$ Een geordend paar van $x$ en $y$ , notatie $(x, y)$ , is een "gesorteerde verzameling". Er geldt namelijk: $\iff (a=c \land b=d)$ . Het carthesisch product van verzamelingen $A$ en $B$ , notatie $\times B$ , is de verzameling met alle geordende paren van $A$ en $B$ : $\times B = \{(a,b) : a \in A \land b \in B\}$ Voorbeeld Gegeven zijn de verzamelingen $A=\{x,y\}$ en $B=\{1,2,3\}$ . $\times B = \{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)\}$ Er geldt: $\times B| = |A| \cdot |B|$ . De vereniging van verzamelingen $A_1,A_2,...,A_n$ wordt genoteerd als notatie $A1∪A2∪...∪AnA_1 \cup A_2 \cup ... \cup A_n$ , of: $\bigcup^n_{i=1} A_i = \{x : x \in A_i \text{ voor een } i \text{ waarvoor } 1 \leq i \leq n\}$ De doorsnede van verzamelingen $A_1,A_2,...,A_n$ wordt genoteerd als notatie $A1∩A2∩...∩AnA_1 \cap A_2 \cap ... \cap A_n$ , of: $\bigcap^n_{i=1} A_i = \{x : x \in A_i \text{ voor elke } i \text{ waarvoor } 1 \leq i \leq n\}$ Voorbeeld Gegeven zijn de verzamelingen $B_1=\{1,2\}, B_2=\{2,3\}, ..., B_9=\{9,10\}$ . Dan geldt: $\bigcup^9_{i=1} B_i = B_1 \cup B_2 \cup ... \cup B_9 = \{1,2,3,4,5,6,7,8,9,10\}$ $\bigcap^9_{i=1} B_i = B_1 \cap B_2 \cap ... \cap B_9 = \emptyset$ We nemen een indexverzameling $I$ en we nemen aan dat $SαS_{\alpha}$ een verzameling is voor elke $α∈I\alpha\in I$ , notatie $\{S_\alpha\}_{\alpha\in I}$ . Nu is de vereniging $\bigcup_{\alpha \in I} S<em>\alpha = \{x : x \in S</em>\alpha \text{ voor een } \alpha \in I\}$ . En de doorsnede is $\bigcap_{\alpha \in I} S<em>\alpha = \{x : x \in S</em>\alpha \text{ voor iedere } \alpha \in I\}$ . Voorbeeld Voor $n∈N\{0}n \in \N \backslash \{0\}$ , gegeven is de verzameling $An=[−1n,1n]A_n = [-\frac 1n, \frac 1n]$ . Dan $⋃n∈N\{0}An=A1∪A2∪...∪An=[−1,1]∪[−12,12]∪...∪[−1n,1n]=[−1,1] \bigcup_{n \in \N \backslash \{0\}} A_n = A_1 \cup A_2 \cup ... \cup A_n = [-1,1]\cup[-\tfrac12, \tfrac12]\cup ... \cup[-\tfrac1n, \tfrac1n] = [-1,1]$ $⋂n∈N\{0}An=A1∩A2∩...∩An=[−1,1]∩[−12,12]∩...∩[−1n,1n]={0} \bigcap_{n \in \N \backslash \{0\}} A_n = A_1 \cap A_2 \cap ... \cap A_n = [-1,1]\cap[-\tfrac12, \tfrac12]\cap ... \cap[-\tfrac1n, \tfrac1n] = \{0\}$ Laat $S$ een verzameling met deelverzamelingen van $A$ zijn, ofwel $\subseteq \mathcal P(A)$ . Dan is $S$ paarsgewijs disjunct precies als $\cap y = \emptyset$ voor alle $\in S$ met $\neq y$ . Voorbeeld Gegeven zijn $A=\{1,2,...,7\}$ , $B=\{1,6\}$ , $C=\{2,5\}$ , $D=\{4,7\}$ . Omdat $\subseteq A$ , geldt dat $S={B,C,D}⊆P(A)S=\{B,C,D\} \subseteq \mathcal P(A)$ . Omdat $\cap C = \emptyset$ , $\cap D = \emptyset$ en $\cap D = \emptyset$ , geldt dat $S$ paarsgewijs disjunct is. Een partitie van een verzameling $A$ is een verzameling $S$ met deelverzamelingen van $A$ waarvoor geldt: $\emptyset \notin S$ Voor elke $\in S$ met $\neq y$ geldt $\cap y = \emptyset$ ( $S$ is paarsgewijs disjunct) $\bigcup_{x \in S} x = A$ Voorbeeld Gegeven is $A=\{1,2,3,4,5,6\}$ . De verzameling $S_1=\{ \{1,3,6\}, \{2,4\}, \{5\} \}$ is een partitie van $A$ . De verzameling $S2={{1,2,3},{4},∅,{5,6}}S_2=\{ \{1,2,3\}, \{4\}, \emptyset, \{5,6\} \}$ is geen partitie van $A$ , omdat het niet voldoet aan eis (1). De verzameling $S_3=\{ \{1,2\}, \{3,4,5\}, \{5,6\} \}$ is geen partitie van $A$ , omdat het niet voldoet aan eis (2). De verzameling $S_4=\{ \{1,4\}, \{3,5\}, \{2\} \}$ is geen partitie van $A$ , omdat het niet voldoet aan eis (3). De verzameling $S_5=\{ \{1,4\}, \{2,5\}, \{3\}, \{6\} \}$ is een partitie van $A$ .
9 september 2024
Logica

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 $(x-3)^2 \leq 1$ over $S=ZS=\Z$ . Dan geldt bijvoorbeeld $P (2)$ is waar, $P (3)$ is waar, $P (4)$ is waar, maar $P (5)$ is niet waar. 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$ Beweringen kun je samenvoegen tot een nieuwe bewering. De negatie van een bewering $P$ is een nieuwe bewering, notatie $¬P\lnot P$ ("niet- $P$ "). De bewering $¬P\lnot P$ is alleen waar als de bewering $P$ niet waar is. De waarheidstabel ziet er dan zo uit: $P$ $¬P\lnot P$ $T$ $F$ $F$ $T$ De disjunctie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $\lor Q$ (" $P$ of $Q$ "). De bewering $\lor Q$ is waar wanneer minstens één van $P$ en $Q$ waar is. De waarheidstabel ziet er dan zo uit: $P$ $Q$ $\lor Q$ $T$ $T$ $T$ $T$ $F$ $T$ $F$ $T$ $T$ $F$ $F$ $F$ De conjunctie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $\land Q$ (" $P$ en $Q$ "). De bewering $\land Q$ is waar wanneer zowel $P$ als $Q$ waar is. De waarheidstabel ziet er dan zo uit: $P$ $Q$ $\land Q$ $T$ $T$ $T$ $T$ $F$ $F$ $F$ $T$ $F$ $F$ $F$ $F$ De implicatie van beweringen $P$ en $Q$ is een nieuwe bewering, notatie $\implies Q$ ("als $P$ , dan $Q$ "). De bewering $\implies Q$ is waar wanneer zowel $P$ als $Q$ waar is, of $P$ niet waar is. In de implicatie $\implies Q$ heet $P$ de voowaarde en $Q$ de conclusie. De implicatie $\implies P$ is de omkering van $\implies Q$ . De waarheidstabel ziet er dan zo uit: $P$ $Q$ $\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=ZS=\Z$ . Nu zijn $\implies P(-3)$ en $\implies P(2)$ waar, maar $\implies P(3)$ is niet waar. Verder geldt voor iedere $x$ dat $\implies Q(x)$ waar is. Voor beweringen $P$ en $Q$ heet de conjunctie $\implies Q) \land (Q \implies P)$ de bi-implicatie, notatie $\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$ $\iff Q$ $T$ $T$ $T$ $T$ $F$ $F$ $F$ $T$ $F$ $F$ $F$ $T$ Een tautologie is een bewering die altijd waar is. Voorbeeld De bewering $\lor \lnot P$ is een tautologie, wat volgt uit de waarheidstabel: $P$ $¬P\lnot P$ $\lor \lnot P$ $T$ $F$ $T$ $F$ $T$ $T$ Een tegenspraak is een bewering die nooit waar is. Voorbeeld De bewering $\land \lnot P$ is een tegenspraak, wat volgt uit de waarheidstabel: $P$ $¬P\lnot P$ $\land \lnot P$ $T$ $F$ $F$ $F$ $T$ $F$ Er geldt: als $P$ een tautologie is, dan is $¬P\lnot P$ een tegenspraak. Samengestelde beweringen $P$ en $Q$ zijn logisch equivalent als ze precies dezelfde waarheidstabellen hebben. We noteren dat als $\equiv Q$ . Er geldt: $P$ en $Q$ zijn logisch equivalent dan en slechts dan als $\iff Q$ een tautologie is. Met deze definitie van logische equivalentie kunnen we een paar eigenschappen opschrijven over beweringen $P$ , $Q$ en $R$ : $\lor Q \equiv Q \lor P$ en $\land Q \equiv Q \land P$ $\lor (Q \lor R) \equiv (P \lor Q) \lor R$ en $\land (Q \land R) \equiv (P \land Q) \land R$ $\lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ en $\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. Een quantor maakt van een open bewering een gesloten bewering. De universele quantor, notatie $∀\forall$ , betekent dat iets waar is voor ieder element uit het domein. Zo betekent $∀x∈S:P(x)\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 $∀x∈{1,2,3,...}:P(x)\forall x \in \{1,2,3,...\}:P(x)$ waar is. Maar de bewering $∀x∈{0,1,2,3,...}:P(x)\forall x \in \{0, 1, 2, 3, ...\}:P(x)$ is niet waar, omdat deze niet waar is voor $x = 0$ . De existentiële quantor, notatie $∃\exists$ , betekent dat iets waar is voor minimaal één element uit het domein. Zo betekent $∃x∈S:P(x)\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 $∃x∈{0,1,2,3,...}:P(x)\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 $∃x∈R:P(x)\exists x \in \R : P(x)$ waar, bijvoorbeeld voor $x=3x=\sqrt3$ . De bewering $∃x∈Z:P(x)\exists x \in \Z : P(x)$ daarentegen is niet waar. 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)$

Gemaakt door Jeroen van Rensen.