Exercises 1.5

1. Show that a formula is valid iff T = 0, where T is an abbreviation for an

instance p V -p of LEM.

2. Which of these formulas are semantically equivalent to p → (q V r)?

(a) qv (-p Vr)

(b) q^-r-p

(c) p^rq

*

(d)¬q^r-p.

3. An adequate set of connectives for propositional logic is a set such that for every

formula of propositional logic there is an equivalent formula with only connectives

from that set. For example, the set {-, V} is adequate for propositional logic,

because any occurrence of A and → can be removed by using the equivalences

→ ¬V and o^= -(-V¬).

(a) Show that {¬, ^}, {¬,→} and {→,1} are adequate sets of connectives for

propositional logic. (In the latter case, we are treating as a nullary con-

nective.)

(b) Show that, if C C {¬, ^, V, →, 1} is adequate for propositional logic, then

¬EC or LEC. (Hint: suppose C contains neither nor and consider

the truth value of a formula o, formed by using only the connectives in C,

for a valuation in which every atom is assigned T.)

(c) Is {,} adequate? Prove your answer.