Basic Logic, Lecture 2
Luca Incurvati
[Link]@[Link]
Luca Incurvati ([Link]@[Link]) Basic Logic 2 1 / 24
Outline
1 Language of PL
2 Deductive system of PL
3 Semantics of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 2 2 / 24
Language of PL
Vocabulary
1 Atomic sentences: P, Q, R, . . . (denumerably infinitely many;
sometimes indexed by natural numbers, e.g. P1 or Q2 ).
2 Sentential connectives: ¬, ∨, ∧, →.
3 Auxiliary symbols: (, )
Luca Incurvati ([Link]@[Link]) Basic Logic 2 3 / 24
Language of PL
Grammar
Any string of symbols of LPL is an expression of LPL .
Some expressions of LPL are gibberish.
We want to know when an expression of LPL constitute a sentence,
that is when it is well-formed.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 4 / 24
Language of PL
Grammar
Definition (Sentence of LPL )
(i) Every atomic sentence is a sentence of LPL .
(ii) If ϕ is a sentence of LPL , then so is ¬ϕ.
(iii) If ϕ and ψ are sentences of LPL , then so are (ϕ ∨ ψ), (ϕ ∧ ψ),
(ϕ → ψ).
(iv) Nothing else is a sentence of LPL .
Luca Incurvati ([Link]@[Link]) Basic Logic 2 5 / 24
Language of PL
Recursive definitions
Example of a recursive definition. Specifies:
1 some elements to which the definiendum applies (base clause);
2 then ways to generate elements to which the definiendum applies
from elements to which the definiendum applies (recursive clause or
clauses);
3 then that the definiendum does not apply to any other thing
(extremal or end clause).
Luca Incurvati ([Link]@[Link]) Basic Logic 2 6 / 24
Deductive system of PL
1 Language of PL
2 Deductive system of PL
3 Semantics of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 2 7 / 24
Deductive system of PL
Natural deduction
We assume you are familiar with a standard natural deduction system
for propositional logic, like the one given in the van Dalen book.
We will briefly remind you of the key ingredients of that system here.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 8 / 24
Deductive system of PL
Natural deduction
We assume you are familiar with a standard natural deduction system
for propositional logic, like the one given in the van Dalen book.
We will briefly remind you of the key ingredients of that system here.
N.B. van Dalen uses ⊥ as a primitive symbol of the language. We
take it instead to be an abbreviation for some canonical contradiction,
like P ∧ ¬P.
Moreover, we take all the rules for the connectives which belong to
the primitive vocabulary of our language to be primitive rules, whilst
in the van Dalen book some of them are derived rules.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 8 / 24
Deductive system of PL
Rules for conjunction
We have one introduction rule and two elimination rules:
ϕ ψ ϕ∧ψ ϕ∧ψ
∧I ϕ ∧E ∧E
ϕ∧ψ ψ
Luca Incurvati ([Link]@[Link]) Basic Logic 2 9 / 24
Deductive system of PL
A few things to note
We use a presentation in tree form; some presentations of natural
deduction use a different form (e.g. Fitch-style presentations).
We label each step by indicating the rule that has been applied.
We have the premises of the argument at the top of the tree and the
conclusion as the root.
Thus, the presentation is naturally thought as top-down, but the
discovery of the proof might well proceed in a bottom-up way.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 10 / 24
Deductive system of PL
Rules for the conditional
We have one introduction rule and one elimination rule:
[ϕ]
.. ϕ ϕ→ψ
. →E
ψ ψ
→I
ϕ→ψ
Note: a hypothesis or assumption between square brackets is cancelled
or discharged, which means it no longer counts as a hypothesis.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 11 / 24
Deductive system of PL
Discharge policies
Example
Use the rules of natural deduction to provide a derivation of
A → (B → A).
Luca Incurvati ([Link]@[Link]) Basic Logic 2 12 / 24
Deductive system of PL
Discharge policies
Example
Use the rules of natural deduction to provide a derivation of
A → (B → A).
[A]1
→I
B→A → I1
A → (B → A)
We have here a case of vacuous discharge.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 12 / 24
Deductive system of PL
Discharge policies
Example
Use the rules of natural deduction to provide a derivation of
(A → (A → B)) → (A → B).
Luca Incurvati ([Link]@[Link]) Basic Logic 2 13 / 24
Deductive system of PL
Discharge policies
Example
Use the rules of natural deduction to provide a derivation of
(A → (A → B)) → (A → B).
[A → (A → B)]2 [A]1
→E
A→B [A]1
→E
B → I1
A→B → I2
(A → (A → B)) → (A → B)
We have here a case of multiple discharge.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 13 / 24
Deductive system of PL
Rules for falsum
We have the following rules concerning falsum and negation:
[¬ϕ]
⊥ ..
.
ϕ ⊥
⊥
ϕ RAA
Luca Incurvati ([Link]@[Link]) Basic Logic 2 14 / 24
Deductive system of PL
Rules for negation
We have one introduction rule and one elimination rule:
[ϕ]
.. ϕ ¬ϕ
. ¬E
⊥
⊥
¬ϕ ¬I
Luca Incurvati ([Link]@[Link]) Basic Logic 2 15 / 24
Deductive system of PL
Rules for disjunction
We have two introduction rules and one elimination rule:
ϕ ψ
∨I ∨I
ϕ∨ψ ϕ∨ψ
[ϕ] [ψ]
.. ..
. .
ϕ∨ψ σ σ
σ ∨E
Luca Incurvati ([Link]@[Link]) Basic Logic 2 16 / 24
Deductive system of PL
Rules for the biconditional
These are derived rules. We have one introduction rule and two
elimination rules:
[ϕ] [ψ]
.. .. ϕ ϕ↔ψ ψ ϕ↔ψ
. . ↔E
ϕ ↔E
ψ ϕ ψ
↔I
ϕ↔ψ
These are justified by the (obvious) facts that: (i) ϕ ↔ ψ, ϕ ` ψ and
ϕ ↔ ψ, ψ ` ϕ; (ii) if Γ, ϕ ` ψ and Γ, ϕ ` ϕ, then Γ ` ϕ ↔ ψ.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 17 / 24
Deductive system of PL
Example
Example
Show that (A ∨ B) ` ¬(¬A ∧ ¬B).
Luca Incurvati ([Link]@[Link]) Basic Logic 2 18 / 24
Deductive system of PL
Example
Example
Show that (A ∨ B) ` ¬(¬A ∧ ¬B).
[¬A ∧ ¬B]1 [¬A ∧ ¬B]2
∧E ∧E
[A]3 ¬A [B]3 ¬B
¬E ¬E
⊥ ¬I1 ⊥ ¬I2
A∨B ¬(¬A ∧ ¬B) ¬(¬A ∧ ¬B)
∨E3
¬(¬A ∧ ¬B)
Luca Incurvati ([Link]@[Link]) Basic Logic 2 18 / 24
Deductive system of PL
Using proof strategies to find the proof
We want to prove ¬(¬A ∧ ¬B) and we have as our premise A ∨ B.
Let’s try to use our premise.
That is, let us see whether we can derive ¬(¬A ∧ ¬B) from the
supposition that A and from the supposition that B. If we do so,
then, by ∨E , we will have established the goal.
First case: ¬(¬A ∧ ¬B) is naturally obtained by deriving ⊥ from the
supposition that ¬A ∧ ¬B. So we add this to our suppositions and try
to prove ⊥.
But now we have A and ¬A ∧ ¬B, and it is easy to see that this will
give rise to a contradiction by applying ∧E to the second supposition
and then ¬E . The second case is similar.
Putting all these things together, we get our proof.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 19 / 24
Deductive system of PL
Example
Example
Show that A ∧ (B ∨ C ), A → ¬C ` B ∨ E .
Luca Incurvati ([Link]@[Link]) Basic Logic 2 20 / 24
Deductive system of PL
Example
Example
Show that A ∧ (B ∨ C ), A → ¬C ` B ∨ E .
A ∧ (B ∨ C )
∧E
A A → ¬C
→E
¬C [C ]1
A ∧ (B ∨ C ) ¬E [B]1
⊥
∧E ⊥ ∨I
B ∨C B ∨E B ∨E
∨E1
B ∨E
Luca Incurvati ([Link]@[Link]) Basic Logic 2 20 / 24
Deductive system of PL
Using proof strategies to find the proof
We want to prove B ∨ E . It’s not clear how to get the conclusion by
∨I . So let’s look at our premises.
We have a statement with ∧ as the main operator: let’s use this. We
then get A and B ∨ C .
Having obtained A, we know we can use our other premise to get ¬C .
How could we get to the conclusion?
Well, having B ∨ C tells us that getting the conclusion from the
supposition that B and the supposition that C would do the trick.
But getting B ∨ E from the supposition that B is obvious (∨I ), and
having established ¬C , we can get B ∨ E from the supposition that C
using ex falso quodlibet.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 21 / 24
Semantics of PL
1 Language of PL
2 Deductive system of PL
3 Semantics of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 2 22 / 24
Semantics of PL
Truth-tables!
We assume you are familiar with the semantics for propositional logic
(through the truth-tables).
Brief remainder to introduce our terminology. We first define:
Definition (Interpretation of PL)
An interpretation I of PL is a function which assigns to each atomic
sentence one of the truth-values True or False.
This is usually known as a valuation.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 23 / 24
Semantics of PL
The notion of satisfiability
We then specify how the assignment of truth-values to atomic
sentences determines the truth-values of more complex ones.
Typically, this information is conveyed via the truth-tables for the
connectives. Here we say:
Definition (Truth in an interpretation of PL)
1 If ϕ is an atomic sentence then ϕ is true in I iff I assigns to ϕ the
truth-value True.
2 If ϕ is ¬ψ, then ϕ is true in I iff ψ is not true in I.
3 If ϕ is ψ ∧ χ, then ϕ is true in I iff ψ is true in I and χ is true in I.
4 If ϕ is ψ ∨ χ, then ϕ is true in I iff ϕ is true in I or χ is true in I.
5 If ϕ is ψ → χ, then ϕ is true in I iff ϕ is not true in I or χ is true in
I.
Luca Incurvati ([Link]@[Link]) Basic Logic 2 24 / 24
