HOOFDSTUK 4. LOGICA
Opgaven Propositionele logica en predikatenlogica 1.
2.
Noteer volgende Nederlandse uitspraken formeel m.b.v. propositionele logica : a)
Als de maan zichtbaar is en het niet sneeuwt, zal Jan een wandeling maken.
b)
Als het morgen zonnig is, ga ik fietsen. Als ik ga fietsen, is dit ofwel naar de zee ofwel naar de bergen.
c)
Als ik een mooie broek of jas zie, zal ik een nieuwe broek of nieuwe jas kopen.
d)
Als een algoritme betrouwbaar is, is het ok. Dus, een algoritme is of ok, of onbetrouwbaar. Is deze conclusie juist ? Verklaar zowel via propositionele logica als in woorden waarom (niet) ?
e)
Een uitspraak p is waar of vals, en kan niet tegelijk waar en vals zijn. (wet van de uitgesloten derde)
Jan zegt dat Piet liegt. Piet zegt dat Klaas liegt. Klaas zegt dat Jan en Piet liegen. Als je weet dat elk van deze drie personen ofwel een pertinente leugenaar is (m.a.w. altijd liegt), ofwel volkomen eerlijk is (m.a.w. nooit liegt), noteer dan bovenstaande uitspraken m.b.v. propositionele logica. Wie spreekt zeker de waarheid ?
3.
Controleer de volgende argumentatie m.b.v. propositionele logica: Als Superman kwaad zou kunnen en willen voorkomen, zou hij dit doen. Als Superman kwaad niet zou kunnen voorkomen, zou hij onkundig zijn; als hij kwaad niet zou willen voorkomen, zou hij kwaadwillig zijn. Superman voorkomt geen kwaad. Als Superman bestaat, is hij noch onkundig, noch kwaadwillig. Dus bestaat Superman niet.
4.
Welke van de volgende samengestelde proposities is een tautologie, een contradictie of een eventualiteit. (Hierbij stellen p, q, r telkens enkelvoudige proposities voor). a)
¬
p ∨ (p ∨ q)
b)
p ∨ ¬(p ∧ q)
c)
p ∧ ¬(p ∨ q)
d)
(¬p ∧ (p ⇒ q)) ⇒ ¬q
HOOFDSTUK 4
LOGICA
4.1
e)
(p ∨ ¬p) ∧ ¬(p ∧ ¬p)
f)
(¬p ∧ q) ∨ (q ∧ ¬r)
g)
p ∧ (¬p ∧ q)
h)
(¬q ∧ (p ⇒ q)) ⇒ ¬p
i)
p ∧ (¬p ∨ q)
j)
5.
6.
7.
¬
p ∧ (p ∧ q)
k)
p ∨ (¬p ∨ q)
l)
(p ⇒ q ∧ ¬q ⇒ ¬r) ⇔ p ∨ r
Stel voor volgende samengestelde proposities de disjunctieve normaalvorm op. (Hierbij stellen x,y,z,u telkens enkelvoudige proposities voor.) a)
y∨z
b)
y ∨ ¬z
c)
(x ∧ y) ∨ (¬x ∧ z)
d)
x ⇔ (y ∧ z)
e)
x ∨ (¬y ∧ (x ∨ ¬y) ∧ (¬x ∨ y))
f)
(x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y)
g)
((x ∨ y ∧ z) ∧ ¬(x ∨ y ∨ z)) ∨ (¬y ∧ z)
h)
((x ∧y) ∨ (z ∧u)) ∧ ((x ∧ ¬z) ∨ (¬y ∧u)) ∧ ((y ∧z) ∨ (x ∧u))
i)
((x ∧y) ∨ z) ⇒ (¬x ⊕ z)
Stel voor volgende samengestelde proposities de conjunctieve normaalvorm op. (Hierbij stellen x,y,z,u telkens enkelvoudige proposities voor.) a)
y∧z
b)
(x ∧ y) ∨ (¬x ∧ z)
c)
x ∨ (y ∧ z)
d)
(x ∨ y) ∧ (x ∧ ¬y)
e)
x ⇒ ¬y
f)
x ∨ (¬y ∧ (x ∨ ¬y) ∧ (¬x ∨ y))
g)
(x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y)
h)
x ⇔ (x ⇒ y)
i)
((x ∨ y ∧ z) ∧ ¬(x ∨ y ∨ z)) ∨ (¬y ∧ z)
Vereenvoudig onderstaande samengestelde proposities zoveel mogelijk. a)
(x ∧ y ∨ z) ∧ ¬x
b)
(x ∧ y) ∨ (¬y ∧ z) ∨ (¬x ∧ z) ∨ (¬x ∧ y )
c)
(¬x ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z)
HOOFDSTUK 4
LOGICA
4.2
8.
9.
d)
(x ∨ y) ∧ ¬(x ∨ y) ∨ x
e)
x ⇔ (x ⇒ y)
f)
y ∧ ((x ∧ ¬y) ∨ (y ∧ z) ∨ (x ∧ y ∧ z))
g)
(x ∧ y) ∨ (y ∧ z) ∨ (¬x ∧ z)
h)
(x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x) ∧ (¬x ∨ ¬y ∨ ¬z)
i)
(x ∧ y) ∨ (¬x ∧ ¬z) ∨ (x ∧ (¬y ∨ ¬z))
Noteer volgende Nederlandse uitspraken formeel m.b.v. predikatenlogica : a)
Iedereen houdt van iemand.
b)
Er is iemand van wie iedereen houdt.
c)
Niemand houdt van iedereen.
d)
Iedereen houdt van zichzelf.
e)
Er bestaat iemand die van niemand houdt behalve van zichzelf.
Als je onderstaande uitdrukkingen aanvult met ‘⇔’, bekom je dan een uitspraak die waar is, vals is of naargelang het geval zowel waar als vals kan zijn ? Idem met ‘≡’ i.p.v. ‘⇔’. a)
( p ∨ (¬p ∧ q)) … ¬p ∧¬q
b)
p ⇔ q … (p ∧ q) ∨ (¬p ∧ ¬q)
c)
((p ⇒ q) ⇒ r) … (p ⇒ (q ⇒ r))
d) e) f)
¬
(p ⇔ q) … (¬p ⇔ q)
(p ⇒ (q ∨ r)) … (p ⇒ q) ¬
(p ⊕ q) … (p ⇔ q)
g)
∀x ∈ U : (p(x) ∧ q(x)) … (∀x ∈ U : p(x) ∧ ∀x ∈ U : q(x))
h)
(∀x ∈ U : p(x) ∨ ∀x ∈ U : q(x)) … ∀x ∈ U : (p(x) ∨ q(x))
i)
∃x ∈ U : (p(x) ∧ q(x)) … (∃x ∈ U : p(x) ∧ ∃x ∈ U : q(x))
j) 10.
¬
¬
(∃x ∈ U : ¬p(x)) … ∀x ∈ U : p(x)
Vereenvoudig volgende logische uitdrukkingen (alle variabelen ∈ R) : a) b)
(x > y+5) ∧ ¬(x > 3) ∧ (y > 0) ¬
(5x > y) ∧ (x < 125) ∧ (y < 0)
c)
((y > x) ∨ (y > 10)) ∧ ¬(x > 0)
d)
(x + y > 6) ∧ ¬(x – y > 6) ∧ ¬(y > 0)
e)
(x > y+5) ∧ (x>3) ∧ (y<0)
f)
(x>6) ∧ ¬( x-y>2) ∧ (y<0)
g)
(-x-y+5z>0) ∧ (x>=0) ∧ (y>0) ∧ (z<=0)
h)
HOOFDSTUK 4
¬
(21x > y) ∧ (x < 125) ∧ (y < 0)
LOGICA
4.3
i)
(x >=5) ∧ (y<8) ∧ (xy<10)
j)
(x+y+2z > 6) ∧ ¬(y>0) ∧ (z>1)
Bewijsstrategieën 11.
a)
Toon aan dat log2 3 een irrationaal getal is.
b)
Is log2 4 ook een irrationaal getal ? Volg dezelfde redenering als bij a) en ga na wat er verandert.
12.
Bewijs dat ten minste 1 van de reele getallen a1, a2, … , an groter is dan of gelijk is aan het gemiddelde van deze getallen.
13.
Toon aan dat ∀a,b,c ∈ R : min(a, min(b,c)) = min(min(a,b), c)
14.
Bewijs: ∀k,l ∈ N: (k en l even ⇒ k+l even)
15.
Bewijs de ongelijkheid n < 2n voor alle natuurlijke getallen n.
16.
Bewijs: ∀x,y ∈ R+ : (x⋅y > 25 ⇒ x > 5 ∨ y > 5)
17.
Wat is verkeerd bij het volgende bewijs dat alle studenten in elke groep grootste onderscheiding halen ? Het bewijs gebeurt via inductie op het aantal studenten. Beschouw een groep van 0 studenten. Aangezien de groep leeg is, heeft iedereen in de groep grootste onderscheiding. We bewijzen dat, als we veronderstellen dat de bewering waar is voor n, de bewering waar is voor n+1. Beschouw een groep van n+1 studenten: haal 1 van hen weg. Alle studenten in de groep hebben nu grootste onderscheiding. Vervang een student van de groep (met grootste onderscheiding) door de student die eerst uit de groep van n+1 studenten genomen werd, nog steeds hebben alle studenten grootste onderscheiding. Dus heeft elke student in de groep van n+1 studenten grootste onderscheiding.
18.
Stel een algemeen geldige (d.w.z. ∀n ∈ N) formule in gesloten gedaante op voor de som van kwadraten van de kleinste natuurlijke getallen : S(n ) =
n
∑m
2
m =0
Ga daarbij als volgt tewerk : b
a)
Bereken 2 integralen van de vorm
∫ x dx 2
waarbij je a en b telkens zo kiest dat de
a
ene integraal een bovengrens en de andere integraal een benedengrens vormt voor S(n).
19.
b)
Probeer daaruit te raden hoe die formule in gesloten gedaante van S(n) er zou kunnen uitzien (met enkele onbekende parameters). [Hint : Bekijk ter analogie ook de formule voor de som 0+1+…+n uit de theoriecursus.]
c)
Bepaal de waarde van de onbekende parameters a.d.h.v. de berekening van S(0), S(1), … Op die manier bekom je een formule in gesloten gedaante voor S(n)
d)
Bewijs de geldigheid van de aldus bekomen formule voor S(n) voor alle natuurlijke getallen n.
Als de natuurlijke getallen 1 t.e.m. 10 in willekeurige volgorde rond een cirkel worden geplaatst, dan kan men 3 opeenvolgende getallen op de cirkel vinden waarvoor de som groter is dan 17.
HOOFDSTUK 4
LOGICA
4.4
a)
Bewijs dit.
b)
Geldt deze eigenschap ook voor 18 i.p.v. 17 ? Indien ja, bewijs. Indien neen, geef een tegenvoorbeeld.
20.
*Toon aan dat het onmogelijk is om een 8×8 schaakbord waaruit 2 diametraal t.o.v. elkaar liggende hoekvakjes werden verwijderd volledig te bedekken met dominostenen (1 dominosteen is een 1×2 stuk), indien de dominostenen elkaar niet mogen overlappen.
21.
Toon aan dat n2-1 steeds deelbaar is door 8 voor elk oneven natuurlijk getal n.
22.
Elke vierkantswortel n van een natuurlijk getal n is irrationaal als en slechts als n geen volkomen kwadraat is.
23.
a)
Formuleer deze eigenschap m.b.v. predikatenlogica.
b)
Bewijs deze eigenschap.
Beschouw de volgende recursieve methoden in Java. Teken telkens de ermee corresponderende gerichte boomstructuur. Betreft het een correcte recursieve methode, met andere woorden zal de opgeroepen methode steeds eindigen na een eindig aantal stappen ? static long iets(int n) { if(n==1) return 1; else if(n==2) return 2; else return(n*iets(n-1)+n*n*iets(n-2)); } static long berekenIets(int n) { if(n==1) return 1; else if((n%2)==1) return(berekenIets(n+1)); else return(2*berekenIets(n/2)); }
Toepassing : digitale circuits 24.
Vereenvoudig volgende digitale schakelingen. a)
HOOFDSTUK 4
LOGICA
4.5
x y z x y z x y z x y z
b) x
y
z u
25.
Zet volgende logische functies om in digitale schakelingen (met enkel NIET-, EN- en OFpoorten). Beperk het aantal poorten zoveel mogelijk. a)
(x ∧ y) ∨ (¬x ∧ z)
b)
(¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z)
c)
x⊕y
d)
(x ∧ ¬y) ⇒ (y ∧ z)
e)
((¬x ∨ y) ∧ z) ∧ (x ¬y ∨ z)
26.
Een 'half adder' of 'two adder' is een digitale schakeling die 2 1-bitsgetallen bij elkaar optelt en het resultaat (bestaande uit 2 bits) berekent. Ontwerp een dergelijke 'half adder'.
27.
I.p.v. gebruik te maken van 3 basispoorten (NIET-, OF- en EN-poort), kan men ook alle logische functies realiseren a.d.h.v. 1 basispoort zoals de NEN-poort (= niet en) met een aanpasbaar aantal ingangen (1, 2, 3, … ingangen). a)
Toon dit aan.
b)
Realiseer de schakelingen uit opgave 25 door enkel gebruik te maken van NENpoorten. Is het resultaat dat je bekomt optimaal wat betreft het aantal gebruikte NEN-poorten ?
HOOFDSTUK 4
LOGICA
4.6
c)
Kan men ook alle logische functies realiseren a.d.h.v. uitsluitend NOF-poorten ?
Toepassing : correctheid programma's 28.
29.
Verifieer of het programmafragment (in JAVA) power=1; int i=1; while (i<=n) { power=power*x; i++; } a)
correct is in geval van de preconditie n ∈ N ∧ x ∈ R ∧ power ∈ R en de postconditie n ∈ N ∧ x ∈ R ∧ power ∈ R ∧ power = xn.
b)
correct is in geval van de preconditie n is int ∧ x is double ∧ power is double ∧ n >= 0 en de postconditie n is int ∧ x is double ∧ power is double ∧ n >= 0 ∧ power = x n.
Gegeven volgend programmafragment (in JAVA) : if(n<0) a=-n; else a=n; k=0; x=0; while ((k++)
30.
a)
Schrijf elk van deze 4 onderdelen als een Hoare triple (neem aan dat alle variabelen gehele getallen voorstellen).
b)
Schrijf het volledige programmafragment als een Hoare triple.
Gegeven volgend programmafragment (in JAVA) : n1 = n; { int i=0; while (n>i) { n--; i++; } } met als preconditie p : “n is int en n>0 en n1 is int en n1<3”. Formuleer een zo volledig mogelijke postconditie.
31.
Gegeven volgend programmafragment (in JAVA) : static long berekenIets(int n) { if(n==1) return 1; else if((n%2)==1) return(berekenIets(n+1)); else return(2*berekenIets(n/2)); } a)
HOOFDSTUK 4
Formuleer de preconditie en de postconditie voor dit fragment (in een zo eenvoudig mogelijke gedaante).
LOGICA
4.7
b)
HOOFDSTUK 4
Toon aan dat dit fragment effectief voldoet aan deze specificaties.
LOGICA
4.8
