Logic and Set Theory (2IT60) Summary Q1 2020
Chapter 1 What is logic?
Logic deals with general reasoning laws, which you can trust. Logical laws are given in the form of formulas
with parameters. When in one such law, you replace the parameters with something concrete, you get a
good trustworthy reasoning.
Chapter 2 Abstract propositions
A proposition is a grammatically correct sentence which (at this moment, at this place, etc.) is either true
or false. Propositions which are not built from other propositions are called simple propositions. Those built
from other propositions are called complex propositions.
Some connectives (symbols to replace words): ∧ This is the symbol for the word ‘and’
∨ The symbol for the word ‘or’. ¬ Represents the word ‘not’.
⇒ For ‘if ... then’ or ‘implies’. ⇔ For ‘if and only if’
We can also give these formulas graphically in the form of a so-
called tree. In Figure 2.1, we give the tree of ((a ∧ b) ⇒ (¬c)). Such a
tree has nodes (the black buttons), branches (the connecting lines)
and labels (the symbols at the nodes, like b, ¬ and ⇒). The nodes at
the end of the tree (in this case: the nodes with labels a, b and c) are
called leaves. At the node at the top of the tree, the so-called root,
there is a label which is called the main symbol of the formula, in this
case ⇒. Characteristic for a tree is that it has a root, that all nodes are connected to each
other and that there are no loops.
We also have a priority scheme to cut down on parentheses. The top has the highest priority.
Chapter 3 Truth tables
The truth tables of all the connectives are as follows:
And Inclusive or Not If 𝑷, then 𝑸 (imply) Bi-implication if and only if
𝑷 𝑸 𝑷 ∧ 𝑸 𝑷 ∨ 𝑸 ¬𝑷 𝑷 ⇒ 𝑸 𝑷 ⇔ 𝑸
0 0 0 0 1 1 1
0 1 0 1 1 1 0
1 0 0 1 0 0 0
1 1 1 1 0 1 1
Chapter 4 The Boolean behaviour of propositions
To each truth-table, one can associate a function, which
expresses how the final result depends on the choice at the
beginning. Such a function is called a truth-function or a
Boolean function. See an example on the right (with its
corresponding truth table).
The collection of all triples (𝑎, 𝑏, 𝑐) (a triple is a sequence of length 3) with 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 and 𝑐 ∈ 𝐶, is
called the Cartesian product 𝐴 × 𝐵 × 𝐶.
Different abstract propositions that give the same truth-function are equivalent.
All abstract propositions that have a truth-function which always returns 1, are called tautologies. True is a
special abstract proposition without any proposition variables and which always returns the value 1, aka a
tautology. Abstract propositions which always return the truth-value 0, are called contradictions. False is
another special abstract proposition without any proposition variables and which always returns the value 0,
aka a contradiction. Contingent propositions are abstract propositions that have at least one 1 and at
least one 0 in their truth table.
1
Logic and Set Theory (2IT60) Summary Q1 2019 by Isabel Rutten
, Logic and Set Theory (2IT60) Summary Q1 2020
Chapter 5 Standard equivalences
The symbol is used to express the
concept ‘has the same truth-value as’ or ‘is
equivalent to’. Commutativity means to
exchange, associativity means to relate.
‘⇒’ can also be used a conclusion, not an implication (P, thus Q). ‘⇔’ can similarly be used as an
alternative for .
We also have a lot of other rules, concerning idempotence, double negation, True and False, distributivity,
De Morgan, ‘⇒’ and ‘⇔’:
aka
Chapter 6 Working with equivalent propositions
The meta-symbol is reflexive, symmetric and transitive. The symbol ‘≡’ is usually reserved for ‘being
identical to’. Similarly, means ‘being not identical to’.
Chapter 7 Strengthening and weakening of propositions
Whenever in the column of 𝑃 there is a 1 and there is also a 1 in the column of 𝑄, we say that 𝑃 is stronger
than 𝑄. So, one can find more zeros in the column of the stronger than the column of the weaker. We
express that ‘𝑃 is stronger than 𝑄’ with 𝑃 𝑄, and ‘𝑄 is weaker than 𝑃’ with 𝑄 𝑃. False is the strongest
proposition and True is the weakest propositions.
See other standard weakenings on the right:
‘Stronger’ and ‘weaker’ are reflexive and transative.
Chapter 8 Predicates and quantifiers
The letters 𝑎, 𝑏, etc. served as proposition variables, which we use as basic building blocks for abstract
propositions. The letters 𝑃, 𝑄 etc. are meta-variables, not intended to cover real propositions, but whole
abstract propositions. A predicate is a function which depends on the values used for the object variables,
and which after saturation (i.e., replacement of all the occurrences of object variables by values) leads to a
real proposition (e.g. 3𝑚 + 𝑛 > 3). Choosing a domain is important and you can draw a graph to show
where the predicate is True and where it is False.
The universal quantifier (∀, all) means “for every 𝑥 it holds that…”. The
existential quantifier (∃, exists) mean “there is an 𝑥 such that it holds that…”.
Thus: The proposition ∃𝑥 [𝑥 ∈ 𝐷 ∶ 𝐴(𝑥)] is true if 𝐴(𝑑) is true for at least one
concrete 𝑑 in 𝐷. If no such 𝑑 can be found in 𝐷, then it is false. There also
exists many-place predicates that work with more than one variable, e.g.
∀𝑚 [𝑚 ∈ 𝑅: ∀𝑛 [𝑛 ∈ 𝑁: 3𝑚 + 𝑛 > 3]]. Tree example: see 8.3.
2
Logic and Set Theory (2IT60) Summary Q1 2019 by Isabel Rutten
Chapter 1 What is logic?
Logic deals with general reasoning laws, which you can trust. Logical laws are given in the form of formulas
with parameters. When in one such law, you replace the parameters with something concrete, you get a
good trustworthy reasoning.
Chapter 2 Abstract propositions
A proposition is a grammatically correct sentence which (at this moment, at this place, etc.) is either true
or false. Propositions which are not built from other propositions are called simple propositions. Those built
from other propositions are called complex propositions.
Some connectives (symbols to replace words): ∧ This is the symbol for the word ‘and’
∨ The symbol for the word ‘or’. ¬ Represents the word ‘not’.
⇒ For ‘if ... then’ or ‘implies’. ⇔ For ‘if and only if’
We can also give these formulas graphically in the form of a so-
called tree. In Figure 2.1, we give the tree of ((a ∧ b) ⇒ (¬c)). Such a
tree has nodes (the black buttons), branches (the connecting lines)
and labels (the symbols at the nodes, like b, ¬ and ⇒). The nodes at
the end of the tree (in this case: the nodes with labels a, b and c) are
called leaves. At the node at the top of the tree, the so-called root,
there is a label which is called the main symbol of the formula, in this
case ⇒. Characteristic for a tree is that it has a root, that all nodes are connected to each
other and that there are no loops.
We also have a priority scheme to cut down on parentheses. The top has the highest priority.
Chapter 3 Truth tables
The truth tables of all the connectives are as follows:
And Inclusive or Not If 𝑷, then 𝑸 (imply) Bi-implication if and only if
𝑷 𝑸 𝑷 ∧ 𝑸 𝑷 ∨ 𝑸 ¬𝑷 𝑷 ⇒ 𝑸 𝑷 ⇔ 𝑸
0 0 0 0 1 1 1
0 1 0 1 1 1 0
1 0 0 1 0 0 0
1 1 1 1 0 1 1
Chapter 4 The Boolean behaviour of propositions
To each truth-table, one can associate a function, which
expresses how the final result depends on the choice at the
beginning. Such a function is called a truth-function or a
Boolean function. See an example on the right (with its
corresponding truth table).
The collection of all triples (𝑎, 𝑏, 𝑐) (a triple is a sequence of length 3) with 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 and 𝑐 ∈ 𝐶, is
called the Cartesian product 𝐴 × 𝐵 × 𝐶.
Different abstract propositions that give the same truth-function are equivalent.
All abstract propositions that have a truth-function which always returns 1, are called tautologies. True is a
special abstract proposition without any proposition variables and which always returns the value 1, aka a
tautology. Abstract propositions which always return the truth-value 0, are called contradictions. False is
another special abstract proposition without any proposition variables and which always returns the value 0,
aka a contradiction. Contingent propositions are abstract propositions that have at least one 1 and at
least one 0 in their truth table.
1
Logic and Set Theory (2IT60) Summary Q1 2019 by Isabel Rutten
, Logic and Set Theory (2IT60) Summary Q1 2020
Chapter 5 Standard equivalences
The symbol is used to express the
concept ‘has the same truth-value as’ or ‘is
equivalent to’. Commutativity means to
exchange, associativity means to relate.
‘⇒’ can also be used a conclusion, not an implication (P, thus Q). ‘⇔’ can similarly be used as an
alternative for .
We also have a lot of other rules, concerning idempotence, double negation, True and False, distributivity,
De Morgan, ‘⇒’ and ‘⇔’:
aka
Chapter 6 Working with equivalent propositions
The meta-symbol is reflexive, symmetric and transitive. The symbol ‘≡’ is usually reserved for ‘being
identical to’. Similarly, means ‘being not identical to’.
Chapter 7 Strengthening and weakening of propositions
Whenever in the column of 𝑃 there is a 1 and there is also a 1 in the column of 𝑄, we say that 𝑃 is stronger
than 𝑄. So, one can find more zeros in the column of the stronger than the column of the weaker. We
express that ‘𝑃 is stronger than 𝑄’ with 𝑃 𝑄, and ‘𝑄 is weaker than 𝑃’ with 𝑄 𝑃. False is the strongest
proposition and True is the weakest propositions.
See other standard weakenings on the right:
‘Stronger’ and ‘weaker’ are reflexive and transative.
Chapter 8 Predicates and quantifiers
The letters 𝑎, 𝑏, etc. served as proposition variables, which we use as basic building blocks for abstract
propositions. The letters 𝑃, 𝑄 etc. are meta-variables, not intended to cover real propositions, but whole
abstract propositions. A predicate is a function which depends on the values used for the object variables,
and which after saturation (i.e., replacement of all the occurrences of object variables by values) leads to a
real proposition (e.g. 3𝑚 + 𝑛 > 3). Choosing a domain is important and you can draw a graph to show
where the predicate is True and where it is False.
The universal quantifier (∀, all) means “for every 𝑥 it holds that…”. The
existential quantifier (∃, exists) mean “there is an 𝑥 such that it holds that…”.
Thus: The proposition ∃𝑥 [𝑥 ∈ 𝐷 ∶ 𝐴(𝑥)] is true if 𝐴(𝑑) is true for at least one
concrete 𝑑 in 𝐷. If no such 𝑑 can be found in 𝐷, then it is false. There also
exists many-place predicates that work with more than one variable, e.g.
∀𝑚 [𝑚 ∈ 𝑅: ∀𝑛 [𝑛 ∈ 𝑁: 3𝑚 + 𝑛 > 3]]. Tree example: see 8.3.
2
Logic and Set Theory (2IT60) Summary Q1 2019 by Isabel Rutten
