Logic: Not & And – Foundations of Mathematics

Statements by themselves aren't that interesting; let's see how to combine them.

"not"

A writing teacher once told me the best way to clean up your writing is to eliminate as many adverbs and adjectives as possible. But one very important adverb--which changes the meaning of anything it touches--is the word not. Let's formalize this.

Definition. Given a statement $S$ , the statement $\sim S$ (read It is not the case that $S$ or the abbreviated version not $S$ is true exactly when $S$ is false.

Note that if $S$ is a statement, it's either true or false; in either case, we know what truth value $\sim S$ has. So $\sim S$ is by definition a statement. Also note the word exactly, which modifies when.

Proposition 1. $\sim \sim S$ is true exactly when $S$ is true.

Proof. There are only two kinds of statements $S$ , namely true and false.

If $S$ is false, then $\sim S$ is true (this is the definition of $\sim$ ). But the only (that's the exactly in the definition of $\sim$ ) way for $\sim \sim S$ to be true would be if $\sim S$ were false; since $\sim S$ is true, we know $\sim \sim S$ is false. So in this situation, $S$ and $\sim \sim S$ are both false.

If $S$ is true, then $\sim S$ is false (remember, $\sim S$ is only true when $S$ is false). So $\sim \sim S$ is true. So here again, $S$ and $\sim \sim S$ agree with one another.

In both cases, we've seen that $S$ and $\sim \sim S$ agree. Thus when $S$ is true, $\sim \sim S$ is true; and this is the only way for $\sim \sim S$ to be true. $\Box$ .

Notice that $\sim \sim S$ is a different statement from $S$ . For example, if $S$ is I wear a plaid shirt every day, then

$\sim S$ is It is not the case that I wear a plaid shirt every day and
$\sim \sim S$ is It is not the case that it is not the case that I wear a plaid shirt every day.

But of course $\sim \sim S$ and $S$ are the same insofar as truth goes. One might say they mean the same thing.

To make better formal sense of the distinction between being the same statement and merely being statements that mean the same thing, we need the following definition:

Definition. A propositional formula or propositional form is a string of logical connectives and variables, so that when each of the variables is substituted with a statement, the result is a statement.

For example, $\sim Q$ is a propositional formula because if we supply a statement in place of $Q$ , we obtain a statement.

Definition. Two propositional forms are equivalent if, whenever we substitute the same statements in for their variables, we obtain statements with the same truth values.

Armed with this definition, we can rewrite Proposition 1 in a different way:

Restatement of Proposition 1. $Q$ and $\sim \sim Q$ are equivalent.

denials, useful and otherwise

Definition. A formula equivalent to $\sim P$ is called a denial

Observe that we've just used the word "denial" to mean two different, but related, things: there are denials of formulae, and denials of statements. One should be careful to keep track of subtle differences like this, which happen so often most mathematicians eventually just learn not to notice them anymore.

of $P$ . If we plug a statement in to the variable $P$ , we obtain a denial of that statement.

E.g. $\sim\sim\sim Q$ and $\sim\sim\sim\sim\sim Q$ are denials of $Q$ . $\sim\sim T$ is a denial of $\sim T$ .

E.g. A denial of Andrew Cooper is from Texas is It is not the case that Andrew Cooper is from Texas.
Another denial is Andrew Cooper is not from Texas.
Another denial is Andrew Cooper is either from someplace other than Texas, or he is not from anyplace in particular, a drifter if you will, rootless, without a home.

These examples show that there are many different denials of any given formula or statement.

One question I want you to ask, and to keep asking is: is a given formulation of a statement useful to me? Utility is in the eye of the beholder, so I won't give you a formal definition of what I mean when I say useful denial. But I'll say this: merely attaching It is not the case that... to the beginning of a statement probably will not yield any insight.

You might be asking yourself: why should I expect that formulating a denial would yield any insight, anyway? Here's why, and it's a very important less in thinking that I hope you take away from this course into the rest of your life beyond mathematics. Statements are, by definition, either true or false (and not both). So, when we are faced with a statement we don't understand (or wish to understand better, or wish to prove), we usually ask questions like

What does this statement mean?
If this statement were true, what else would be true?
When have I encountered similar (or just similar-looking) statements in the past?

These are great questions, but they don't always get us where we need to go. Sometimes they can even lead us astray. Since we know that the statement in question is either true or false, we could as well ask about it:

What would it mean for this statement to be false?

That is, we could formulate a denial of the statement. If we articulate all the ways the statement could be false, then we have also articulated what it means for the statement to be true: that's just everything not on our list.

I call this method what-if-not thinking, and we're going to use it a lot. But it depends, critically, on being able to formulate denials precisely and accurately. (Don't worry, we'll develop lots of practice.)

truth tables

Definitions like that of $\sim$ are kind of hard to read, so let's record them symbolically. We can think of $\sim P$ as being like a function: you tell it the truth value of $P$ , and it tells you the truth value of $\sim P$ . So, just like you first did in some long-ago algebra class, we can record the values in a table. We call such a table a truth table. The truth table for $\sim$ looks like this:

$P$	$\sim P$
T	F
F	T

We can make a truth table for any formula; here's the truth table for $\sim\sim P$ :

$P$	$\sim\sim P$
T	T
F	F

Observe that we always list the input values (the first column) in the same order.

It's pretty clear that Two formulae are equivalent if the output columns of their truth tables are the same.

"and"

not was nice, but it only acts on one statement or formula. (We call such operations unary, from the Latin unus "one".) Let's get some binary operations: operations which combine two statements or formulae. We'll start with the word and.

Before reading any further, make sure you've done the preticipation exercise: read the dictionary.com entry on the word and and see if it would help you understand what the word meant, if you didn't already know. Try this definition also.

Instead of giving a wordy definition, I'll just give the truth table for "and". The symbol we use is $\wedge$ . Since there are two inputs, each of which has two possible truth values, there are four possible inputs:

$P$	$Q$	$P\wedge Q$
T	T	T	1
T	F	F	2
F	T	F	3
F	F	F	4

Because we're going to use this table rather than just look at it, I've given numbers to the rows.

Let's play around a bit with this. What's $Q\wedge P$ ? We'll make a truth table. In order to compare it with the truth table for $P\wedge Q$ , we need to list the inputs in the same order.

$P$	$Q$	$Q\wedge P$
T	T	T	1
T	F	F	3
F	T	F	2
F	F	F	4

Look carefully at the row labels. In order to populate row 2 of the $Q\wedge P$ table, we have to look at row 3 of the $P\wedge Q$ table -- this row is the "FALSE and TRUE" row.

We can conclude from this truth table that

Proposition. $P\wedge Q$ and $Q\wedge P$ are equivalent formulae.

Or, somewhat more pithily, we say

Restatement of Proposition. $\wedge$ is commutative.

While this proposition may not surprise you, it does indicate a slight difference from the ordinary-English word and.

Let's try something else out, too: what about $(P\wedge Q)\wedge R$ ? This time we're have three inputs, each of which has two possible truth values, for a total of $2\times 2\times 2=8$ possible input truth values:

$P$	$Q$	$R$	$P\wedge Q$	$(P\wedge Q)\wedge R$
T	T	T	T	T	1
	T	F	T	F	2
	F	T	F	F	3
	F	F	F	F	4
F	T	T	F	F	3
	T	F	F	F	4
	F	T	F	F	3
	F	F	F	F	4

Here I've done two tricks: first, instead of writing so many Ts and Fs, I combined some rows in the $P$ and $Q$ columns to make the table easier to read. Second, I wrote down the intermediate step of computing $P\wedge Q$ as a separate column. The last column records which row of the truth table for $\wedge$ I used to go combine the values in the third and fourth columns to get the truth value in the last column.

Exercise. Make a truth table for $P\wedge(Q\wedge R)$ .

Proposition. $(P\wedge Q)\wedge R$ is equivalent to $P\wedge(Q\wedge R)$ .

The pithy way to say this is

Restatement of Proposition. $\wedge$ is associative.

Finally, let's do two truth table computations with $\sim$ and $\wedge$ :

Exercise. Make truth tables for $P\wedge (\sim P)$ and $\sim\left( (\sim P)\wedge P\right)$ . Before beginning this, think hard about how many rows and how many columns your truth table will require. Then see if you notice anything interesting.

Tautologies and Contradictions

The result of the previous exercise will leave us with the need for the following definition:

Definition. A formula which always has a truth value of T, no matter what inputs it takes, is called a tautology. A formula which always has a truth value of F, no matter what inputs it takes, is called a contradiction.

If we're thinking of propositional formulae as functions, then tautologies and contradictions are the constants. (There are only two constant functions, because statements can only be true or false (and not both).)

The philosopher's version of this definition goes something like A tautology is a sentence that is true in virtue of its form. and A contradiction is a sentence that is false in virtue of its form., the point being that neither a tautology nor a contradiction can contain much in the way of meaningful content, because its form gets in the way. But that's all a bit above our heads.

Shades of Meaning

Here's a shocking claim:

and and but mean the same thing.

What do I mean by this? Consider the two statements:

I have a dog and he weighs twelve pounds.
I have a dog but he weighs twelve pounds.

In terms of the facts on the ground, what do we know in situation 1? That I have a dog. That the dog weighs twelve pounds. What do we know if situation 2? Exactly the same information!

So what's different? Presumably, if I'm saying statement 2, it's because I'm vaguely embarrassed to have such a small dog (sorry, Mugzy). That is, the difference between and and but lies in how the speaker feels about the circumstances. And because that's not something that can be true or false, our logical framework just doesn't care about it.

You might think this is a bug, but I see it as a feature. (Perhaps better to say: you might see this as a bug, and I see it as a feature.) It will allow us to subtly influence our reader's perception -- and our own perception -- in ways that may make our written proofs clearer and easier to understand.

A neat thinking trick you can deploy to help make sure you aren't being unduly influenced (say, when you're watching talking heads): every time someone says but, just repeat what they said with an and instead. And make sure you don't use but when you mean and.