Discrete Mathematics and Proof

Tautologies and contradictions

A compound statement’s letters can be true or false in every possible way there is. Can its form alone force it to be true in every case, or false in every case, and what is either one good for?

You need

Building a truth table for a compound statementDiscrete Mathematics and Proof

Where you are 3 in Truth tables

Logic, proof and discrete math6

Logic9

Truth tables3

Building a truth table for a compound statement

Tautologies and contradictions

Truth table for the conditional

Why this exists

Building a table for a compound statement usually gives a mixed column: some rows T, some F, depending on which combination of true and false you plugged into the letters. That is the ordinary case. Whether “the shop is open” is true depends on the shop: you have to go and look. Joining it to other statements with “and”, “or” and “not” usually keeps that dependence, and the compound is true in some situations and false in others.

Every so often the last column comes out T on every single row, however the letters are chosen. That is no longer luck: it means the connectives alone force the truth, with no help at all from what P or Q stand for. You could let P be “the bus is late” and Q be “seven is prime”, or any other pair of sentences at all, and the compound statement would still come out true, because nothing about it ever asked whether P or Q were actually true. Such a statement is a tautology, and it turns out to be exactly the fact underneath why some arguments work regardless of their subject matter, and why two differently written statements can be guaranteed to say the same thing.

The column can also come out F on every row. “The shop is open and the shop is not open” is false before anyone looks at the shop, and it would be false whatever shop it named. Its falsehood comes from how it is built, not from the world. A statement like that is a contradiction. Recognizing one pays twice. A claim with the form of a contradiction can be rejected without gathering any evidence. And reaching a contradiction is the finishing move of one of the strongest methods of proof: if an assumption leads to a statement that cannot be true, the assumption was false.

Definition

Tautology

A statement is a tautology when its truth table has T in the last column on every row: true for every possible assignment of true and false to its letters, with no exception anywhere in the table.

S \text{ is a tautology} \iff S \text{ is T on every row}

Contradiction

A statement is a contradiction when its truth table has F in the last column on every row: false for every way of assigning true and false to the simple statements it is built from.

S \text{ is a contradiction} \iff S \text{ is F on every row}

The plainest one is P \wedge \neg P, “P and not P”:

Row	P	\neg P	P \wedge \neg P
1	T	F	F
2	F	T	F

Contingent statements, and contradictory pairs

A statement that is T on some rows and F on others is neither a tautology nor a contradiction: it is contingent, and most compound statements are. So every compound statement is exactly one of three kinds: a tautology, a contradiction, or neither. Each kind is a property of the whole table, not of any one row, so deciding it means accounting for every row.

Two statements are contradictory when they have opposite truth values in every row, as P and \neg P do. Joining two contradictory statements with “and” always gives a contradiction, because in every row one of the two is false; joining them with “or” always gives a tautology, because in every row one of the two is true.

Intuition

A truth table lists every possible world the letters could describe: every combination of true and false there is, with nothing left out and nothing repeated. A contingent statement wins in some of those worlds and loses in others. A tautology wins in every one of them, and a contradiction holds in none of them. Neither is telling you a fact about the world the letters describe; each is telling you a fact about how the connectives were put together, one that would survive no matter which world turned out to be the real one.

Because the verdict comes from the form, it survives substitution. Replace P in P \wedge \neg P by any statement at all, “7 is prime”, “x > 2” or a long compound, and the result is still false in every row. The table never looked at what P says, only at whether it is true.

There is also a way to see a contradiction without writing the table: try to make the statement true, and watch the attempt collapse. To make (P \to Q) \wedge P \wedge \neg Q true, every part must be true. So P is true and Q is false, and then P \to Q is false. Every route to a true row runs into a letter that would have to be true and false at once. A tautology can be seen the same way from the other side: try to make it false, and watch that attempt collapse.

Results

Tautologies worth knowing

A short toolkit of tautologies worth recognizing on sight. Excluded middle, self-implication and simplification are checked in Examples 1 to 3, addition is Exercise 5, and non-contradiction is the negation of the all-F statement in Exercise 3:

