40

Propositional logic as a language

The above input/output table specifies precisely the circumstances under which the valve must be closed. According to row 10, for example, a request for closing the valve is to be made if the gas is flowing but not burning, even if there is no leakage. Note that certain combinations of inputs such as those on rows 9 and 10, may never occur or may be unrealistic. In such cases the actual value of the output may be irrelevant from the point of view of the application. For the purpose of illustrating the application of digital logic let us now consider a si mpler scenario.

A patient monitoring system, which monitors a patient with a particular disorder, is provided with patient's temperature, blood pressure and pulse rate. The following table gives threshold values of these parameters requiring the raising of an alarm for medical assistance.

An application: digital circuits Description of states

4i

Inputs/outputs
A B C 0

Meaning
Patient's temperature is in the range 36-40 C. Patient's systolic blood pressure is outside the range 80-160 mm. Patient's pulse rate is outside the range 60-120 beats per minute. Raising the alarm is necessary.

Input/output table for the recognizer

and pulse rates are outside the relevant ranges of values. In real life this kind of information is provided to the circuit designer by the medical expert. The first step in developing a circuit is to work out for it the required logic. This can be done in several ways. We propose a logic based on a truth table, the construction of which has been guided by the formula

where each disjunct corresponds to a row where the output 0 is 1. The solution given below does not match exactly the above formula. (We justify the solution adopted in the next chapter.)

Truth table for a particular design of the recognizer Table 3.3 may now be used in developing, as shown in Figure 3.3, an equivalent graphical layout for the circuit. According to this diagram, each of the inputs A, B and C is fed into two gates. The and gates 1, 2 and 3 perform the logical function enumerated under columns 4, 5, and 6 respect ve'" in the truth table. The or gate 4 performs

An application: digital circuits Description of states

41

Inputs/outputs
A B C 0

Meaning
Patient's temperature is in the range 36-40 C. Patient's systolic blood pressure is outside the range 80-160 mm. Patient's pulse rate is outside the range 60-120 beats per minute. Raising the alarm is necessary.

Input/output table for the recognizer

The first step in developing a circuit is to work out for it the required logic. This can be done in several ways. We propose a logic based on a truth table, the construction of which has been guided by the formula

where each disjunct corresponds to a row where the output 0 is 1. The solution given below does not match exactly the above formula. (We justify the solution adopted in the next chapter.)

Truth table for a particular design of the recognizer Table 3.3 may now be used in developing, as shown in Figure 3.3, an equivalent graphical layout for the circuit. According to this diagram, each of the inputs A, B and C is fed into two gates. The and gates 1, 2 and 3 perform the logical function enumerated under columns 4, 5, and 6 respectively in the truth table. The or gate 4 performs

A2 Propositional

logic as a language

the logical function given by column 7 using the outputs produced by gates 1 and 2. The or gate 5 then produces the final output according to column 8 by using the outputs produced by gates 3 and 4.

44

Propositional logic as a language 2. A recognizer with three inputs.

Suggest an application where this digital circuit could have a use.

Think of an application and a recognizer invol ving just three inputs for performing a particular task of the application. Produce the input/output table for the desired recognizer and construct a digital circuit implementing it.

