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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper hildeeschx. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,49. Je zit daarna nergens aan vast.