Excluded middle: P \vee \neg P
Self-implication: P \to P
Non-contradiction: \neg(P \wedge \neg P)
Simplification: (P \wedge Q) \to P
Addition: P \to (P \vee Q)

What a tautology tests

Two further facts follow directly from the definition, and each connects tautology to a star of its own.

An argument is valid exactly when its premises-imply-conclusion conditional is a tautology. For premises P_1, \dots, P_n and conclusion C, the argument is valid exactly when

(P_1 \wedge P_2 \wedge \cdots \wedge P_n) \to C

is a tautology. This is the idea behind testing an argument with a truth table: a whole argument becomes one statement, and validity becomes the question of whether that statement’s column is all T.

Two statements are logically equivalent exactly when their biconditional is a tautology. Two compound statements A and B are logically equivalent exactly when

A \leftrightarrow B

is a tautology.

What a contradiction does

Negation swaps the two extremes. S is a contradiction exactly when \neg S is a tautology, and S is a tautology exactly when \neg S is a contradiction.

A contradiction implies anything. If C is a contradiction, then C \to Q is a tautology for every statement Q. So an argument whose premises together form a contradiction is valid, whatever its conclusion says.

“And” absorbs a contradiction; “or” ignores it. If C is a contradiction and S is any statement, then S \wedge C is a contradiction, and S \vee C has the same truth table as S.

Reaching a contradiction proves the opposite of the assumption. If C is a contradiction, then \neg P \to C has the same truth table as P.

Why it is true

Why the argument link holds. An argument is valid when there is no row in which every premise is T and the conclusion is F: no case where the premises hold and the conclusion still fails. Use one table whose rows run over every letter in the premises and the conclusion. The conditional (P_1 \wedge \cdots \wedge P_n) \to C is F on a row exactly when its hypothesis P_1 \wedge \cdots \wedge P_n is T and C is F on that row. A conjunction is T exactly when every one of its parts is T, so that is exactly a row where every premise holds and the conclusion fails. So the conditional has an F row exactly when the argument has a counterexample row, and the conditional is a tautology (no F row at all) exactly when the argument has no counterexample row, which is what valid means.

Why the equivalence link holds. Use one table whose rows run over every letter in A and B. By the rule for \leftrightarrow, A \leftrightarrow B is T on a row exactly when A and B agree on that row, both T or both F. Two statements are logically equivalent exactly when they agree on every row. So A \leftrightarrow B is T on every row, a tautology, exactly when A and B agree on every row, which is what logically equivalent means.

Why negation swaps the extremes. \neg S is T on a row exactly when S is F there, so the column of \neg S is the column of S with every entry flipped. A column of all F becomes a column of all T, and a column of all T becomes a column of all F. Flipping twice gives back the original column, so each direction of the statement follows from the other.

Why anything follows from a contradiction. By the table for the conditional, C \to Q is false only in a row where C is true and Q is false. C is true in no row, so that never happens. For arguments the same reasoning applies: an argument is valid when no row makes every premise true and the conclusion false. If the premises together are a contradiction, no row makes every premise true, so there is no row to be a counterexample. This is often called the principle of explosion, or ex falso quodlibet, “from a falsehood, anything”.

Why “and” absorbs and “or” ignores. S \wedge C needs both parts true, and C never is, so S \wedge C is F on every row. S \vee C is true when either part is, and since C never is, it is true exactly when S is.

Why reaching a contradiction proves the opposite. Whatever letters C contains, its column is F in every row, so it can be set beside P as a column of F:

Row	P	\neg P	C	{\neg P \to C}
1	T	F	F	T
2	F	T	F	F

The last column matches the P column. So an argument that shows “if not P, then a contradiction” has shown P itself. That is the logical engine of proof by contradiction, which has its own lesson.

Worked examples

Example 1

One letter, the simplest tautology

Is P \vee \neg P a tautology?

