Contents
Week 1 – Propositional logic.................................................................................................................2
1.1 Syntax..........................................................................................................................................2
1.2 Semantics.....................................................................................................................................3
1.3 Tautologies, contradictions and contingencies............................................................................4
1.4 Contingencies..............................................................................................................................4
1.5 Logical equivalence......................................................................................................................4
1.6 Logical consequence....................................................................................................................4
Lecture 1............................................................................................................................................4
Week 2 – Predicate logic.......................................................................................................................5
2.1 Introduction to predicates and quantifiers..................................................................................5
2.2 Predicates....................................................................................................................................5
2.3 Quantification of unary predicates..............................................................................................6
2.4 Domain of quantification.............................................................................................................6
2.5 Quantification of predicates of higher arity.................................................................................6
2.6 Binding.........................................................................................................................................7
Week 3 – Derivations.............................................................................................................................7
3.1 – Introduction..............................................................................................................................7
3.2 & 3.3 – Implication and conjunction in proofs.............................................................................7
3.4 – Validity, context, correctness of derivations.............................................................................8
3.5, 3.6, 3.7 – Negation and contradiction in derivations (and an example)......................................8
3.8, 3.9 – Disjunction, bi-implication in derivations (and an example)..............................................9
3.10, 3.11 – Universal quantification in derivations (with an example).............................................9
3.12, 3.13 – Existential quantification in derivations (with an example)..........................................10
3.14 – Variables and declarations....................................................................................................10
3.15 – From derivation to proof; case distinction (with an example)..............................................10
Week 4 – Sets......................................................................................................................................11
4.1 Introduction to sets...................................................................................................................11
4.2 Operations on sets.....................................................................................................................11
4.3 Counterexamples: refuting an equality......................................................................................12
4.4 Inclusion, powerset....................................................................................................................12
4.5 Example with subset, equality, complement and difference.....................................................12
4.6 Equality predicate revisited.......................................................................................................13
4.7 Example with empty set, union, difference and equality...........................................................13
4.8 Pairing and Cartesian product....................................................................................................13
,Week 5 – Relations and mappings.......................................................................................................13
5.1 Introduction...............................................................................................................................13
5.2 Equivalence modulo 5 (example of proving equivalence relation)............................................14
5.3 Equivalence classes....................................................................................................................14
5.4 Definition of mapping................................................................................................................15
5.5 Image.........................................................................................................................................16
5.6 Example with image...................................................................................................................17
5.7 Counterexample with image......................................................................................................17
5.8 Source........................................................................................................................................17
5.9 Surjection (mappings)................................................................................................................17
5.10 Injection...................................................................................................................................18
5.11 Example with image and injection...........................................................................................18
5.12 Bijection and inverse (mappings).............................................................................................18
Week 6 – Induction..............................................................................................................................19
6.1 Principle of induction.................................................................................................................19
6.2 First example of induction.........................................................................................................19
6.3 Example of induction with summation......................................................................................19
6.4 Example of induction with divisibility........................................................................................19
6.5 Strong induction........................................................................................................................20
6.6 First example of strong induction..............................................................................................20
6.7 Second example of strong induction..........................................................................................21
6.8 Third example of strong induction (divisibility)..........................................................................21
Tips from the tutorial.......................................................................................................................21
Week 1 – Propositional logic
1.1 Syntax
Proposition: Boolean statement statement that is true or false
, - Can be mathematical, not necessarily
Vocabulary
- Proposition variables
o a,b,c (statements)
- Connectives (see signs in picture)
o Not: negation
o And: conjunction
o Or: disjunction (inclusive)
o If: implication
o If and only if: bi-implication
- Combinations of these form the syntax (of abstract
propositions)
o Using clauses, we can show how combinations of
propositions again form propositions
o Use parentheses around the original propositions when combining them, but omit
those not necessary to prevent ambiguity
1.2 Semantics
- Propositions take in input (propositions) and give an output (truth or false)
- P and Q are the inputs (either true (=T or 1) or false (=F or 0)), which give the following
outputs for the different connectives
- Implication can be regarded as a promise:
o When the condition is true and the consequence is true, the promise is hold (thus
true)
o When the condition is true, the promise does not apply, thus any consequence holds
(thus always true)
o When the condition is true, but the consequence is false, the promise is not hold
(thus false)
- Bi-implication can be regarded as an equal sign
o If p and q have the same value (both 0/false or both 1/true), the output is true
o Otherwise: false
Week 1 – Propositional logic.................................................................................................................2
1.1 Syntax..........................................................................................................................................2
1.2 Semantics.....................................................................................................................................3
1.3 Tautologies, contradictions and contingencies............................................................................4
1.4 Contingencies..............................................................................................................................4
1.5 Logical equivalence......................................................................................................................4
1.6 Logical consequence....................................................................................................................4
Lecture 1............................................................................................................................................4
Week 2 – Predicate logic.......................................................................................................................5
2.1 Introduction to predicates and quantifiers..................................................................................5
2.2 Predicates....................................................................................................................................5
2.3 Quantification of unary predicates..............................................................................................6
2.4 Domain of quantification.............................................................................................................6
2.5 Quantification of predicates of higher arity.................................................................................6
2.6 Binding.........................................................................................................................................7
Week 3 – Derivations.............................................................................................................................7
3.1 – Introduction..............................................................................................................................7
3.2 & 3.3 – Implication and conjunction in proofs.............................................................................7
3.4 – Validity, context, correctness of derivations.............................................................................8
3.5, 3.6, 3.7 – Negation and contradiction in derivations (and an example)......................................8
3.8, 3.9 – Disjunction, bi-implication in derivations (and an example)..............................................9
3.10, 3.11 – Universal quantification in derivations (with an example).............................................9
3.12, 3.13 – Existential quantification in derivations (with an example)..........................................10
3.14 – Variables and declarations....................................................................................................10
3.15 – From derivation to proof; case distinction (with an example)..............................................10
Week 4 – Sets......................................................................................................................................11
4.1 Introduction to sets...................................................................................................................11
4.2 Operations on sets.....................................................................................................................11
4.3 Counterexamples: refuting an equality......................................................................................12
4.4 Inclusion, powerset....................................................................................................................12
4.5 Example with subset, equality, complement and difference.....................................................12
4.6 Equality predicate revisited.......................................................................................................13
4.7 Example with empty set, union, difference and equality...........................................................13
4.8 Pairing and Cartesian product....................................................................................................13
,Week 5 – Relations and mappings.......................................................................................................13
5.1 Introduction...............................................................................................................................13
5.2 Equivalence modulo 5 (example of proving equivalence relation)............................................14
5.3 Equivalence classes....................................................................................................................14
5.4 Definition of mapping................................................................................................................15
5.5 Image.........................................................................................................................................16
5.6 Example with image...................................................................................................................17
5.7 Counterexample with image......................................................................................................17
5.8 Source........................................................................................................................................17
5.9 Surjection (mappings)................................................................................................................17
5.10 Injection...................................................................................................................................18
5.11 Example with image and injection...........................................................................................18
5.12 Bijection and inverse (mappings).............................................................................................18
Week 6 – Induction..............................................................................................................................19
6.1 Principle of induction.................................................................................................................19
6.2 First example of induction.........................................................................................................19
6.3 Example of induction with summation......................................................................................19
6.4 Example of induction with divisibility........................................................................................19
6.5 Strong induction........................................................................................................................20
6.6 First example of strong induction..............................................................................................20
6.7 Second example of strong induction..........................................................................................21
6.8 Third example of strong induction (divisibility)..........................................................................21
Tips from the tutorial.......................................................................................................................21
Week 1 – Propositional logic
1.1 Syntax
Proposition: Boolean statement statement that is true or false
, - Can be mathematical, not necessarily
Vocabulary
- Proposition variables
o a,b,c (statements)
- Connectives (see signs in picture)
o Not: negation
o And: conjunction
o Or: disjunction (inclusive)
o If: implication
o If and only if: bi-implication
- Combinations of these form the syntax (of abstract
propositions)
o Using clauses, we can show how combinations of
propositions again form propositions
o Use parentheses around the original propositions when combining them, but omit
those not necessary to prevent ambiguity
1.2 Semantics
- Propositions take in input (propositions) and give an output (truth or false)
- P and Q are the inputs (either true (=T or 1) or false (=F or 0)), which give the following
outputs for the different connectives
- Implication can be regarded as a promise:
o When the condition is true and the consequence is true, the promise is hold (thus
true)
o When the condition is true, the promise does not apply, thus any consequence holds
(thus always true)
o When the condition is true, but the consequence is false, the promise is not hold
(thus false)
- Bi-implication can be regarded as an equal sign
o If p and q have the same value (both 0/false or both 1/true), the output is true
o Otherwise: false
