Topic RS: Answers
Exercise
1.1a
Exercise
1.1a
Explain why &I,
∨I
and
∨E
are all sound rules.
If φ is
entailed by some formula or formulas then
(φ∨ψ)
and (ψ∨φ)
are both
entailed by those formulas too.
Also, if φ is a tautology, then so are
(φ∨ψ)
and (ψ∨φ).
So, in a derivation, if φ is entailed by its dependencies,
and (φ∨ψ)
is written
down with the same dependencies,
then (φ∨ψ)
will be
entailed by its dependencies too.
And if (ψ∨φ)
is written
down with the same dependencies,
then (ψ∨φ)
will be
entailed by its dependencies too.
So
∨I is a
sound rule.
Similar reasoning holds for &I and
∨E.
Exercise
1.2a
Would the system be sound if we add the following rule?
If you have
derived (φ∨φ),
you can write down φ,
depending on everything (φ∨φ)
depends on.
Yes. This is a sound rule. If (φ∨φ)
is entailed by some
formula or formulas then φ is entailed by those formulas
too.
Also, if
(φ∨φ)
is a tautology, then φ is a tautology too.
So, in a derivation, if
(φ∨φ)
is entailed by its dependencies,
and φ is written down with the same dependencies, then φ
will
be entailed by its dependencies.
Exercise
1.2b
Would
the system be sound if we remove rule &I?
Yes. All the rules in the system are sound. After removing
one rule the system, the remaining rules are still sound,
so the system will continue to be sound.
Exercise
1.2c
Would
the system be sound if we change rule
→I
this way?
Why or why not?
If you have
derived φ, and you have derived ψ,
you can write down (φ→ψ),
depending on everything ψ depends on except φ.
Yes. This is a sound rule.
When using this rule, you will only be able to derive
formulas
that are entailed by their dependencies.
Exercise
1.3a
Suppose
we add the flip rule and remove
Rule
∨E
from our natural deduction system.
Would the resulting system be sound?
No. The flip rule is not sound. It would, for example,
let you derive "~A" from "A". But "A" does not entail "~A".
So adding the flip rule would make the system unsound,
whether or not Rule
∨E
is removed.
Exercise
2.1a
Show
that "(A → (A
∨
B))" is a tautology in two
different ways.
Every
row in the truth table for "(A
→
(A
∨
B))" is "T":
A B (A
→
(A
∨
B))
T T T
T F T
F T T
F F T
So "(A
→
(A
∨
B))" is a tautology.
"(A
→
(A
∨
B))" is derivable in our system with no
dependencies:
1 1. A A
1 2. (A
∨
B) 1
∨I
3. (A
→
(A
∨
B)) 1,2
→I
Since our system is sound, any formula derivable
with no dependencies is a tautology.
So "(A
→
(A
∨
B))" is a tautology.
Exercise
2.1b
Show
that "((A
∨
~B) → ~(~A & B))" is a tautology in two
different ways.
Every row in the truth table for
"((A
∨
~B)
→
~(~A & B))" is "T":
A B ((A
∨
~B)
→
~(~A & B))
T T T
T F T
F T T
F F T
So "((A
∨
~B)
→
~(~A & B))" is a tautology.
"((A
∨
~B)
→
~(~A & B))" is derivable in our system
with no dependencies:
1 1. (A
∨
~B) A
2 2. (~A & B) A
2 3. ~A 2 &E
1,2 4. ~B 1,3
∨E
2 5. B 2 &E
1,2 6. (B&~B) 4,5 &I
1 7. ~(~A & B) 2,6 ~I
8. ((A
∨
~B)
→
~(~A & B)) 1,7
→I
Since our system is sound, any formula derivable
with no dependencies is a tautology.
So "((A
∨
~B)
→
~(~A & B))" is a tautology.
Exercise 2.1c
Suppose
we remove Rules →I, ~I and ~E from the system.
Is it still possible to derive "((A
∨
~B) → ~(~A & B))"?
No it is not possible.
Exercise
2.3a
Suppose
we get rid of some of the rules.
For example, suppose we remove rules
↔I
and
↔E.
Would the system still be complete?
No,
the system would no longer be complete.
There are formulas we could derive before that
we will no longer be able to derive.
For example, we would no longer be able to
derive the tautology "(A↔A)".
Exercise
2.3b
Suppose
we add the following new rule
to our system:
Flip rule
If you have derived φ, you can write down ~φ,
depending on everything φ depends on.
Would
the revised system still be complete?
Yes,
the system would still be complete.
In the revised system, we can still derive
everything that we could derive before adding the rule.
(However, the revised system is not sound.)