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.)