Discrete Mathematics/Logic

Introduction

In conventional algebra, letters and symbols are used to represent numbers and the operations associated with them: +, -, ×, ÷, etc. Doing so can help simplify and solve complex problems. In Logic, we seek to express statements, and the connections between them in algebraic symbols - again with the object of simplifying complicated ideas. Unfortunately, like ordinary algebra, the opposite seems true initially. This is probably because simple examples always seem easier to solve by common-sense methods!

Propositions

A proposition is a statement which has truth value: it is either true (T) or false (F).

Example 1

Which of the following are propositions?

(a) 17 + 25 = 42

(b) July 4 occurs in the winter in the Northern Hemisphere.

(c) The population of the United States is less than 250 million.

(d) Is the moon round?

(e) 7 is greater than 12.

(f) x is greater than y.

Answers

(a) is a proposition; and of course it has the 'truth value' true.

(b) is a proposition. Of course, it's false, but it's still a proposition.

(c) is a proposition, but we may not actually know whether it's true or false. Nevertheless, the fact is that the statement itself is a proposition, because it is definitely either true or false.

(d) is not a proposition. It's a question.

(e) is a proposition. It's false again, of course 7<12.

(f) is a bit more debatable! It's certainly a potential proposition, but until we know the values of x and y, we can't actually say whether it is true or false. Note that this isn't quite the same as (c), where we may not know the truth value because we aren't well-enough informed. See the next paragraph.

Propositional Functions

A function is, loosely defined, an operation that takes as input one or more parameter values, and produces a single, well-defined output.

You're probably familiar with the sine and cosine functions in trigonometry, for example. These are examples of functions that take a single number (the size of an angle) as an input and produce a decimal number (which in fact will lie between +1 and -1) as output.

If we want to, we can define a function of our own, say RectangleArea, which could take two numbers (the length and width of a rectangle) as input, and produce a single number as output (formed by multiplying the two input numbers together).

In (f) above, we have an example of a Propositional Function. This is a function that produces as output not a number like sine, cosine or RectangleArea, but a truth value. It's a statement, then, that becomes a proposition when it is supplied with one or more parameter values. In (f), the parameters are x and y. So if x = 2 and y = 7, its output is False; if x = 4 and y = -10, its output is True.

More about propositional functions later.

Notation

We shall often represent propositions by lower-case letters p, q, ...

Compound Propositions

Propositions may be modified by means of one or more logical operators to form what are called compound propositions.

There are three logical operators:

• conjunction: $\scriptstyle \wedge$ meaning AND

• disjunction: ∨ meaning OR

• negation: ¬ meaning NOT

Example 2

p represents the proposition "Henry VIII had six wives".

q represents the proposition "The English Civil War took place in the nineteenth century".

(a) Connect these two propositions with OR. Is the resulting compound proposition true or false?

(b) Now connect them with AND. Is this compound proposition true or false?

(c) Is the 'opposite' of p true or false?

Answers

(a) p ∨ q is "Henry VIII had six wives or the English Civil War took place in the nineteenth century"

This is true. The first part of the compound proposition is true, and this is sufficient to make the whole statement true – if a little odd-sounding!

If you think that this example seems very artificial, imagine that you're taking part in a History Quiz; there are two questions left, and you need to get at least one right to win the quiz. You make the two statements above about Henry VIII and the Civil War. Do you win the quiz? Yes, because it is true that either Henry VIII had six wives or the English Civil War took place in the nineteenth century.

Note that this is an inclusive OR: in other words, we don't rule out both parts being true. So p ∨ q means "Either p is true, or q is true, or both".

(b) p $\scriptstyle \wedge$ q is "Henry VIII had six wives and the English Civil War took place in the nineteenth century"

This is false.

To be true, both parts would have to be true. This is equivalent to your needing both questions right to win the quiz. You fail, because you got the second one wrong.

(c) The opposite of p, which we write as ¬p, is "Henry VIII did not have six wives". This is clearly false. And in general, if p is true, then ¬p is false, and vice versa.

Example 3

p is "The printer is off-line"

q is "The printer is out of paper"

