Essential Skills Mathematics
Studiewijzer

Module L1
Propositielogica

Leerdoelen en onderwerpen

Leerdoelen

Na deze module bestudeerd te hebben moet je:
1.	kunnen definiëren wat een propositie is
2.	de definities van de logische operatoren kennen en kunnen toepassen
3.	waarheidstabellen kunnen maken en de waarheidswaarde van een logische    expressie kunnen evalueren
4.	de begrippen tautologie, contradictie en contingentie kennen en logische expressies hiermee kunnen indelen
5.	proposities kunnen herschrijven met behulp van regels

Onderwerpen

L1.1. 	Beschrijving van propodities

L1.2.	Logische operatoren 

L1.3.	Waarheidstabellen

L1.4.	Eigenschappen van logische operatoren

L1.5. 	Herschrijven van expressies

	Antwoorden van de opgaven

 

1.1 Beschrijving van proposities
De logica is een wetenschap die zich (o.a.) bezig houdt met methoden van redeneren om vast te kunnen stellen of een bepaalde bewering waar is of niet. Logica kan ook goed worden gebruikt om de correctheid van programma's aan te tonen en zelfs correcte programma's af te leiden. Ook bij veel andere wetenschappen wordt logica gebruikt om conclusies te formuleren of problemen op te lossen. In de logica spelen beweringen een grote rol. Als deze beweringen slechts waar of niet waar kunnen zijn, noemen we zo'n bewering een propositie. In de informatica is het gebruikelijk om waar en niet waar respectievelijk true en false te noemen. We zullen ons hierbij aansluiten. In algemene situaties (waar de actuele waarde van een propositie niet van belang is) praten we over de waarheidswaarde van een propositie.
Definitie.  Een propositie is een bewering die true of false is, maar niet beide. Opmerking: In plaats van het woord bewering wordt vaak ook assertie gebruikt.
Voorbeeld. Enkele voorbeelden van proposities zijn:1. De aarde is een planeet.2. De ribben van een kubus zijn gelijk.3. .4. Het oppervlak ingesloten door een cirkel is .5. Op 1 augustus 1800 heeft het in Eindhoven de gehele dag hard gewaaid.
Van deze voorbeelden zijn 1, 2 en 3 true, 4 is false en van 5 is de waarheidswaarde op dit moment moeilijk vast te stellen, maar het is een bewering die true of false is, zodat het een propositie is.
De volgende beweringen zijn geen proposities:1. 2. 3. Het socialisme is schuldig aan de huidige crisis.
De waarheidswaarde van de beweringen 1 en 2 kan niet worden vastgesteld zolang de waarden van a, b en x niet bekend zijn. Dat betekent dat deze beweringen zowel true als false kunnen zijn. Op het moment dat de waarden bekend zijn worden de beweringen proposities. De derde bewering is geen propositie omdat de waarheidswaarde voor verschillende personen verschillend zal zijn.

Opgave 1.1.1

Geef aan of de volgende uitspraken proposities zijn:

a) Dat is een mooi schilderij.

b) Henk is groter dan Kees.

c) De toets van Module [1] was makkelijk!

Maak op Maple T.A. de oefening: [1.1.1] Proposities

1.2 Logische operatoren

In de wiskunde is het gebruikelijk om variabelen voor te stellen met behulp van letters die kunnen worden vervangen door 'echte' waarden. Verder kunnen deze variabelen worden gecombineerd tot grotere gehelen door middel van de bekende operatoren als +, x, -, enz. In de logica worden dit soort conventies ook gebruikt en noemt men de letters (vaak , , ,..) propositie-variabelen. Deze propositie-variabelen kunnen dan met behulp van logische operatoren worden gecombineerd tot grotere gehelen, de propositionele vormen of logische expressies.
Voorbeeld. Stel dat is gedefinieerd:: De zon schijnt vandaag. : Het regent. : Ik ben gelukkig.
De bewering De zon schijnt vandaag en ik ben gelukkig kan dan ook worden geschreven als:  en . Zo is het ook mogelijk een bewering als Het regent of de zon schijnt vandaag te schrijven als:  of . We noemen 'en' en 'of' de logische operatoren (of logische connectieven) en ,  en  de operanden.

