Bij bewijzen met reële getallen gebruik je vaak dat xn≥0x^n \ge 0 voor even, positieve nn. Stelling ∀x,y∈R:13x2+34y2≥xy \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=4x2−12xy+9y2(2x-3y)^2 = 4x^2 - 12xy + 9y^2. Nu krijgen we: (2x−3y)2≥0 (2x-3y)^2 \ge 0 4x2−12xy+9y2≥0 4x^2 - 12xy + 9y^2 \ge 0 4x2+9y2≥12xy 4x^2 + 9y^2 \ge 12xy 13x2+34y2≥xy \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 ∀x∈R:∣x∣2=x2 \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<0x<0. (1) We nemen aan dat x≥0x\ge0. Dan, per definitie van de absolute waarde, geldt ∣x∣=x|x|=x en dus ook ∣x∣2=x2|x|^2=x^2. (2) We nemen aan dat x<0x<0. Dan, per definitie van de absolute waarde, geldt ∣x∣=−x|x|=-x en daaruit volgt dat ∣x∣2=(−x)2=x2|x|^2=(-x)^2=x^2. QED. Dan nu de stelling. Stelling ∀x,y∈R:∣x+y∣≤∣x∣+∣y∣ \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: xy≤∣x∣∣y∣x2+2xy+y2≤x2+2∣x∣∣y∣+y2x2+2xy+y2≤∣x∣2+2∣x∣∣y∣+∣y∣2(x+y)2≤(∣x∣+∣y∣)2(∣x+y∣)2≤(∣x∣+∣y∣)2∣x+y∣≤∣x∣+∣y∣ \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 xx uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen AA en BB toon je eerst aan dat A⊆BA \subseteq B, en daarna B⊆AB \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 x∈Ax \in A en x∉Bx \notin B. Omdat x∉Bx \notin B, geldt x∈B‾x \in \overline B. Er geldt dus x∈Ax \in A en x∈B‾x \in \overline B, dus x∈A∩B‾x \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 x∈A∩B‾x \in A \cap \overline B. Dus x∈Ax \in A en x∈B‾x \in \overline B. Uit x∈B‾x \in \overline B volgt x∉Bx \notin B. Er geldt dus x∈Ax \in A en x∉Bx \notin B, dus x∈A\Bx \in A \backslash B. Uit x∈A∩B‾ ⟹ 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)(x,y) uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling (A⊆C∧B⊆D) ⟹ A×B⊆C×D (A \subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D Bewijs Neem aan dat A⊆CA \subseteq C en B⊆DB \subseteq D. Laat (x,y)∈A×B(x,y) \in A \times B. Dan geldt dat x∈Ax \in A. Omdat A⊆CA \subseteq C, geldt ook dat x∈Cx \in C. Vergelijkbaar geldt dat y∈By \in B, waaruit volgt dat y∈Dy \in D. Omdat x∈Cx \in C en y∈Dy \in D, geldt dat (x,y)∈C×D(x,y) \in C \times D. Uit (x,y)∈A×B ⟹ (x,y)∈C×D(x,y) \in A \times B \implies (x,y) \in C \times D concluderen we dat A×B⊆C×DA \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)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 ∀x∈R:(x−1)2>0 \forall x \in \R : (x-1)^2 > 0 . Voor x=0x=0 is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering PP kan contradictie gebruikt worden. Bij contradictie neem je aan dat ¬P\lnot P, om vervolgens FF (niet waar) te concluderen. Als dit lukt, is er bewezen dat PP waar is. Stelling Er bestaat geen kleinste x∈R+x \in \R^+. Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste x∈R+x \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 r∈Qr \in \mathbb Q. Omdat r∈Qr \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 xr∈Qxr \in \mathbb Q. Dan bestaan er c,d∈Zc,d\in\Z met d≠0d\neq0 zodat xr=cdxr=\dfrac cd. Dit geeft xab=cdx \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.
Bij bewijzen met reële getallen gebruik je vaak dat xn≥0x^n \ge 0 voor even, positieve nn. Stelling ∀x,y∈R:13x2+34y2≥xy \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=4x2−12xy+9y2(2x-3y)^2 = 4x^2 - 12xy + 9y^2. Nu krijgen we: (2x−3y)2≥0 (2x-3y)^2 \ge 0 4x2−12xy+9y2≥0 4x^2 - 12xy + 9y^2 \ge 0 4x2+9y2≥12xy 4x^2 + 9y^2 \ge 12xy 13x2+34y2≥xy \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 ∀x∈R:∣x∣2=x2 \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<0x<0. (1) We nemen aan dat x≥0x\ge0. Dan, per definitie van de absolute waarde, geldt ∣x∣=x|x|=x en dus ook ∣x∣2=x2|x|^2=x^2. (2) We nemen aan dat x<0x<0. Dan, per definitie van de absolute waarde, geldt ∣x∣=−x|x|=-x en daaruit volgt dat ∣x∣2=(−x)2=x2|x|^2=(-x)^2=x^2. QED. Dan nu de stelling. Stelling ∀x,y∈R:∣x+y∣≤∣x∣+∣y∣ \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: xy≤∣x∣∣y∣x2+2xy+y2≤x2+2∣x∣∣y∣+y2x2+2xy+y2≤∣x∣2+2∣x∣∣y∣+∣y∣2(x+y)2≤(∣x∣+∣y∣)2(∣x+y∣)2≤(∣x∣+∣y∣)2∣x+y∣≤∣x∣+∣y∣ \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 xx uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen AA en BB toon je eerst aan dat A⊆BA \subseteq B, en daarna B⊆AB \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 x∈Ax \in A en x∉Bx \notin B. Omdat x∉Bx \notin B, geldt x∈B‾x \in \overline B. Er geldt dus x∈Ax \in A en x∈B‾x \in \overline B, dus x∈A∩B‾x \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 x∈A∩B‾x \in A \cap \overline B. Dus x∈Ax \in A en x∈B‾x \in \overline B. Uit x∈B‾x \in \overline B volgt x∉Bx \notin B. Er geldt dus x∈Ax \in A en x∉Bx \notin B, dus x∈A\Bx \in A \backslash B. Uit x∈A∩B‾ ⟹ 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)(x,y) uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling (A⊆C∧B⊆D) ⟹ A×B⊆C×D (A \subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D Bewijs Neem aan dat A⊆CA \subseteq C en B⊆DB \subseteq D. Laat (x,y)∈A×B(x,y) \in A \times B. Dan geldt dat x∈Ax \in A. Omdat A⊆CA \subseteq C, geldt ook dat x∈Cx \in C. Vergelijkbaar geldt dat y∈By \in B, waaruit volgt dat y∈Dy \in D. Omdat x∈Cx \in C en y∈Dy \in D, geldt dat (x,y)∈C×D(x,y) \in C \times D. Uit (x,y)∈A×B ⟹ (x,y)∈C×D(x,y) \in A \times B \implies (x,y) \in C \times D concluderen we dat A×B⊆C×DA \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)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 ∀x∈R:(x−1)2>0 \forall x \in \R : (x-1)^2 > 0 . Voor x=0x=0 is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering PP kan contradictie gebruikt worden. Bij contradictie neem je aan dat ¬P\lnot P, om vervolgens FF (niet waar) te concluderen. Als dit lukt, is er bewezen dat PP waar is. Stelling Er bestaat geen kleinste x∈R+x \in \R^+. Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste x∈R+x \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 r∈Qr \in \mathbb Q. Omdat r∈Qr \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 xr∈Qxr \in \mathbb Q. Dan bestaan er c,d∈Zc,d\in\Z met d≠0d\neq0 zodat xr=cdxr=\dfrac cd. Dit geeft xab=cdx \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.
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)P(m) niet waar is. Het doel is om dan uit te komen op een contradictie. Stelling ∀n∈N:6∣n3−n \forall n \in \N : 6 | n^3 - n Bewijs Bij contradictie, neem aan dat er een n∈Nn\in\N bestaat waarvoor 6∤n3−n6 \nmid n^3 - n. Dan bestaat er een kleinste m∈Nm\in\N waarvoor 6∤m3−m6 \nmid m^3 - m. Omdat 6∣13−1=06|1^3-1=0 en 6∣23−2=66|2^3-2=6, moet gelden dat m≥3m \ge 3. Dan schrijven we m=k+2m=k+2 voor een k∈Nk\in\N met 1≤k<m1 \le k < m. Nu geldt: m3−m=(k+2)3−(k+2)=k3−k+6(k2+2k+1) m^3-m = (k+2)^3-(k+2) = k^3-k+6(k^2+2k+1) Omdat k<mk<m en mm het kleinste getal is waarvoor 6∤m3−m6 \nmid m^3-m, geldt dat 6∣k3−k6|k^3-k. We schrijven kk dus als 6x6x voor een x∈Zx\in\Z. Dit geeft: m3−m=6x+6(k2+2k+1) m^3-m = 6x + 6(k^2+2k+1) En omdat x,k2+2k+1∈Zx, k^2+2k+1 \in \Z, concluderen we dat 6∣m3−m6|m^3-m. Dit is een contradictie. QED. Sterke inductie is een uitbreiding op normale inductie, en gaat alsvolgt: Laat P(n)P(n) een bewering zijn met domein N\N. Als (1) P(1)P(1) waar is en (2) ∀k∈N:(P(1)∧P(2)∧...∧P(k)) ⟹ 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 ana_n recursief gedefiniëerd zijn door a1=1a_1=1, a2=3a_2=3 en an=2an−1−an−2a_n = 2a_{n-1} - a_{n-2} voor n≥3n \ge 3. Dan geldt an=2n−1a_n=2n-1 voor alle n∈Nn\in\N. Bewijs Met sterke inductie op nn, bewijzen we (1) 1=2(1)−11=2(1)-1 en 2=2(2)−12=2(2)-1, en (2) ∀k∈N:(a1=2(1)−1∧a2=2(2)−1∧...∧ak=2k−1) ⟹ 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=12(1)-1=1 en 2(2)−1=32(2)-1=3, dus dit klopt. (2) Laat k∈Nk\in\N. We nemen aan dat ai=2i−1a_i=2i-1 geldt voor elke i∈Ni\in\N waarvoor i<ki<k. Er geldt: ak=2ak−1−ak−2=IH2(2(k−1)−1)−(2(k−2)−1)=2k−1 \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 AA en BB is een relatie RR van AA naar BB een deelverzameling van A×BA \times B. Als (a,b)∈R(a,b) \in R, zeggen we dat aa gerelateerd is aan bb, notatie aRbaRb. Voor een relatie RR van AA naar BB geldt dat het domein, notatie dom(R)\text{dom}(R), en het bereik, notatie range(R)\text{range}(R), gelijk zijn aan: dom(R)={a∈A:(a,b)∈R voor een b∈B} \text{dom}(R) = \{ a \in A : (a, b) \in R \text{ voor een } b \in B \} range(R)={b∈B:(a,b)∈R voor een a∈A} \text{range}(R) = \{ b \in B : (a, b) \in R \text { voor een } a \in A \} Voorbeeld Gegeven zijn A={1,2,3}A=\{1,2,3\}, B={x,y}B=\{x,y\} en R={(2,x),(1,y),(2,y)}R=\{(2,x),(1,y),(2,y)\}. Er geldt R⊆A×BR \subseteq A \times B, dus RR is een relatie van AA naar BB. 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 RR van AA naar BB, notatie R−1R^{-1}, is een relatie van BB naar AA, zodat: R−1={(b,a):(a,b)∈R} R^{-1} = \{ (b,a) : (a,b) \in R \} Een relatie RR op een verzameling AA is een relatie van AA naar AA, oftewel R⊆A×AR \subseteq A \times A. Laat RR een relatie zijn op AA. Dan is RR: Reflexief precies als aRaaRa voor alle a∈Aa \in A. Symmetrisch precies als aRb ⟹ bRaaRb \implies bRa voor alle a,b∈Aa,b \in A. Transitief precies als (aRb∧bRc) ⟹ aRc(aRb \land bRc) \implies aRc voor alle a,b,c∈Aa,b,c \in A. Voorbeeld Laat RR de relatie zijn op R\R zodat aRbaRb precies als ∣a−b∣≤1|a-b|\le1. Dan is RR wel reflexief, wel symmetrisch, maar niet transitief.
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)f(x) Domein Bereik sin(x)\sin(x) R\R [−1,1][-1,1] arcsin(x)\arcsin(x) [−1,1][-1,1] [−12π,12π][-\frac12\pi,\frac12\pi] cos(x)\cos(x) R\R [−1,1][-1,1] arccos(x)\arccos(x) [−1,1][-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: ddxsin(arcsin(x))=ddxx \tfrac{d}{dx} \sin(\arcsin(x)) = \tfrac{d}{dx} x cos(arcsin(x))⋅ddxarcsin(x)=1 \cos(\arcsin(x)) \cdot \tfrac{d}{dx} \arcsin(x) = 1 ddxarcsin(x)=1cos(arcsin(x)) \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 xx noemen en een andere zijde 11. 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: ddxarcsin(x)=11−x2 \tfrac{d}{dx} \arcsin(x) = \frac1{\sqrt{1-x^2}} Op vergelijkbare wijze krijgen we ook dat: ddxarccos(x)=−11−x2 \tfrac{d}{dx} \arccos(x) = \frac{-1}{\sqrt{1-x^2}} ddxarctan(x)=11+x2 \tfrac{d}{dx} \arctan(x) = \frac{1}{1+x^2}
Bij bewijzen met reële getallen gebruik je vaak dat xn≥0x^n \ge 0 voor even, positieve nn. Stelling ∀x,y∈R:13x2+34y2≥xy \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=4x2−12xy+9y2(2x-3y)^2 = 4x^2 - 12xy + 9y^2. Nu krijgen we: (2x−3y)2≥0 (2x-3y)^2 \ge 0 4x2−12xy+9y2≥0 4x^2 - 12xy + 9y^2 \ge 0 4x2+9y2≥12xy 4x^2 + 9y^2 \ge 12xy 13x2+34y2≥xy \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 ∀x∈R:∣x∣2=x2 \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<0x<0. (1) We nemen aan dat x≥0x\ge0. Dan, per definitie van de absolute waarde, geldt ∣x∣=x|x|=x en dus ook ∣x∣2=x2|x|^2=x^2. (2) We nemen aan dat x<0x<0. Dan, per definitie van de absolute waarde, geldt ∣x∣=−x|x|=-x en daaruit volgt dat ∣x∣2=(−x)2=x2|x|^2=(-x)^2=x^2. QED. Dan nu de stelling. Stelling ∀x,y∈R:∣x+y∣≤∣x∣+∣y∣ \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: xy≤∣x∣∣y∣x2+2xy+y2≤x2+2∣x∣∣y∣+y2x2+2xy+y2≤∣x∣2+2∣x∣∣y∣+∣y∣2(x+y)2≤(∣x∣+∣y∣)2(∣x+y∣)2≤(∣x∣+∣y∣)2∣x+y∣≤∣x∣+∣y∣ \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 xx uit een verzameling te nemen, en daarmee te redeneren met de eigenschappen van de verzameling. Voor gelijkheid van verzamelingen AA en BB toon je eerst aan dat A⊆BA \subseteq B, en daarna B⊆AB \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 x∈Ax \in A en x∉Bx \notin B. Omdat x∉Bx \notin B, geldt x∈B‾x \in \overline B. Er geldt dus x∈Ax \in A en x∈B‾x \in \overline B, dus x∈A∩B‾x \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 x∈A∩B‾x \in A \cap \overline B. Dus x∈Ax \in A en x∈B‾x \in \overline B. Uit x∈B‾x \in \overline B volgt x∉Bx \notin B. Er geldt dus x∈Ax \in A en x∉Bx \notin B, dus x∈A\Bx \in A \backslash B. Uit x∈A∩B‾ ⟹ 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)(x,y) uit de verzameling en redeneer je met de eigenschappen van de verzameling. Stelling (A⊆C∧B⊆D) ⟹ A×B⊆C×D (A \subseteq C \land B \subseteq D) \implies A \times B \subseteq C \times D Bewijs Neem aan dat A⊆CA \subseteq C en B⊆DB \subseteq D. Laat (x,y)∈A×B(x,y) \in A \times B. Dan geldt dat x∈Ax \in A. Omdat A⊆CA \subseteq C, geldt ook dat x∈Cx \in C. Vergelijkbaar geldt dat y∈By \in B, waaruit volgt dat y∈Dy \in D. Omdat x∈Cx \in C en y∈Dy \in D, geldt dat (x,y)∈C×D(x,y) \in C \times D. Uit (x,y)∈A×B ⟹ (x,y)∈C×D(x,y) \in A \times B \implies (x,y) \in C \times D concluderen we dat A×B⊆C×DA \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)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 ∀x∈R:(x−1)2>0 \forall x \in \R : (x-1)^2 > 0 . Voor x=0x=0 is deze bewering niet waar, dus daarmee is aangetoond dat de hele bewering niet waar is. Bij het bewijzen van een bewering PP kan contradictie gebruikt worden. Bij contradictie neem je aan dat ¬P\lnot P, om vervolgens FF (niet waar) te concluderen. Als dit lukt, is er bewezen dat PP waar is. Stelling Er bestaat geen kleinste x∈R+x \in \R^+. Bewijs Met bewijs uit contradictie, neem aan dat er een kleinste x∈R+x \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 r∈Qr \in \mathbb Q. Omdat r∈Qr \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 xr∈Qxr \in \mathbb Q. Dan bestaan er c,d∈Zc,d\in\Z met d≠0d\neq0 zodat xr=cdxr=\dfrac cd. Dit geeft xab=cdx \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.
Twee getallen a,b∈Za,b\in\Z hebben dezelfde pariteit als aa en bb allebei even of allebei oneven zijn. Voor twee getallen a,b∈Za,b\in\Z met a≠0a\neq0 zeggen we dat "aa deelt bb", notatie a∣ba|b, precies als er een c∈Zc\in\Z bestaat zodat b=acb=ac. Voor een even n∈Zn\in\Z geldt dus dat 2∣n2|n. Voorbeeld Er geldt 3∣63|6, 4∣44|4 en −2∣10-2|10. Als a∣ba|b, zeggen we dat aa een deler is van bb en bb een veelvoud is van aa. Verder, als aa niet bb deelt, schrijven we a∤ba \nmid b. Stelling Laat a,b,c∈Za,b,c\in\Z met a,b≠0a,b\neq0. Als a∣ba|b en b∣cb|c, dan a∣ca|c. Bewijs Neem a,b,c∈Za,b,c\in\Z met a,b≠0a,b\neq0 zodat a∣ba|b en b∣cb|c. Dan bestaat er x,y∈Zx,y\in\Z zodat b=axb=ax en c=byc=by. Er geldt dus dat c=axyc=axy. Omdat xy∈Zxy\in\Z, geldt dat a∣ca|c. QED. Voor a,b,n∈Za,b,n\in\Z met n≥2n\ge2 zeggen we dat aa congruent is aan bb modulo nn, notatie a≡bmod na \equiv b \mod n, precies als n∣a−bn|a-b. Voorbeeld Er geldt 15≡7mod 415\equiv7\mod4, want 4∣15−7=84|15-7=8. Verder geldt 3≡−15mod 93\equiv-15\mod9, want 9∣3−−15=189|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 a≡bmod na \equiv b \mod n, dan ak≡bkmod nak \equiv bk \mod n. Bewijs Neem a,b,k,n∈Za,b,k,n\in\Z met n≥2n\ge2 zodat a≡bmod na \equiv b \mod n. Dan geldt n∣a−bn|a-b, dus er bestaat een x∈Zx\in\Z zodat a−b=nxa-b=nx. Nu geldt ak−bk=nkxak-bk=nkx. Omdat kx∈Zkx\in\Z, geldt n∣ak−bkn|ak-bk en dus ak≡bkmod nak \equiv bk \mod n. QED.
Bij het bewijzen van een stelling bewijs je meestal een implicatie van de vorm: ∀x∈S:P(x) ⟹ Q(x) \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)Q(x) altijd waar is, wat de implicatie waar maakt. Bij een vaculeus bewijs toon je aan dat P(x)P(x) nooit waar is, wat de implicatie ook waar maakt. Dit is een voorbeeld van een triviaal bewijs: Stelling ∀x∈R:x<0 ⟹ x2+1>0 \forall x \in \R : x < 0 \implies x^2 + 1 > 0 Bewijs Neem x∈Rx \in R. Omdat x2≥0x^2 \ge 0, geldt x2+1≥1>0x^2 + 1 \ge 1 > 0. Dus x2+1>0x^2 + 1 > 0. QED. En dit is een voorbeeld van een vaculeus bewijs: Stelling ∀x∈R:x2−2x+2≤0 ⟹ x3≥8 \forall x \in \R : x^2-2x+2 \le 0 \implies x^3 \ge 8 Bewijs Neem x∈Rx \in \R. Merk op dat x2−2x+1=(x−1)2x^2-2x+1=(x-1)^2. x2−2x+2=(x−1)2+1≥0 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 ∀x∈S:P(x) ⟹ Q(x)\forall x \in S : P(x) \implies Q(x) nemen we een element x∈Sx \in S waarvoor P(x)P(x) waar is, en gebruiken we eigenschappen van P(x)P(x) om aan te tonen dat Q(x)Q(x) waar is. Stelling Voor iedere n∈Zn \in \Z, als nn oneven is, dan is 3n+73n+7 even. Bewijs Neem een oneven n∈Zn \in \Z. Omdat nn oneven is, bestaat er een k∈Zk \in \Z zodat n=2k+1n = 2k+1. Dan geldt: 3n+7=3(2k+1)+7=6k+10=2(3k+5) 3n + 7 = 3(2k + 1)+ 7 = 6k + 10 = 2(3k + 5) Omdat 3k+5∈Z3k+5\in\Z, geldt dat 2(3k+5)=3n+72(3k+5)=3n+7 even is. QED. Bij een bewijs met contrapositie van de bewering ∀x∈S:P(x) ⟹ Q(x)\forall x \in S : P(x) \implies Q(x), toon je aan dat ∀x∈S:¬Q(x) ⟹ ¬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 5x−75x-7 even is, dan is xx oneven. Bewijs Neem x∈Zx\in\Z. We bewijzen dit met contrapositie, dus we nemen aan dat xx even is en tonen aan dat 5x−75x-7 oneven is. Er bestaat dus een k∈Zk\in\Z zodat x=2kx=2k. Dit geeft: 5x−7=5(2k)−7=2(5k−4)+1 5x-7 = 5(2k)-7 = 2(5k-4)+1 Omdat 5k−4∈Z5k-4\in\Z, geldt dat 2(5k−4)+1=5x−72(5k-4)+1=5x-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 n2+3n+5n^2+3n+5 oneven is. Bewijs Neem n∈Zn\in\Z. We onderscheiden twee gevallen: (1) nn is even en (2) nn is oneven. Geval (1): nn is even. Dan bestaat er een k∈Zk\in\Z zodat n=2kn=2k Dit geeft n2+3n+5=(2k)2+3(2k)+5=4k2+6k+5=2(2k2+3k+2)+1 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(2k2+3k+2)+1=n2+3n+52(2k^2+3k+2)+1=n^2+3n+5 oneven is. Geval (2): nn is oneven. Dan bestaat er een k∈Zk\in\Z zodat n=2k+1n=2k+1. Dit geeft n2+3n+5=(2k+1)2+3(2k+1)+5=4k2+10k+9=2(2k2+5k+4)+1n^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(2k2+5k+4)+1=n2+3n+52(2k^2+5k+4)+1=n^2+3n+5 oneven is. QED. Soms is het bij gevalsonderscheiding handig om zelfs nog deelgevallen te onderscheiden.
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 aa een element is van AA, noteren we a∈Aa \in A. Anders a∉Aa \notin A. De cardinaliteit van een verzameling AA is het aantal elementen van AA, notatie ∣A∣|A|. Zo geldt bijvoorbeeld ∣{2,4,6,8}∣=4|\{2,4,6,8\}|=4. De lege verzameling, notatie ∅\emptyset, is de verzameling die geen elementen bevat: ∅={}\emptyset = \{\}. Een verzameling AA kan op verschillende manieren genoteerd worden (dit is telkens dezelfde verzameling): Opsomming: A={2,4,6,8,10,12,14,16,18,20}A=\{2,4,6,8,10,12,14,16,18,20\} Puntjes: A={2,4,6,...,20}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{1,2,3} = {1,3,2} = {1,2,1,3,1}. Een verzameling AA is een deelverzameling van verzameling BB als alle elementen van AA ook elementen zijn van BB, notatie A⊆BA \subseteq B. Stelling Als A⊆BA \subseteq B en B⊆CB \subseteq C, dan A⊆CA \subseteq C. Twee verzamelingen AA en BB zijn gelijk, notatie A=BA=B, als AA en BB precies dezelfde elementen hebben, oftewel A⊆B A \subseteq B en B⊆A B \subseteq A . De verzameling AA is een strikte deelverzameling van BB als A⊆BA \subseteq B en A≠BA \neq B. Dit noteer je als A⊂BA \subset B. De machtsverzameling van AA, notatie P(A)\mathcal P(A), is de verzameling van alle deelverzamelingen van AA. Dus P(A)={B:B⊆A}\mathcal P(A) = \{B : B \subseteq A\}. Voorbeeld De machtsverzameling van A={1,2}A=\{1,2\} is gelijk aan: P(A)={∅,{1},{2},{1,2}} \mathcal P(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\} \} Er geldt: ∣P(A)∣=2∣A∣|\mathcal P(A)|=2^{|A|}. Op twee verzamelingen AA en BB kun je operaties uitvoeren. De vereniging van AA en BB, notatie A∪BA \cup B, bevat alle elementen die in AA of in BB zitten (inclusief). A∪B={x:x∈A∨x∈B} A \cup B = \{x : x \in A \lor x \in B\} De doorsnede van AA en BB, notatie A∩BA \cap B, bevat alle elementen die in AA en in BB zitten. A∩B={x:x∈A∧x∈B} A \cap B = \{x : x \in A \land x \in B\} Verzamelingen AA en BB heten disjunct als A∩B=∅A \cap B = \emptyset. Het verschil van AA en BB, notatie A\BA \backslash B, bevat alle elementen die wel in AA zitten, maar niet in BB. A\B={x:x∈A∧x∉B} A \backslash B = \{x : x \in A \land x \notin B\} Er geldt: A∩B⊆A∪B A \cap B \subseteq A \cup B . De universele verzameling, notatie UU, is de verzameling waar alle verzamelingen (van interesse) deelverzameling van zijn. Het complement van AA, notatie A‾\overline A, bevat alle elementen die wel in UU zitten, maar niet in AA. A‾={x:x∈U∧x∉A} \overline A = \{x : x \in U \land x \notin A\} Er geldt: A‾‾=A \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}A=\{2,5,7,8\}, B={1,3,5,7}B=\{1,3,5,7\} en U={1,2,...,10}U=\{1,2,...,10\}. Nu geldt: A∪B={1,2,3,5,7,8} A \cup B = \{1,2,3,5,7,8\} A∩B={5,7} A \cap B = \{5,7\} A\B={2,8} A \backslash B = \{2,8\} A‾={1,3,4,6,9,10} \overline A = \{1,3,4,6,9,10\} Een geordend paar van xx en yy, notatie (x,y)(x,y), is een "gesorteerde verzameling". Er geldt namelijk: (a,b)=(c,d) ⟺ (a=c∧b=d)(a,b)=(c,d) \iff (a=c \land b=d). Het carthesisch product van verzamelingen AA en BB, notatie A×BA \times B, is de verzameling met alle geordende paren van AA en BB: A×B={(a,b):a∈A∧b∈B} A \times B = \{(a,b) : a \in A \land b \in B\} Voorbeeld Gegeven zijn de verzamelingen A={x,y}A=\{x,y\} en B={1,2,3}B=\{1,2,3\}. A×B={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)} A \times B = \{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)\} Er geldt: ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|. De vereniging van verzamelingen A1,A2,...,AnA_1,A_2,...,A_n wordt genoteerd als notatie A1∪A2∪...∪AnA_1 \cup A_2 \cup ... \cup A_n, of: ⋃i=1nAi={x:x∈Ai voor een i waarvoor 1≤i≤n} \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 A1,A2,...,AnA_1,A_2,...,A_n wordt genoteerd als notatie A1∩A2∩...∩AnA_1 \cap A_2 \cap ... \cap A_n, of: ⋂i=1nAi={x:x∈Ai voor elke i waarvoor 1≤i≤n} \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 B1={1,2},B2={2,3},...,B9={9,10}B_1=\{1,2\}, B_2=\{2,3\}, ..., B_9=\{9,10\}. Dan geldt: ⋃i=19Bi=B1∪B2∪...∪B9={1,2,3,4,5,6,7,8,9,10} \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\} ⋂i=19Bi=B1∩B2∩...∩B9=∅ \bigcap^9_{i=1} B_i = B_1 \cap B_2 \cap ... \cap B_9 = \emptyset We nemen een indexverzameling II en we nemen aan dat SαS_{\alpha} een verzameling is voor elke α∈I\alpha\in I, notatie {Sα}α∈I \{S_\alpha\}_{\alpha\in I} . Nu is de vereniging ⋃α∈IS<em>α={x:x∈S</em>α voor een α∈I} \bigcup_{\alpha \in I} S<em>\alpha = \{x : x \in S</em>\alpha \text{ voor een } \alpha \in I\} . En de doorsnede is ⋂α∈IS<em>α={x:x∈S</em>α voor iedere α∈I} \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 SS een verzameling met deelverzamelingen van AA zijn, ofwel S⊆P(A)S \subseteq \mathcal P(A). Dan is SS paarsgewijs disjunct precies als x∩y=∅x \cap y = \emptyset voor alle x,y∈Sx,y \in S met x≠yx \neq y. Voorbeeld Gegeven zijn A={1,2,...,7}A=\{1,2,...,7\}, B={1,6}B=\{1,6\}, C={2,5}C=\{2,5\}, D={4,7}D=\{4,7\}. Omdat B,C,D⊆AB,C,D \subseteq A, geldt dat S={B,C,D}⊆P(A)S=\{B,C,D\} \subseteq \mathcal P(A). Omdat B∩C=∅B \cap C = \emptyset, B∩D=∅B \cap D = \emptyset en C∩D=∅C \cap D = \emptyset, geldt dat SS paarsgewijs disjunct is. Een partitie van een verzameling AA is een verzameling SS met deelverzamelingen van AA waarvoor geldt: ∅∉S \emptyset \notin S Voor elke x,y∈Sx,y \in S met x≠yx \neq y geldt x∩y=∅x \cap y = \emptyset (SS is paarsgewijs disjunct) ⋃x∈Sx=A \bigcup_{x \in S} x = A Voorbeeld Gegeven is A={1,2,3,4,5,6}A=\{1,2,3,4,5,6\}. De verzameling S1={{1,3,6},{2,4},{5}}S_1=\{ \{1,3,6\}, \{2,4\}, \{5\} \} is een partitie van AA. De verzameling S2={{1,2,3},{4},∅,{5,6}}S_2=\{ \{1,2,3\}, \{4\}, \emptyset, \{5,6\} \} is geen partitie van AA, omdat het niet voldoet aan eis (1). De verzameling S3={{1,2},{3,4,5},{5,6}}S_3=\{ \{1,2\}, \{3,4,5\}, \{5,6\} \} is geen partitie van AA, omdat het niet voldoet aan eis (2). De verzameling S4={{1,4},{3,5},{2}}S_4=\{ \{1,4\}, \{3,5\}, \{2\} \} is geen partitie van AA, omdat het niet voldoet aan eis (3). De verzameling S5={{1,4},{2,5},{3},{6}}S_5=\{ \{1,4\}, \{2,5\}, \{3\}, \{6\} \} is een partitie van AA.
Een bewering is een zin die waar (TT) is of niet waar (FF) is, maar niet allebei. Beweringen worden vaak opgeschreven met P,Q,R,P1,P2,...,PnP, Q, R, P_1, P_2, ..., P_n. Voorbeelden van beweringen zijn: Het getal 33 is oneven (TT) Het getal 5757 is priem (FF) Een open bewering P(x)P(x) over een domein SS is een bewering voor iedere xx in SS. Voorbeeld Gegeven is de bewering P(x):(x−3)2≤1P(x): (x-3)^2 \leq 1 over S=ZS=\Z. Dan geldt bijvoorbeeld P(2)P(2) is waar, P(3)P(3) is waar, P(4)P(4) is waar, maar P(5)P(5) is niet waar. Een waarheidstabel is een tabel met alle mogelijke waar/niet waar-waardes voor de beweringen. Een waarheidstabel voor nn beweringen heeft 2n2^n rijen. Voorbeeld Voor beweringen PP en QQ ziet de waarheidstabel er als volgt uit: PP QQ TT TT TT FF FF TT FF FF Beweringen kun je samenvoegen tot een nieuwe bewering. De negatie van een bewering PP is een nieuwe bewering, notatie ¬P\lnot P ("niet-PP"). De bewering ¬P\lnot P is alleen waar als de bewering PP niet waar is. De waarheidstabel ziet er dan zo uit: PP ¬P\lnot P TT FF FF TT De disjunctie van beweringen PP en QQ is een nieuwe bewering, notatie P∨QP \lor Q ("PP of QQ"). De bewering P∨QP \lor Q is waar wanneer minstens één van PP en QQ waar is. De waarheidstabel ziet er dan zo uit: PP QQ P∨QP \lor Q TT TT TT TT FF TT FF TT TT FF FF FF De conjunctie van beweringen PP en QQ is een nieuwe bewering, notatie P∧QP \land Q ("PP en QQ"). De bewering P∧QP \land Q is waar wanneer zowel PP als QQ waar is. De waarheidstabel ziet er dan zo uit: PP QQ P∧QP \land Q TT TT TT TT FF FF FF TT FF FF FF FF De implicatie van beweringen PP en QQ is een nieuwe bewering, notatie P ⟹ QP \implies Q ("als PP, dan QQ"). De bewering P ⟹ QP \implies Q is waar wanneer zowel PP als QQ waar is, of PP niet waar is. In de implicatie P ⟹ QP \implies Q heet PP de voowaarde en QQ de conclusie. De implicatie Q ⟹ PQ \implies P is de omkering van P ⟹ QP \implies Q. De waarheidstabel ziet er dan zo uit: PP QQ P ⟹ QP \implies Q TT TT TT TT FF FF FF TT TT FF FF TT Voorbeeld Gegeven zijn de beweringen P(x):x=−3P(x): x = -3 en Q(x):∣x∣=3Q(x): |x| = 3 over S=ZS=\Z. Nu zijn Q(−3) ⟹ P(−3)Q(-3) \implies P(-3) en Q(2) ⟹ P(2)Q(2) \implies P(2) waar, maar Q(3) ⟹ P(3)Q(3) \implies P(3) is niet waar. Verder geldt voor iedere xx dat P(x) ⟹ Q(x)P(x) \implies Q(x) waar is. Voor beweringen PP en QQ heet de conjunctie (P ⟹ Q)∧(Q ⟹ P)(P \implies Q) \land (Q \implies P) de bi-implicatie, notatie P ⟺ QP \iff Q. Deze bi-implicatie is alleen waar als PP en QQ allebei waar of allebei niet waar zijn. De waarheidstabel ziet er dan zo uit: PP QQ P ⟺ QP \iff Q TT TT TT TT FF FF FF TT FF FF FF TT Een tautologie is een bewering die altijd waar is. Voorbeeld De bewering P∨¬PP \lor \lnot P is een tautologie, wat volgt uit de waarheidstabel: PP ¬P\lnot P P∨¬PP \lor \lnot P TT FF TT FF TT TT Een tegenspraak is een bewering die nooit waar is. Voorbeeld De bewering P∧¬PP \land \lnot P is een tegenspraak, wat volgt uit de waarheidstabel: PP ¬P\lnot P P∧¬PP \land \lnot P TT FF FF FF TT FF Er geldt: als PP een tautologie is, dan is ¬P\lnot P een tegenspraak. Samengestelde beweringen PP en QQ zijn logisch equivalent als ze precies dezelfde waarheidstabellen hebben. We noteren dat als P≡QP \equiv Q. Er geldt: PP en QQ zijn logisch equivalent dan en slechts dan als P ⟺ QP \iff Q een tautologie is. Met deze definitie van logische equivalentie kunnen we een paar eigenschappen opschrijven over beweringen PP, QQ en RR: P∨Q≡Q∨P P \lor Q \equiv Q \lor P en P∧Q≡Q∧PP \land Q \equiv Q \land P P∨(Q∨R)≡(P∨Q)∨R P \lor (Q \lor R) \equiv (P \lor Q) \lor R en P∧(Q∧R)≡(P∧Q)∧R P \land (Q \land R) \equiv (P \land Q) \land R P∨(Q∧R)≡(P∨Q)∧(P∨R) P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) en P∧(Q∨R)≡(P∧Q)∨(P∧R) P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R) ¬(P∨Q)≡¬P∧¬Q \lnot (P \lor Q) \equiv \lnot P \land \lnot Q en ¬(P∧Q)≡¬P∨¬Q \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 xx uit SS, P(x)P(x) waar is. Voorbeeld Gegeven is de open bewering P(x):x2>0P(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=0x=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 xx bestaat in SS, zodat P(x)P(x) waar is. Voorbeeld Gegeven is de open bewering P(x):x2>0P(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=1x=1. Let op dat het domein belangrijk is: Voorbeeld Gegeven is de open bewering P(x):x2=3P(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: ¬(∀x∈S:P(x))≡∃x∈S:¬P(x) \lnot \big(\forall x \in S: P(x)\big) \equiv \exists x \in S : \lnot P(x) ¬(∃x∈S:P(x))≡∀x∈S:¬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 ¬(∀x∈S:∃y∈T:P(x,y))≡∃x∈S:∀y∈T:¬P(x,y) \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.