Discrete Mathematics/Logic/Page 2

Conditional Propositions

Example 8

Discuss what Andy means when he says to Bernard: "If you want some more coffee, there’s some in the pot".

What Andy probably means is simply "There's some coffee in the pot, and if you want some, help yourself". Almost certainly, he doesn't really mean to imply that the presence (or otherwise) of the coffee in the pot is somehow dependent upon Bernard's desire for some. As you may have realised, we are sometimes very sloppy in our use of English! One of the things we need to do if we want to represent a sentence using logic symbols, is to work out what it really means.

The ⇒ IMPLICATION

Example 9

Suppose that

p is "The weather is warm"; and

q is "I go swimming at lunchtime"

Then we can represent the conditional proposition "If the weather is warm, then I go swimming at lunchtime" by the symbols:

p ⇒ q

So ⇒ means: "if ... then", or "implies (or means) that".

Other ways of saying the same thing are:

• "The weather is warm means that I go swimming at lunchtime"

• "Whenever the weather is warm, I go swimming at lunchtime"

• "The weather is warm only if I go swimming at lunchtime"

Be careful with the last statement. It does not follow (and does not correspond to) the logic of our expression p ⇒ q. It changes the direction of ⇒ , as it were. Using word "if" at this place in the sentence changes causality of the proposition, such as my doing swimming at lunchtime means the weather is warm. This would be q ⇒ p, a reversal of conditions in our original expression. Words "only if" mean that if on a particular day I didn't go swimming at lunchtime, then the weather could not have been warm on that day, also a reverse implication. Our expression does not, of course, mean that my going swimming (or otherwise) determines the weather on that day, it’s another way around!

Necessary and Sufficient Conditions

Suppose that last Tuesday I went swimming at lunchtime. Given p and q as above, and given also that p ⇒ q, can you be sure that the weather was warm last Tuesday?

The answer is that, no, you can't. I might have gone swimming anyway, for some other reason.

Note, then, that p ⇒ q means that p is a sufficient condition for q. It is not, however, a necessary condition: q can still be true without p.

Other ways of saying this:

"I can go swimming at lunchtime even if the weather is not warm"

"I can go swimming at lunchtime regardless of the weather"

The truth table for ⇒

Note that p ⇒ q is itself a proposition; i.e. it has a truth value - it may or may not be the case that if the weather is warm, I go swimming at lunchtime.

Now the value of the proposition p ⇒ q depends upon the combination of the values of p and q. So we can construct its truth table:

p	q	p ⇒ q
T	T	T
T	F	F
F	T	T
F	F	T

Note in particular the (perhaps surprising) third line of this table! The fact is that p ⇒ q means that we cannot draw any conclusions about q if p is false. That is to say, if p is false, q may equally well be true or false without contradicting the truth of p ⇒ q.

To put this another way, p ⇒ q is false only when p is T and q is F; i.e. a true statement cannot imply a false one.

To clarify this further, consider the statement above: "If the weather is warm, then I go swimming at lunchtime". This says nothing about what happens when the weather is not warm: I may go swimming or I may not. The only time this statement is untrue is when the weather is warm, but I don't go swimming.

Biconditional Propositions

As we have already noted, we often use English in a very imprecise way. Using Example 9, suppose what I really mean to say is:

If the weather is warm I go swimming at lunchtime, and if it’s not I don’t.

In this case p and q are either both true or both false: you can’t have one without the other. We could re-phrase this and say:

I go swimming at lunchtime if and only if the weather is warm.

The phrase "if and only if" is represented by the symbol ⇔, and so we can say in this case:

p ⇔ q

In such a case as this, p is a necessary and sufficient condition for q.

Example 10

p is "x² = 9". Find a suitable statement q about x (rather than x²) for which p ⇔ q is true.

Solution

If x = 3, then certainly x² = 9. So if q is "x = 3", then q ⇒ p is true, and this would make q a sufficient condition.

But is it necessary and sufficient? No, because 3 is not the only number whose square is 9. x = -3 would also make x² = 9.

To ensure a necessary and sufficient q, then, we would have to say:

q is "x = ±3"

Logically Equivalent

We have said that p ⇔ q means that p and q are either both true, or both false, and we can therefore say that in such a case they are logically equivalent.

The truth table for ⇔

Since p ⇔ q means that p and q are either both true or both false, the truth table for ⇔ is:

p	q	p ⇔ q
T	T	T
T	F	F
F	T	F
F	F	T

Example 11

By drawing up a truth table show that

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

Solution

The truth table for (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p) is:

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

The output is T, F, F, T which is the same as the output for p ⇔ q, and therefore

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (q ⇒ p)

The ⇐ Notation

We sometimes use ⇐ to mean "is implied by". So q ⇐ p is an alternative way of writing p ⇒ q, and we could have written Example 11 as:

p ⇔ q ≡ (p ⇒ q) $\scriptstyle \wedge$ (p ⇐ q)

Logic Exercise 4

Click the link for Logic Exercise 4.

Predicate Logic

So far, we have considered only Propositional Logic, with statements like:

p is "All people with red hair have fiery tempers"

q is "Joe has red hair"