OntkenningAls  een propositie is, dan is de ontkenning van  ook een propositie. De ontkenning van  (ook wel negatie genoemd) kan de waarde true of false aannemen, afhankelijk van de waarde van . De ontkenning van  wordt geschreven als en wordt uitgesproken als niet . Omdat de ontkenningsoperator slechts op één operand werkt noemen we dit een unaire operator. Uit de informele definitie kunnen we afleiden dat indien  true is, dan is  false en omgekeerd. In een tabel kunnen we dat als volgt noteren:

	

	

	

Zo'n tabel noemen we een waarheidstabel. 
Voorbeeld. Indien we definiëren als : Op dit moment schijnt in Amsterdam de zon. Dan is  dus gelijk aan de uitspraak: Het is niet zo dat op dit moment de zon schijnt in Amsterdam. Dit kunnen we natuurlijk ook kunnen lezen als: Op dit moment schijnt de zon niet in Amsterdam.

Conjunctie
Twee proposities kunnen tot een propositionele vorm worden samengesteld met behulp van de binaire operator 'en'. Een binaire operator is een operator die op twee operanden werkt. We noemen deze propositionele vorm de conjunctie van de twee oorspronkelijke operanden. De conjunctie van  en  wordt geschreven als:  en uitgesproken als:  en . De conjunctie van  en  is true als  en  beide true zijn en false in alle andere gevallen. De definitie in de vorm van een tabel:

	

	

	

	

	

 
Opmerking: We beschouwen in het vervolg enkel deze tabel (en de andere in dit hoofdstuk) als de definitie van de operator en niet het informele taalgebruik dat wordt gebruikt als introductie.
Voorbeeld.1. 'Een schimmel is een wit paard''2+3 = 5'2. 'Een schimmel is een bruin paard''2+3 = 5'3. 'Een schimmel is een bruin paard''2+3 = 6'4. 'Een schimmel is een wit paard''2+3 = 6'
In dit voorbeeld is alleen de eerste propositie true en de andere drie zijn false omdat tenminste één van de twee operanden false is.
Programmeervoorbeeld. In controlestructuren van programma's komt het gebruik van logische operatoren vaak voor.De programma opdracht:
IF ((x<3) AND (z=2)) THEN x:=(x+z) ELSE x:=(x+2)
zorgt ervoor dat x: = (x+z) alleen wordt uitgevoerd als geldt: (x<3) èn (z=2); in alle andere gevallen zal x: = (x+2) worden uitgevoerd. Merk op dat ((x<3) AND (Z=2)) geen propositie is, immers of deze uitspraak true of false is, hangt af van de waarden die x en z op een bepaald moment hebben. Indien echter de waarden van x en z bekend zijn (in dit geval zal dat zijn tijdens de uitvoering van het programma), dan is deze uitspraak een propositie geworden (hij is dan immers true of false). Dit soort uitspraken noemen we predikaten en zal worden besproken in Module [3]. Ook combinaties met andere operatoren komen voor:
IF (NOT(x>=3) AND NOT (z<>2)) THEN x:=(x+z) ELSE x:=(x+2) èn IF (NOT(x>=3) OR (z<>2)) THEN x:=(x+z) ELSE x:=(x+2)
veroorzaken precies hetzelfde effect.
DisjunctieNet zoals de conjunctie als logische voorstelling van het in de taal gebruikte woord 'en' wordt gebruikt is er ook een logisch equivalent van 'of', nl. de disjunctie (), gedefinieerd met behulp van de volgende tabel:

	

	

	

	

	

 

Deze definitie toont aan dat true is als (tenminste) één van de operanden true is. 
De disjunctie wordt dus genoteerd als  en uitgesproken als  of .

