Juul van Engeland – TU Eindhoven
1.1 Syntax
A proposition is a statement that is true or false, it can be written in different languages
(mathematical/grammatical).
Abstract propositions worden benoemd met a,b,c….. de propositions worden beschreven met
verschillende connectives.
De syntax vertelt hoe een abstract proposition in elkaar zit, dit zijn de regels hoe het is opgebouwd. Dit
kan worden geschreven in ‘Prooftrees’:
De buitenste haken van een abstract proposition kunnen altijd worden verwijderd. Verder moet er goed
gekeken worden naar het precedence scheme, dit bepaalt waar de haken kunnen worden verwijdert.
1.2 Semantics
In de taal van semantics staat 0 voor false en 1 voor true. Er zijn verschillende verbanden voor de
propositions en connectives uitgelegd met ‘truth tables’.
Er wordt bij een truthtable altijd van binnen naar buiten gewerkt bij een grotere abstract proposition.
1.3 Tautologies and contradictions
Een tautology is een abstract proposition dat als elke uitkomst true heeft. Een contradiction is een
abstract proposition dat als elke uitkomst false heeft. Een contingency is een abstract proposition welke
geen tautology of contradiction is. Een syntaxregel die wordt toegevoegd aan de rij wordt:
1.2 True en false zijn abstract propositions
Een gevolg hieruit is dat in de truthtable nu ook Truth of False kan worden toegevoegd.
, Juul van Engeland – TU Eindhoven
1.4 Contingency
Om een contingency te krijgen moet er bewezen worden dat de abstract proposition geen tautology of
contradiction is. Een voorbeeld volgt waarin wordt bewezen dat een deel van de proposition 0 kan zijn
en een voorbeeld dat de proposition 1 maakt:
Not a Tautology
Not a contradiction
Omdat deze abstract proposition True of False kan zijn, is dit een contingency.
1.5 Logical equivalence
𝑣𝑣𝑣𝑣𝑣𝑣
P en Q zijn logically equivalent als geldt dat P is true if and only if Q is true (��). De volgende gevallen
vertonen commutativity.
Associativity geldt voor bimplications en dis/conjunction, implication is dit niet.
1.6 Logical consequence
Q is een logische consequentie van P als P is true en daarna Q is true.
Als P weaker is dan Q, of P sterker is dan Q, dan zijn P en Q comparable. Anderzijds zijn P en Q
incomparable.
False is de sterkste abstract proposition, true is de zwakste abstract proposition.
Wanneer een ‘truth table’ wordt gemaakt van een abstract proposition en er wordt gekeken of P of Q
sterker of zwakker is dan de ander, dan wordt er gekeken of de ‘truth table’ van de één in de ander past.
Stel P Q Dan past de truth table van Q in die van P, wat betkent dat Q
1 1 sterker is dan P. De notatie is dan als volgt (P =|Q)
1 0
0 0
2.1 Introduction to predicates and quantifiers
Wanneer een statement wordt gegeven worden alle delen eruit gefilterd en toegewezen aan een
proposition. Zo kan een logische beredenering plaatsvinden. Individuelen, predicates (properties) en
quantification (specifications) worden gespecificeerd.
, Juul van Engeland – TU Eindhoven
2.2 Predicates
Integers kunnen worden gebruikt in een abstract proposition.
- Nullary predicate is ookwel een proposition
- Een predicate neemt een bepaald aantal van een type als input en produceert een truth value
als output.
- Een unary predicate neemt één ding van een bepaald type als input en produceert een truth
value als output.
- Een binaire predicate neemt twee dingen van een bepaald type als input en produceert een
truth value als output.
- Een ternary predicatie neemt drie dingen van een bepaald type als input en produceert een
truth value als output.
Predicates kunnen worden gecombineerd met een connective.
P en Q zijn logically equivalent als P is true if and only if Q is true (zelfde notatie als equivalentie
propositions). Bij equivalentie moet goed worden beschreven wat er kan worden gebruikt voor de
variabelen (integers of cijfers).
2.3 Quantification of unary predicates
Predicates hebben een algemene notatie wanneer een proposition ontstaat.
Een voorbeeld van deze algemene notatie is met een interpretatie dat alle x ∈ N geldt dat 4x≤ 5x :
∀x[x ∈ N : 4x ≤ 5x]
Het symbool ∀x is een universal quantifier. Als P(x) en Q(x) de predicates zijn dan waar geldt dat iedere x
die voldoet aan P(x) dan ook Q(x) geldt:
∀x[P(x) : Q(x)]
De existential quantificatie in een proposition wordt nu geïntroduceerd. Een voorbeeld van een
proposition met een existential quantificatie is: ‘Er bestaat een x ∈ N zodat 4x < 5x’. Het stuk van de
proposition waar de existential quantificatie aanwezig is, is ‘Er bestaat’. In deze propositions worden
existential quantifiers gebruikt, deze worden aangeduid met ∃x.
∃x[x ∈ N : 4x < 5x]
Er bestaat een x die voldoet aan P(x) waar ook Q(x) geldt:
∃x[P(x) : Q(x)]
2.4 Domain of quantification
Het domein van een quantification wordt gegeven voor het : teken. Een quantification heeft altijd true
(1) of false (0) als uitkomst. Een leeg domain is een extreem geval, dit betekent dat het domein gelijk is
aan false:
∃x[False : P] = False
∀x[False : P] = True
Wanneer het domein van een quantification ‘true’ is wordt deze weggelaten in de notatie:
∃x[True : P] = ∃x[P]
∀x[True : P] = ∀x[P]
Het domein kan worden verzwakt wanneer een domein bestaat uit een conjunctie (∧) door een van de
propositions weg te halen. Een voorbeeld met de algemene regels hiervan is:
∃x[x ∈ N ∧ x > 0 : x2 =1] = ∃x[x ∈ N : x > 0 ∧ x2 =1]
∀x[x ∈ R ∧ x > 1: x2 =1 ] = ∀x[x ∈ R : x > 1 => x2 =1]
, Juul van Engeland – TU Eindhoven
2.5 Quantification of predicates of higher arity
Als geldt voor alle x ∈ R bestaat er een y ∈ N zodat 2x + y > 2. Dit is een proposition welke kan worden
geschreven als een quantification met meerdere haken:
∀x[x ∈ R : ∃y[y ∈ N : 2x + y >2]] ≠ ∃y[y ∈ N : ∀x[x ∈ R : 2x + y > 2]]
De volgorde van de quantification maakt WEL uit!
Quantifications kunnen ook samen worden gepakt als één quantification:
∀x[P : ∀y[Q:R]] = ∀x,y[P ∧ Q : R]
∀x[P : ∃y[Q:R]] = ∀x ∃y[P ∧ Q : R]
2.6 Binding
∃x of ∀x wordt een binder genoemd, alles wat er binnen de haken staat wordt de scope genoemd en er
wordt gesteld dat ∀x/∃x x bindt in zijn scope. Een variabele is dus ‘gebonden’ als het zich in de scope
bevindt, anderzijds is de variabele ‘vrij’. In het volgende voorbeeld is de variabele y dus ‘gebonden’ en is
de variabele x ‘vrij’.
∃y[y ∈ N : x + y > 6]
De volgende regels gelden voor het hernoemen van quantifications:
∀x[P : Q] = ∀y[P[x y] : Q[x y]]
3.1 Introduction to flag-style derivations
Een voorbeeld van een mathematical proof:
Voor alle x ∈ Z, als x is even, dan is x2 ook even (goal).
Bij deze proposition moet worden bewezen dat x2 even is als x even (aanname) is en als x ∈ Z (variable
declaration).
Uit deze aanname dat x even is volgt dat x=2y voor enkele y ∈ Z (conclusie). Nu wordt x vervangen door
2y waardoor x2=(2y)2=4y2=2(2y2) ontstaat met 2y2 ∈ Z. Omdat x2=2(2y2) en 2y2 ∈ Z dan volgt dat x2 is
even.
De volgorde is het definiëren van een goal, een variable declaration, aanname (flagpole) en het stellen
van een conclusie. De mathematical proof kan worden geschreven in een flag-style derivation:
Let x ∈ Z (variable declaration).
x is even (aanname)
x=2y voor enkele y ∈ Z (conclusie)
x2=(2y)2=4y2=2(2y2)
2y2 ∈ Z
x2 is even.
Voor alle x ∈ Z, als x is even, dan is x2 ook even (goal)
3.2 Rules for conjunction and implication
Voor het bewijzen dat een conjunction is true, dan is het voldoende om te bewijzen dat beide conjucts
true zijn. Hieruit volgen verschillende bewijsstructuren:
|| || |
(m) P ∧ Q P
|| || |
(n-1) {∧ eliminatie op (m):} Q
(n) P {∧ introductie op (m) en (n-1):}
(n) P ∧ Q
, Juul van Engeland – TU Eindhoven
Voor het bewijzen dat een implicatie ‘true’ is, is het genoeg om te bewijzen dat zijn conclusie ‘true’ is,
met de voorwaarde dat de conditie is ‘true’. Dit kan worden weergegeven in een flag-style derivation:
{ Assume:}
(m) P
:
(n-1) Q
{=> introductie on (m) and (n-1):}
(n) P => Q
Als de implicatie is ‘true’ en zijn conditie is ook ‘true’, dan kan worden geconcludeerd dat de conclusie
ook ‘true’ is.
|| ||
(l) P => Q
|| ||
(m) P
|| ||
{ => eliminatie op (l) en (m):}
(n) Q
3.3 Example derivation with conjunction and implication
Dit gehele college bestaat uit een voorbeeld. Het voorbeeld dat wordt gebruikt is:
(P => (Q ∧ R)) => ((P => Q) ∧ (P => R)) is een tautologie.
P => (Q ∧ R) wordt gezien als de aanname en bevindt zich in de flagpole, (P => Q) ∧ (P => R) wordt gezien
als de goal.
Bewijs nu dat ((P => Q) ∧ (P => R)) => (P => (Q ∧ R))
(1) P => (Q ∧ R) een tautologie is:
{Assume:} (1) (P => Q) ∧ (P => R)
(2) P
(2) P
{=> eliminatie op (1) en (2):}
{∧ elimination (1):}
(3) (Q ∧ R)
{∧ eliminatie op (3):} (3) P => Q
(4) Q {=> eliminatie (2) en (3):}
{=> introductie op (2) en (4):} (4) Q
(5) P => Q {∧ eliminatie (1):}
{Assume:} (5) (P => R)
(6) P { => eliminatie (2) en (5):}
{=> eliminatie op (1) en (6):} (6) R
(7) Q∧R {∧ introductie (4) en (6):}
{∧ eliminatie op (7):} (7) Q∧R
(8) R {=> introductie (2) en (7):}
{=> introduction op (6) en (8):}
(8) P => Q ∧ R
(9) P => R
{=> introduction (1) en (8):}
{∧ introductie op (5) en (9):}
(10) (P => Q) ∧ (P => R) (9) ((P => Q) ∧ (P => R)) => (P => (Q ∧ R))
{=> introductie op (1) en (10):}
(11) (P => (Q ∧ R)) => ((P => Q) ∧ (P => R))