"r" is "The document has finished printing"

Write as English sentences, in as natural a way as you can:

(a) p ∨ q

(b) r $\scriptstyle \wedge$ q

(c) q $\scriptstyle \wedge$ ¬r

(d) ¬(p ∨ q)

Answers

(a) The printer is off-line or out of paper.

Notice how we often leave words out when we're writing or speaking English. This sounds much more natural than "The printer is off-line or the printer is out of paper".

(b) The document has finished printing and the printer is out of paper.

The subject of each part of the sentence is different now, so no words are missing this time.

(c) The printer is out of paper and the document has not finished printing.

But and And

The statement in (c) could be someone reporting a problem, and they might equally well say:

(c) The printer is out of paper but the document has not finished printing.

So note that, in logic, but and and mean the same thing. It's just that we use but to introduce a note of contrast or surprise. For example, we might well say:

• The sun is shining brightly, but it's freezing cold outside.

Logically, we could use and to connect both parts of this sentence, but(!) it's more natural to use but.

In (d) what does ¬(p ∨ q) mean? Well, p ∨ q means either p is true or q is true (or both). When we place ¬ in front, we negate this. So it means (literally):

• It is not true that either the printer is off-line or the printer is out of paper.

In other words:

(d) The printer is neither off-line nor out of paper.

Notice that it's often convenient to translate ¬ using the phrase 'It is not true that …'.

Logic Exercise 1

Click link for Logic Exercise 1.

Truth Tables

Consider the possible values of the compound proposition p $\scriptstyle \wedge$ q for various combinations of values of p and q. The only combination of values that makes p $\scriptstyle \wedge$ q true is where p and q are both true; any other combination will include a false and this will render the whole compound proposition false. On the other hand, the compound proposition p ∨ q will be true if either p or q (or both) is true; the only time p ∨ q is false is when both p and q are false.

We summarise conclusions like these in what is called a Truth Table, the truth table for AND being:

p	q	p $\scriptstyle \wedge$ q
T	T	T
T	F	F
F	T	F
F	F	F

The truth table for OR is:

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

The order of the Rows in a Truth Table

Notice the pattern of T's and F's in the first two columns of each of the truth tables above. In the first column (the truth values of p), there are 2 T's followed by 2 F's; in the second (the values of q), the T's and F's change on each row. We shall adopt this order of the rows throughout this text. Adopting a convention for the order of the rows in a Truth Table has two advantages:

