Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 6.1.5 Necessary and Sufficient Conditions

We’ve already talked about necessary and sufficient conditions in the context of Boolean logic. (You might want to take another look at that video now.)

Recall that:

• P is a sufficient condition for Q if, whenever P is true, Q must also be true (regardless of any other conditions). Put another way:

P → Q If P then Q.

• P is a necessary condition for Q if Q cannot be true without P also being true. Put another way:

Q → P Q only if P.

So, if we write Q if and only if P (sometimes shortened to Q iff P), we have:

(P → Q) ∧ (Q → P)

In other words, P and Q must have the same truth value. So we have:

P ≡ Q

This is typically what we want to say when we are defining P. We’ll also use it for other things, for example requirements specifications.

We’ve been exploiting if and only if all along. In some cases, we’ve used the mathematics convention of writing just “if” when we mean “iff”. But now that we actually know how to reason with the sentences that we write, it makes sense to consider some more examples.

Let’s encode the rule for deciding when leap years occur:

A year is a leap year if and only if it is divisible by 4 but not divisible by 100 unless it is also divisible by 400.

Define:

Leap(y): True if y is a leap year.

Div(x, y): True if x is evenly divisible by y.

Now we can write the leap year rule as a logical expression:

[1] y (Leap(y)  (Div(y, 4)  (Div(y, 100)  Div(y, 400))))

Read [1] as, “y is a leap year if and only if it is divisible by 4 and (it is not divisible by 100 or it is divisible by 400.)” Notice that we had to use parentheses to make the English sentence unambiguous. Also, notice that our or statement is, as usual, inclusive or. So, in principle, if y were not divisible by 100 but divisible by 400, it would be a leap year. Except, of course, that’s not possible. So we don’t actually have to consider it.

Let’s see how we can use [1] to decide whether a given year is a leap year. Assume that we can appeal to an arithmetic engine to tell us whether Div(x, y), where x and y are specific numbers, is true. So, for example, Div(100, 4) will return T, since 100 is divisible by 4. Div(100, 7) will return F.

Let’s see whether 2000 was a leap year:

[1] y (Leap(y) \(\equiv\) (Div(y, 4) \(\wedge\) (\(\neg\)Div(y, 100) \(\vee\) Div(y, 400)))) Definition

[2] Leap(2000) \(\equiv\) (Div(2000, 4) \(\wedge\) (\(\neg\)Div(2000, 100) \(\vee\) Div(2000, 400))) Universal Instantiation [1]

[3] Leap(2000) \(\equiv\) (T \(\wedge\) (\(\neg\)T \(\vee\) T)) Arithmetic [2]

[4] Leap(2000) \(\equiv\) (T \(\wedge\) T) Computation [3]

[5] Leap(2000) \(\equiv\) T Computation [4]

So we have that Leap(2000) is true.