Houd je strikt aan de definitie uit de tabel, want het gebruik van 'of' in natuurlijke taal kan tot misverstanden of dubbelzinnigheden aanleiding geven. Beschouw hiervoor het volgende: Laten we uitgaan van de zin: Vandaag zal de zon schijnen of het zal regenen. Iemand die deze uitspraak doet, zal waarschijnlijk niet voor leugenaar worden uitgemaakt, als vandaag de zon schijnt èn het regent. Maar in de zin: Je moet je kamer opruimen of je moet de afwas doen, wordt waarschijnlijk niet van je verwacht dat je zowel je kamer opruimt, als ook de afwas doet. 
Voorbeeld.1. 'Een schimmel is een wit paard'  '2+3 = 5'2. 'Een schimmel is een bruin paard'  '2+3 = 5'3. 'Een schimmel is een wit paard'  '2+3 = 6'4. 'Een schimmel is een bruin paard'  '2+3 = 6'
In dit voorbeeld zijn de eerste drie proposities true en de laatste is false omdat bij deze propositie beide operanden false zijn. Dus: zoals al vermeld is de logische 'of' equivalent met de Nederlandse zin: òf het een òf het ander òf beide. Dit wordt de zg. inclusive or genoemd. Dit in tegenstelling tot de exclusive or (XOR) die zegt: òf het een, òf het ander, maar niet beide. ImplicatieEen derde binaire operator is de implicatie. Deze operator maakt het mogelijk om 'oorzaak-gevolg' uitspraken in een logische expressie vorm te geven. Denk daarbij aan constructies als: Indien ik genoeg geld heb, dan koop ik een nieuwe fiets.
De implicatie wordt geschreven als en uitgesproken als  impliceert . De definitie in de vorm van een tabel is de volgende:

	

	

	

	

	

 

Hieruit blijkt dat de implicatie altijd de waarde true heeft, tenzij de eerste operand true is en de tweede false. De operand  wordt de premisse (ook wel hypothese of antecedent) genoemd en  de conclusie (of consequentie). Taalgebruik waarin implicaties een rol spelen komt vaak voor.
Voorbeeld. De assertie '' kan de logische vertaling zijn van zinnen als:'als , dan '' volgt uit '' is een voldoende voorwaarde voor '' is het gevolg van ' ' mits '
Toch kunnen ook hier problemen ontstaan, zoals blijkt uit het volgende voorbeeld:
Voorbeeld. Beschouw de uitspraak Als jij de kamer stoft, dan zal ik afwassen. Voor de meesten zal dit betekenen dat als de andere de kamer stoft, de eerste persoon de afwas zal doen. Geschreven als implicatie: Jij stoft de kamer→ Ik was af. In deze notatie is Jij stoft de kamer de premisse en Ik was af de conclusie. Uit de definitietabel blijkt dat indien de premisse false is (Jij stoft de kamer niet) dat dan de conclusie nog true kan zijn {Ik was dus af). Waarschijnlijk is dat niet de bedoeling. Een implicatie kan soms raar overkomen. Beschouw de volgende constructie: Als er kabouters bestaan dan is de aarde een meloen. De implicatie op zich is true (de premisse Kabouters bestaan is uiteraard false) maar er kan natuurlijk niet de conclusie aan worden verbonden dat de aarde inderdaad een meloen is. Pas dus op voor situaties waarin de premisse false is!
De implicatie levert vaak meer problemen op dan de andere logische operatoren. Dat komt voornamelijk door de logische regel dat uit een FALSE - hypothese alles kan worden afgeleid. Zo is FALSE → FALSE gelijk aan TRUE. En zelfs FALSE → TRUE is TRUE. Willekeurige proposities invullend levert dat verschrikkelijke onzin op: 'Als 2 oneven is, dan is 7 x 3 = 21 ' is dus een ware bewering, strikt logisch gezien. Zo ook is 'Als 2 oneven is, dan is 7 x 3 = 22 ' een ware bewering in strikt logische zin. Deze logica lijkt niet erg zinvol! Toch is er in het spraakgebruik wel iets te herkennen van deze logische afspraak. In de uitspraak 'Als Piet zijn propedeuse haalt, dan vreet ik mijn schoenen op' gaat de spreker er natuurlijk van uit dat de hypothese tòch niet waar zal blijken te zijn. Blijkbaar kun je uit een foute veronderstelling alles afleiden! 

