Samenvatting
Summary - Logic and set theory (2IT60/2ITS60)
- Vak
- 2IT60 (2IT60)
- Instelling
- Technische Universiteit Eindhoven (TUE)
A concise summary of the logic and set course 2IT60 provided at the TU/e.
[Meer zien]Voorbeeld 2 van de 8 pagina's
Voorbeeld 2 van de 8 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
LOGIC AND SET THEORYWEEK 1 𝑃 ∧ 𝑄 =𝑣𝑎𝑙 𝑄 ∧ 𝑃
Commutativity 𝑃 ∨ 𝑄 =𝑣𝑎𝑙 𝑄 ∨ 𝑃
PROPOSITIONAL LOGIC 𝑃 ⇔ 𝑄 =𝑣𝑎𝑙 𝑄 ⇔ 𝑃
Proposition A statement that is true (1) or false (0) (𝑃 ∧ 𝑄) ∧ 𝑅 =𝑣𝑎𝑙 𝑄 ∧ (𝑃 ∧ 𝑅)
This may involve mathematical expressions Associativity (𝑃 ∨ 𝑄) ∨ 𝑅 =𝑣𝑎𝑙 𝑄 ∨ (𝑃 ∨ 𝑅)
Tautology A proposition that always evaluates to True (𝑃 ⇔ 𝑄) ⇔ 𝑅 =𝑣𝑎𝑙 𝑄 ⇔ (𝑃 ⇔ 𝑅)
Contradiction A proposition that always evaluates to False
𝑃 ∧ (𝑄 ∨ 𝑅) =𝑣𝑎𝑙 (𝑃 ∧ 𝑄) ∨ (𝑃 ∧ 𝑅)
Contingency A proposition that is neither a tautology nor a Distributivity
contradiction 𝑃 ∨ (𝑄 ∧ 𝑅) =𝑣𝑎𝑙 (𝑃 ∨ 𝑄) ∧ (𝑃 ∨ 𝑅)
Connectives ∧ (conjugation/and) ¬ (not)
∨ (disjunction/or) ⇒ (implication)
⇔ (bi-implication) LOGICAL CONSEQUENCE
Proposition variables a, b, c 𝑃 is a logical consequence of 𝑄 if for every assignment,
(lower case, beginning of alphabet) if 𝑃 evaluates to true, then 𝑄 evaluates to true.
𝑃 ⊨𝑣𝑎𝑙 𝑄 → {𝑊ℎ𝑒𝑛 𝑃 = 1, 𝑡ℎ𝑒𝑛 𝑄 = 1
Syntax of abstract propositions
If 𝑃 ⊨𝑣𝑎𝑙 𝑄 or 𝑄 ⊨𝑣𝑎𝑙 𝑃 , P and Q are comparable
1. Every proposition variable is an abstract proposition
2. If 𝑃 is an abstract proposition, then so is (1)(¬𝑃) ∧ − ∨ −weakening
If 𝑃 and 𝑄 are abstract propositions, then so are 𝑃 ∧ 𝑄 ⊨𝑣𝑎𝑙 𝑃
(2)(𝑃 ∧ 𝑄), (3)(𝑃 ∨ 𝑄), (4)(𝑃 ⇒ 𝑄), and (5)(𝑃 ⇔ 𝑄) 𝑃 ⊨𝑣𝑎𝑙 𝑃 ∨ 𝑄
3. True and False are abstract propositions
Where True is a tautology and False is a contradiction Weakening rules - Extremes
𝐹𝑎𝑙𝑠𝑒 ⊨𝑣𝑎𝑙 𝑃
Precedence scheme: 𝑃 ⊨𝑣𝑎𝑙 𝑇𝑟𝑢𝑒
¬ > ∨,∧ > ⇒ > ⇔
The grass is green and not all trees are green → 𝒂 ∧ ¬𝒃
TRUTH TABLES
Truth tables are used to determine whether a proposition is
True (1) or False (0).
𝑷 𝑸 ¬𝑷 𝑷∧𝑸 𝑷∨𝑸 𝑷⇒𝑸 𝑷⇔𝑸
0 0 1 0 0 1 1
0 1 1 0 1 1 0
1 0 0 0 1 0 0
1 1 0 1 1 1 1
When determining whether a proposition is true or false,
you work inside out:
((𝑎 ∧ (¬𝑏)) ⇒ 𝑏) → first compute ¬𝑏, then 𝑎 ∧ ¬𝑏, and so on
They can be used to prove that a proposition is a
contingency. Alternatively, it is also sufficient to:
• Find 1 assignment that evaluates the proposition to
false (it’s not a tautology)
• Find 1 assignment that evaluates the proposition to
true (it’s not a contradiction)
EQUIVALENCY
𝑃 and 𝑄 are Logically equivalent if for every assignment,
𝑃 evaluates to true if, and only if, 𝑄 evaluates to true.
𝑊ℎ𝑒𝑛 𝑃 = 1, 𝑡ℎ𝑒𝑛 𝑄 = 1
𝑃 =𝑣𝑎𝑙 𝑄 → {
𝑊ℎ𝑒𝑛 𝑄 = 1, 𝑡ℎ𝑒𝑛 𝑃 = 1
, PREDICATE LOGIC
A predicate takes a fixed number of fixed types as input and
produces a truth value as output
Unary predicate takes 1 thing of a certain type and
produces a truth value as output.
Binary predicate takes 2 things of certain types as input
and produces a truth value as output.
…
Nullary predicates take 0 inputs, these are propositions.
QUANTIFICATION OF UNARY PREDICATES
∀𝑥[ 𝑃(𝑥), 𝑄(𝑥) ] For all 𝑥 satisfying 𝑃(𝑥), such that 𝑄(𝑥)
holds as well (universal quantification)
∃𝑥[ 𝑃(𝑥), 𝑄(𝑥) ] There exists a 𝑥 satisfying 𝑃(𝑥), such that
𝑄(𝑥) holds (existential quantification)
𝑷(𝒙) is considered the domain.
If there are no candidates to
∃𝒙[𝑭𝒂𝒍𝒔𝒆: 𝑷] =𝒗𝒂𝒍 𝑭𝒂𝒍𝒔𝒆
satisfy 𝑃
There are no candidates that
∀𝒙[𝑭𝒂𝒍𝒔𝒆: 𝑷] =𝒗𝒂𝒍 𝑻𝒓𝒖𝒆
can refute predicate P
Weakening the domain
∃𝑥 [𝑃 ∧ 𝑄: 𝑅] =𝑣𝑎𝑙 ∃𝑥 [𝑃: 𝑄 ∧ 𝑅]
∀𝑥 [𝑃 ∧ 𝑄: 𝑅] =𝑣𝑎𝑙 ∀𝑥 [𝑃: 𝑄 ⇒ 𝑅]
PREDICATES OF HIGHER ARITY
It is possible to combine multiple predicates:
∀𝑥 [𝑃(𝑥): ∃𝑦 [𝑄(𝑦): 𝑅(𝑥, 𝑦)]]
If 𝒚 does not occur in 𝑷 and the quantifiers are the same:
∀𝑥 [𝑃: ∀𝑦 [𝑄: 𝑅]] → ∀𝑥 [𝑃 ∧ 𝑄: 𝑅]
∃𝑥 [𝑃: ∃𝑦 [𝑄: 𝑅]] → ∃𝑥 [𝑃 ∧ 𝑄: 𝑅]
BINDING
This works the same for both universal and existential
quantifiers
∀𝑥 [𝑃(𝑥): 𝑄(𝑥)]
∀𝑥 is the binder, 𝑃(𝑥): 𝑄(𝑥) is the scope:
∀𝒙 binds 𝒙 in its scope
A variable 𝑥 is bound if it is within the scope of a ∀𝑥 or ∃𝑥 .
Otherwise the occurrence of the variable is free.
The variable name (𝑥) can be changed to any other letter, so
long as every instance of the variable is renamed and that
the new letter does not occur at all in 𝑃 or 𝑄.
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 NienkeUr. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,69. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen