Summary - Logic and set theory (2IT60/2ITS60)

LOGIC AND SET THEORY
WEEK 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 𝑄.