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.