Transcript Slide 1

For Friday, read Chapter 4, section 4.
Exam #2 is Wednesday and will cover
Chapter 3, sections 1-4, and Chapter 4,
sections 1-4.
Monday will be devoted to review – mostly to
doing proofs.
→Introduction
j
(j) p
.
.
a1,…,an
(k) q
.
.
{a1,…,an}/j (m) p → q
j > k, j < k, or j = k
Assumption
j, k →I
What Do the Symbols
Mean?
To say that j > k or j = k is to say that the assumption
can come after the line that becomes the consequent
or that j and k can be the very same line.
a1,…,an refers to the lines on which the thing that
becomes the consequent depends. {a1,…,an}/j
means “remove j from that set, if it’s in there”
The line that becomes the antecedent is always an
assumption. As an assumption, it depends only on
itself.
Semantic vs. Deductive
Consequences
‘p1…pn |= q’ says that it is impossible for p1…pn
to be true while q is false. This double-turnstile says
that the statement on the right is a semantic
consequence of the statement(s) on the left.
‘p1…pn |- q’ (which is called a ‘sequent’) says
that q can be derived from p1…pn using some
particular natural deduction system (NK, in our
case). It says that q is a deductive consequence of
p1…pn.
Proving Theorems
So, ‘|- q’, with no premises given on the left,
means that q can be derived within our system from
no premises at all.
Statements that can be derived from no premises
are the theorems of our natural deduction system.
In sentential logic, the set of theorems is identical to
the set of tautologies (assuming we have a
complete natural deduction system).
How to Prove Theorems
Always start by making an assumption.
Let the conclusion (the theorem) be your guide. If
the theorem is a conditional, start by assuming
its entire antecedent.
Then proceed with your proof, making other
assumptions where necessary. When you arrive
at the desired theorem, if you’ve done the proof
properly, it should have no dependence lines
listed off to its left.
Exercises on p. 102