Solution

One letter gives 2^1 = 2 rows. Fill \neg P from P, then read the last column from the table for \vee.

Row	P	\neg P	P \vee \neg P
1	T	F	T
2	F	T	T

Both rows end in T, so P \vee \neg P is a tautology. Whichever way P turns out, one of P and \neg P is true, so the disjunction can never fail.

Example 2

A tautology built on the conditional

Is P \to P a tautology?

Solution

Recall the rule for \to: it is false only when the part before the arrow is T and the part after it is F. Here the two parts are the same letter, so they can never disagree.

Row	P	P \to P
1	T	T
2	F	T

Both rows end in T. A conditional whose two sides are forced to match can never land in the one case that makes a conditional false.

Example 3

Simplification, two letters

Is (P \wedge Q) \to P a tautology?

Solution

Two letters give 2^2 = 4 rows. Fill P \wedge Q first.

Row	P	Q	{P \wedge Q}
1	T	T	T
2	T	F	F
3	F	T	F
4	F	F	F

Then set the two sides of the arrow next to each other, P \wedge Q before it and P after it, and combine them row by row using the rule for \to.

Row	{P \wedge Q}	P	{(P \wedge Q) \to P}
1	T	T	T
2	F	T	T
3	F	F	T
4	F	F	T

Every row ends in T. Row 1 is the only row where P \wedge Q is T, and P is T there too, so the conditional cannot fail; on the other three rows the hypothesis P \wedge Q is already F, and a false hypothesis makes a conditional T no matter what follows it.

Example 4

Recognizing a statement that is not a tautology

Is (P \to Q) \to P a tautology?

Solution

Build the full table before deciding anything. First P \to Q:

Row	P	Q	{P \to Q}
1	T	T	T
2	T	F	F
3	F	T	T
4	F	F	T

Then the outer arrow, with P \to Q before it and P after it:

Row	{P \to Q}	P	{(P \to Q) \to P}
1	T	T	T
2	F	T	T
3	T	F	F
4	T	F	F

Rows 3 and 4 end in F, so this is not a tautology, even though it starts from a plausible-looking conditional. Both failing rows have P false. There the hypothesis P \to Q is T (a conditional whose first part is false is always T) while the conclusion P is F, which is the one combination that makes a conditional false. Knowing that P \to Q holds can never hand P back as true. Rows 1 and 2 end in T, so it is not a contradiction either: it is contingent.

Example 5

A four-row contradiction

Show that (P \vee Q) \wedge (\neg P \wedge \neg Q) is a contradiction.

Solution

Two letters give four rows. Call the two parts A = P \vee Q and B = \neg P \wedge \neg Q, build each, then join them with “and”, which is true only where both parts are. B needs \neg P and \neg Q both true, so it is true only in row 4, where P and Q are both false.

Row	P	Q	A	B	{A \wedge B}
1	T	T	T	F	F
2	T	F	T	F	F
3	F	T	T	F	F
4	F	F	F	T	F

The last column is F in every row, so the statement is a contradiction. The A and B columns show why: they are opposite in every row. By De Morgan’s laws the second is the negation of the first, so the statement is P \wedge \neg P in disguise.

Example 6

Tautology, contradiction or neither

Classify each statement as a tautology, a contradiction or neither.

(a) (P \to Q) \wedge (P \wedge \neg Q)
(b) \neg P \wedge (P \vee Q)
(c) (P \wedge \neg Q) \to P

Solution

For (a), call its two parts A = P \to Q and B = P \wedge \neg Q, and join them with “and”.

Row	P	Q	A	B	(a)
1	T	T	T	F	F
2	T	F	F	T	F
3	F	T	T	F	F
4	F	F	T	F	F

(a) is a contradiction. P \wedge \neg Q is true only in row 2, which is exactly the one row where P \to Q is false: the two parts are contradictory.

For (b) and (c), a second table adds the P \vee Q column; the hypothesis of (c) is the B column above.

