Summary
Summary - Logic and set theory (2IT60/2ITS60)
- Course
- Institution
A concise summary of the logic and set course 2IT60 provided at the TU/e.
[Show more]
Seller
Follow
NienkeUr
Reviews received
Content preview
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 𝑄.
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 NienkeUr. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.04. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52510 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now