• It ensures that all combinations of T and F are included. (That may be easy enough with just two propositions and only four rows in the Truth Table; it's not so easy with, say, 4 propositions where there will be 16 rows in the table.)

• It produces a standard, recognisable output pattern of T's and F's. So, for example, T, F, F, F is the output pattern (or 'footprint' if you like) of AND ($\scriptstyle \wedge$), and T, T, T, F is the footprint of OR (∨).

The truth table for NOT

Each of the two truth tables above had two 'input' columns (one for the values of p and one for q), and one 'output' column. They each needed four rows, of course, because there are four possible combinations of T's and F's when two propositions are combined. The truth table for NOT (¬) will be simpler, since ¬ is a unary operation – one that requires a single proposition as input. So it just two columns – an input and an output – and two rows.

p	¬p
T	F
F	T

Drawing up Truth Tables

The method for drawing up a truth table for any compound expression is described below, and four examples then follow. It is important to adopt a rigorous approach and to keep your work neat: there are plenty of opportunities for mistakes to creep in, but with care this is a very straightforward process, no matter how complicated the expression is. So:

• Step 1: Rows

  Decide how many rows the table will require. One input requires only two rows; two inputs require 4 rows; three require 8, and so on. If there are n propositions in the expression, 2ⁿ rows will be needed.

• Step 2: Blank Table

  Draw up a blank table, with the appropriate number of input columns and rows, and a single output column wide enough to accommodate comfortably the output expression. If 8 or more rows are needed, you'll probably find it helps to rule a horizontal line across the table every four rows, in order to keep your rows straight.

• Step 3: Input Values

  Fill in all the input values, using the convention above for the Order of Rows in a Truth Table; that is to say, begin with the right-most input column and fill in the values T and F, alternating on every row. Then move to the next column to the left, and fill in T's and F's changing on every second row. And so on for all the remaining columns. The left-most column will then contain T's in the first half of all the rows in the table, and F's in the second half.

• Step 4: Plan your strategy

  Study carefully the order in which the operations involved in evaluating the expression are carried out, taking note of any brackets there may be. As in conventional algebra, you don't necessarily work from left to right. For example, the expression p ∨ ¬q will involve working out ¬q first, then combining the result with p using ∨. When you've worked out the order in which you need to carry out each of the operations, rule additional columns under the output expression - one for each stage in the evaluation process. Then number each of the columns (at its foot) in the order in which it will be evaluated. The column representing the final output will be the last stage in the evaluation process, and will therefore have the highest number at its foot.

• Step 5: Work down the columns

  The final stage is to work down each column in the order that you've written down in Step 4. To do this, you'll use the truth tables for AND, OR and NOT above using values from the input columns and any other columns that have already been completed. Remember: work down the columns, not across the rows. That way, you'll only need to think about one operation at a time.

You're probably thinking that this all sounds incredibly complicated, but a few examples should make the method clear.

Worked examples

Example 4

Produce truth tables for:

(a) ¬(¬p)

(b) p $\scriptstyle \wedge$ (¬q)

(c) (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q)

(d) q $\scriptstyle \wedge$ (p ∨ r)

Solutions

(a) ¬(¬p) is pretty obviously the same as p itself, but we'll still use the above method in this simple case, to show how it works, before moving on to more complicated examples. So:

• Step 1: Rows

There's just one input variable here, so we shall need two rows.

• Step 2: Blank Table

So the table is:

p	¬(¬p)
.
.

• Step 3: Input Values

Next, we fill in the input values: just one T and one F in this case:

p	¬(¬p)
T
F

• Step 4: Plan your strategy

As in 'ordinary' algebra we evaluate whatever's in brackets first, so we shall first (1) complete the (¬p) values, followed (2) by the left-hand ¬ symbol, which gives us the final output values of the whole expression. We rule an extra column to separate these two processes, and write the (1) and (2) at the foot of these two columns. Thus:

p	¬	(¬p)
T
F
	(2) Output	(1)

• Step 5: Work down the columns

Finally we insert the values in column (1) – F followed by T – and then use these values to insert the values in column (2). So the completed truth table is:

p	¬	(¬p)
T	T	F
F	F	T
	(2) Output	(1)

As we said at the beginning of this example, ¬(¬p) is clearly the same as p, so the pattern of the output values, T followed by F, is identical to the pattern of the input values. Although this may seem trivial, the same technique works in much more complex examples, where the results are far from obvious!

(b) p $\scriptstyle \wedge$ (¬q)

• Step 1

There are two input variables, p and q, so we shall need four rows in the table.

• Steps 2 & 3

In the q column write T's and F's alternating on every row; in the p column alternate every two rows. At this stage, the table looks like this:

p	q	p $\scriptstyle \wedge$ (¬q)
T	T
T	F
F	T
F	F

• Steps 4 & 5

As Example (a), we begin (1) by evaluating the expression in brackets, (¬q), and then (2) we combine these results with p using the $\scriptstyle \wedge$ operator. So we divide the output section of the table into two columns; then work down column (1) and finally column (2). The completed table is:

p	q	p $\scriptstyle \wedge$	(¬q)
T	T	F	F
T	F	T	T
F	T	F	F
F	F	F	T
		(2) output	(1)

(c) (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q)

• Steps 1 to 3

As in Example (b).

• Steps 4 & 5

There will be 5 stages in evaluating the expression (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q). In order, they are:

(1) The first bracket: (p $\scriptstyle \wedge$ q)

(2) The ¬p in the second bracket

(3) The ¬q in the second bracket

(4) The ∨ in the second bracket

(5) The ∨ between the two brackets. This final stage, then, represents the output of the complete expression.

Reminder: Don't work across the rows; work down the columns in order (1) to (5). That way, you'll only have to deal with a single operation at a time.

The completed table is:

p	q	(p $\scriptstyle \wedge$ q)	∨	(¬p	∨	¬q)
T	T	T	T	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	T	F
F	F	F	T	T	T	T
		(1)	(5) output	(2)	(4)	(3)

Notice that the output consist solely of T's. This means that (p $\scriptstyle \wedge$ q) ∨ (¬p ∨ ¬q) is always true whatever the values of p and q. It is therefore a tautology (see below).

(d) q $\scriptstyle \wedge$ (p ∨ r)

This simple expression involves 3 input variables, and therefore requires 2³ = 8 rows in its truth table. When drawing this truth table by hand, rule a line below row 4 as an aid to keeping your working neat. It is shown as a double line in this table. The completed table is shown below.

p	q	r	q $\scriptstyle \wedge$	(p ∨ r)
T	T	T	T	T
T	T	F	T	T
T	F	T	F	T
T	F	F	F	T
F	T	T	T	T
F	T	F	F	F
F	F	T	F	T
F	F	F	F	F
			(2) output	(1)

Tautology

An expression which always has the value true is called a tautology.

In addition, any statement which is redundant, or idempotent, is also referred to as a tautology, and for the same reason previously mentioned. If P is True then we can be sure that P ∨ P is true, and P ∧ P is also true.

Logic Exercise 2

Click link for Logic Exercise 2.

Order of Precedence

In 'ordinary' algebra, the order of precedence in carrying out operations is:

1 brackets

2 exponents (powers)

3 × and ÷

4 + and -

In the algebra of logic, brackets will often be inserted to make clear the order in which operations are to be carried out. To avoid possible ambiguity, the agreed rules of precedence are:

1 brackets

2 NOT (¬)

3 AND ($\scriptstyle \wedge$)

4 OR (∨)

So, for example, p ∨ q $\scriptstyle \wedge$ r means:

Evaluate q $\scriptstyle \wedge$ r first.

Then combine the result with p ∨.

Since it would be easy to misinterpret this, it is recommended that brackets are included, even if they are not strictly necessary. So p ∨ q $\scriptstyle \wedge$ r will often be written p ∨ (q $\scriptstyle \wedge$ r).

Logically Equivalent Propositions

Look back to your answers to questions 2 and 3 in Exercise 2. In each question, you should have found that the last columns of the truth tables for each pair of propositions were the same.

Whenever the final columns of the truth tables for two propositions p and q are the same, we say that p and q are logically equivalent, and we write:

p ≡ q

Example 5

Construct truth tables for

(i) p ∨ (q $\scriptstyle \wedge$ r), and

(ii) (p ∨ q) $\scriptstyle \wedge$ (p ∨ r),

and hence show that these propositions are logically equivalent.

Solution

(i)

p	q	r	p ∨	(q $\scriptstyle \wedge$ r)
T	T	T	T	T
T	T	F	T	F
T	F	T	T	F
T	F	F	T	F
F	T	T	T	T
F	T	F	F	F
F	F	T	F	F
F	F	F	F	F
			(2) output	(1)

(ii)

p	q	r	(p ∨ q)	$\scriptstyle \wedge$	(p ∨ r)
T	T	T	T	T	T
T	T	F	T	T	T
T	F	T	T	T	T
T	F	F	T	T	T
F	T	T	T	T	T
F	T	F	T	F	F
F	F	T	F	F	T
F	F	F	F	F	F
			(1)	(3) output	(2)

The outputs in each case are T, T, T, T, T, F, F, F. The propositions are therefore logically equivalent.

Example 6

Construct the truth table for ¬(¬p ∨ ¬q), and hence find a simpler logically equivalent proposition.

Solution

p	q	¬	(¬p	∨	¬q)
T	T	T	F	F	F
T	F	F	F	T	T
F	T	F	T	T	F
F	F	F	T	T	T
		(4) output	(1)	(3)	(2)

We recognise the output: T, F, F, F as the 'footprint' of the AND operation. So we can simplify ¬(¬p ∨ ¬q) to

p $\scriptstyle \wedge$ q

Laws of Logic

Like sets, logical propositions form what is called a Boolean Algebra: the laws that apply to sets have corresponding laws that apply to propositions also. Namely:

Commutative Laws

p $\scriptstyle \wedge$ q ≡ q $\scriptstyle \wedge$ p

p ∨ q ≡ q ∨ p

Associative Laws

(p $\scriptstyle \wedge$ q) $\scriptstyle \wedge$ r ≡ p $\scriptstyle \wedge$ (q $\scriptstyle \wedge$ r)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributive Laws

p $\scriptstyle \wedge$ (q ∨ r) ≡ (p $\scriptstyle \wedge$ q) ∨ (p $\scriptstyle \wedge$ r)

p ∨ (q $\scriptstyle \wedge$ r) ≡ (p ∨ q) $\scriptstyle \wedge$ ( p ∨ r)

Idempotent Laws

p $\scriptstyle \wedge$ p ≡ p

p ∨ p ≡ p

Identity Laws

p $\scriptstyle \wedge$ T ≡ p

p ∨ F ≡ p

Domination laws

p ∨ T ≡ T

p $\scriptstyle \wedge$ F ≡ F

Involution Law

¬(¬p) ≡ p

De Morgan’s Laws

¬(p ∨ q) ≡ (¬p) $\scriptstyle \wedge$ (¬q)

(sometimes written p NOR q)

¬(p $\scriptstyle \wedge$ q) ≡ (¬p) ∨ (¬q)

(sometimes written p NAND q)

Complement Laws

p $\scriptstyle \wedge$ ¬p ≡ F

p ∨ ¬p ≡ T

¬T ≡ F

¬F ≡ T

Worked Examples

Example 7

Propositional functions p, q and r are defined as follows:

p is "n = 7"

q is "a > 5"

r is "x = 0"

Write the following expressions in terms of p, q and r, and show that each pair of expressions is logically equivalent. State carefully which of the above laws are used at each stage.

(a)

((n = 7) ∨ (a > 5)) $\scriptstyle \wedge$ (x = 0)

((n = 7) $\scriptstyle \wedge$ (x = 0)) ∨ ((a > 5) $\scriptstyle \wedge$ (x = 0))

(b)

¬((n = 7) $\scriptstyle \wedge$ (a ≤ 5))

(n ≠ 7) ∨ (a > 5)

(c)

(n = 7) ∨ (¬((a ≤ 5) $\scriptstyle \wedge$ (x = 0)))

((n = 7) ∨ (a > 5)) ∨ (x ≠ 0)

Solutions

(a)

(p ∨ q) $\scriptstyle \wedge$ r

(p $\scriptstyle \wedge$ r) ∨ (q $\scriptstyle \wedge$ r)

(p ∨ q) $\scriptstyle \wedge$ r	= r $\scriptstyle \wedge$ (p ∨ q)	Commutative Law
	= (r $\scriptstyle \wedge$ p) ∨ r $\scriptstyle \wedge$ q)	Distributive Law
	= (p $\scriptstyle \wedge$ r) ∨ (q $\scriptstyle \wedge$ r)	Commutative Law (twice)

(b)

First, we note that

¬q is "a ≤ 5"; and

¬p is "n ≠ 7".

So the expressions are:

¬(p $\scriptstyle \wedge$ ¬q)

¬p ∨ q

¬(p $\scriptstyle \wedge$ ¬q)	= ¬p ∨ ¬(¬q)	De Morgan's Law
	= ¬p ∨ q	Involution Law

(c)

First, we note that

¬r is "x ≠ 0".

So the expressions are:

p ∨ (¬(¬q $\scriptstyle \wedge$ r))

(p ∨ q) ∨ ¬r

p ∨ (¬(¬q $\scriptstyle \wedge$ r))	= p ∨ (¬(¬q) ∨ ¬r)	De Morgan's Law
	= p ∨ (q ∨ ¬r)	Involution Law
	= (p ∨ q) ∨ ¬r	Associative Law

Logic Exercise 3

Click link for Logic Exercise 3.