Statements and negation
A sentence is true, or it is false, and never both. What single sentence swaps the two?
Where you are 9 in Logic
Why this exists
Before you can decide whether a sentence is true, you have to decide whether it is the kind of sentence that could be true at all. “Close the door” cannot be true or false; neither can “Is it raining?” Mathematics only argues about sentences that settle one way or the other, so the first job, before any proof or calculation, is picking out which sentences those are.
Once you have one, the fastest way to prove you understand it is to say exactly what would make it false. That opposite sentence is the negation, and it comes up everywhere a proof needs to rule something out: to show a shape is not a square, a number is not prime, or a line is not parallel to another, you first have to know precisely what sentence you are trying to make true.
What negation means takes one sentence to say. Using it inside longer statements needs some bookkeeping as well: a way to record, in one small table, what “not” does to every truth value a statement can have, so that the negation of a statement can be one column of a bigger table and every \neg in a formula is read as covering exactly what it covers and nothing more. That table, the truth table for not, is the second half of this lesson.
Definition
A statement is a sentence that is either true or false, and not both. It does not have to be about mathematics, and nobody has to know which one it is yet, but there has to be a fact of the matter.
- “54 is divisible by 9.” is a statement. It happens to be true.
- “Every even number greater than 2 is the sum of two primes.” is a statement, even though no one has ever proved it true or false.
- “Close the door.” is not a statement. It gives an instruction, not a claim.
- “Is 17 prime?” is not a statement. It asks a question rather than making one.
- “x + 4 = 10” is not a statement, on its own. Whether it is true depends on a number, x, that has not been fixed. Once x is given a value, say x = 6, the sentence becomes a statement, and a true one.
The negation of a statement P is the statement that is true exactly when P is false, and false exactly when P is true. It is written \neg P, read “not P”, and it can usually be built in words either as “It is not the case that P” or, more naturally, by working the word “not” directly into the sentence.
So if P is “54 is divisible by 9,” then \neg P is “54 is not divisible by 9.” The second sentence is false, because the first one is true. Negation does not judge which sentence is correct; it only builds the sentence that disagrees with the original in every single case.
A truth value is one of the two labels T (true) and F (false). A truth table lists every combination of truth values the letters in a formula can take, one combination to a row, and gives the formula’s value in each row as a column.
Intuition
Picture every possibility that could happen, everything that could be the case, as one region. A statement P carves that region into two pieces: the possibilities where P holds, and the possibilities where it does not. The negation \neg P is simply a name for that second piece.
Nothing is left over, and nothing is claimed twice. Every possibility is on exactly one side of the line, which is the whole reason a statement is useful: knowing which side you are on tells you everything the statement could tell you.
The truth table below is the same picture with the region squeezed down to its two kinds of possibility: one row for the left piece, where P holds, and one row for the right piece, where \neg P holds.
Results
Exactly one is true. For any statement P, exactly one of P and \neg P is true, and exactly one is false. They cannot both be true, and they cannot both be false. Older texts split this into two named laws: the law of the excluded middle (one of the two must be true) and the law of noncontradiction (they cannot both be true).
Double negation. Negating twice returns you to the start: \neg(\neg P) has exactly the same truth value as P itself, for every statement P. “It is not the case that 54 is not divisible by 9” and “54 is divisible by 9” say the same thing, just in more words. More generally, an even number of \neg signs stacked in front of P gives back P, and an odd number gives \neg P.
The truth table for not
One letter needs two rows. A statement P is true or false, never both and never neither, so a table for P alone has exactly two rows, with T first, the usual order:
| Row | P | \neg P |
|---|---|---|
| 1 | T | F |
| 2 | F | T |
Fill the \neg P column by swapping the letter in each row. The definition says \neg P is true exactly when P is false. Row 1 has P true, so \neg P is false there; row 2 has P false, so \neg P is true. Nothing else is consulted: not what P says, not whether anyone knows its truth value, only the single letter in the same row. That is the whole table.
Read it backwards as well as forwards. Forwards, the value of P in a row gives the value of \neg P. Backwards, the value of \neg P pins down P: if \neg P is true you must be in row 2, so P is false. Negation loses nothing on the way through. Each value of \neg P comes from exactly one row, which is not true of and, where a false P \wedge Q still leaves three rows open.
A negation can sit over any column, not only a letter. Once the column for some statement X is on the page, however long X is, the column for \neg X is made the same way, by swapping T and F row by row. Nothing inside X is recomputed, because the rule for \neg only ever looks at the truth value of what it negates. So the rows where \neg X is true are exactly the rows where X is false, and if the column of X holds k T’s out of 2^n rows, the column of \neg X holds 2^n - k.
Inside a longer table, a negation column comes after what it negates and before whatever uses it. The letters come first, in the fixed order of building a compound truth table: the first letter changes slowest, so two letters give the rows TT, TF, FT, FF. A column for \neg Q needs only the Q column, and a column that joins \neg Q to something else has to wait until \neg Q exists. Adding a \neg never adds rows: n different letters always give 2^n rows, and a negation brings in no new letter.
A \neg reaches only as far as the letter or the bracket written straight after it. So \neg P \wedge Q means (\neg P) \wedge Q, and to negate the whole conjunction you must write \neg(P \wedge Q). They are different statements with different tables, and Example 9 builds both.
Why it is true
All of these results follow from nothing more than the definition of a statement (it is true, or it is false, and there is no third option) and the definition of negation.
Exactly one of P, \neg P is true. P is true or P is false; those are the only two cases, by definition. If P is true, then by the definition of negation \neg P is false, so exactly one of the pair is true. If P is false, then \neg P is true, and again exactly one of the pair is true. Either way, one is true and the other is false, never both and never neither.
Double negation. Check the same two cases. If P is true, then \neg P is false, and negating a false statement gives a true one, so \neg(\neg P) is true too, matching P. If P is false, then \neg P is true, and negating a true statement gives a false one, so \neg(\neg P) is false, again matching P. In both cases \neg(\neg P) and P come out the same. For a longer stack, each pair of \neg signs cancels by this same argument, so an even number of them cancels completely and an odd number leaves exactly one.
The truth table for not. The table has two rows because a statement has exactly two possible truth values, and listing each once covers every case with nothing repeated. Each entry in the \neg P column is forced by the definition of negation applied to the entry beside it, so the column could not be anything other than F, T. Reading backwards works because the swap sends T to F and F to T: two different inputs never give the same output, so the output names the input. The same argument applies to any column X, since the definition of \neg X mentions only whether X is true, never what X is built from; and because every row holds a T in exactly one of the columns X and \neg X, their T’s together fill all 2^n rows, which is why \neg X has {2^n - k} of them. Finally, the row count of a table is 2^n because each of the n letters independently doubles the cases, and a \neg adds a column without adding a letter.
The two cases in each proof above are exactly the two rows of the table: listing every case is what a truth table records in a grid.
Worked examples
Deciding what is a statement
Which of these are statements? For each one that is, say whether it is true or false.
(a) “36 is a perfect square.” (b) “What time does the shop close?” (c) “y - 3 = 11.” (d) “Pineapple belongs on pizza.”
Solution(a) is a statement: it is either true or false, and in fact it is true, since 36 = 6^2.
(b) is not a statement. A question asks for information; it does not assert anything that could be true or false.
(c) is not a statement as written, because y has not been fixed. For some values of y the sentence is true (say y = 14), and for others it is false. Without a value it is neither.
(d) is not a statement. It records a preference, and there is no fact about pizza that settles it one way or the other, however strongly people disagree.
Negating a number fact
Write the negation of “51 is prime.” Is the original statement true or false? What about its negation?
SolutionThe negation replaces “is” with “is not”: “51 is not prime.”
Check the original: 51 = 3 \times 17, so 51 has a factor besides 1 and itself, and it is not prime. The original statement is false, so its negation, “51 is not prime”, is true.
Fixing a sentence with a free variable
Is “x + 5 = 12” a statement? Is “x + 5 = 12 when x = 7” a statement, and is it true? Write its negation.
Solution“x + 5 = 12” alone is not a statement: x could be any number, and the sentence is true for some values and false for the rest.
“x + 5 = 12 when x = 7” fixes the value, so it is a statement. Substituting, 7 + 5 = 12, which is a true equation, so the statement is true.
Its negation is “x + 5 \neq 12 when x = 7”, and since the original is true, this negation is false.
Negating an inequality
Write the negation of “n > 12”, where n stands for one particular whole number. Explain why the negation is “n \leq 12” and not “n < 12”.
SolutionThe negation must be true in exactly the cases where “n > 12” is false, and false in exactly the cases where “n > 12” is true.
“n > 12” is false whenever n is 12 or smaller, since 12 itself does not satisfy n > 12: substituting n = 12 gives 12 > 12, which is false. So the case n = 12 has to be included in the negation, along with every n below 12. That range is exactly n \leq 12, so the negation is “n \leq 12”. Leaving out the boundary case, as “n < 12” would, misses the value n = 12: there the original is false, so the negation must be true there, and “n < 12” is false at n = 12.
Negation and a double check
Let P be “36 is divisible by 4.” Write \neg P and \neg(\neg P), and give the truth value of all three.
Solution36 \div 4 = 9 with no remainder, so P is true.
\neg P is “36 is not divisible by 4”, which is false, since P is true.
\neg(\neg P) is “It is not the case that 36 is not divisible by 4”, which is true, matching P exactly as the double negation result says it must.
Building the table for a named statement
Let P be “91 is prime.” Build the table for \neg P, and say which row this particular P falls in.
SolutionThe table itself does not depend on what P says, so it is the two general rows:
| Row | P | \neg P |
|---|---|---|
| 1 | T | F |
| 2 | F | T |
Now decide which row applies. 91 = 7 \times 13, so 91 has a factor other than 1 and itself, and P is false. That is row 2, so \neg P is true: “91 is not prime” is a true statement.
Stacking negations
Let P be “40 is a multiple of 5.” Build a table with columns P, \neg P, \neg(\neg P) and \neg(\neg(\neg P)), and say which row this particular P falls in.
SolutionEach new column negates the one just before it, so each is that column with T and F swapped:
| Row | P | \neg P | {\neg(\neg P)} | {\neg(\neg(\neg P))} |
|---|---|---|---|---|
| 1 | T | F | T | F |
| 2 | F | T | F | T |
The \neg(\neg P) column matches the P column row for row. That is the double negation result, now seen as two equal columns. The next column matches \neg P, and the pattern carries on for as long as you stack negations: every two swaps cancel, so an even number of \neg signs in a row gives back the column of P, and an odd number gives the column of \neg P.
40 = 5 \times 8, so P is true and this P is in row 1. Reading across, \neg(\neg(\neg P)) is false there, exactly as “40 is not a multiple of 5” is.
Negating a finished column
The table for or gives the column of P \vee Q as T, T, T, F. Build the column for \neg(P \vee Q), and say in words when it is true.
SolutionThe \neg stands in front of a bracket, so it negates the whole of P \vee Q. Its column is built from the P \vee Q column alone, swapping each entry; the P and Q columns are not looked at again.
| Row | P | Q | {P \vee Q} | {\neg(P \vee Q)} |
|---|---|---|---|---|
| 1 | T | T | T | F |
| 2 | T | F | T | F |
| 3 | F | T | T | F |
| 4 | F | F | F | T |
\neg(P \vee Q) is true only in row 4, the one row where P \vee Q is false, which is the row where P and Q are both false. In words it says “neither P nor Q”. The three T’s above became three F’s, and the one F became a T: a negation swaps which rows are true, while the number of rows stays four.
Where the \neg stops: two different statements
Build the tables for \neg P \wedge Q and \neg(P \wedge Q), and say in which rows they disagree.
SolutionBoth need four rows. \neg P \wedge Q flips P first and then joins it to Q, so its table needs the \neg P column before its own:
| Row | P | Q | \neg P | {\neg P \wedge Q} |
|---|---|---|---|---|
| 1 | T | T | F | F |
| 2 | T | F | F | F |
| 3 | F | T | T | T |
| 4 | F | F | T | F |
\neg(P \wedge Q) joins first and then flips the result, so its table needs the P \wedge Q column instead:
| Row | P | Q | {P \wedge Q} | {\neg(P \wedge Q)} |
|---|---|---|---|---|
| 1 | T | T | T | F |
| 2 | T | F | F | T |
| 3 | F | T | F | T |
| 4 | F | F | F | T |
Reading the two final columns against each other, they agree in rows 1 and 3 and disagree in rows 2 and 4. Row 2 shows the difference plainly: P is true and Q is false, so P \wedge Q is false and its negation is true, while \neg P is false, which already makes \neg P \wedge Q false. Moving the bracket moved the \neg from P alone to the whole conjunction, and the statement changed with it.
Three letters, two of them negated
Build the table for \neg P \wedge (Q \vee \neg R).
SolutionThree letters give 2^3 = 8 rows. Two negations each cover a single letter, so \neg P is built from the P column and \neg R from the R column:
| Row | P | Q | R | \neg P | \neg R |
|---|---|---|---|---|---|
| 1 | T | T | T | F | F |
| 2 | T | T | F | F | T |
| 3 | T | F | T | F | F |
| 4 | T | F | F | F | T |
| 5 | F | T | T | T | F |
| 6 | F | T | F | T | T |
| 7 | F | F | T | T | F |
| 8 | F | F | F | T | T |
Only then can the bracket Q \vee \neg R be filled, from the Q and \neg R columns, and last of all the conjunction, from the \neg P column and the bracket. The rows below are the same eight rows, in the same order, so row 5 here is row 5 above, with P false and Q and R true:
| Row | \neg P | {Q \vee \neg R} | {\neg P \wedge (Q \vee \neg R)} |
|---|---|---|---|
| 1 | F | T | F |
| 2 | F | T | F |
| 3 | F | F | F |
| 4 | F | T | F |
| 5 | T | T | T |
| 6 | T | T | T |
| 7 | T | F | F |
| 8 | T | T | T |
In rows 1 to 4, P is true, so \neg P is false and the conjunction is false whatever the bracket says. Only in rows 5 to 8 is anything left to decide, and there the answer is the Q \vee \neg R column: false only in row 7, where Q is false and \neg R is false.
Negation as a proof strategy
Write the negation of “97 is prime,” and use it to decide whether the statement is true without testing all 95 possible divisors from 2 to 96.
Solution“97 is prime” means 97 has no whole-number factor other than 1 and itself. Its negation, “97 is not prime,” means 97 does have such a factor: 97 = a \times b for some whole numbers a and b, both between 2 and 96.
If that were so, the smaller of a and b would be at most \displaystyle \sqrt{97} \approx 9.8, because two factors both bigger than \displaystyle \sqrt{97} multiply to more than 97. So the negation can only be true if one of 2 through 9 divides 97. None does: 97 is odd, so 2, 4, 6 and 8 fail; its digits add to 16, so 3 and 9 fail; it does not end in 0 or 5, so 5 fails; and 97 = 7 \times 13 + 6, so 7 fails. The negation is false, and by the first result above, that makes the original statement true. Turning a claim into “show the negation fails” is one of the most common moves in proof; building an argument out of statements like these is the next step.
Boundaries
A free variable stops a sentence from being a statement. “x < 5” is not a statement by itself, because its truth depends on a value nobody has supplied, so it has no truth value to put in a row of a table either. Two different fixes exist: substitute a specific number, as in the worked examples above, or bind the variable with a quantifier such as “for every x” or “there is an x”, which is the subject of quantifiers.
Negating an open sentence is still meaningful, as a rule. A sentence like “x \leq 5” is not a statement on its own, yet it is completely reasonable to ask for its negation, “x > 5”, because that negation is a promise: whatever fixed number is substituted for x, the two sentences will always land on opposite sides, one true and one false. The exercises below use this shortcut for comparisons, even though, strictly, each side is only a statement once a number is chosen. The swap of \leq for > leans on a fact about real numbers: for any two of them, exactly one of “less than”, “equal to” and “greater than” holds. Where that fails, so does the swap; complex numbers, for instance, cannot be put in order at all.
The two-row table needs exactly two truth values. The table lists T and F and nothing else because a statement is true or false, never both and never neither. Some systems deliberately allow a third value, such as “unknown” in database logic, and there the negation of unknown is again unknown: the two-row table and the swap rule no longer cover every case.
Not knowing the truth value is not the same as having none. “Every even number greater than 2 is the sum of two primes” is a statement, and a true one as far as every case ever checked goes, yet no one has proved it for all even numbers. It still has exactly one truth value; the gap is in what is known, not in what the sentence is.
Moving one bracket makes a different statement. \neg P \vee Q and \neg(P \vee Q) use the same symbols in the same order and differ only by a bracket, yet their columns, T, F, T, T and F, F, F, T, disagree in rows 1 and 3. Deciding what each \neg covers comes before any row is filled in.
The table swaps truth values, not words. It says \neg P is true exactly when P is false; it does not say how to write \neg P as a sentence. The negation of “n > 12” is “n \le 12”, not “n < 12”, as Example 4 shows, and a sentence with “every” or “some” in it takes more care still, which is the job of negating a quantified statement.
The table is about the pattern, not about one statement’s real truth value. It says what \neg P comes to for each possible value of P. Deciding which row a particular P, such as “91 is prime”, actually sits in is a separate step, done outside the table, as in Example 6.
Negation flips a claim, it does not weaken it. \neg P is not “P is unlikely” or “P is usually false.” It is a full statement of its own, exactly as strong as P, just true in the opposite cases.
Where this goes next
Negation is the simplest of the logical connectives: the other four, “and”, “or”, “if...then” and “if and only if”, combine two statements, while negation works alone on one. Each of those adds its own column rule once the plain and negated columns are ready, and building a compound truth table is the general method for putting all those columns together in the right order.
Two patterns are worth watching for once a \neg column is in hand. A statement whose final column is all T, such as P \vee \neg P, is a tautology, and one whose final column is all F, such as P \wedge \neg P, is a contradiction. Negating a column swaps one kind for the other.
Once compound statements are built, their own negations follow rules of their own; negating an “and” turns it into an “or” and negating an “or” turns it into an “and”, which is De Morgan’s laws for statements. Setting the column of \neg(P \wedge Q) beside the column of \neg P \vee \neg Q is how those laws get checked.
Negation also shows up the moment a statement talks about a whole collection rather than one fixed case. Turning “for all” into “there exists” is exactly what happens when you negate a quantified statement, once Quantifiers are in place.
And once “if P then Q” is on the table, negation is what builds its inverse and contrapositive, two of the converse, inverse, and contrapositive. Only the contrapositive says the same thing as the original; the converse and the inverse say the same thing as each other, and not always the same as the original.
Exercises
Statement or not
- “102 is divisible by 3.”
- “Please turn off the lights.”
- “x - 5 = 12”
- “Is every multiple of 4 even?”
- “Rocky road is the best ice cream flavor.”
Writing negations
- Write the negation of “The train leaves at six o’clock.”
- Write the negation of “17 is prime.” Is the original true or false? What about the negation?
- “n is even,” where n stands for one particular, but unstated, whole number. Explain why this is a statement even though you cannot say whether it is true, and write its negation.
- Write the negation of “\displaystyle \sqrt{2} is a rational number.” Which one, the statement or its negation, is true?
- Negate the sentence you wrote for Exercise 7. What do you notice about the result, and why does the double negation result guarantee it?
Negating comparisons
In Exercises 11 to 14, x stands for one particular real number.
- Negate “x = 5.”
- Negate “x < 5.”
- Negate “x \geq 5.”
- Negate “x \neq 5.”
Truth values
- Is “91 is prime” true or false? What is the truth value of its negation?
- Is “50 is a perfect square” true or false? What is the truth value of its negation?
- Let P be “8 is a factor of 36.” Is P true? Is \neg P true?
Building the table for not
- Let P be “57 is prime.” Build the table for \neg P, say which row applies, and state whether P and \neg P are true or false.
- Let P be “\displaystyle \sqrt{81} = 9.” Build the table for \neg P, say which row applies, and state whether P and \neg P are true or false.
- Let P be “2^{10} = 1000.” Build the table for \neg P, say which row applies, and state whether P and \neg P are true or false.
- You are told only that \neg P is true. Which row of the table for \neg P are you in, and what is the truth value of P?
Stacking negations
- Let P be “63 is a multiple of 9.” Build the table for P, \neg P and \neg(\neg P), and say which row applies to this P.
- Let P be “2 + 2 = 5.” Build the table for P, \neg P and \neg(\neg P), and say which row applies to this P.
- A statement is P with seven \neg signs stacked in front of it, each negating everything after it. Without writing seven columns, give its column in rows 1 and 2.
- Explain why the columns for \neg P and \neg(\neg P) can never agree in any row.
Negating a column
- A statement S in P and Q has the column T, F, T, T in rows 1 to 4. Write the column for \neg S and name every row in which \neg S is true.
- Build the column for \neg(P \wedge Q \wedge R) over eight rows. In how many rows is it true?
- In a table with 2^n rows, the column for a statement X has k T’s. How many T’s does the column for \neg X have?
Negation inside a bigger table
- Build the truth table for \neg(\neg P \wedge Q).
- Build the truth table for \neg P \vee Q.
- Build the truth table for \neg(\neg P \vee \neg Q).
- Build the truth table for (P \vee Q) \wedge \neg P.
- Build the truth table for (\neg P \vee Q) \wedge \neg R.
Where the not stops
- Build the truth tables for \neg P \wedge Q and \neg(P \wedge Q), and state every row in which they disagree.
- Build the truth tables for \neg P \vee \neg Q and \neg(P \vee Q), and state every row in which they disagree.
Reasoning
- Explain why “x + 3 = 9” is not a statement, and describe two different ways to turn it into one.
- Give an example of a sentence that is a statement even though nobody currently knows whether it is true, and explain why not knowing does not stop it from being a statement.
- A statement and its negation can never both be true, and can never both be false. Explain why, using only the definition of a statement, and say what this means for the columns of P and \neg P in each row of a truth table.
- Without building the whole table, explain why the final column of P \vee \neg P must be all T.
- Without building the whole table, explain why the final column of P \wedge \neg P must be all F.
- Explain why writing a \neg in front of a statement never changes how many rows its truth table needs.
- Let P be “the number is even” and Q be “the number is a multiple of 3.” Write “The number is not even, and it is not a multiple of 3” and “It is not the case that the number is even and a multiple of 3” in symbols, and find a whole number from 1 to 6 for which the two sentences have different truth values.
Answers
- This is a statement, and it is true: 102 = 3 \times 34, so 3 divides it evenly.
- Not a statement. It is an instruction, not a claim that could be true or false.
- Not a statement as written. x has no fixed value, so the sentence is true for some numbers and false for others.
- Not a statement. It is a question.
- Not a statement. It expresses a preference, with no fact that settles it.
- “The train does not leave at six o’clock.”
- “17 is not prime.” The original is true, since 17 has no factor besides 1 and itself, so the negation is false.
- It is a statement because n is one particular whole number, even though which one is not said; whichever number it is, it is either even or it is not, so the sentence has a fixed truth value, just not one you can name without knowing n. Its negation is “n is not even,” which for a whole number is the same as “n is odd.”
- “\displaystyle \sqrt{2} is not a rational number.” \displaystyle \sqrt{2} is irrational, so the negation is the true one and the original statement is false.
- “It is not the case that 17 is not prime,” which says the same thing as “17 is prime.” That is the double negation result: “17 is prime,” negated twice, comes back to itself.
- “x \neq 5.”
- “x \geq 5.”
- “x < 5.”
- “x = 5.”
- False. 91 = 7 \times 13, so it is not prime. Its negation, “91 is not prime,” is true.
- False. 7^2 = 49 and 8^2 = 64, and 50 falls strictly between them, so no whole number squares to 50. The negation, “50 is not a perfect square,” is true.
- P is false: 36 \div 8 = 4.5, not a whole number, so 8 is not a factor of 36. Since P is false, \neg P, “8 is not a factor of 36,” is true.
- Row 2. 57 = 3 \times 19, so P is false and \neg P is true. The table is the two general rows: P reads T, F and \neg P reads F, T.
- Row 1. 9^2 = 81 and 9 > 0, so \displaystyle \sqrt{81} = 9; P is true and \neg P is false. Table: P reads T, F and \neg P reads F, T.
- Row 2. 2^{10} = 1024 \ne 1000, so P is false and \neg P is true. Table: P reads T, F and \neg P reads F, T.
- Row 2, and P is false. \neg P is T only in row 2, and P is F in that row.
- Row 1. 63 = 9 \times 7, so P is true: P true, \neg P false, \neg(\neg P) true. The table’s columns are T, F for P, then F, T, then T, F.
- Row 2. 2 + 2 = 4 \ne 5, so P is false: P false, \neg P true, \neg(\neg P) false. The columns are the same as in Exercise 22.
- F, T, the column of \neg P. Six of the seven swaps cancel in pairs, which leaves one.
- \neg(\neg P) is the column of \neg P with every entry swapped, so in each row it holds the other letter. Two columns that hold opposite letters in every row agree in none.
- F, T, F, F. \neg S is true only in row 2, the one row where S is false.
- F, T, T, T, T, T, T, T: true in 7 rows. P \wedge Q \wedge R is true only in row 1, where all three letters are T, so its negation is false there and true in the other seven.
- 2^n - k. Each of the 2^n rows holds a T in exactly one of the two columns, so the T’s of \neg X are the rows left over from the k T’s of X.
- Rows 1 to 4 give T, T, F, T. \neg P \wedge Q is F, F, T, F, true only in row 3, and the outer \neg swaps every entry.
- Rows 1 to 4 give T, F, T, T. \neg P is F, F, T, T, and \vee with Q fails only in row 2, where both sides are false.
- Rows 1 to 4 give T, F, F, F. \neg P is F, F, T, T and \neg Q is F, T, F, T, so \neg P \vee \neg Q is F, T, T, T, false only in row 1; the outer \neg swaps every entry, leaving the column of P \wedge Q.
- Rows 1 to 4 give F, F, T, F. P \vee Q is T, T, T, F and \neg P is F, F, T, T; both are true only in row 3.
- Rows 1 to 8 give F, T, F, F, F, T, F, T. \neg R is true only in the even rows, and of those \neg P \vee Q is false only in row 4, where P is true and Q false.
- \neg P \wedge Q is F, F, T, F and \neg(P \wedge Q) is F, T, T, T. They disagree in rows 2 and 4.
- \neg P \vee \neg Q is F, T, T, T and \neg(P \vee Q) is F, F, F, T. They disagree in rows 2 and 3.
- “x + 3 = 9” has a free variable, x, so its truth is not settled: it is true when x = 6 and false for every other value. It becomes a statement either by substituting a specific number for x, as in “x + 3 = 9 when x = 6,” or by attaching a quantifier, as in “there exists an x such that x + 3 = 9.”
- For example, “Every even number greater than 2 is the sum of two primes.” Nobody has proved this true or false for every even number, but the sentence still asserts something definite: either every such number splits that way, or some one of them does not. Not knowing which is a limit on current knowledge, not a hole in the sentence itself; the statement has a truth value whether or not anyone has found it.
- By definition, a statement is true or false and never both, so P cannot be both true and false at once. If P is true, then by the definition of negation \neg P is false, so they cannot both be true. If P is false, then \neg P is true, so they cannot both be false either. Every case is covered by “P is true” or “P is false,” so there is no way around this. In a truth table, each row has P holding exactly one letter and \neg P holding the other, so the two columns hold exactly one T and one F between them in every row.
- In every row, P and \neg P hold opposite letters, so one of them is T. \vee is true whenever at least one side is true, so P \vee \neg P is true in every row.
- In every row, one of P and \neg P is F. \wedge is true only when both sides are true, so P \wedge \neg P is false in every row.
- The row count is 2^n, where n is the number of different letters, since each letter independently doubles the cases. A \neg adds a column worked out from one already there, but no new letter, so n and the row count stay the same.
- The first is \neg P \wedge \neg Q, the second \neg(P \wedge Q). The number 4 works: 4 is even and not a multiple of 3, so P is true and Q false. Then \neg P \wedge \neg Q is false, since \neg P is false, while P \wedge Q is false and so \neg(P \wedge Q) is true. (2 works for the same reason, and so does 3, with P false and Q true.)