Logic and Truth Tables: Fundamentals

1Introduction

This lecture defines the logical connectives used to construct compound propositions and explains how truth tables determine properties of logical formulas. In particular, it clarifies the direction of implication and the roles of necessary and sufficient conditions.

2Propositions and Truth Values

A {proposition} is a declarative sentence that has exactly one of the two truth values: true or false. We write $\mathrm{T}$\mathrm{T} when a proposition is true and $\mathrm{F}$\mathrm{F} when it is false. A question, or a sentence whose truth cannot be determined until a variable is specified, is not itself a proposition.

3Logical Connectives

Let $P$P and $Q$Q be propositions.

• The {negation} $\text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg P has the truth value opposite to that of $P$P.
• The {conjunction} $P\wedge Q$P\land Q is true if and only if both $P$P and $Q$Q are true.
• The {disjunction} $P\vee Q$P\lor Q is true if and only if at least one of $P$P and $Q$Q is true. Thus, this inclusive “or” includes the case in which both propositions are true.
• The {implication} $P\to Q$P\to Q is false if and only if $P$P is true and $Q$Q is false. We call $P$P the antecedent and $Q$Q the consequent.
• The {biconditional} $P\leftrightarrow Q$P\leftrightarrow Q is true if and only if $P$P and $Q$Q have the same truth value.

4Truth Tables

A {truth table} lists the truth value of a logical formula for every assignment of truth values to its component propositions. The basic formulas involving two propositions are defined by the following table.

For $P\to Q$P\to Q, the implication is true in both rows in which the antecedent $P$P is false. This convention reflects that $P\to Q$P\to Q is not an assertion of causation; instead, it states that there is no counterexample in which $P$P is true while $Q$Q is false.

5Tautologies, Contradictions, and Logical Equivalence

A {tautology} is a formula that is true under every assignment of truth values. A {contradiction} is a formula that is false under every assignment. For example, $P\vee \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\lor\neg P is a tautology, whereas $P\wedge \text{[PARSE ERROR: Undefined("Command("neg")")]}P$P\land\neg P is a contradiction.

Two formulas $A$A and $B$B are {logically equivalent}, written $A\equiv B$A\equiv B, if they have the same truth value under every assignment. Equivalently, $A\leftrightarrow B$A\leftrightarrow B is a tautology. For example, implication satisfies

6Direction of Implication and Necessary and Sufficient Conditions

In $P\to Q$P\to Q, $P$P is a {sufficient condition} for $Q$Q, and $Q$Q is a {necessary condition} for $P$P. That is, the truth of $P$P guarantees the truth of $Q$Q, and $Q$Q must be true whenever $P$P is true.

The statement $Q\to P$Q\to P is the {converse} of $P\to Q$P\to Q and, in general, does not follow from the original implication. In contrast, $\text{[PARSE ERROR: Undefined("Command("neg")")]}Q\to \text{[PARSE ERROR: Undefined("Command("neg")")]}P$\neg Q\to\neg P is its {contrapositive}, and

For conditions $P\left(x\right)$P(x) and $Q\left(x\right)$Q(x) containing a variable, if both $P\left(x\right)\to Q\left(x\right)$P(x)\to Q(x) and $Q\left(x\right)\to P\left(x\right)$Q(x)\to P(x) hold for every object $$x$$x under consideration, then $P\left(x\right)\leftrightarrow Q\left(x\right)$P(x)\leftrightarrow Q(x) is a tautology, and $P\left(x\right)$P(x) is a {necessary and sufficient condition} for $Q\left(x\right)$Q(x). The fact that both implications are true under one particular truth-value assignment does not establish this relationship.

7Example

For an integer $$n$$n, let $P\left(n\right)$P(n) mean “$$n$$n is divisible by 4,” and let $Q\left(n\right)$Q(n) mean “$$n$$n is even.” Until $$n$$n is specified, $P\left(n\right)$P(n) and $Q\left(n\right)$Q(n) are not propositions; they are {predicates} that assign truth values to integers. The implication $P\left(n\right)\to Q\left(n\right)$P(n)\to Q(n) holds for every integer $$n$$n, so divisibility by 4 is sufficient for being even. In contrast, $Q\left(2\right)$Q(2) is true and $P\left(2\right)$P(2) is false, so $$n=2$$n=2 is a counterexample to $Q\left(n\right)\to P\left(n\right)$Q(n)\to P(n).

8Key Points

• The meanings of logical connectives are determined by truth tables, not by informal impressions of natural-language expressions.
• A tautology is true in every row of its truth table, whereas a contradiction is false in every row.
• Logical equivalence means agreement under every assignment of truth values.
• In $P\to Q$P\to Q, $P$P is sufficient and $Q$Q is necessary; the converse must not be confused with the contrapositive.

9Related Links