In this question, you will prove that every truth table can be implemented us-

ing

only

the conditional operator

and the constant

False

. Hint: in your justifications,

you are free to use the fact that

a

b

a

b

.

a.

[3 marks]

Show that

can be simulated using only

and

False

. That is, design

a logical expression that is logically equivalent to

p

, and uses only

p

,

and

False

.

You must prove that your logical expression is correct using equivalence rules. (See,

e.g., Epp 4th ed page 35, Epp 5th ed page 49, or Daves excellent formula sheet)

b.

[3 marks]

Show that

can be simulated using only

and

False

. That is, design a

logical expression that is logically equivalent to

p

q

and uses only

p

,

q

,

and

False

.

You must prove that your logical expression is correct using equivalence rules.

c.

[3 marks]

Show that

can be simulated using only

and

False

. That is, design a

logical expression that is logically equivalent to

p

q

and uses only

p

,

q

,

and

False

.

You must prove that your logical expression is correct using equivalence rules.

Since for every truth table over

k

atomic propositions, we can write a propositional form

that matches the truth table using

,

and

, your answers to parts (a), (b) and (c)

show that you every propositional form is logically equivalent to a propositional form that

uses only

and

False

.