Problems

1. Consider a version of the language of propositional logic, where the only connective is implication ($\rightarrow$), but the language also contains a special `propositional constant' $\bot$. Sentences of the language are defined as follows:
   1. Any propositional variable is a sentence;
   2. $\bot$ is a sentence;
   3. if $A$ and $B$ are sentences, then so is $(A \rightarrow B)$;
   4. nothing else is a sentence.
   The connective $\rightarrow$ is assumed to have its usual meaning (i.e. truth function) and $\bot$ represents falsehood (i.e. it always has the truth value $f$).

   Show that the usual propositional connectives $\neg$ (negation) and $\wedge$ (conjunction) can be expressed in terms of $\rightarrow$ and $\bot$.

   Hint: see the approach to Sheffer Stroke in lecture 4 of the course

2. A rule of inference is said to be sound if the conclusion of the rule is entailed by the rule premises. Show that the rule of inference known as Modus Ponens is sound.

3. As part of a digital circuit, it is necessary to design a device which exhibits the behaviour shown by the following truth table. The device has four input variables ($p$, $q$, $r$ and $s$) and a single output.

   p	q	r	s	Output
   t	t	t	t	t
   t	t	t	f	t
   t	t	f	t	t
   t	t	f	f	f
   t	f	t	t	t
   t	f	t	f	f
   t	f	f	t	t
   t	f	f	f	f
   f	t	t	t	t
   f	t	t	f	f
   f	t	f	t	t
   f	t	f	f	f
   f	f	t	t	t
   f	f	t	f	f
   f	f	f	t	f
   f	f	f	f	f

   Construct a single statement of propositional logic that characterizes the output behaviour of the device in terms of the input variables $p$, $q$, $r$ and $s$. Explain how you used the information provided by the truth table to obtain your answer.
4. Using the laws of logical equivalence introduced in lecture 4, prove the following equivalences:
   1. $(A \rightarrow (B \rightarrow A)) \equiv \top$
   2. $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)) \equiv \top$
   3. $( \neg A \rightarrow \neg B) \rightarrow (B \rightarrow A) \equiv \top$
   What does this tell you about the axioms of the formal system of propositional logic introduced in lecture 6?