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 ...
Summary Logic and Set Theory for P&T - All video lectures
Alles voor dit studieboek (3)
Geschreven voor
Technische Universiteit Eindhoven (TUE)
Computer Science and Engineering
Logic and Set Theory 2IT60 (2IT60)
Alle documenten voor dit vak (1)
3
beoordelingen
Door: scfcsv • 2 jaar geleden
Door: mikolajhilgert • 2 jaar geleden
Door: juliadobladez • 4 jaar geleden
Verkoper
Volgen
IsabelRutten
Ontvangen beoordelingen
Beschikbare oefenvragen
Logic and Set Theory - Everything that I learned by heart
Flashcards28 Flashcards
€2,993 verkocht
Flashcards28 Flashcards
€2,993 verkocht
Enkele voorbeelden uit deze set oefenvragen
1.
What is the definition of the subset A ⊆ B?
Antwoord: 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?
Antwoord: 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?
Antwoord: The definition of t ∈ A^c? is ¬ ( t ∈ A).
4.
What is the definition of the powerset C ∈ P(A)?
Antwoord: The definition of the powerset C ∈ P(A) is C ⊆ A.
5.
What is the definition of an image?
Antwoord: 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?
Antwoord: The definition of a source is x ∈ F^(<-) (B\') (=val) F(x) ∈ B\'.
7.
What is the definition of a surjection?
Antwoord: The definition of a surjection is ∀y[ y ∈ B: ∃x[ x ∈ A\': F(x) = y]].
8.
What is the definition of a bijection?
Antwoord: 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?
Antwoord: 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?
Antwoord: 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)]
Voorbeeld van de inhoud
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
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, Bancontact of creditcard 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 IsabelRutten. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,99. Je zit daarna nergens aan vast.