Row	P	Q	{P \vee Q}	(b)	(c)
1	T	T	T	F	T
2	T	F	T	F	T
3	F	T	T	T	T
4	F	F	F	F	T

(b) is neither. \neg P is true only in rows 3 and 4, and of those P \vee Q is true only in row 3. So (b) is true in row 3 and false in the others.

(c) is a tautology. Its hypothesis P \wedge \neg Q is true only in row 2, where P is also true, so the conditional never has a true hypothesis with a false conclusion.

Example 7

Three letters without the full table

Show that (P \to Q) \wedge (Q \to R) \wedge P \wedge \neg R is a contradiction.

Solution

Three letters give eight rows. Instead of writing them all, hunt for a row that makes the statement true. A conjunction is true only when every part is, so such a row must have:

P true, from the third part, and R false, from the fourth;
Q true, because P \to Q is true and P is true;
R true, because Q \to R is true and Q is true.

The last line demands R true and the first demands R false. No row can do both, so no row makes the statement true, and it is a contradiction. The first three parts force R by chaining the conditionals, and the fourth denies it.

Example 8

A negated conditional

Show that \neg\big((P \wedge Q) \to P\big) is a contradiction without writing its table.

Solution

A negation is true exactly where the statement it negates is false. A conditional A \to B is false in just one case, A true and B false, so \neg(A \to B) is true in exactly that case. That is also the only case where A \wedge \neg B is true, so the two have the same truth table.

With A = P \wedge Q and B = P, the statement has the same table as (P \wedge Q) \wedge \neg P. An “and” is true only when every part is, and this one needs P true (inside P \wedge Q) and \neg P true in the same row. No row does both, so the statement is false in every row: a contradiction.

The first result about contradictions gives the same verdict from the other side: (P \wedge Q) \to P is the simplification form, shown to be a tautology in Example 3, and negating a tautology gives a contradiction. The rewriting route did not need that fact; it read the clash of P with \neg P straight off the form.

Example 9

A whole argument as one conditional

A hiker’s rule: if the trail is muddy, she wears boots. If she wears boots, she brings a walking stick. Does it follow, purely from the form of those two rules, that if the trail is muddy, she brings a walking stick?

Solution

Let P be “the trail is muddy”, Q be “she wears boots”, R be “she brings a walking stick”. The two rules are P \to Q and Q \to R; the claimed conclusion is P \to R. By the argument link, the argument is valid exactly when the single statement

\big((P \to Q) \wedge (Q \to R)\big) \to (P \to R)

is a tautology, so the question is now about one column. Three letters give 2^3 = 8 rows, but this conditional can be F only on a row where its conclusion P \to R is F, and that happens exactly when P is T and R is F: rows 2 and 4 in the usual order. On the other six rows the conclusion is T, so the whole statement is T there without further work. On those two rows, first the letters and the first rule:

Row	P	Q	R	{P \to Q}
2	T	T	F	T
4	T	F	F	F

Then the second rule, the hypothesis H = (P \to Q) \wedge (Q \to R) that joins the two rules, and the whole statement H \to (P \to R), whose conclusion P \to R is F on both rows:

Row	{Q \to R}	H	{H \to (P \to R)}
2	F	F	T
4	T	F	T

On row 2 the rule Q \to R fails and on row 4 the rule P \to Q fails, so the hypothesis is F on both and the whole statement is T. Every row is accounted for and every row ends in T, so the conditional is a tautology and the argument is valid, whatever “muddy”, “boots” and “stick” happen to mean. This form is hypothetical syllogism.

What the tautology adds is reuse. Because this is a tautology, it stays one when P, Q and R are replaced by any statements at all (see Boundaries), so the chain can be used as a rule in any subject without building a table again.

Example 10

A biconditional that proves two statements equivalent

Is P \vee (P \wedge Q) logically equivalent to P alone?

Solution

By the equivalence link above, that is the same question as: is \big(P \vee (P \wedge Q)\big) \leftrightarrow P a tautology? Call the left side L = P \vee (P \wedge Q), and build it: P \wedge Q first, then L.