Here are some general questions. 1. Can a prime proposition be a tautology or a contradiction? 2. What is the difference between formulae in general and well-formed formulae? Is it possible to determine the truth value of an ill-formed formula? 3. What is the distinction between the table in the definition on page 28 and the table in Example 3.5? 4. Why do computer scientists need to know about tautologies, contradictions and contingent contradictions? 5. `Syntax is more important than semantics'. Discuss this statement.

Objectives
On completion of this chapter you should be able to: Prove the equivalence of formulae using truth tables. Remember and use the laws of equivalence. Carry out a transformational proof. Simplify conditionals in computer programs. Simplify digital circuits.

In natural language we are often able to express the same idea in several different ways. The same is true in logic as well as in programming. However, since in logic the meaning is concealed by symbols, it is not always easy to establish whether two formulae are identical in meaning. Transformational proof is the kind of reasoning which allows just that in such situations. Transformational proofs have other uses too. Conditionals in programs and Boolean expressions relating inputs and outputs of digital circuits are just two areas with immediate applications of such proofs, which often enable the simplification of the relevant logical formulae. The last two sections of this chapter demonstrate how this can be done.

Logical laws and how to establish them

Chapter 3 discussed the equivalence of propositions and tautologies. Continuing this discussion here, we will learn how to demonstrate that any given two
45

46

Transformational proofs

formulae are logically equivalent. There are two approaches: using truth tables and transformational proofs.
4.1.1

Truth tables and logical laws

The notion of logical law is based on the notion of logical equivalence, introduced in Chapter 3. Let us restate in a slightly different form the definition of logical equivalence given there.

Two formulae are logically equivalent if and only if they are identical in meaning. The Description means that we can use any two logically equivalent formulae interchangeably. Given an occurrence of one, we can replace it with its logically equivalent counterpart without affecting the meaning of the original formula. This is what we intend to exploit when transforming formulae into simpler forms. Recall that, in a truth table incorporating logically equivalent formulae, those formulae have identical columns. We can use this property to establish some basic logical equivalences to be used as logical laws. Some candidate logical laws are given in Examples 4.1 and 4.2.

Another way to show that two formulae are logically equivalent is to show that the equivalence of the formulae is a tautology (recall the definition on page 35). This is demonstrated in Example 4.2.

Logical laws and how to establish them

47

Indeed it is a tautology because the last column of Table 4.1 contains only Ts.

4.1.2

New logical laws from the already known ones

As Example 4.2 may have demonstrated, the use of truth tables becomes increasingly tedious as the number of variables increases. With four variables, there will be 2 ^4 rows, that is, 16 rows. With five variables there will be 2 5 , or 32 rows, and so on. It has become necessary to find an alternative. Once we agree upon a small number of logical equivalences, as we are about to do, it is possible to use them to establish further equivalences. Why not use this as an alternative? First, let us list the equivalences we have established so far and give them some names (Table 4.2).

48

Transformational proofs

The logical laws listed

Logical laws are a collection of specially chosen logical equivalences.

Below is a complete list of the equivalence laws used later in proofs. We have already established many of them. If in doubt of any, try them as exercises. Most of these laws are intuitive. Those which may require a special effort to remember are marked with a < on the right. Commutative laws

Law of negation

Logical laws and how to establish them

51

52

Transformational proofs

Note, however, following our discussion in Section 3.6 of the previous chapter, we do not write T but true in formulae such as (4.11), (4.18) and (4.19). The same applies to F and false in formulae (4.12), (4.20) and (4.21). Example 4.4 is intended to reinforce this distinction.

On the art of proofs

On page 48 we saw some simple proofs using logical laws. It is time now to consider why these proofs work. There are two rules implicit in this kind of proof:
1. Rule of substitution

We can always substitute a logically equivalent formula for a sub-formula embedded in a much larger formula without affecting its meaning.
2. Rule of transitivity

If every step in a proof is carried out using a logical equivalence, then every pair of formulae appearing anywhere in the chain of the complete proof are logically equivalent to each another. The best way to learn how to do this kind of proof is to practise. One must become familiar with the logical laws and learn which ones to apply under different circumstances. However, keep the following points in mind: 1. The solution may require translating between formulae containing different connectives. 2. Where formulae seem very complex, it is often a good idea to treat a complex subformula as a single fictitious variable. This will help you to identify the general structure (form) of the formula. Then look for a law with a matching form.

On the art of proofs

53

56

Transformational proofs

An application: digital circuits

57

having as its guard the negated conjunction of existing guards and skip (a program which does nothing but successfully terminates) or an error handling facility as its command.

Thus, the alternation command in GCL is concise, clearer and more general. It offers more, since it is also a framework for mathematical program verification and program development by refinement - an approach that allows the development of code by a series of mathematically verifiable small steps.

In the design of digital circuits, the logical laws given in Section 4.13 have several uses. An obvious use is in the simplification of circuits. Example 4.6 illustrates this in relation to the problem we attempted in Exercise 3.14. The design of digital circuits

58

Transformational proofs

is not always driven by simplicity of the circuit. There can be other factors. Sometimes the design of a large circuit may be influenced by the preference for some repetitiveness in its subcircuits and sometimes by a desired number of different types of gate to be used. Whatever the goal, once the desired functionality is established in the form of a formula in propositional logic, the criteria appropriate to a given design may be met by manipulating the formula using logical laws. We now know that any transformation of a formula done by applying logical laws does not affect the meaning, which in this case b the circuit functionality.

An application: digital circuit :

59

Objectives
On completion of this chapter you should be able to: Define the notion of validity of an argument. Establish the validity of an argument using truth tables. Demonstrate the invalidity of an argument. Remember and use inference laws. Establish the validity of an argument by providing a proof. Reason about theories that can be expressed using prime propositions.

Proofs are not just about how to transform a formula to an equivalent one. They are really about how to establish the validity of arguments, which, as mentioned in Section 1.1 of Chapter 1, is the prime concern of logic. Therefore, compared with transformational proofs covered in the previous chapter, the kind of proof introduced in this chapter has a more general applicability. As far as the relevance of proof in computing is concerned, it is sufficient to note that questions about specifications and claims made in programming are arguments as well. Therefore, it is legitimate to ask for the proof at the end of a requirements validation exercise (validation of user requirements documented in a specification) or a verification of correctness of a computer program.

If the conclusion of an argument is wholly justified by the premises, the argument is said to be deductive. Deductive arguments reason about knowledge that is implicit, or seems to be i mplicit, in an already known body of knowledge. Part of this known body of knowledge is explicitly stated and the rest must have been established by prior reasoning. Inductive arguments reason about more general new knowledge from a small number of particular facts or observations.

The following is a deductive argument: 1. All Rugby players drink too much. 2. Jenny is a Rugby player. 3. Therefore, Jenny drinks too much. The following is an inductive argument: 1. All those taking part in these league matches are a fair sample of Rugby players. 2. They all drink too much. 3. Therefore, all Rugby players drink too much. Induction is a special form of reasoning in its own right. Whether it concerns the boiling point of water or the size of the population of a particular species of animals in the wild, they are all estimated on the basis of inductive principles. Inductive generalizations are based on observations about a fair sample of individuals or experiments. The premise that the observations constitute a fair sample is pivotal to the validity of an inductive argument. The first piece of evidence to the contrary could be fatal.