Introduction to Logic

Assessed Exercise 1

February 2005

Read the text carefully and then attempt each of the problems given below. Your solutions to the problems should be submitted by 4pm on 24th February 2005. It is your responsibility to obtain a cover-sheet for the work before submitting it.

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?