1 Logica
1.1.1 a. neen: de spreker bedoelt met "hier" de plek waar hij op dat moment is, maar "warm" is subjectief; vgl.: "het is hier 25 graden Celsius". b. ja: de uitspraak is onwaar (=120 uur). c. neen: dit is een vraag; vgl.: "ik ben vandaag jarig". d. neen: de uitspraak is een gezegde. e. ja: Picasso was een schilder, geen schilderij: onware propositie. f. neen: dit is een bevel, een gebod. g. neen: dit is een gebod (hou je eraan!!). 1.2.1 a. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p q c p ∧ q c p ∧ q ⇒ q c c c c 0 0 c 0 1 c c c c 1 c 0 1 c 0 c c 0 c 0 1 c 1 c c ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii 1 1 c 1 c 1 c tautologie
-1-
b. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii h h h ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p q c p c p ∨ q c (p ∨ q ) ∧ p c c c c 0 0 c 1 c 1 0 c c c c c 1 c 1 c 1 0 c 0 c c 0 c 0 c 0 0 c 1 c c 1 1 c 0 c 1 1 ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c contingentie c. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p q c p ⇒ q c (p ⇒ q ) ∨ q c c c c 0 0 c 1 1 c c c c 1 c 1 1 c 0 c c 0 c 0 0 c 1 c c ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii 1 1 c 1 c 1 c contingentie d. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p q c p ∧ q c p ⇒ q c (p ∧ q ) ∨ (p ⇒ q ) c c c c c 0 0 c 0 1 1 c c c c c 1 c 0 1 1 c 0 c c c 0 c 0 0 0 c 1 c c c 1 1 c 1 1 1 ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c contingentie e. i iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii cipiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii q r c p ⇒ r c q ⇒ r c (p ⇒ r ) ∧ (q ⇒ r ) c c c c c 0 0 0 c 1 1 1 c c c c c 0 1 c 1 1 1 c 0 c c c 1 0 c 1 0 0 c 0 c c c 1 1 c 1 1 1 c 0 c c c c 1 c c c c 0 0 0 1 0 c 1 c c c c 0 1 1 1 1 c c c c c 1 1 0 0 0 0 c c c c c 1 1 1 c 1 1 1 ci iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c contingentie
-2-
f. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii h h h ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p r c r ⇒ p c p c r ∧ p c (r ⇒ p ) ∧ (r ∧ p ) c c c c c 0 0 c 1 1 c 0 0 c c c c c c 1 c 0 1 0 c 0 c 1 c c c 0 c 1 0 0 c 1 c 0 c c c 1 c 1 0 0 c 1 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c 0 c c c contradictie 1.2.2 Zie boven 1.2.3 T heeft waarheidswaarde 1 en F heeft waarheidswaarde 0. 1.2.4 a. [ p ⊕ q ]
⇔
Ook: [ p ⊕ q ] Ook: [ p ⊕ q ] Ook: [ p ⊕ q ] Ook: [ p ⊕ q ] Ook: [ p ⊕ q ]
h h [(p ∧ q ) ∨ (p ∧ q )] hhhhhh ⇔ [(p ∨ q ) ∧ (p ∧ q )] h hhhhhhh ⇔ [ p ⇔ q ] h ⇔ [p ⇔ q ] h ⇔ [p ⇔ q ] h h ⇔ [(p ⇒ q ) ∧ (p ⇒q )]
b. Laatste kolom: 1110 (*N.B.: dit laatste is een antwoord en ge´e´n uitwerking dus!*) hhhhhh h h 1.3.1 a. p ∧ q ⇔ p ∨ q (de Morgan). h hhhhhh h h h (de Morgan). b. p ∨ q ⇔ p ∧ q h ⇔ p ∧ q (dubbele ontkenning). hhhhhhh hhhhhhh c. p ⇒ q ⇔ p ∨ q (⇒-vervanging); h h h (de Morgan); ⇔ p ∧ q h ⇔ p ∧ q (dubbele ontkenning). hhhhhhhhhhhhh hhhhhh h d. ( p ∧ q ) ∨ r ⇔ p ∧ q ∧ r (de Morgan); h h h ⇔ (p ∨ q ) ∧ r (de Morgan). hhhhhhh hhhhhhhhhh hhhhhhhhhhhhhh e. ( p ∨ r ) ⇒ q ⇔ p ∨ r ∨ q (⇒-vervanging); hhhhhh h (de Morgan); ⇔ p ∨ r ∧ q h ⇔ (p ∨ r ) ∧ q (dubbele ontkenning);
-3-
hhhhhhhhhhhhhhhhhhhhhh hhhhhh hhhhhhh f. ( p ∨ q ) ∧ ( p ⇒ r ) ⇔ ( p ∨ q ) ∨ ( p ⇒ r ) (de Morgan); hhhhhhh h h ⇔ ( p ∧ q ) ∨ ( p ⇒ r ) (de Morgan); h h hhhhhhh ⇔ ( p ∧ q ) ∨ ( p ∨ r ) (⇒-vervanging); h h h hh ⇔ ( p ∧ q ) ∨ ( p ∧ r ) (de Morgan); h h h ⇔ ( p ∧ q ) ∨ ( p ∧ r ) (dubbele ontkenning).
N.B.: Hoe ’ver’ je met deze opgave (met name vraag f.) moet gaan vereenvoudigen is enigszins arbitrair. 1.3.2 1. optellen is associatief, commutatief, maar niet distributief (over zichzelf); 2. vermenigvuldiging is associatief, commutatief, maar niet distributief (over zichzelf); 3. optelling distribueert niet over vermenigvuldiging; 4. vermenigvuldiging distribueert wel over optelling.
1.3.3 a. Uit de waarheidstabel van de Breuksma volgt direct: h [p @ q ] ⇔ [p ∧ q ] b. Idem (na enig puzzelen): hhhhhhh [p @ q ] ⇔ [q ⇒ p ] hhhhhhhh h Ook: [ p @ q ] ⇔ [ p ⇒ q ] c. Nagaan: p @ ( q ∧ r ) ⇔ ( p @ q ) ∧ ( p @ r ) iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii p q r c q ∧ r c p @ ( q ∧ r ) c p @ q c ( p @ r ) c ( p @ q ) ∧ ( p @ r ) c I ⇔ II c c c c c c c 0 0 0c 0 c 0 0 0 0 1 c c c c c c c c 0 0 1 0 1 c 0 0 1c 0 c c c c c c 0 1 0 0 1 c 0 1 0c 0 c c c c c c 1 1 1 1 1 c 0 1 1c 1 c c c c c c c 1 0 0c 0 c c c c c c 0 0 0 0 1 c 1 0 1c 0 c c c c c c 0 0 0 0 1 c c c c c c c c 1 1 0c 0 c 0 0 0 0 1 c c c c c c 0 0 0 0 1 c 1 1 1c 1 c c c c c c c c c c c c c c ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c I c c c II c c tautologie; dus: bewezen.
-4-
h h 1.3.4 a. p ∧ ( q ∨ p ) ⇔ ( p ∧ q ) ∨ ( p ∧ p )
⇔ (p ∧ q ) ∨ F ⇔ p ∧ q
(distr. ∧ over ∨ );
(inverse);
(identiteit).
We hebben dus bewezen dat de stelling juist is. h b. p ⇒ ( p ∧ q ) ⇔ p ∨ ( p ∧ q ) (⇒-vervanging); h h ⇔ ( p ∨ p ) ∧ ( p ∨ q ) (distr. ∨ over ∧ ); h ⇔ T ∧ ( p ∨ q ) (inverse); h ⇔ p ∨ q (identiteit); ⇔ p ⇒ q
(vervanging ⇒).
We hebben dus bewezen dat de stelling juist is. hhhhhh c. ( p ∨ q ) ⇒ r ⇔ ( p ∨ q ) ∨ r (⇒-vervanging); h h ⇔ (p ∧ q ) ∨ r (de Morgan); h h ⇔ ( p ∨ r ) ∧ ( q ∨ r ) (distr. ∨ over ∧ ); ⇔ (p ⇒ r ) ∧ (q ⇒ r )
verv-⇒.
We hebben dus bewezen dat de stelling juist is. hhhhhhh d. ( p ⇒ q ) ⇒ ( p ∧ q ) ⇔ ( p ⇒ q ) ∨ ( p ∧ q ) (⇒-vervanging); hhhhhhh ⇔ ( p ∨ q ) ∨ ( p ∧ q ) (⇒-vervanging); h hh ⇔ ( p ∧ q ) ∨ ( p ∧ q ) (de Morgan); h ⇔ ( p ∧ q ) ∨ ( p ∧ q ) (dubbele ontkenning); h ⇔ p ∧ ( q ∨ q ) ("terug"-distributie); ⇔ p ∧ T ⇔ p
(inverse);
(identiteit).
We hebben dus bewezen dat de stelling juist is. N.B.: Let er op dat elk bewijs eindigt met een (soort van) conclusie.
-5-
h h h h 1.3.5 a. p ∧ ( p ⇒ q ) ⇔ p ∧ ( p ∨ q ) (⇒-vervanging); h ⇔ p (absorptie). Conclusie: de stelling is juist. h b. p ∨ ( p ⇒ q ) ⇔ p ∨ ( p ∨ q ) (⇒-vervanging); h ⇔ (p ∨ p ) ∨ q (assoc. van ∨ );
⇔ T
∨ q
⇔ T
(inverse); (dominantie).
Als p onwaar is dan klopt de equivalentie dus niet. Dit bewijzen we met een (geschikt gekozen) tegenvoorbeeld: kies: p onwaar (zie boven waarom); q willekeurig, bijvoorbeeld onwaar. Dan: iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c p q c p ⇒ q c p ∨ ( p ⇒ q ) c [p ∨ ( p ⇒ q ) ] ⇔ p c ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c 0 c 1 1 0 c 0 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c Conclusie: de stelling is onjuist. Met q als waarheidswaarde 1 wordt het (uitgewerkte) tegenvoorbeeld: iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c p q c p ⇒ q c p ∨ ( p ⇒ q ) c [p ∨ ( p ⇒ q ) ] ⇔ p c ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c 1 c 1 1 0 c 0 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c h c. ( p ⇒ q ) ∧ ( p ∨ q ) ⇔ ( p ∨ q ) ∧ ( p ∨ q ) ⇒-vervanging; h ⇔ (p ∧ p ) ∨ q ("terug"-distributie); ⇔
F
⇔
q
∨ q
(inverse); (identiteit).
Conclusie: de stelling is juist. hhhhhh h h d. ( p ∨ q ) ∨ r ⇔ ( p ∧ q ) ∨ r ⇔
(de Morgan);
???
Dit levert verder niets op. Merk op dat wel geldt: hhhhhh ( p ∨ q ) ∨ r ⇔ ( p ∨ q ) ⇒ r. Een tegenvoorbeeld zoeken dus. Uit bovenstaande vervanging kunnen we afleiden dat het verschil tussen beide uitdrukkingen zit in het verschil tussen de ∧ en de ∨. Daarom:
-6-
kies: r heeft waarheidswaarde 0 p heeft waarheidswaarde 1 q heeft waarheidswaarde 0 (We kunnen p en q ook respectievelijk 0 en 1 maken.) Dan geldt: iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c hhhhhh c hhhhhh c c c c p q r p ∨ q c c c p ∨ q c (p ∨ q ) ∨ r c (p ∧ q ) c (p ∧ q ) ⇒ r c I ⇔ II c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c c c c 1 0 0 0 1 0 c 1 0 0c c c c c c c c c c c c c c c I II c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c c c De stelling is onjuist. 1.4.1 a. ∃ x P (x )
⇔
∃ x [ x > 10 ] is waar: b.v. voor x = 11;
b. ∀ x Q (x ) ⇔ ∀ x [ x ≥ 5 ] is onwaar: beschouw b.v. x = 4 dan blijkt dat het predicaat (x ≥ 5) niet voor elke x geldt; c. ∃ x [ P (x ) ∧ R (x ) ] ⇔ ∃ x [ (x > 10) ∧ (x < 7) ] is onwaar: geen enkele x kan aan het predicaat (x > 10 ∧ x < 7) voldoen; d. ∀ x [ P (x ) ⇒ Q (x ) ] ⇔ ∀ x [ (x > 10) ⇒ (x ≥ 5) ] is waar: als x > 10 dan is x ook zeker groter dan 5 en als x < 10 geldt de implicatie (het predicaat) sowie-so: het linkerdeel is dan onwaar; e. ∃ x P (x ) ⇒ ∃ x R (x ) ⇔ ∃ x [ x > 10 ] ⇒ ∃ x [ x < 7 ] is waar: daar zowel ∃ x [ x > 10 ] als ∃ x [ x < 7 ] waar zijn. De laatste regel van de waarheidtabel van de implicatie is hier van toepassing. N.B.: De x -en mogen verschillend gekozen worden, maar het moet niet. Als bijvoorbeeld respectievelijk 11 en 6 gekozen wordt, ontstaat het volgende: ( 11 > 10 ) ⇒ ( 6 < 7 ), hetgeen juist is. f. ∀ x [ Q (x ) ∨ R (x ) ] ⇔
⇒
∀ x P (x )
∀ x [ (x ≥ 5) ∨ (x < 7) ] ⇒ ∀ x [ x > 10 ] is onwaar:
∀ x [ (x ≥ 5) ∨ (x < 7) ] is waar terwijl ∀ x [ x > 10 ] onwaar is: de derde regel van de waarheidstabel van de implicatie is hier van toepassing. g. ∃! x [ Q (x ) ∧ R (x ) ] ⇔ ∃! x [ (x ≥ 5) ∧ (x < 7) ] is onwaar: zowel 5 als 6 voldoen; er zijn dus (minstens) twee x -en i.p.v. precies e´ e´ n die beide voldoen.
-7-
h. ∃ x [ R (x ) ∧ T (x ) ]
⇔
[ ∃ x R (x ) ∧ ∃ x T (x ) ]
Ofwel: ∃ x [ (x < 7) ∧ T (x ) ] zijn.
⇔
[ ∃ x ( x < 7 ) ∧ ∃ x T (x ) ] moet onwaar
Ga alvast na dat: ∃ x [ x < 7 ] waar is. Kies T (x ) zo dat ∃ x T (x ) ook waar is en dat tevens ∃ x [ (x < 7) ∧ T (x ) ] onwaar is. Dus b.v.: T (x ) betekent x ≥ 7. 1.4.2 We definieren als universum U de verzameling leraren en als predicaat S(x) "x is slim". a. ∀ x S (x ); hhhhhhhh b. ∀ x S (x ); c. Niet alle leraren zijn slim h hhh d. ∃ x S (x ); e. Ze zijn equivalent: "niet alle leraren zijn slim" betekent dat er (minstens) e´ e´ n niet-slimme leraar bestaat! (we noemen geen voorbeeld!) f. Elke stelling kunnen we schrijven als ∀ x P (x ). Als de stelling niet waar is geldt hhhhhhhh dus dat ∀ x P (x ) welh hhh waar is. Hierboven hebben we gezien dat dit laatste equivalent is met ∃ x P (x ) en we kunnen dus volstaan met het beschrijven van e´ e´ n x waarvoor P (x ) niet waar is (een tegenvoorbeeld dus!).
1.4.3 a. Vertalen in "logica-taal" levert: hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh hhhhhhh ( x < 10 ) ∨ ( ( y > 5 ) ∧ ( x < 2 ) ) hhhhhhhhhhhhhhhh hhhhhh hhhhh ⇔ x < 10 ∧ ( y > 5 ∧ x < 2 ) (de Morgan); hhhh hhhhhh hhhhh hhhhhh ⇔ x < 10 ∧ (y > 5 ∨ x < 2) (de Morgan); hhhhhh hhhhh ⇔ x < 10 ∧ (y > 5 ∨ x < 2 ) (dubbele ontkenning); ⇔
x ≥ 10 ∧ (y ≤ 5 ∨ x < 2 )
⇔
( x ≥ 10 ∧ y ≤ 5 ) ∨ (x ≥ 10 ∧ x < 2 )
⇔
( x ≥ 10 ∧ y ≤ 5 ) ∨
⇔
( x ≥ 10 ∧ y ≤ 5 )
F
(ontkenning uitwerken);
(inverse);
(identiteit);
In Pascal wordt dit dus: ((x ≥ 10) AND
(y ≤ 5)). -8-
(distr. van ∧ over ∨ );
b. Vertalen in "logica-taal" levert: hhhhhhhhhhhhhhhhhhhhhhhh hhhhhhh (teller > 20) ∧ KLAAR ∨ eoln hhhhhhh hhhhhhhhhhh ⇔ teller > 20 ∨ KLAAR ∨ eoln hhhhhhhhhhh ⇔ teller > 20 ∨ KLAAR ∨ eoln ⇔
teller ≤ 20 ∨ KLAAR
(de Morgan); (dubbele ontkenning);
∨ eoln
In Pascal wordt dit: ((teller <= 20)
OR
(ontkenning uitwerken); KLAAR
OR
eoln )
1.4.4 a. De logische wetten zijn hier niet van toepassing omdat t := 5 ge´ e´ n bewering is! (maar een toekennings- opdracht). Stel dat we deze opmerking negeren, dan krijgen we: (x > 3) ⇒ (t := 5) hhhhh ⇔ x > 3 ∨ (t := 5) ⇔
(x ≤ 3) ∨ (t := 5)
(⇒-vervanging); (ontkenning uitwerken);
In Pascal wordt dit: ((x <= 3)
OR
(t := 5));
b. Neen! In Pascal is if ...then een "opdracht onder voorwaarde", terwijl ...OR... een bewering moet zijn. Daar t := 5 een toekenningsopdracht is (ge´ e´ n bewering dus) staat er in x <= 3 OR t := 5 onzin. Elke Pascal-compiler zal hier behoorlijk moeilijk over doen. (Zal een foutmelding geven.) In de taal C is de toekenning (t = 5) een ware bewering.
-9-
1.4.5 Eerst in logica-taal schrijven (m.b.v. proposities dus): n : je stoot je neus p : je hebt pijn. De uitspraak wordt dan in logica-taal: n ⇒ p De beweringen in respectievelijk 1. en 2. worden: h h 1. n ⇒ p h h 2. p ⇒ n Merk op dat de uitspraak onder 1. niet equivalent is met de eerstgenoemde, terwijl de uitpraak onder 2. (met behulp van de contrapositiviteit) wel equivalent is met de eerstgenoemde. iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii h h h h h h c n p c n c p c n ⇒ p c n ⇒ p c (n ⇒ p ) ⇔ (n ⇒ p ) c ic iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c c cciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii cc cc cc 0 1 cc 1 cc 0 cc 1 0 0 1.4.6 a. Eerst in logica-taal schrijven (m.b.v. proposities dus): o: je let goed op h: je haalt een hoog cijfer b: je studeert braaf. Dan staat er: [o ∧ b ]
⇒
h
⇔
(o ⇒ h ) ∧ (b ⇒ h )
Afleiden levert: [o ∧ b ] ⇒ h hhhhhh ⇔ o ∧ b ∨ h vervanging ⇒; hh h ⇔ (o ∨ b ) ∨ h de Morgan; ⇔
??
Hier kunnen we verder niets mee; de stelling is dan ook onjuist. Tegenvoorbeeld: Piet let wel goed op, maar studeert niet braaf en haalt dan ook ge´ e´ n hoog cijfer:
- 10 -