Overigens houdt de logica zich niet bezig met de semantiek van haar uitspraken. Dat wil zeggen: zij trekt zich niets aan van wat de proposities en de samengestelde proposities voor een betekenis hebben in de dagelijkse wereld; zij houdt zich slechts bezig met strikte afspraken over wat geldig is binnen de door ons mensen opgestelde strakke logische structuur. 
Een voorbeeld nog om te laten zien wat hier bedoeld wordt: met de regel "TRUE → TRUE wordt TRUE" heeft niemand moeite. Maar wat is de betekenis dan van: 'Als 2 even is, dan is 7 x 3 = 21' .....?? De logica is niet geïnteresseerd in het antwoord op deze vraag. De logica stelt slechts vast dat de waarheidswaarde van deze propositie TRUE is. Als de logica dus indruist tegen je 'gevoel' dan moet je je maar vasthouden aan de formele afspraken die we in dit hoofdstukje hebben gemaakt: de waarheidstabel heeft het in de logica voor het zeggen, en de 'informele' "vertaling" van een propositie in een natuurlijke taal als het Nederlands is vaak dubbelzinnig en voor meerdere uitleg vatbaar. In dit verband onderstrepen we nogmaals de opmerking: We beschouwen in het vervolg enkel de tabellen in dit hoofdstuk als de definitie van de operatoren en niet het informele taalgebruik dat wordt gebruikt als introductie.

Equivalentie
De laatste operator die we zullen bespreken is de equivalentie of gelijkheid. Deze operator heeft de waarde true indien beide operanden dezelfde waarheidswaarde hebben. We noteren de equivalentie als  en spreken dit uit als  equivalent met . Soms wordt de equivalentie uitgesproken als ' dan en slechts dan als ', ook wel eens afgekort tot ' desda '. Ook andere afkortingen komen voor: ' asa '(' als en slechts als ') en (in Engelse literatuur): ' iff ' (' if and only if '). Er geldt:

	

	

	

	

	

 