Given p and q as above and r is "Joe has a fiery temper", we can write:

p $\scriptstyle \wedge$ q ⇒ r

If we want to make a statement about Brenda having red hair, and therefore a fiery temper, we should need further propositions, like this:

s is "Brenda has red hair"

t is "Brenda has a fiery temper"

and so:

p $\scriptstyle \wedge$ s ⇒ t

… and so on.

Each time we want to make a statement about another person having red hair, and therefore a fiery temper (which may or may not be true!), we shall need further propositions. A much better way of representing these ideas is to use predicates like this:

redHair is the phrase "... has red hair"

(Notice that redHair is not a proposition. Why not?)

We can now use this predicate to form statements about anyone who has red hair; like this:

redHair(Joe) is "Joe has red hair"

redHair(Brenda) is"‘Brenda has red hair"

... and so on.

In the same way, we can define the predicate fieryTemper to stand for the phrase:

"... has a fiery temper"

So the statement "If Joe has red hair, then he has a fiery temper" can be represented by:

redHair(Joe) ⇒ fieryTemper(Joe)

and the statement "If Brenda has red hair, then she has a fiery temper" by:

redHair(Brenda) ⇒ fieryTemper(Brenda)

Notation

We shall use single words or several words joined together, using upper- and lower-case letters as shown, to denote predicates.

The "object" to which the predicate applies - a person, number, or whatever - will be written in parenthesis following the predicate.

Negation

With red Hair defined as above:

¬with red Hair is "it is not the case that with red hair"

Logic Exercise 5

Click the link for Logic Exercise 5.

Propositional Functions

If we want to talk about general, undefined, predicates, we shall use upper-case letters: P, Q, ..., and if we want a general, undefined, object, we shall use a lower-case letter: x, y, ...

So if P is "... has property P", then P(x) is "x has property P".

• P(x) can then be described as a propositional function whose predicate is P.

A function has the property that it returns a unique value when we know the value(s) of any parameter(s) supplied to it. P(x) is therefore a function since it returns a truth value which depends upon the value of its parameter, x.

For example, if American(x) is the propositional function "x is an American", then American(x) will return the value

T if x = Bill Clinton; and the value

F if x = HM The Queen

Quantifiers

We now extend the ideas in Exercise 5 above. Suppose we want to make statements like:

(a) All of my friends are wealthy.

(b) Some of my friends are boring.

The problem here is that we are making statements about my friends in general, without referring to a particular individual. So we need to define propositional functions as follows:

friend(x) is "x is a friend of mine"

wealthy(x) is "x is wealthy"

boring(x) is "x is boring"

We can then write the two statements above as:

(a) For all x, friend(x) ⇒ wealthy(x)

(b) For some x, friend(x) $\scriptstyle \wedge$ boring(x)

Notation: ∀ and ∃

The symbol ∀ (called the universal quantifier) stands for the phrase "For all …"

So we can write (a) above as:

(a) ∀ x, friend(x) ⇒ wealthy(x)

The symbol ∃ (called the existential quantifier) stands for the phrase "For some …"

So we can write (b) above as:

(b) ∃ x, friend(x) $\scriptstyle \wedge$ boring(x)

Plural or singular?

Note that, although statements (a) and (b) above use plural words – all, are, some, friends – when we symbolise them, the predicates and the variables are singular: x is wealthy, x is boring, etc. It is important to realise, then, that x can stand for just one value at a time.

So the symbolic statement:

∀ x, friend(x) ⇒ wealthy(x)

would be literally translated using singular words as:

"For each value of x, if x is a friend of mine, then x is wealthy".

and

∃ x, friend(x) $\scriptstyle \wedge$ boring(x)

is more literally translated:

"For at least one value of x, x is a friend of mine and x is boring".

To emphasise this, you might find it helpful to use the following as translations of the symbols:

∀ means "For each (value of) ..."

and

∃ means "For at least one (value of) ..."

We can now make our earlier statement that "All people with red hair have fiery tempers" using Propositional Function notation as follows:

redHair(x) is: "x has red hair"

fieryTemper(x) is: "x has a fiery temper"

Now "All people with red hair have fiery tempers" is re-written in the singular as:

For each value of x, if x has red hair, then x has a fiery temper.

In symbols, then:

∀ x, redHair(x) ⇒ fieryTemper(x)

Example 12

Define suitable propositional functions and then express in symbols:

(a) Some cats understand French.

(b) No footballers can sing.

(c) At least one lecturer is not boring.

(d) I go swimming every sunny day.

Solutions

(a) Re-write in the singular: "At least one cat understands French". So we shall need to define propositional functions as:

cat(x) is "x is a cat"

French(x) is "x understands French"

So there is at least one x that is a cat and understands French; or, in symbols:

∃x, cat(x) $\scriptstyle \wedge$ French(x)

(b) Re-write in the singular: "It is not true that at least one footballer can sing". So:

footballer(x) is "x is a footballer"

sing(x) is "x can sing"

In symbols, then:

¬ (∃x, footballer(x) $\scriptstyle \wedge$ sing(x))

