Logic Flashcards
(114 cards)
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