Chapter 15 Partial truth tables

Sometimes, we do not need to know what happens on every line of a truth table. Sometimes, just a line or two will do.

Tautology

In order to show that a sentence is a tautology, we need to show that it is true on every valuation. That is to say, we need to know that it comes out true on every line of the truth table. So we need a complete truth table.

To show that a sentence is not a tautology, however, we only need one line: a line on which the sentence is false. Therefore, in order to show that some sentence is not a tautology, it is enough to provide a single valuation—a single line of the truth table—which makes the sentence false.

Suppose that we want to show that the sentence ‘ $(U\wedge T)\rightarrow(S\wedge W)$ ’ is not a tautology. We set up a partial truth table :

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
							F

We have only left space for one line, rather than 16, since we are only looking for one line, on which the sentence is false (hence, also, the ‘F’).

The main logical operator of the sentence is a conditional. In order for the conditional to be false, the antecedent must be true and the consequent must be false. So we fill these in on the table:

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
					T		F		F

In order for the ‘ $(U\wedge T)$ ’ to be true, both ‘ $U$ ’ and ‘ $T$ ’ must be true.

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
	T	T		T	T	T	F		F

Now we just need to make ‘ $(S\wedge W)$ ’ false. To do this, we need to make at least one of ‘ $S$ ’ and ‘ $W$ ’ false. We can make both ‘ $S$ ’ and ‘ $W$ ’ false if we want. All that matters is that the whole sentence turns out false on this line. Making an arbitrary decision, we finish the table in this way:

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
F	T	T	F	T	T	T	F	F	F	F

We now have a partial truth table, which shows that ‘ $(U\wedge T)\rightarrow(S\wedge W)$ ’ is not a tautology. Put otherwise, we have shown that there is a valuation which makes ‘ $(U\wedge T)\rightarrow(S\wedge W)$ ’ false, namely, the valuation which makes ‘ $S$ ’ false, ‘ $T$ ’ true, ‘ $U$ ’ true and ‘ $W$ ’ false.

Contradictions

Showing that something is a contradiction in TFL requires a complete truth table: we need to show that there is no valuation which makes the sentence true; that is, we need to show that the sentence is false on every line of the truth table.

However, to show that something is not a contradiction, all we need to do is find a valuation which makes the sentence true, and a single line of a truth table will suffice. We can illustrate this with the same example.

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
							T

To make the sentence true, it will suffice to ensure that the antecedent is false. Since the antecedent is a conjunction, we can just make one of them false. Making an arbitrary choice, let’s make ‘ $U$ ’ false; we can then assign any truth value we like to the other sentence letters.

$S$	$T$	$U$	$W$	$(U$	$\wedge$	$T)$	$\rightarrow$	$(S$	$\wedge$	$W)$
F	T	F	F	F	F	T	T	F	F	F

Equivalence

To show that two sentences are equivalent, we must show that the sentences have the same truth value on every valuation. So this requires a complete truth table.

To show that two sentences are not equivalent, we only need to show that there is a valuation on which they have different truth values. So this requires only a one-line partial truth table: make the table so that one sentence is true and the other false.

Joint satisfiability

To show that some sentences are jointly satisfiable, we must show that there is a valuation which makes all of the sentences true, so this requires only a partial truth table with a single line.

To show that some sentences are jointly unsatisfiable, we must show that there is no valuation which makes all of the sentence true. So this requires a complete truth table: You must show that on every row of the table at least one of the sentences is false.

Validity and entailment

To show that an argument is valid, we must show that there is no valuation which makes all of the premises true and the conclusion false. So this requires a complete truth table. (Likewise for entailment.)

To show that argument is invalid, we must show that there is a valuation which makes all of the premises true and the conclusion false. So this requires only a one-line partial truth table on which all of the premises are true and the conclusion is false. (Likewise for a failure of entailment.)

This table summarizes what is required:

	Yes	No
tautology?	complete	one-line partial
contradiction?	complete	one-line partial
equivalent?	complete	one-line partial
satisfiable?	one-line partial	complete
valid?	complete	one-line partial
entailment?	complete	one-line partial