Row	P	Q	{P \wedge Q}	L
1	T	T	T	T
2	T	F	F	T
3	F	T	F	F
4	F	F	F	F

Now set L beside P and compare the two using the rule for \leftrightarrow, which is T exactly when its two sides agree.

Row	L	P	{L \leftrightarrow P}
1	T	T	T
2	T	T	T
3	F	F	T
4	F	F	T

The L column matches the P column on every row, so the biconditional is T on every row: a tautology, and the two statements are logically equivalent. The rows show why. When P is T the “or” is already T; when P is F so is P \wedge Q, and nothing is left to make the “or” true. The extra \wedge\, Q never changes the outcome, so the longer statement can always be replaced by P alone. This equivalence is called absorption. The same test is what justifies rewriting a conditional as an “or”.

Example 11

Premises that cannot all be true

Test the argument: “Ana is at home or at school. She is not at home. She is not at school. Therefore she is on the moon.”

Solution

Let H be “Ana is at home”, S be “Ana is at school” and M be “Ana is on the moon”. The premises are H \vee S, \neg H and \neg S. Their conjunction is (H \vee S) \wedge \neg H \wedge \neg S, and Example 5 showed this form is a contradiction: \neg H and \neg S make H \vee S false. So no row makes all three premises true.

Testing the argument with a table means looking for a row with every premise true and the conclusion false. There is none, whatever M is, so the argument is valid.

It still gives no reason to believe Ana is on the moon. A valid argument only carries truth from the premises to the conclusion, and these premises can never all be true, so the argument can never be sound. The same premises “prove” that she is not on the moon just as well.

Boundaries

Both extremes are facts about the connective skeleton, not about what the letters mean. P \vee \neg P is a tautology whatever P stands for, but it says nothing about whether that particular P is true. A single-letter tautology like P \to P can never be used to decide P itself; it only says the whole compound never depends on P’s actual value.

Substitution keeps a tautology a tautology, and a contradiction a contradiction, but only in one direction. Replace P at every place it occurs in P \vee \neg P with any compound statement at all, say A \wedge B, and (A \wedge B) \vee \neg(A \wedge B) is still a tautology: whatever truth value A \wedge B takes, it and its negation cannot both be false. The table only ever looked at the two possible values of the letter it replaced, never at how that value was built. The replacement has to be made at every occurrence; replacing only the first P gives (A \wedge B) \vee \neg P, which is F when A is F and P is T. And the reverse fails: P \to Q is not a tautology, yet putting P in place of Q turns it into P \to P, which is. In the same way “neither” describes the form, not every instance: P \wedge Q is neither, but put \neg P in place of Q and it becomes P \wedge \neg P. So a contingent statement can still have tautologies and contradictions among its substitution instances.

Every row must be accounted for, and one wrong row settles it the other way. Checking a few rows, or the rows that happen to come to mind first, proves nothing. A statement is a tautology only once every row is accounted for, either by building the full table or, as in Example 9, by showing that each row where it could be F is not. A statement is a contradiction only once every row is shown F, as Example 7 does by showing no row can be T. Example 4 looked reasonable right up until row 3.

A truth table sees only logical form. “Every square is a rectangle, and this shape is a square, so this shape is a rectangle” is a valid argument, but with a letter for each of its three statements it becomes (P \wedge Q) \to R, which is not a tautology. Its force comes from the word “every” inside the first statement, which no truth table can see; that needs quantifiers. In the same way, “x > 3 and x < 2” is false for every real number, but written as A \wedge B its two letters are independent, and row 1 of its table is T. The clash lives in what “>” and “<” mean for numbers, which the table never sees. It is always false, but it is not a contradiction in the truth-table sense. The same goes for statements about “every” and “some”, whose clashes need quantifier reasoning.