Voorbeeld. Let op dat de equivalentie enkel aangeeft of twee logische operanden dezelfde waarheidswaarde hebben. Aangezien beide operanden in de logische expressie (5 >7) (12 < (5+7)) false zijn heeft de expressie dus in zijn geheel de waarde true. Nog een opmerking over het taalgebruik bij equivalentie. Bekijk als voorbeeld de volgende zin: ´Ik ga alleen afwassen, als jij de kamer stofzuigt`. Op het eerste gezicht lijkt dit een implicatie, maar wij interpreteren deze zin als volgt: ´als jij de kamer stofzuigt, dan ga ik afwassen´, maar ook: ´als ik ga afwassen, dan stofzuig jij de kamer´, want ik was alleen maar dan af, als jij stofzuigt, dus als ik afwas dan moet jij wel aan het stofzuigen zijn. Dit betekent dat het één de ander impliceert én omgekeerd, dat wil zeggen: het is een equivalentie! Kortom: ´ alleen als  vertalen wij met .
Opgave 1.2.1

We definiëren de volgende uitspraken:: Ik heb honger.: Ik eet.: Ik word dik.
Geef van de volgende beweringen het logisch equivalent:
a) Als ik honger heb, eet ik en word ik dik.
b) Ik eet alleen maar als ik honger heb.
c) Ik eet, ongeacht of ik honger heb of niet.
d) Ik word dik als ik eet.
Maak op Maple T.A. de oefening: [1.2.1] Logische operatoren

Opgave 1.2.2

Voor de definitie van ,  en  zie vraag 1.2.1. Vertaal de volgende logische expressies in een goed lopende, Nederlandse zin:
a) 

b) 

c) (

Maak op Maple T.A. de oefening: [1.2.2] Logische expressies vertalen

1.3 Waarheidstabellen
Tot nu toe zijn waarheidstabellen gebruikt om de definitie van een operator vast te leggen. Waarheidstabellen kunnen ook worden gebruikt om grotere propositionele vormen te onderzoeken. Het is met behulp van een waarheidstabel mogelijk om bijvoorbeeld te onderzoeken of twee propositionele vormen gelijk zijn (equivalent), maar ook de waarheidswaarde van een logische expressie kan worden bepaald (zie het tweede voorbeeld hierna). Volgens de definitie van equivalentie zijn twee proposities (en dus ook twee propositionele vormen) equivalent als beide operanden (altijd) dezelfde waarheidswaarde hebben. We kunnen dat onderzoeken door 'eenvoudigweg' alle mogelijk gevallen te onderzoeken. Let er wel op dat het aantal te onderzoeken gevallen exponentieel toeneemt naarmate er meer propositie-variabelen in de vorm voorkomen. In het algemeen zal met drie variabelen nog gewerkt kunnen worden (acht gevallen). Vier variabelen vraagt al zestien gevallen te onderscheiden.
Voorbeeld. Stel dat we willen bewijzen dat  equivalent is met .
Het beste is nu om onder de eerste twee kolommen alle mogelijke combinaties van  en  op te sommen. Vervolgens wordt de waarheidswaarde van  en van  voor al die combinaties onderzocht en genoteerd in de juiste kolom. Deze laatste vorm kan pas worden onderzocht nadat de waarheidswaarde van is vastgesteld. In overzichtelijke situaties kan dat vaak in één keer samen met de gehele vorm worden onderzocht. Tenslotte kan de equivalentie van deze twee proposities worden aangegeven in de overgebleven kolom. Slechts indien in deze laatste kolom overal een T verschijnt hebben we bewezen dat  equivalent is met  voor alle mogelijke combinaties van de waarde van de propositievariabelen  en .

Daartoe gebruiken we de volgende tabel:

	

	

	

	

	

	

	

	

	

	

 

Opmerking: Het is gebruikelijk om de waarheidswaarde onder de operator te noteren.
Voorbeeld. Nog een voorbeeld, maar dan met drie propositie-variabelen. Onderzocht dient te worden wat de waarheidswaarde van de volgende propositionele vorm is:

Daartoe gebruiken we de volgende tabel:

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

	

Eerst worden de kleinste vormen onderzocht (kolom 4, 6 en 8), waarna uit de kolommen 4 en 6 kolom 5 kan worden herleid, tenslotte gevolgd door kolom 7 (Ga dit na!). Uit de vorm van de zevende kolom blijkt duidelijk dat deze propositionele vorm altijd true is. 

Overigens bepaalt het aantal operanden (ook wel atomaire proposities genoemd) uit hoeveel regels een waarheidstabel moet bestaan. Met 3 operanden (,  en  bijvoorbeeld) zijn er  verschillende combinaties mogelijk van waarheidswaarden. Dus de waarheidstabel van bv. heeft 8 regels. Om geen enkele combinatie van waarheidswaarden te missen structureren we zo'n waarheidstabel meestal zó:

	

	

	

	

	

	

	

	

	

 

waarmee we alle 8 verschillende combinaties hebben gehad. 

Indien een propositionele vorm altijd de waarde true heeft noemen we deze een tautologie, indien de waarde altijd false is een contradictie of absurditeit; in alle andere gevallen spreken we van een contingentie.
Definitie. Een tautologie is een propositionele vorm waarvan de waarheidswaarde true is voor alle mogelijke waarden van de propositie-variabelen.
Definitie. Een contradictie of absurditeit is een propositionele vorm waarvan de waarheidswaarde false is voor alle mogelijke waarden van de propositie-variabelen.
Definitie. Een propositionele vorm die geen tautologie of contradictie is, is een contingentie.
Voorbeeld.  is een contingentie;  is een tautologie;   is een contradictie. De laatste vorm wordt ook wel eens omschreven als 'het uitgesloten wonder'. 

In sommige gevallen is het niet nodig om alle gevallen te onderzoeken om toch een uitspraak te kunnen doen over de waarheidswaarde van een propositie. In dat geval moet gezocht worden naar een bijzonder geval dat nader moet worden onderzocht.
Voorbeeld. We willen onderzoeken of  een tautologie is. Daartoe hoeven we eigenlijk alleen maar te zoeken naar een geval waarin de implicatie false kan worden. De enige manier waaropde waarde false kan hebben is het geval waarin  true is en  false. In ons voorbeeld betekent dit het vinden van een geval waarin  true is en  false. Om  true te laten zijn moeten zowel  als  de waarde true hebben. Alleen dat geval moeten we dus nader onderzoeken. Maar het is duidelijk dat dan  niet meer false kan zijn! Deze vorm van onderzoek noemen we wel gepast gevallen onderscheid of verkorte waarheidstabel indien het onderzoek wordt gedaan met behulp van een tabel:

	

	

	

	

ContrapositieDe contrapositie is van speciaal belang. Het is een alternatieve manier om een implicatie te beschrijven. Dat wil zeggen:  en  hebben dezelfde waarheidstabel. Let op: hele volksstammen denken dat uit de regel: 'als het regent, dan word ik nat' wel volgt: 'als het niet regent dan word ik niet nat'. Maar dat is niet correct. Als je immers bv. onder de douche staat word je ook nat. Wèl geldt: 'als ik niet nat ben, dan heeft het ook niet geregend.' Deze laatste zin is de contrapositie van de allereerste in dit voorbeeld. In logische bewoordingen geldt dus dat:  een tautologie is, maar niet.

Opgave 1.3.1

Maak voor de volgende propositionele vormen een waarheidstabel:
a) 

b) 

c)  

Maak op Maple T.A. de oefening: [1.3.1] Waarheidstabel opstellen

1.4 Eigenschappen van logische operatoren
Zoals bekend bestaan er in de rekenkunde bepaalde eigenschappen en afspraken, waaraan operatoren, zoals optelling en vermenigvuldiging, voldoen. Er wordt dan gewerkt met een prioriteitsvolgorde (Meneer Van Dalen Wacht Op Antwoord). Ook bij logische operatoren is er een prioriteitsvolgorde (in dalende prioriteit): niet ( ) - en (  ) - of (  ) - implicatie ( ) - gelijkheid ().
Voorbeeld.  is gelijk aan    is gelijk aan 
Omdat de logische expressie met haakjes veel makkelijker leest en enig (onbedoeld) misverstand opheft, adviseren we om van haakjes gebruik te maken, ook al zijn die (in principe) overbodig.
Andere eigenschappen die bij rekenkundige operatoren een rol spelen zijn:- associativiteit - commutativiteit - distributiviteit 
Opmerking: Dit geldt natuurlijk niet voor alle rekenkundige bewerkingen; zo zijn de '' en de '' operatoren niet commutatief ()!
Voor de logische operatoren gelden de volgende eigenschappen: ' ' en ' 'zijn zowel commutatief als associatief en '' distribueert over ''  en ''  over '' .In logische expressies opgeschreven wordt dit: 
commutativiteit :

associativiteit:

distributiviteit:

Verder gelden er nog enkele eigenschappen, zoals:

idempotentie:

dubbele ontkenning:

De Morgan:

De correctheid van deze expressies kan eenvoudig via een waarheidstabel worden aangetoond. Vooral de wetten van De Morgan spelen bij het opstellen van programma's een grote rol. Vaak is het mogelijk om ontkenningen in constructies te vereenvoudigen.

Programmeervoorbeeld. In een programma moet een opdracht S herhaaldelijk worden uitgevoerd totdat geldt dat x tenminste 0 is of x kleiner is dan 0, maar in dat geval moet y groter dan 0 zijn. In een formele beschrijving ziet dat er als volgt uit: 

((x ≥ 0) ∨ ((x < 0) ∧ (y > 0))
De constructie die daarvoor zorgt zou kunnen zijn:
WHILE NOT ( (x >= 0) OR ( ( x < 0 ) AND (y>0) ) ) DO S
Deze opdracht zorgt er immers voor dat S steeds wordt uitgevoerd totdat op een bepaald moment wel geldt ((x ≥ 0) ∨ ((x < 0) ∧ (y > 0)). De opdracht S moet natuurlijk wel invloed hebben op de waarden van x en y. Als namelijk x en y de waarden zouden behouden zoals die waren voor het begin van deze constructie, dan zal dit stukje van het programma nooit eindigen. Op het moment dat ((x ≥ 0) ∨ ((x < 0) ∧ (y > 0)) tot true evalueert, wordt de constructie:
WHILE false DO S;
en zal S niet meer worden uitgevoerd.
De expressie ¬ ((x ≥ 0) ∨ ((x < 0) ∧ (y > 0)) laat zich gelukkig wel wat vereenvoudigen (rechts staat steeds op welke eigenschap we ons beroepen om de equivalentie met de volgende expressie aan te tonen):
¬ ((x ≥ 0) ∨ ((x < 0) ∧ (y > 0)) {wet van De Morgan} ⇔( ¬ (x ≥ 0) ∧ ¬ ((x < 0) ∧ (y > 0)) {wet van De Morgan} ⇔( ¬ (x ≥ 0) ∧ ( ¬ (x < 0) ∨ ¬ (y > 0)) {eigenschap van >,< en ≥}⇔((x < 0) ∧ ( (x ≥ 0) ∨ (y ≤ 0)) {distributiviteit}⇔((x < 0) ∧ (x ≥ 0)) ∨ ((x < 0) ∧ (y ≤ 0)) {eigenschap getallen}⇔F ∨ ((x < 0) ∧ (y ≤ 0)) {false-true regels}⇔((x<0) ∧ (y ≤ 0))
Deze afleiding vereenvoudigt dus de constructie tot:
WHILE ( x < 0 ) AND (y<=0) DO S

1.5 Herschrijven van expressies
Zoals uit het laatste voorbeeld van 1.4 blijkt, kan op grond van de beschreven eigenschappen het gebruik van waarheidstabellen worden vermeden(zeker gewenst als er meer propositie-variabelen in een expressie voorkomen). De techniek hierbij is om (delen van) de expressie te herschrijven totdat de gewenste vorm is verkregen. Het is hierbij gebruikelijk om de argumenten voor de herschrijving als een soort commentaar in de afleiding op te nemen, zoals in het laatste voorbeeld van 1.4 al is gedaan.
De herschrijfregels zijn gebaseerd op het toepassen van tautologieën. Over de schrijfwijze van deze logische wetten is nog wel het één en ander op te merken. 

In de equivalentie  is het teken een logische operator, met een bepaald rekenvoorschrift. Zoals gebleken kan het berekenen van de uitkomst van logische expressies soms leiden tot de conclusie dat er sprake is van een tautologie. 
Zo is de equivalentie  een tautologie, maar de equivalentie is dat niet. Daardoor is de eerste een herschrijfregel en de tweede niet. We noemen een equivalentie die een tautologie is ook wel een logische equivalentie. 
Er is een schrijfwijze waarmee we meteen het verschil duidelijk kunnen maken tussen een logische equivalentie en een ´gewone´ equivalentie. We gebruiken devoor logische equivalenties.
Conclusie. omdat we bewezen hebben dat  een tautologie is, zullen we voortaan schrijven: 
In herschrijvingen waar je gebruik maakt van de logische equivalenties van het fomuleblad ‘Logische Equivalenties’ zul je ook zelf van het teken gebruik moeten maken. In het algemeen vindt men het gebruik van herschrijfregels moeilijker dan het maken van waarheidstabellen. Beide technieken zijn geschikt om de logische equivalentie van twee proposities aan te tonen. Herschrijven is echter een noodzakelijke vaardigheid, die bij het programmeren en het vereenvoudigen van digitale schakelingen nog vaak van pas zal komen. De reden voor de moeilijkheidsgraad ligt in het feit dat er niet één methode is aan te geven wat je moet doen. Vaak zijn er meerdere regels van toepassing op een propositie. Welke regel je dan moet gebruiken ligt aan wat je wilt bereiken, en de 'verkeerde' weg inslaan is een onvermijdelijke stap naar dieper inzicht en grotere ervaring. Gewoon blijven proberen!

We geven nu twee voorbeelden van het gebruik van herschrijfregels, de gebruikte namen verwijzen naar de regels op het fomuleblad ‘Logische Equivalenties’. Waar het symbool * wordt gebruikt wordt aangegeven dat deze regel meerdere keren is toegepast.

 {implicatieregel *}
 {associativiteit}
 {De Morgan}
 {associativiteit}
 {FT regels}

 {implicatieregel}
 {De Morgan}
 {associativiteit}
 {commutativiteit}
 {associativiteit}
 {FT regels}
 {idempotentie}

Opgave 1.5.1

Vereenvoudig de volgende expressies doormiddel van herschrijven:
a) 

b) 

Maak op Maple T.A. de oefening: [1.5.1] Herschrijven van een expressie

1.6 Antwoorden van de opgaven

Opgave 1.1.1

a) Geen propositie

b) Propositie

c) Geen propositie

Opgave 1.2.1

a) 
b)  
c)  
d)  

Opgave 1.2.2

a) Als ik eet dan word ik dik.

b) Als ik niet eet dan heb ik honger.

c) Als ik niet eet dan word ik niet dik en als ik eet dan heb ik honger.

Opgave 1.3.1

a) 

	

	

	

	

	

 

b) 

	

	

	

	

	

 

c)  

	

	

	

	

	

 

Opgave 1.5.1

a) 

 {Implicatieregel 3x}
 {False/True regel}
T {Distributieregel}
T {False/True regel}
FT {False/True regel}

b) 

 {Associativiteit}
 {Implicatieregel}
 {Simplificatie}
 {De Morgan}
 {Distributieregel}
 {False/True regel}
T {Associativiteit}
T {False/True regel}