Practice exercises

A. Use complete or partial truth tables (as appropriate) to determine whether these pairs of sentences are logically equivalent:

1.

$A$ , $\neg A$
2.

$A$ , $A\vee A$
3.

$A\rightarrow A$ , $A\leftrightarrow A$
4.

$A\vee\neg B$ , $A\rightarrow B$
5.

$A\wedge\neg A$ , $\neg B\leftrightarrow B$
6.

$\neg(A\wedge B)$ , $\neg A\vee\neg B$
7.

$\neg(A\rightarrow B)$ , $\neg A\rightarrow\neg B$
8.

$(A\rightarrow B)$ , $(\neg B\rightarrow\neg A)$

B. Use complete or partial truth tables (as appropriate) to determine whether these sentences are jointly satisfiable, or jointly unsatisfiable:

1.

$A\wedge B$ , $C\rightarrow\neg B$ , $C$
2.

$A\rightarrow B$ , $B\rightarrow C$ , $A$ , $\neg C$
3.

$A\vee B$ , $B\vee C$ , $C\rightarrow\neg A$
4.

$A$ , $B$ , $C$ , $\neg D$ , $\neg E$ , $F$
5.

$A\wedge(B\vee C)$ , $\neg(A\wedge C)$ , $\neg(B\wedge C)$
6.

$A\rightarrow B$ , $B\rightarrow C$ , $\neg(A\rightarrow C)$

C. Use complete or partial truth tables (as appropriate) to determine whether each argument is valid or invalid:

1.

$A\vee\bigl{[}A\rightarrow(A\leftrightarrow A)\bigr{]}\therefore A$
2.

$A\leftrightarrow\neg(B\leftrightarrow A)\therefore A$
3.

$A\rightarrow B,B\therefore A$
4.

$A\vee B,B\vee C,\neg B\therefore A\wedge C$
5.

$A\leftrightarrow B,B\leftrightarrow C\therefore A\leftrightarrow C$

D. Determine whether each sentence is a tautology, a contradiction, or a contingent sentence. Justify your answer with a complete or partial truth table as appropriate.

1.

$A\rightarrow\neg A$
2.

$A\rightarrow(A\wedge(A\vee B))$
3.

$(A\rightarrow B)\leftrightarrow(B\rightarrow A)$
4.

$A\rightarrow\neg(A\wedge(A\vee B))$
5.

$\neg B\rightarrow[(\neg A\wedge A)\vee B]$
6.

$\neg(A\vee B)\leftrightarrow(\neg A\wedge\neg B)$
7.

$[(A\wedge B)\wedge C]\rightarrow B$
8.

$\neg\bigl{[}(C\vee A)\vee B\bigr{]}$
9.

$\bigl{[}(A\wedge B)\wedge\neg(A\wedge B)\bigr{]}\wedge C$
10.

$(A\wedge B)]\rightarrow[(A\wedge C)\vee(B\wedge D)]$

E. Determine whether each sentence is a tautology, a contradiction, or a contingent sentence. Justify your answer with a complete or partial truth table as appropriate.

1.

$\neg(A\vee A)$
2.

$(A\rightarrow B)\vee(B\rightarrow A)$
3.

$[(A\rightarrow B)\rightarrow A]\rightarrow A$
4.

$\neg[(A\rightarrow B)\vee(B\rightarrow A)]$
5.

$(A\wedge B)\vee(A\vee B)$
6.

$\neg(A\wedge B)\leftrightarrow A$
7.

$A\rightarrow(B\vee C)$
8.

$(A\wedge\neg A)\rightarrow(B\vee C)$
9.

$(B\wedge D)\leftrightarrow[A\leftrightarrow(A\vee C)]$
10.

$\neg[(A\rightarrow B)\vee(C\rightarrow D)]$

F. Determine whether each the following pairs of sentences are logically equivalent using complete truth tables. Justify your answer with a complete or partial truth table as appropriate.

1.

$A$ and $A\vee A$
2.

$A$ and $A\wedge A$
3.