Two truth values are assumed. Everything here rests on each statement being exactly true or false. Logics that allow a third value, or that deliberately reject the principle that a contradiction implies anything, draw these lines differently; the results above belong to ordinary two-valued logic.

Where this goes next

A tautology and a contradiction are the two ends of the same scale, mirror images across the same tables, and negating turns a fact about one into a fact about the other. Recognizing a tautology is the entire test behind deciding whether an argument is valid and behind proving two statements say the same thing: two statements are equivalent exactly when “S if and only if T” is a tautology, which is to say when its negation is a contradiction. So the identities collected here, excluded middle, simplification, addition, absorption and the rest, become the working stock of moves used when testing a real argument or simplifying a real statement, without rebuilding a table from scratch every time.

The larger payoff of contradictions is in proof. Proof by contradiction assumes the opposite of what it wants and drives that assumption into a contradiction, and the table in “Why it is true” is the reason this counts as a proof. The same move shows that \displaystyle \sqrt{2} is irrational and runs through indirect proofs in geometry.

Exercises

Tautology or not: one letter

Decide whether each statement is a tautology.

Q \vee \neg Q
Q \to Q
P \wedge \neg P

Tautology or not: two letters

(P \vee Q) \to Q
P \to (P \vee Q)
(P \to Q) \vee (Q \to P)
(P \wedge Q) \to (P \vee Q)
\big(P \wedge (P \to Q)\big) \to Q

Tautology or not: three letters

\big(P \to (Q \to R)\big) \leftrightarrow \big((P \wedge Q) \to R\big)
\big((P \to Q) \wedge (P \to R)\big) \to \big(P \to (Q \wedge R)\big)
\big(P \vee (Q \wedge R)\big) \leftrightarrow \big((P \vee Q) \wedge (P \vee R)\big)
\big((P \to Q) \wedge (P \to R)\big) \to (Q \to R)

Showing a statement is a contradiction

Use a truth table to show that each statement is a contradiction.

\neg(P \vee \neg P)
(P \leftrightarrow Q) \wedge (P \leftrightarrow \neg Q)
P \wedge (P \to \neg P)
(P \wedge Q) \wedge (\neg P \vee \neg Q)

Tautology, contradiction or neither

Classify each statement, and give a row that shows it when the answer is “neither”.

(P \to Q) \wedge \neg Q
(P \wedge \neg Q) \vee (P \to Q)
(P \vee Q) \leftrightarrow (\neg P \wedge \neg Q)
P \to \neg P
(P \vee Q) \wedge (\neg P \vee R) \wedge \neg Q \wedge \neg R
(P \to R) \wedge (Q \to R) \wedge \neg R

Translate, then test

A store’s policy: if a customer pays in full, the order ships. A clerk summarizes it as: it is not the case that a customer pays in full and the order fails to ship. Symbolize both, with P for “pays in full” and Q for “order ships”, and test whether the two phrasings are forced to agree.
A club’s entry rule: a visitor may enter if they hold a membership card or are a guest of a member. Someone claims this means the same as: a visitor may enter if they hold a card, or else a visitor may enter if they are a guest. Symbolize the rule with P for “holds a card”, Q for “is a guest” and E for “may enter”, and test whether the two phrasings are forced to agree.
A rule at a lab: if a sample is contaminated, it is discarded. A technician sees that a sample was discarded and concludes that it was contaminated. With P for “the sample is contaminated” and Q for “the sample is discarded”, write the technician’s argument as one conditional and test whether it is a tautology.

Symbolize and classify

Write each sentence in symbols, naming your letters, and classify it.

“The test is on Friday, and the test is not on Friday.”
“The alarm rings if and only if the alarm does not ring.”
“Mia passed, or Mia both passed and did not pass.”

Using contradictions

An argument has premises P \to Q, P and \neg Q, and conclusion R. Is it valid? Explain using its premises.
C is a contradiction and S is any statement. Say whether each is always a tautology, always a contradiction, or depends on S: (a) S \wedge C (b) S \vee C (c) C \to S (d) S \to C.
A proof by contradiction often derives both Q and \neg Q from the assumption \neg P. Show that (\neg P \to Q) \wedge (\neg P \to \neg Q) has the same truth table as P.

