logic notes Flashcards
¬
not, negation
not
¬
∧
And, conjunction
and
∧
conjunction
∧
negation
¬
∨
or, disjunction
or
∨
disjunction
∨
→
if … then, implication
if … then
→
implication
→
↔
if and only if, iff, equivalence
if and only if
↔
equivalence
↔
not premise p
_
p
_
p
not premise p
He has an Ace if he does not have a Knight or a Spade
¬(k ∨ s) → a
or
(¬k ∨ s) → a
exclusive disjunction
⊕
⊕
exclusive disjunction
define the Language of propositional logic
Let P be a set of proposition letters and let p ∈ P
ϕ ::= p | ¬ϕ | (ϕ ∧ ϕ) | (ϕ ∨ ϕ) | (ϕ → ϕ) | (ϕ ↔ ϕ)
syllogism
a logical argument where a quantified statement of a specific form (the conclusion) is inferred from two other quantified statements (the premises).
4 corners of Square of Opposition
All A are B
……..No A are B
Some A are B
……..Not all A are B
syllogistic Q N V
Q: quantifier
N: noun
V: verb
well known tautologies
Double Negation
De Morgan laws
Distribution laws
Double Negation
¬¬ϕ ↔ ϕ
De Morgan laws
¬(ϕ ∨ ψ) ↔ (¬ϕ ∧ ¬ψ)
¬(ϕ ∧ ψ) ↔ (¬ϕ ∨ ¬ψ)
Distribution laws
(ϕ ∧ (ψ ∨ χ)) ↔ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ))
ϕ ∨ (ψ ∧ χ)) ↔ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)
aristotals inference pattern as human language
Q=Quantifier
NP = noun phrase
CN = Common Noun
VP = verb phrase (Q + CN)
Q1 CN1 VP1
Q2 CN2 VP2
__________
Q3 CN3 VP3
syllogistic form
2 predicates and a conclusion
middle term
the missing class that is in the predicates but not the conclusion
For all A then B
For all B then C
____________
for all A then C
the middle term is B
∈
“is an element of” operation
member of operation
a is an element of a set A
a ∈ A
a ∈ A
a is an element of a set A
a is not an element of a set A
a ∉ A
a ∉ A
a is not an element of a set A
the set of those x that have the property described by ϕ.
{x | ϕ(x)}
the set of all those x in U for which ϕ holds
{x ∈ U | ϕ(x)}
a set of elements sharing multiple properties ϕ1, . . . , ϕn
{x | ϕ1(x), . . . , ϕn(x)}
(Bill Clinton, Hillary Clinton) ∈ A
, (Hillary Clinton,Bill Clinton) ∉ A
A = {(x, y) | x is in the list of presidents of the US , y is married to x}
A ∩ B
intersection
{x | x ∈ A and x ∈ B}
{x | x ∈ A and x ∈ B}
A ∩ B
intersection
intersection
A ∩ B
{x | x ∈ A and x ∈ B}
A ∪ B
union
{x | x ∈ A or x ∈ B}
{x | x ∈ A or x ∈ B}
union
A ∪ B
union
A ∪ B
{x | x ∈ A or x ∈ B}
A \ B (set)
difference
{x | x ∈ A and x ∉ B}
{x | x ∈ A and x ∉ B}
difference
A \ B
difference (set)
A \ B
{x | x ∈ A and x ∉ B}
complement (set)
_
A
{x ∈ U | x ∉ A}
{x ∈ U | x ∉ A}
complement
_
A
_
A
complement
{x ∈ U | x ∉ A}
_
A ∩ B
A \ B
_
_
A
A
de morgans law (in set operations)
______
A ∪ B = A ∩ B
______
A ∩ B = A ∪ B
distributive equations (in set operations)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
definition of a union of 2 sets (using negatives)
______
__ __
A ∪ B = A ∪ B = A ∩ B
number of predicate forms in a sylogism
3
venn diagram inference steps
1) draw skeleton
2) Universal step - cross out All and No
3) Existential step - ◦ in Some and Not all (where not removed by Universal step)
4) Check conclustion, if existential and universal are where they are meant to be then valid, otherwise a counter argument can exist
A syllogism with only universal premises and an existential conclusion is
always invalid, because ..
the situation with all classes empty is a counterexample
predicate logic is the most important system in logic because …
it is a universal language for talking about structure
a,b,c (predicate) are ..
constant / proper names
x,y,z (predicate) are …
variable / indefinite names
A,B,C (predicate) are …
predicate letters
1-place predicate
a predicate with 1 argument , e.g. intransitive verbs (walk) common nouns (boy)
2-place predicate
a predicate with 2 arguments - transitive verbs (see)
3-place predicate
a predicate with 3 arguments - distributive verbs (give(
unary predicates
1-place predicates
binary predicates
2-place predicates
ternary predicates
3-place predicates
sentence combination operators (predicate)
¬, ∧, ∨, →, ↔,∀x,∃x
∃x
Existential operator - “there exists an x”
“there exists an x”
∃x
Existential operator
∃x
∀x
universal operator - “for all x”
universal operator
∀x
“for all x”
∀x
natural language:John walks
W j
natural language:John is a boy
B j
natural language:He walks
W x
natural language:John sees Mary
S jm
natural language:John gives Mary the book
G jmb
an atomic statements …
express basic properties of one or more objects together
natural language: John sees her
Sjx
natural language: He sees her
Syx
natural language: This is less than that
x < y
natural language: He sees himself
Sxx
natural language: John does not see Mary
¬Sjm
natural language: Three is not less than two
¬3 < 2, or abbreviated: 3 ≮ 2.
natural language: John sees Mary or Paula
Sjm ∨ Sjp
natural language: Three is less than three or three is less than four
3 < 3 ∨ 3 < 4
natural language: x is odd (i.e., two does not divide x)
¬(2|x)
natural language: If John sees Mary, he is happy
Sjm → Hj
natural language: Someone walks
∃xW x
natural language: Some boy walks
∃x(Bx ∧ W x)
natural language: A boy walks
∃x(Bx ∧ W x)
natural language: John sees a girl
∃x(Gx ∧ Sjx)
natural language: A girl sees John
∃x(Gx ∧ Sxj)
natural language: A girl sees herself
∃x(Gx ∧ Sxx)
natural language: Everyone walks
∀xW x
natural language: Every boy walks
∀x(Bx → W x)
natural language: Every girl sees Mary
∀x(Gx → Sxm)
natural language: Everyone sees someone
∀x∃ySxy
natural language: Someone sees everyone
∃x∀ySxy
natural language: Everyone is seen by someone
∀x∃ySyx
natural language: Someone is seen by everyone
∃x∀ySyx
domain of discourse
quantifiers range over all objects in some given set of relevant objects
All A are B
∀x(Ax → Bx)
No A are B
¬∃x(Ax ∧ Bx)
Some A are B
∃x(Ax ∧ Bx)
Not all A are B
¬∀x(Ax → Bx)
translate in steps:
Every boy loves a girl.
1) All B are . . .:
∀x (Bx → ϕ(x))
2) “Some C are D”, where C represents the class of girls and D the class of those objects which are loved by x: ∃y (Gy ∧ Lxy)
3) substitute ϕ(x):
∀x (Bx → ∃y (Gy ∧ Lxy))
translate in steps:
No girl who loves a boy is not loved by some boy
1) “No A are B”:
¬∃x (ϕ(x) ∧ ψ(x))
- ϕ(x) who are girls who love some boy
- ψ(x) class of those x who are loved by no boy
2) x is a girl and x loves a boy:
(Gx ∧ ϕ1(x))
3) substitute with ϕ(x)
¬∃x ((Gx ∧ ϕ1(x)) ∧ ψ(x))
4) “x loves a boy:
∃y (By ∧ Lxy)
5) substitute
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ψ(x))
6) No boy loves x:
¬∃z (Bz ∧ Lzx)
7) substitute:
¬∃x ((Gx ∧ ∃y (By ∧ Lxy)) ∧ ¬∃z (Bz ∧ Lzx))
translate: “Someone can fool some people some of the time”
∃x(P x ∧ ∃y(P y ∧ ∃z(T z ∧ F xyz)))
translate: ”Someone cannot fool all people all of the time”
¬∃x(P x ∧ ∀y(P y → ∀z(T z → F xyz)))
monadic predicate logic
“unary properties”, with atomic statements involving one object only.
e.g: ∀x(Ax → Bx), ∀x(Bx → Cx) imply ∀x(Cx → Ax)
Not all A are B =
Some A are not B
All A are not B =
there are no A that are also B
There are no A that are also B =
All A are not B
Some A are not B =
Not all A are B
¬∀x(Ax → Bx) is equivalent to
∃x¬(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)
∃x¬(Ax → Bx) is equivalent to
¬∀x(Ax → Bx)
and
∃x(Ax ∧ ¬Bx)
∃x(Ax ∧ ¬Bx) is equivalent to
¬∀x(Ax → Bx)
and
∃x¬(Ax → Bx)
∀x(Ax → ¬Bx) is equivalent to
¬∃x¬(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)
¬∃x¬(Ax → ¬Bx) is equivalent to
∀x(Ax → ¬Bx)
and
¬∃x(Ax ∧ Bx)
¬∃x(Ax ∧ Bx) is equivalent to
¬∃x¬(Ax → ¬Bx)
and
∀x(Ax → ¬Bx)
¬∀xϕ is equivalent to
∃x¬ϕ,
¬∃xϕ is equivalent to
∀x¬ϕ
∀xϕ is equivalent to
¬∃x¬ϕ
∃xϕ is equivalent to
¬∀x¬ϕ
what is epistemic logic
logic of knowledge as based on information, including changes in knowledge which result from observations of facts, or communication between agents knowing different things
main sources of information
observation
inference
communication
functions V valuations
V (ϕ) = 1, means ϕ is true in V, V ⊨ ϕ
V (ϕ) = 0 means ϕ is false in V, V ⊭ϕ
Truth table: Logical True
p
T T
F T
Truth table: Logical False
p
T F
F F
Truth table: logical Identity
p
T T
F F
Truth table: negation
p ¬p
T F
F T
Truth table: Logical Conjunction
p q p ∧ q T T T T F F F T F F F F
Truth table: Logical Disjunction
p q p ∨ q T T T T F T F T T F F F
Truth table: Logical implication
p q p → q T T T T F F F T T F F T
Truth table: Logical Equality
p q p ↔ q T T T T F F F T F F F T
Truth table: Exclusive Disjunction
p q p ⊕ q T T F T F T F T T F F F
(p ∧ ¬q) ∨ (¬p ∧ q)
Truth table: Logical NAND
p q p ↑ q T T F T F T F T T F F T
¬(p ∧ q)
Truth table: Logical NOR
p q p ↓ q T T F T F F F T F F F T
¬(p ∨ q)
Build Truth table: for (¬ (p ∨ q) → r)
(¬ (p ∨ q) → r) · 0 0 0 · 0 · 0 0 0 · 1 · 0 1 1 · 0 · 0 1 1 · 1 · 1 1 0 · 0 · 1 1 0 · 1 · 1 1 1 · 0 · 1 1 1 · 1
(¬ (p ∨ q) → r) 1 0 0 0 · 0 1 0 0 0 · 1 0 0 1 1 · 0 0 0 1 1 · 1 0 1 1 0 · 0 0 1 1 0 · 1 0 1 1 1 · 0 0 1 1 1 · 1
(¬ (p ∨ q) → r) 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1
If p then q
p → q
p if q
q → p
p only if q
p → q
p if and only if q
p ↔ q
The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence
ϕ1, . . . , ϕk ⊨ ψ
ϕ1, . . . , ϕk ⊨ ψ
The inference from a finite set of premises ϕ1, . . . , ϕk to to a conclusion ψ is a valid consequence
if ϕ ⊨ ψ and ψ ⊨ ϕ
ϕ and ψ are logically equivalent.
ϕ and ψ are logically equivalent.
if ϕ ⊨ ψ and ψ ⊨ ϕ
Modus Tollens
(The simplest case of refutation) (the way that denies by denying) (denying the consequent) If P, then Q. Not Q. Therefore, not P. ϕ → ψ, ¬ψ ⊨ ¬ϕ
Truth table: Modus Tollens
ϕ ψ ϕ → ψ ¬ψ ¬ϕ 1 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1
Satisfiable
X (say, ϕ1, . . . , ϕk) is satisfiable if there is a valuation that makes all formulas in X true
Consistent
A set of formulas that does not lead to a contradiction is called a consistent formula set
ϕ |= ψ if and only if {ϕ, ¬ψ} is not consistent
inconsistent
there is no valuation where all formulas in the set are true simultaneously
Tautology
A formula ψ that gets the value 1 in every valuation
⊨ ψ
ϕ1, . . . , ϕk |= ψ if and only if (ϕ1 ∧ . . . ∧ ϕk) → ψ is a tautology
Logical Equivalences: Commutative
p ∧ q ⇐⇒ q ∧ p
p ∨ q ⇐⇒ q ∨ p
Logical Equivalences: Associative
(p ∧ q) ∧ r ⇐⇒ p ∧ (q ∧ r)
p ∨ q) ∨ r ⇐⇒ p ∨ (q ∨ r
Logical Equivalences: Distributive
p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r)
Logical Equivalences: Identity
p ∧ T ⇐⇒ p
p ∨ F ⇐⇒ p
Logical Equivalences: Negation
p ∨ ¬p ⇐⇒ T
p ∧ ¬p ⇐⇒ F
Logical Equivalences: Double Negative
¬(¬p) ⇐⇒ p
Logical Equivalences: Idempotent
p ∧ p ⇐⇒ p
p ∨ p ⇐⇒ p
Logical Equivalences: Universal Bound
p ∨ True ⇐⇒ True
p ∧ False ⇐⇒ False
Logical Equivalences: De Morgan’s
¬(p ∧ q) ⇐⇒ (¬p) ∨ (¬q)
¬(p ∨ q) ⇐⇒ (¬p) ∧ (¬q)
Logical Equivalences: Absorption
p ∨ (p ∧ q) ⇐⇒ p
p ∧ (p ∨ q) ⇐⇒ p
Logical Equivalences: Conditional
(p =⇒ q) ⇐⇒ (¬p ∨ q)
¬(p =⇒ q) ⇐⇒ (p ∧ ¬q)
Rules of Inference: Modus Ponens
p =⇒ q
If P, then Q.
P.
Therefore, Q.
Rules of Inference: Modus Tollens
p =⇒ q
If P, then Q.
Not Q.
Therefore, not P.
Rules of Inference: Elimination
p ∨ q
P or Q
Not Q
therefore P
Rules of Inference: Transitivity
p =⇒ q q =⇒ r if P then Q if Q then R therefore If P then R
Rules of Inference: Generalization
p =⇒ p ∨ q q =⇒ p ∨ q If P then P or Q therefore If Q then P or Q
Rules of Inference: Specialization
p ∧ q =⇒ p p ∧ q =⇒ q If P and Q then P therefore If P and Q then Q
Rules of Inference: Conjunction
P
Q
therefore P or Q
Rules of Inference: Contradiction Rule
¬p =⇒ False
If Not P then False
therefore P
A proof
A proof is a finite sequence of formulas, where each
formula is either an axiom, or follows from previous formulas in the proof by a deduction
rule.
theorem
A formula that occurs in a proof, typically as the last formula in the sequence
axiomatization
A set of axioms and rules defines an axiomatization for a given logic
axiomatization for propositional logic
(1) (ϕ → (ψ → ϕ))
(2) ((ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)))
(3) ((¬ϕ → ¬ψ) → (ψ → ϕ))
and modus ponens
if ϕ and (ϕ → ψ) are theorems, then ψ is also a theorem
sound
If all theorems of an axiomatic system
are valid, the system is sound
complete
if all valid formulas are provable theorems,the logic is called complete
MOD(ϕ)
The information content of a formula ϕ is the set MOD(ϕ) of its models,
that is, the valuations that assign the formula ϕ the truth-value 1.
The Sheffer stroke
nand (equivalent to the negation of the conjunction operation)
conjunctive normal form
Every propositional logical formula is equivalent to a conjunction of disjunctions of propositions or their negations
boolean tautalogies (in binary arithmatic for or)
x + (y + z) = (x + y) + z x + y = y + x x + x = x x + x = x x + 0 = 0 x + 1 = 1 x + −x = 1
boolean tautalogies (in binary arithmatic for and)
x · (y · z) = (x · y) · z x · y = y · x x · x = x x · 0 = 0 x · 1 = x x · −x = 0
boolean tautalogies (in binary arithmatic mixed and/or/not)
x + (y · z) = (x + y) · (x + z) x + (x · y) = x −(x + y) = −x · −y x · (y + z) = (x · y) + (x · z) x · (x + y) = x −(x · y) = −x + −y − − x = x
All A’s are B’s
(x)(Ax ⊃ Bx)
No A’s are B’s
(x)(Ax ⊃ ¬Bx)
Some A’s are B’s
(∃x)(Ax ⋀ Bx)
Some A’s are not B’s
(∃x)(Ax ⋀ ¬Bx)
All and only A’s are B’s
(∃x)(Ax ↔ Bx)
Only A’s are B’s
(x)(Bx ⊃ Ax)
Not all A’s are B’s
(∃x)(Ax ⋀ ¬Bx)
All A’s are not B’s
(x)(Ax ⊃ ¬Bx)
what is Rˇ
Rˇ is the relational converse of Rˇ
Rˇ = {(y, x) ∈ S^2 | (x, y) ∈ R}.