$A\vee\neg B$ and $A\rightarrow B$
4.

$(A\rightarrow B)$ and $(\neg B\rightarrow\neg A)$
5.

$\neg(A\wedge B)$ and $\neg A\vee\neg B$
6.

$((U\rightarrow(X\vee X))\vee U)$ and $\neg(X\wedge(X\wedge U))$
7.

$((C\wedge(N\leftrightarrow C))\leftrightarrow C)$ and $(\neg\neg\neg N\rightarrow C)$
8.

$[(A\vee B)\wedge C]$ and $[A\vee(B\wedge C)]$
9.

$((L\wedge C)\wedge I)$ and $L\vee C$

G. Determine whether each collection of sentences is jointly satisfiable or jointly unsatisfiable. Justify your answer with a complete or partial truth table as appropriate.

1.

$A\rightarrow A$ , $\neg A\rightarrow\neg A$ , $A\wedge A$ , $A\vee A$
2.

$A\rightarrow\neg A$ , $\neg A\rightarrow A$
3.

$A\vee B$ , $A\rightarrow C$ , $B\rightarrow C$
4.

$A\vee B$ , $A\rightarrow C$ , $B\rightarrow C$ , $\neg C$
5.

$B\wedge(C\vee A)$ , $A\rightarrow B$ , $\neg(B\vee C)$
6.

$(A\leftrightarrow B)\rightarrow B$ , $B\rightarrow\neg(A\leftrightarrow B)$ , $A\vee B$
7.

$A\leftrightarrow(B\vee C)$ , $C\rightarrow\neg A$ , $A\rightarrow\neg B$
8.

$A\leftrightarrow B$ , $\neg B\vee\neg A$ , $A\rightarrow B$
9.

$A\leftrightarrow B$ , $A\rightarrow C$ , $B\rightarrow D$ , $\neg(C\vee D)$
10.

$\neg(A\wedge\neg B)$ , $B\rightarrow\neg A$ , $\neg B$

H. Determine whether each argument is valid or invalid. Justify your answer with a complete or partial truth table as appropriate.

1.

$A\rightarrow(A\wedge\neg A)\therefore\neg A$
2.

$A\vee B$ , $A\rightarrow B$ , $B\rightarrow A\therefore A\leftrightarrow B$
3.

$A\vee(B\rightarrow A)\therefore\neg A\rightarrow\neg B$
4.

$A\vee B$ , $A\rightarrow B$ , $B\rightarrow A\therefore A\wedge B$
5.

$(B\wedge A)\rightarrow C$ , $(C\wedge A)\rightarrow B\therefore(C\wedge B)\rightarrow A$
6.

$\neg(\neg A\vee\neg B)$ , $A\rightarrow\neg C\therefore A\rightarrow(B\rightarrow C)$
7.

$A\wedge(B\rightarrow C)$ , $\neg C\wedge(\neg B\rightarrow\neg A)\therefore C\wedge\neg C$
8.

$A\wedge B$ , $\neg A\rightarrow\neg C$ , $B\rightarrow\neg D\therefore A\vee B$
9.

$A\rightarrow B\therefore(A\wedge B)\vee(\neg A\wedge\neg B)$
10.

$\neg A\rightarrow B$ , $\neg B\rightarrow C$ , $\neg C\rightarrow A\therefore\neg A\rightarrow(\neg B\vee\neg C)$

I. Determine whether each argument is valid or invalid. Justify your answer with a complete or partial truth table as appropriate.

1.

$A\leftrightarrow\neg(B\leftrightarrow A)\therefore A$
2.

$A\vee B$ , $B\vee C$ , $\neg A\therefore B\wedge C$
3.

$A\rightarrow C$ , $E\rightarrow(D\vee B)$ , $B\rightarrow\neg D\therefore(A\vee C)\vee(B\rightarrow(E\wedge D))$
4.

$A\vee B$ , $C\rightarrow A$ , $C\rightarrow B\therefore A\rightarrow(B\rightarrow C)$
5.

$A\rightarrow B$ , $\neg B\vee A\therefore A\leftrightarrow B$