Reasoning

Explain why the negation of a tautology must be a contradiction, a statement that is F on every row, without building any new table.
An argument has two premises and one conclusion. Explain why finding even one row of the argument’s compound table where every premise is T and the conclusion is F is enough, on its own, to prove the argument invalid, without checking any further row.
Explain why P \to P being a tautology gives no information at all about whether P is actually true.
Explain why a statement being a tautology can never depend on which particular simple statements were substituted for its letters, only on the connectives joining them.
Explain why any two contradictions are logically equivalent, even when they are built from different letters.
“x > 3 and x < 2” is false for every real number x. Is it a contradiction in the sense of this lesson? Explain.
Show that a statement built from letters using only \wedge and \vee can never be a contradiction.
An argument’s premises together form a contradiction. Explain why the argument is valid, and why it still gives no reason to believe its conclusion.

Answers

Tautology. Q and \neg Q always disagree, so one of them is always T, and their disjunction is T on both rows.
Tautology. The two sides of the arrow are the same letter, so they never land in the one case, T before and F after, that makes a conditional false.
Not a tautology; false on both rows. P and \neg P always disagree, so their conjunction is F however P is chosen. (This is in fact a contradiction, the plainest one, from the Definition.)
Not a tautology. Row P{=}\text{T}, Q{=}\text{F}: P \vee Q is T but Q is F, so the conditional is F there.
Tautology. Whenever P is T, P \vee Q is T too, so the conditional never has a T hypothesis with an F conclusion; whenever P is F the hypothesis is already F.
Tautology. On every row at least one of P \to Q, Q \to P is T: the only way for both to be F would need P{=}\text{T}, Q{=}\text{F} and Q{=}\text{T}, P{=}\text{F} at once, which is impossible.
Tautology. Whenever P \wedge Q is T, both P and Q are T, so P \vee Q is T too; the conditional never has a T hypothesis with an F conclusion.
Tautology. This is modus ponens. If P and P \to Q are both T, then by the rule for \to, Q must be T; if the hypothesis P \wedge (P \to Q) is F, the conditional is automatically T.
Tautology. This is exportation. Each side is F in exactly the same single case, P{=}\text{T}, Q{=}\text{T}, R{=}\text{F}, and T everywhere else, so the two sides agree on every row and the biconditional is T throughout.
Tautology. When P is F the conclusion P \to (Q \wedge R) is automatically T. When P is T, the hypothesis forces Q and R both T, which is exactly what the conclusion needs.
Tautology. This is a distributive law. Checking all eight rows, the two sides agree on every one: both are T whenever P is T, and when P is F both sides reduce to Q \wedge R.
Not a tautology. Row P{=}\text{F}, Q{=}\text{T}, R{=}\text{F}: both P \to Q and P \to R are T (a false hypothesis), so the left side is T, but Q \to R is F there, making the whole conditional F.
Contradiction. P \vee \neg P is T, T, so its negation is F, F. It is the negation of the tautology P \vee \neg P.
Contradiction. P \leftrightarrow Q is T, F, F, T and P \leftrightarrow \neg Q is F, T, T, F. They are never true together, so the whole is F, F, F, F.
Contradiction. P is T, F and P \to \neg P is F, T, so the conjunction is F, F. P \to \neg P says the same as \neg P.
Contradiction. P \wedge Q is T, F, F, F and \neg P \vee \neg Q is F, T, T, T. They are opposite in every row (the second is the negation of the first), so the whole is F, F, F, F.
Neither. P \to Q is T, F, T, T and \neg Q is F, T, F, T, so the whole is F, F, F, T: true in row 4, with P and Q both false, and false in row 1.
Tautology. P \wedge \neg Q is F, T, F, F and P \to Q is T, F, T, T. They are contradictory, so exactly one is true in each row, and the whole is T, T, T, T.
Contradiction. P \vee Q is T, T, T, F and \neg P \wedge \neg Q is F, F, F, T. They differ in every row, and a biconditional is false wherever its sides differ, so the whole is F, F, F, F.
Neither. It is F when P is true and T when P is false.
Contradiction. For a true row, \neg Q and \neg R make Q and R false; then P \vee Q forces P true; then \neg P \vee R is false. No row survives.
Neither. True in row 8, with P, Q and R all false: both conditionals and \neg R are true. False in row 1, where \neg R is false.
(P \to Q) \leftrightarrow \neg(P \wedge \neg Q), and it is a tautology. Both sides are F in exactly the same case, P{=}\text{T}, Q{=}\text{F}, and T everywhere else, so the two phrasings always agree.
\big((P \vee Q) \to E\big) \leftrightarrow \big((P \to E) \vee (Q \to E)\big), and it is not a tautology. Row P{=}\text{T}, Q{=}\text{F}, E{=}\text{F}: the left side is F (a card holder is refused), but the right side is T because Q \to E is T on a false hypothesis. The two phrasings can disagree.
\big((P \to Q) \wedge Q\big) \to P, and it is not a tautology. Row P{=}\text{F}, Q{=}\text{T}: both P \to Q and Q are T, but P is F, so the conditional is F there. A sample can be discarded for some other reason, so the technician’s argument is invalid; this form is affirming the consequent.
F \wedge \neg F, with F “the test is on Friday”. A contradiction.
A \leftrightarrow \neg A, with A “the alarm rings”. A contradiction: A and \neg A differ in both rows, so the biconditional is F, F.
M \vee (M \wedge \neg M), with M “Mia passed”. Neither. M \wedge \neg M is a contradiction, and “or” ignores it, so the whole has the same table as M: T, F.
Valid. The premises can never all be true: P true and P \to Q true force Q true, which clashes with \neg Q. No row makes every premise true, so none is a counterexample, whatever R says.
(a) Always a contradiction. (b) Depends on S: it has the same table as S. (c) Always a tautology. (d) Depends on S: it has the same table as \neg S, so it is a tautology exactly when S is a contradiction.
Where P is true, \neg P is false, so both conditionals are true and so is their “and”. Where P is false, \neg P is true, so the first part needs Q true and the second needs \neg Q true, which no row gives. Over the four rows the column is T, T, F, F, the same as P.
A tautology’s last column is T on every row; negating a statement flips every entry in its column, so a column of all T’s becomes a column of all F’s, which is exactly what a contradiction’s column looks like.
Validity means no row exists where every premise is T and the conclusion is F. Finding one such row already shows such a row exists, which is precisely what invalidity means; no further row can undo that.
A tautology is T on every row of its own table, including the row where P is T and the row where P is F. Since both rows end in T, knowing only that P \to P holds cannot tell you which of those two rows is the real one.
A truth table only ever reads the values already sitting in its letter columns; it never asks what those letters were written to mean. Whatever simple statements a letter stands for, the table sees only T or F, so a column of all T’s built from the connectives alone stays a column of all T’s under any substitution.
Put both in one table that uses every letter of either. Adding a letter a statement does not mention cannot change its value, so each is still F in every row. The two columns agree everywhere, which is what logically equivalent means. In particular, every contradiction is equivalent to P \wedge \neg P.
No. Written as A \wedge B, with A “x > 3” and B “x < 2”, its table has a T in the row where A and B are both true. The table treats A and B as unrelated; that no number makes both true is a fact about numbers, not about the logical form.
Take the row where every letter is true. “And” and “or” of true statements are true, so, working outward from the letters, every part is true in that row, and so is the whole. A statement with a T in its column is not a contradiction.
Valid, because no row makes every premise true, so no row makes every premise true and the conclusion false. No reason to believe it, because a valid argument only passes truth from its premises to its conclusion, and these premises can never all be true. The same premises would “prove” the conclusion’s negation equally well.