Alternatively, we might re-write "No footballers can sing" as "For each x, if x is a footballer, then x cannot sing". In symbols, then, this gives the equally valid solution:

∀ x, footballer(x) ⇒ ¬ sing(x)

(c) This is already in the singular; so:

lecturer(x) is "x is a lecturer"

boring(x) is "x is boring"

So:

∃ x, lecturer(x) $\scriptstyle \wedge$ ¬ boring(x)

(d) In this example, it is important to realise what the variable represents. In (a) to (c) the variable x has denoted an animal or a person. In the sentence "I go swimming every sunny day" it is the day that changes, and, with it, the weather and my going swimming. So we must form our propositional functions around a variable x that stands for a day. Thus:

sunny(x) is "x is a sunny day"

swimming(x) is "x is a day when I go swimming"

Then, re-writing "I go swimming every sunny day" in the singular, we get:

"For each day, if it is a sunny day then it is a day when I go swimming"

So, in symbols:

∀x, sunny(x) ⇒ swimming(x)

Logic Exercise 6

Click the link for Logic Exercise 6.

Universe of Discourse

Many of the propositions in Exercises 5 and 6 referred to 'my friends'. For example, consider the proposition: "All of my friends are either wealthy or clever."

Using predicates, we can symbolise this as:

∀ x, friend(x) ⇒ (wealthy(x) ∨ clever(x))

However, if we agreed that the variable x can only stand for one of my friends, then we could symbolise this more simply as:

∀ x, wealthy(x) ∨ clever(x)

For a given propositional function P(x), the universe of discourse is the set from which the value of x may be chosen. Defining a universe of discourse can simplify the symbolisation of propositional functions. If a universe of discourse is not defined, then we shall have to assume that any object or individual may be substituted for x.

Example 13

Define, in each case, a suitable universe of discourse and predicates to symbolise:

(a) Some students are hard-working or drink too much.

(b) Everybody was hot and someone fainted.

Solutions

(a) Define the following:

Universe of discourse = {students}

hardWorking(x) is "x is hard-working"

drink(x) is "x drinks too much"

Writing in the singular: "For at least one x, x is hard-working or x drinks too much", we get:

∃ x, hardWorking(x) ∨ drink(x)

(b) In the given sentence, the word "everybody" clearly doesn't mean everybody in the whole world, simply everybody in the story being recounted. So we can define as follows:

Universe of discourse = {people in the story}

hot(x) is "x was hot"

fainted(x) is "x fainted"

Then, in the singular, we have "For each x, x was hot and for at least one x, x fainted". So:

∀ x, hot(x) $\scriptstyle \wedge$ ∃ x, fainted(x)

Two-place Predicates

The predicates we have looked at so far have been one-place predicates. To convert each predicate into a proposition, we have had to supply a single object or individual - the value of a single parameter, if you like.

We can create predicates which require two objects (or parameter values) to be supplied to convert them to propositions. Such predicates are called two-place predicates.

Example 14

Consider the following predicates:

greaterThan is "… is greater than …"

loves is "… loves …"

belongsTo is "… belongs to …"

Then the following are two-variable propositional functions:

greaterThan(x, y) is "x is greater than y"

loves(x, y) is "x loves y"

belongsTo(x, y) is "x belongs to y"

So, for example, the following are propositions:

greaterThan(5, 2) is "5 is greater than 2"

loves(Bob, Lizzie) is "Bob loves Lizzie"

belongsTo(This coat, Harry) is "This coat belongs to Harry"

Two-place Predicates and Quantifiers

With the predicates above, we can quantify over one variable:

∀ x, belongsTo(x, me) is "Everything belongs to me"

∃ x, greaterThan(2, x) is "2 is greater than something"

∀ x, loves(Mary, x) is "Mary loves everyone"

... or both variables:

∀ x, ∃y, loves(x, y) is "Everybody loves somebody"

∃ x, ∀ y, loves(x, y) is "Somebody loves everybody"

∃ x, ∃ y, loves(x, y) is "Somebody loves somebody"

∀ x, ∀ y, loves(x, y) is "Everybody loves everybody"

Negation of Quantified Propositional Functions

In Question 5 of Exercise 1, we had to say which of several options represented the negation of a proposition. Let’s look at this again, using our Quantified Propositional Function notation.

Example 15

Consider the negation of the proposition

"All sheep are black".

The negation is:

"It is not true that all sheep are black".

which is equivalent to:

"At least one sheep is not black".

If we define the universe of discourse as {sheep} and isBlack in the obvious way, then we can symbolise all this as follows:

¬ (∀ x, isBlack(x)) ≡ ∃ x, ¬isBlack(x)

Now consider the proposition

"Some sheep are black".

The negation of this is:

"It is not true that some sheep are black"

which is equivalent to:

"All sheep are not black"

This can then be symbolised as:

¬ (∃ x, isBlack(x)) ≡ ∀ x, ¬isBlack(x)

We can generalise what we have found here to any propositional function P(x), as follows:

¬(∀ x, P(x)) ≡ ∃ x, ¬ P(x)

¬(∃ x, P(x)) ≡ ∀ x, ¬P(x)

Logic Exercise 7

Click the link for Logic Exercise 7.