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