Logic Flashcards
curly L stands for what?
The alphabet
What does the alphabet consist of in propositional calculus?
propositional variables p_0, p_1, . . . (p_i for each i ∈ N_0), negation ¬, implication
→, conjunction ∧, disjunction ∨, equivalence ↔ and parentheses (, ).
What group are the symbols ¬, ∧, ∨, ↔ part of?
They are logical connectives
What is a string of curly L?
a finite sequence of symbols from curly L
The length of a
string is
the number of symbols it contains.
A string of L is a formula of L if and only if
• it is a propositional variable (i.e. it consists of a single symbol, which
is a propositional variable),
• it is of the form ¬A, where A is a formula,
• it is of the form (A → B), (A ∧ B), (A ∨ B) or (A ↔ B), where A and
B are formulas.
The set of all formulas of L is denoted
Form(L).
State the Unique Readability Theorem
For each formula φ of L,
exactly one of the following holds. Either φ is a propositional variable p_i for
a unique i ∈ N_0, or it is ¬ψ for a unique formula ψ, or it is (ψ * χ) for
unique formulas ψ, χ and a unique binary connective *.
Prove the Unique Readability Theorem
Problem Sheet 1 (By induction on the length of φ)
A valuation is
a function v : {pi : i ∈ N0} → {T, F }, where
the values T, F are called true and false.
Given a valuation v, we can __ to a __ ̃v by…
Given a valuation v, we can extend it to a function ̃v :
Form(L) → {T, F } by letting ̃v(φ) = v(φ) is φ is a propositional variable,
and using the table below for the cases φ = ¬ψ and φ = (ψ * χ). This
extension is well-defined and unique by the Unique Readability Theorem.
Recount the table of valuations of the unary and binary connectives ¬ψ, ψ → χ, ψ ↔ χ, ψ ∧ χ, ψ ∨ χ
ψ χ ¬ψ ψ → χ ψ ↔ χ T T... F..... T ..........T T F... F..... F.......... F F T... T..... T ......... F F F... T..... T......... T ψ ∧ χ ψ ∨ χ .....T.......... T .....F......... T .....F......... T .....F......... F
A valuation v satisfies a formula φ if
̃v(φ) = T
A formula
that is satisfied by some valuation is called
satisfiable
A formula that is
satisfied by no valuation is called
a contradiction
A formula φ that is satisfied
by all valuations is called ___, written
a tautology, written as |= φ.
A formula φ is a logical consequence of ψ if _____, we write
or all valuations
v such that ̃v(ψ) = T we also have ̃v(φ) = T .
We write ψ |= φ.
Let Γ be a set of formulas and φ a formula. Then φ is a
logical consequence of Γ if ____, we write
or all valuations v such that ̃v(ψ) = T for all
ψ ∈ Γ, we also have ̃v(φ) = T.
We write Γ |= φ.
For any formulas φ and ψ, we have ψ |= φ iff
In fact, for any Γ ⊆ Form(L), Γ ∪ {ψ} |= φ iff
|= (ψ → φ)
Γ |= (ψ → φ)
Formulas ψ and φ are logically equivalent iff
We write
φ |= ψ and ψ |= φ, i.e. if
̃v(ψ) = ̃v(φ) for all valuations v
We write ψ |==| φ.
For any formulas α, β, γ we have (α ∧ (β ∧ γ)) |==|___ and (α ∧ β) |==|
Therefore, when we are only interested in formulas up to
(α ∧ (β ∧ γ)) |==| ((α ∧ β) ∧ γ) and (α ∧ β) |==| (β ∧ α).
Therefore, when we are only interested in formu-
las up to logical equivalence, we will often write ∧n
i=1 Ai (generic and between 1 and n of all Ai) instead of (A1 ∧ (A2 ∧ . . . (An−1 ∧ An) . . . )). Similarly with ∨. We will also sometimes drop
parentheses in formulas, provided that unique readability is preserved.
The following equivalences hold: ¬ (∨(n)(i=1) Ai) |==| ¬ (∧(n)(i=1) Ai) |==| (A → B) |==| (A ∨ B) |==| \_\_\_ |==| (A ∧ B) |==| (A ↔ B) |==|
¬ (∨(n)(i=1) Ai) |==| ∧(n)(i=1) ¬Ai ¬ (∧(n)(i=1) Ai) |==| ∨(n)(i=1) ¬Ai (A → B) |==| (¬A ∨ B) (A ∨ B) |==| (¬A → B) |==| ((A → B) → B) (A ∧ B) |==| ¬(A → ¬B) (A ↔ B) |==| ((A → B) ∧ (B → A))
Let Vn be the set of ___,
then an n-ary truth function is
Let Vn be the set of partial valuations
v′ : {p0, . . . , pn−1} → {T, F }. Then an n-ary truth function is a function
J : Vn → {T, F }.
Denote by Form_n(L) the ___
If φ ∈ Form_n(L), then φ
determines an ___ J_φ given by v |→ v(φ)
set of all formulas of L in which
only the first n propositional variables occur.
n-ary truth function
For any n ∈ N and any n-ary truth function J there exists
φ ∈ Formn(L) such that J_φ = J
Prove that for any n ∈ N and any n-ary truth function J there exists
φ ∈ Form_n(L) such that Jφ = J.
If J(v) = F for all v ∈ Vn, then φ = (p0 ∧ ¬p0) works.
Otherwise the set U = {v ∈ Vn | J(v) = T } is nonempty. For each v ∈ U
and i < n we can define ψᵛᵢ as pᵢ if v(pᵢ) = T and as ¬pᵢ if v(pᵢ) = F . Then
define ψᵛ = ∧(n−1)(i=0) ψᵛ
i , so that u(ψᵛ) = T if and only if u(pᵢ) = v(pᵢ) for all i,
which is when u = v. Finally if we put φ = ∨_(v∈U) ψᵛ, then u(φ) = T if and
only if u = v for some v ∈ U . By the definition of U , that is when J(u) = T .
Therefore Jφ(u) = u(φ) = J(u) for all u, i.e. Jφ = J.A formula which is a conjunction of pis and ¬pis is called
a conjunctive clause
A formula which is a disjunction of conjunctive clauses
is said to be
in disjunctive normal form (DNF)
Similarly, a conjunction of
disjunctive clauses is called
a conjunctive normal form (CNF)
What is the important thing about DNF and CNF?
any formula is equivalent to one in dis-
junctive normal form. It can also be shown (using the first two equivalences
in Proposition (1.11)) that any formula is equivalent to one in conjunctive
normal form.
Let S be a set of logical connectives on which the extension
of a valuation is given by a truth table, Then
L[S] denotes
the alphabet consisting of propositional variables, parentheses,
and the connectives in S. Similarly as for L = L[{¬, ∧, ∨, → ↔}] we define
formulas Form(L[S]), with proper parenthesising, so that unique readability
is preserved.A set S of logical connectives is adequate if
for any n ∈ N
and any n-ary truth function J there exists a formula φ ∈ Form_n(L[S]) such
that Jφ = J.
The set {¬, →} is
adequate
Prove the set {¬, →} is adequate.
the set {¬, →, ↔, ∧, ∨} is adequate, so for any
truth function J we can find a formula φ with Jφ = J. Using the logical
equivalences from Proposition (1.11), we can find a logically equivalent for-
mula ψ using only the connectives ¬ and →.
But if ψ |==| φ then Jψ = Jφ,
so we have found a formula ψ ∈ Form(L[{¬, →}]) such that Jψ = J.
Let L0 = L[{¬, →}]. The system L0 is defined as follows: As in what we can use to prove in L0
An axiom of L0 is any formula of L0 of the form
(α → (β → α)) (A1)
((α → (β → γ)) → ((α → β) → (α → γ))) (A2)
((¬β → ¬α) → (α → β)) (A3)
where α, β, γ ∈ Form(L0).
The only rule of inference in L0 will be the modus
ponens rule: from α and (α → β) we infer β.
Let Γ ⊆ Form(L0) and α ∈ Form(L0). We say α is deducible
from the hypoheses Γ if
There exists a finite sequence α1, . . . , αn of formulas
of L0 such that for each i, either
• αi is an axiom,
• αi ∈ Γ, or
• αi follows from αj and αk by modus ponens (MP) for some j, k < i,
and αn = α.
The sequence α1, . . . , αn where αn = α is called a
proof or a derivation of α.
If α is deducible from Γ, we write
Γ ⊢ α
If ∅ ⊢ α, we just write __
and call α a
If ∅ ⊢ α, we just write ⊢ α and call α a theorem (of L0).
Prove for any φ, ψ ∈ Form(L0), {φ, ¬φ} ⊢ ψ.
We give a full derivation of ψ: ¬φ → (¬ψ → ¬φ) (A1) ¬φ ∈ Γ (¬ψ → ¬φ) MP from 1,2 (¬ψ → ¬φ) → (φ → ψ) (A3) (φ → ψ) MP from 1,2 φ ∈ Γ ψ MP from 5,6.
For any α, β ∈ Form(L0), the following are theorems.
(α → α)
(¬α → (α → β))
(¬¬α → α) and (α → ¬¬α)
((¬α → α) → α)
State the Soundness Theorem for L0
The system L0 is sound, i.e. if
Γ ⊢ α, then Γ |= α.
Prove the Soundness Theorem for L0
Suppose that Γ ⊢ α and let α1, . . . , αn = α be a derivation of α in L0.
Let v be any valuation for which ̃v(ψ) = T for all ψ ∈ Γ. By induction, we
show that for each i ≤ n, ̃v(αi) = T . Then also ̃v(α) = T.
It is easy to check that all axioms are tautologies, so if αi is an axiom,
̃v(αi) = T . If αi ∈ Γ, then ̃v(αi) = T by the assumption on v. Finally, if
αi follows by modus ponens from some αj , αk with j, k < i, then WLOG we
can assume αk = (αj → αi). And since ̃v(αj ) = T and ̃v(αj → αi) = T by
the induction hypothesis, we also get ̃v(αi) = T .
State the Deduction Theorem for L0
For any Γ ⊆ Form(L0) and
α ∈ Form(L0), Γ ∪ {α} ⊢ β if and only if Γ ⊢ (α → β).
Prove the Deduction Theorem for L0
Suppose that Γ ∪ {α} ⊢ β and let β1, . . . , βn = β be a derivation of β
from Γ ∪ {α}. By induction on k we can prove that Γ ⊢ (α → βk).
Suppose that Γ ⊢ (α → βi) for all i < k. If βk is an axiom or is in Γ, we
can proceed as follows:
Γ ⊢ βk Axiom or ∈ Γ
Γ ⊢ (βk → (α → βk)) (A1)
Γ ⊢ (α → βk) MP from 1,2.
If βk = α, it is easy to show that Γ ⊢ (α → βk), since we know from
Proposition (2.5) that ⊢ (α → α). Finally if βk follows from βi and βj
by MP (in the derivation of β from Γ ∪ {α}), we can WLOG assume that
βj = (βi → βk), and then
Γ ⊢ (α → βi) IH
Γ ⊢ (α → βj ) = (α → (βi → βk)) IH
Γ ⊢ ((α → (βi → βk)) → ((α → βi) → (α → βk))) (A2)
Γ ⊢ (α → βk) MP used twice.
Therefore, in any case, (α → βk) is provable from Γ. By induction we get
that also Γ ⊢ (α → βn) = (α → β).
The converse is easy. If Γ ⊢ (α → β), then following the same derivation
we can prove Γ ∪ {α} ⊢ (α → β). But also Γ ∪ {α} ⊢ α, and by modus
ponens we get Γ ∪ {α} ⊢ β.
