EN: Logic and Set Theory (2IT60) is a course taught at Eindhoven University of Technology. It is a mandatory course for Bachelor Computer Science and Engineering students. It is given in the first quartile of the first year and forms the basis for the study.
Logic and Set Theory discusses boolean ...
Logic and Set Theory - Everything that I learned by heart
Flashcards28 Flashcards
$3.213 sales
Flashcards28 Flashcards
$3.213 sales
Some examples from this set of practice questions
1.
What is the definition of the subset A ⊆ B?
Answer: The definition of the subset A ⊆ B is ∀x[ x ∈ A: x ∈ B] or t ∈ A (=val) t ∈ B.
2.
What is the definition of A = B?
Answer: The definition of A = B is ∀x[ x ∈ A <=> x ∈ B] or t ∈ A (|=val) t ∈ B or A ⊆ ^ B ⊆ A.
3.
What is the definition of t ∈ A^c?
Answer: The definition of t ∈ A^c? is ¬ ( t ∈ A).
4.
What is the definition of the powerset C ∈ P(A)?
Answer: The definition of the powerset C ∈ P(A) is C ⊆ A.
5.
What is the definition of an image?
Answer: The definition of an image is x ∈ A\' (|=val) F(x) ∈ F(A\') and also y ∈ F(A\') (|=val) ∃x[ x ∈ A\': F(x) = y].
6.
What is the definition of a source?
Answer: The definition of a source is x ∈ F^(<-) (B\') (=val) F(x) ∈ B\'.
7.
What is the definition of a surjection?
Answer: The definition of a surjection is ∀y[ y ∈ B: ∃x[ x ∈ A\': F(x) = y]].
8.
What is the definition of a bijection?
Answer: The definition of a bijection is ∀y[ y ∈ B: ∃^(1)x[ x ∈ A\': F(x) = y]] (which is the same as a surjection but with ∃^(1)).
9.
What is the definition of an injection?
Answer: The definition of an injection is ∀x1,x2[ x1, x2 ∈ A: (F(x1) = F(x2)) => (x1 = x2)].
10.
What is the definition of strong induction?
Answer: The definition of strong induction is as follows:
∀n[ n ∈ N: A(n)]
{...}
∀k[ k ∈ N: ∀j[ j ∈ N ^ j < k: A(j)] => A(k)]
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller IsabelRutten. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.29. You're not tied to anything after your purchase.
