Mathematics 1 (2DD40) Summary Q1
2021
Contents
Part I: Logic........................................................................................................................... 2
Part II: Sets ........................................................................................................................... 4
Part III: Linear algebra........................................................................................................... 6
Part IV: Series ....................................................................................................................... 9
Part V: Probability ............................................................................................................... 12
1
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
,Part I: Logic
There are different types of logic, we treat the main types proposition and predicate.
Proposition: statement which is either “true” or “false”
Basic statement: smallest unit that is true/false e.g. John sleeps
Composite statement: statements connected by and/or/not e.g. John sleeps and John does
not study. i.e. 𝑝: “John sleeps”. 𝑞: “John studies”. 𝑝 ∧ 𝑞: “John sleeps and John studies”
A proposition can have 2 truth values: False (also 0, F) and True (also 1, T).
Logical operators (also called connectives): ¬ not (negation), ∧ and (conjunction), ∨
inclusive or (disjunction), → implies (implication, from something false everything follows/the
truth follows from everything, (𝑝 → 𝑞) ↔ (¬𝑝 ∨ 𝑞) and (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝)), ↔ is
equivalent to (bi-implication, iff=if and only if, same as ← and → together). All are binary
except ¬ is unary. The priority of these signs is from first to last (¬ is strongest).
Truth table has left all possible values of the composing propositions and right the value of
the composite proposition, options increase exponentially with the number of propositions.
Tautology: (composite) statement that is true for all possible truth values of the variables
Equivalent: 2 statements are that if their truth columns in the truth table are equal
De Morgan: Negation of ∧ and ∨: ¬(𝑝 ∧ 𝑞) ↔ (¬𝑝 ∨ ¬𝑞) and ¬(𝑝 ∨ 𝑞) ↔ (¬𝑝 ∧ ¬𝑞).
Negation of →: ¬(𝑝 → 𝑞) ↔ (𝑝 ∧ ¬𝑞). Double negation cancels itself: ¬¬𝑝 ↔ 𝑝.
Every connective can be written with ∧, ∨ and ¬.
Fig. 1: Replacement rules Fig. 2: Step-by-step plan CNF and DNF
Every proposition can be written in Conjunctive Normal Form (CNF): of the form
(… ) ∧ … ∧ (… ) where between the brackets only ¬ and ∨ may appear.
Every proposition can be written in Disjunctive Normal Form (DNF): of the form
(… ) ∨ … ∨ (… ) where between the brackets only ¬ and ∧ may appear.
Incorrect reasonings: Do not make incorrect assumptions. An example does not suffice as
a proof. Correlation ≠ causation.
Paradox: 1 or more statements that lead to a contradiction.
2
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
, Predicate: quality / property, predicate logic is an extension of proposition logic with
variables (𝑥, 𝑦), predicates (descr. properties/relations), quantifiers, functions and constants.
Quantifiers: ∀ for all, universal quantifier; ∃ there exists, existential quantifier.
A quantifier binds a free variable, then it becomes a proposition, and is true or false.
Also: ∃! there exists exactly one.
Multiple quantifiers: e.g. ∀𝑥 ∃𝑦: 𝑦 < 𝑥 is true. Cannot interchange ∀ and ∃ without changing
the meaning of the statement, but multiple ∀’s or multiple ∃’s may be changed.
Negation of quantifiers:
∀𝑥: 𝜙(𝑥) where 𝜙(𝑥) is a certain property. Negation ¬(∀𝑥: 𝜙(𝑥)) means ∃𝑥: ¬𝜙(𝑥).
∃𝑥: 𝜙(𝑥) where 𝜙(𝑥) is a certain property. Negation ¬(∃𝑥: 𝜙(𝑥)) means ∀𝑥: ¬𝜙(𝑥).
To show that something does not hold for all x, 1 counterexample suffices. To show that
something is true, one needs a proof.
We can translate English sentences to the language of (predicate) logic like with 𝑀(𝑥, 𝑦): 𝑥 is
mother of 𝑦. E.g. ∀𝑦 ∃𝑥: 𝑀(𝑥, 𝑦) means everybody has a mother.
Quantifiers with extra condition: ∃𝑥 ∶ (𝑥 > 0) → ⋯ is the same as ∃𝑥 > 0 ∶ …
From something false everything follows.
Definition: agreement to give a certain name to something.
Theorem: (important) true statement/result
Corollary: theorem that (often quickly) follows from another.
Lemma: auxiliary theorem (preparation of more important result)
Proposition: theorem, but not very important
Conjecture: statement of which we suspect (but are not certain) that it is true
Defining a variable: : =, ≡
Hypothesis: statement that is preliminary assumed (assumption)
Proof techniques:
- Direct proof: based on the assumptions, results shown previously, etc.
- Counterexample: shows that statement cannot be proven / is false
- Proof with contraposition: instead of (𝐴) ⇒ (𝐵) we show ¬(𝐵) ⇒ ¬(𝐴)
- Proof of (𝐴) ↔ (𝐵) statement: show 2 parts: (𝐴) ⇒ (𝐵) and (𝐵) ⇒ (𝐴)
- Proof by contradiction: prove ¬(𝐴) by deriving a contradiction from (𝐴)
3
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
2021
Contents
Part I: Logic........................................................................................................................... 2
Part II: Sets ........................................................................................................................... 4
Part III: Linear algebra........................................................................................................... 6
Part IV: Series ....................................................................................................................... 9
Part V: Probability ............................................................................................................... 12
1
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
,Part I: Logic
There are different types of logic, we treat the main types proposition and predicate.
Proposition: statement which is either “true” or “false”
Basic statement: smallest unit that is true/false e.g. John sleeps
Composite statement: statements connected by and/or/not e.g. John sleeps and John does
not study. i.e. 𝑝: “John sleeps”. 𝑞: “John studies”. 𝑝 ∧ 𝑞: “John sleeps and John studies”
A proposition can have 2 truth values: False (also 0, F) and True (also 1, T).
Logical operators (also called connectives): ¬ not (negation), ∧ and (conjunction), ∨
inclusive or (disjunction), → implies (implication, from something false everything follows/the
truth follows from everything, (𝑝 → 𝑞) ↔ (¬𝑝 ∨ 𝑞) and (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝)), ↔ is
equivalent to (bi-implication, iff=if and only if, same as ← and → together). All are binary
except ¬ is unary. The priority of these signs is from first to last (¬ is strongest).
Truth table has left all possible values of the composing propositions and right the value of
the composite proposition, options increase exponentially with the number of propositions.
Tautology: (composite) statement that is true for all possible truth values of the variables
Equivalent: 2 statements are that if their truth columns in the truth table are equal
De Morgan: Negation of ∧ and ∨: ¬(𝑝 ∧ 𝑞) ↔ (¬𝑝 ∨ ¬𝑞) and ¬(𝑝 ∨ 𝑞) ↔ (¬𝑝 ∧ ¬𝑞).
Negation of →: ¬(𝑝 → 𝑞) ↔ (𝑝 ∧ ¬𝑞). Double negation cancels itself: ¬¬𝑝 ↔ 𝑝.
Every connective can be written with ∧, ∨ and ¬.
Fig. 1: Replacement rules Fig. 2: Step-by-step plan CNF and DNF
Every proposition can be written in Conjunctive Normal Form (CNF): of the form
(… ) ∧ … ∧ (… ) where between the brackets only ¬ and ∨ may appear.
Every proposition can be written in Disjunctive Normal Form (DNF): of the form
(… ) ∨ … ∨ (… ) where between the brackets only ¬ and ∧ may appear.
Incorrect reasonings: Do not make incorrect assumptions. An example does not suffice as
a proof. Correlation ≠ causation.
Paradox: 1 or more statements that lead to a contradiction.
2
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
, Predicate: quality / property, predicate logic is an extension of proposition logic with
variables (𝑥, 𝑦), predicates (descr. properties/relations), quantifiers, functions and constants.
Quantifiers: ∀ for all, universal quantifier; ∃ there exists, existential quantifier.
A quantifier binds a free variable, then it becomes a proposition, and is true or false.
Also: ∃! there exists exactly one.
Multiple quantifiers: e.g. ∀𝑥 ∃𝑦: 𝑦 < 𝑥 is true. Cannot interchange ∀ and ∃ without changing
the meaning of the statement, but multiple ∀’s or multiple ∃’s may be changed.
Negation of quantifiers:
∀𝑥: 𝜙(𝑥) where 𝜙(𝑥) is a certain property. Negation ¬(∀𝑥: 𝜙(𝑥)) means ∃𝑥: ¬𝜙(𝑥).
∃𝑥: 𝜙(𝑥) where 𝜙(𝑥) is a certain property. Negation ¬(∃𝑥: 𝜙(𝑥)) means ∀𝑥: ¬𝜙(𝑥).
To show that something does not hold for all x, 1 counterexample suffices. To show that
something is true, one needs a proof.
We can translate English sentences to the language of (predicate) logic like with 𝑀(𝑥, 𝑦): 𝑥 is
mother of 𝑦. E.g. ∀𝑦 ∃𝑥: 𝑀(𝑥, 𝑦) means everybody has a mother.
Quantifiers with extra condition: ∃𝑥 ∶ (𝑥 > 0) → ⋯ is the same as ∃𝑥 > 0 ∶ …
From something false everything follows.
Definition: agreement to give a certain name to something.
Theorem: (important) true statement/result
Corollary: theorem that (often quickly) follows from another.
Lemma: auxiliary theorem (preparation of more important result)
Proposition: theorem, but not very important
Conjecture: statement of which we suspect (but are not certain) that it is true
Defining a variable: : =, ≡
Hypothesis: statement that is preliminary assumed (assumption)
Proof techniques:
- Direct proof: based on the assumptions, results shown previously, etc.
- Counterexample: shows that statement cannot be proven / is false
- Proof with contraposition: instead of (𝐴) ⇒ (𝐵) we show ¬(𝐵) ⇒ ¬(𝐴)
- Proof of (𝐴) ↔ (𝐵) statement: show 2 parts: (𝐴) ⇒ (𝐵) and (𝐵) ⇒ (𝐴)
- Proof by contradiction: prove ¬(𝐴) by deriving a contradiction from (𝐴)
3
Mathematics 1 (2DD40) Summary Q1 2021 by Isabel Rutten
