Chapter 2 - The Logic of Compound Statements

Entry | Solutions

Logical Form and Logical Equivalence

Definition

Statement

A statement (or proposition) is a sentence that is true or false but not both.

Definition

Negation

If $p$ is a statement variable, the negation of $p$ is “not $p$” or “It is not the case that $p$” and is denoted $\neg p$. It has opposite truth value from $p$: if $p$ is true, $\neg p$ is false; if $p$ is false, $\neg p$ is true.

Definition

Conjunction

If $p$ and $q$ are statement variables, the conjunction of $p$ and $q$ is “$p$ and $q$,” denoted $p\wedge q$. It is true when, and only when, both $p$ and $q$ are true. If either $p$ or $q$ is false, or if both are false, $p\wedge q$ is false.

Definition

Disjunction

If $p$ and $q$ are statement variables, the disjunction of $p$ and $q$ is “$p$ or $q$,” denoted $p\vee q$. It is true when either $p$ is true, or $q$ is true, or both $p$ and $q$ are true; it is false only when both $p$ and $q$ are false.

Definition

A statement form (or propositional form) is an expression made up of statement variables (such as $p$, $q$, and $r$) and logical connectives (such as $\neg$, $\wedge$ and $\vee$) that becomes a statement when actual statements are substituted for the component statement variables. The truth table for a given statement form displays the truth values that correspond to all possible combinations of truth values for its component statement variables.

Definition

Logically Equivalent

Two statement forms are called logically equivalent if, and only if, they have identical truth values for each possible substitution of statements for their statement variables. The logical equivalence of statement forms $P$ and $Q$ is denoted by writing $P\equiv Q$. Two statements are called logically equivalent if, and only if, they have logically equivalent forms when identical component statement variables are used to replace identical component statements.

Note

De Morgan’s Law

The negation of an and statement is logically equivalent to the or statement in which each component is negated.

$$\neg (p\wedge q)\equiv \neg p\vee \neg q$$

The negation of an or statement is logically equivalent to the and statement in which each component is negated.

$$\neg (p\vee q)\equiv \neg p\wedge \neg q$$

Definition

A tautology is a statement form that is always true regardless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a tautology is a tautological statement. A contradication is a statement form that is always false regardless of the truth values of the individual statements substituted for its statement variables. A statement whose form is a contradiction is a contradictory statement.

Theorem

Given any statement variables p, q, and r, a tautology t and a contradiction c, the following logical equivalences hold.

1. Commutative Laws:

$$p\vee q\equiv q\vee p$$ $$p\wedge q\equiv q\wedge p$$

2. Associative Laws:

$$(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)$$ $$(p\vee q)\vee r\equiv p\vee (q\vee r)$$

3. Distributive Laws:

$$p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$$ $$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$$

4. Identity Laws:

$$p\wedge t\equiv p$$ $$p\vee c\equiv p$$

5. Negation Laws:

$$p\vee \neg p\equiv t$$ $$p\wedge \neg p\equiv c$$

6. Double negative Law:

$$\neg (\neg p)\equiv p$$

7. Idempotent Laws:

$$p\wedge p\equiv p$$ $$p\vee p\equiv p$$

8. Universal Bound Laws:

$$p\vee t\equiv t$$ $$p\wedge c\equiv c$$

9. De Morgan’s Laws:

$$\neg (p\wedge q)\equiv \neg p\vee \neg q$$ $$\neg (p\vee q)\equiv \neg p\wedge \neg q$$

10. Absorption Laws:

$$p\vee (p\wedge q)\equiv p$$ $$p\wedge (p\vee q)\equiv p$$

11. Negations of $t$ and $c$:

$$\neg t\equiv c$$ $$\neg c\equiv t$$

Conditional Statements

Definition

Conditional Statement

If $p$ and $q$ are statement variables, the conditional of $q$ by $p$ is “If $p$ then $q$” or “$p$ implies $q$” and is denoted $p\to q$. It is false when $p$ is true and $q$ is false; otherwise it is true. We call $p$ the hypothesis (or antecedent) of the conditional and $q$ the conclusion (or consequent).

Note

Vacuously true or true by default

A conditional statement that is true by virtue of the fact that its hypothesis is false is often called vacuously true or true by default. Thus the statement “If you show up for work Monday morning, then you will get the job” is vacuously true if you do not show up for work Monday morning. In general, when the “if” part of an if-then statement is false, the statement as a whole is said to be true, regardless of whether the conclusion is true or false.

Note

Logical Equivalences Involving $\to$

• $p\vee q\to r\equiv (p\to r)\wedge (q\to r)$
• $p\to q\equiv \neg p\vee q$
• $\neg (p\to q)\equiv p\wedge \neg q$

Definition

The Contrapositive of a Conditional Statement

The contrapositive of a conditional statement of the form “If $p$ then $q$” is

$$\text{if }\neg q\text{ then }\neg p$$

Symbolically,

$$\text{The contrapositive of }p\to q\text{ is }\neg q\to \neg p$$

Note

A conditional statement is logically equivalent to its contrapositive.

Definition

The Converse and Inverse of a Conditional Statement

Suppose a conditional statement of the form “If $p$ then $q$” is given.

1. The converse is “If $q$ then $p$.”
2. The inverse is “If $\neg p$ then $\neg q$.”

Symbolically,

$$\text{The converse of }p\to q\text{ is }q\to p$$

and

$$\text{The inverse of }p\to q\text{ is }\neg p\to \neg q$$

Note

1. A conditional statement and its converse are not logically equivalent.
2. A conditional statement and its inverse are not logically equivalent.
3. The converse and the inverse of a conditional statement are logically equivalent to each other.

Definition

Only If

If p and q are statements,

$$p\text{ only if }q\text{ means "if not q then not p,"}$$

or, equivalently,

$$\text{"if p then q."}$$

Definition

Biconditional

Given statement variables $p$ and $q$, the biconditional of $p$ and $q$ is “$p$ if, and only if, $q$” and is denoted $p\leftrightarrow q$. It is true if both $p$ and $q$ have the same truth values and is false if $p$ and $q$ have opposite truth values. The words if and only if are sometimes abbreviated iff.

Note

$$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$$

Note

Order of Operations for Logical Operators

1. $\neg$: Evaluate negations first.
2. $\wedge ,\vee$: Evaluate them second. When both are present, parentheses may be needed.
3. $\to ,\leftrightarrow$: Evaluate them third. When both are present, parentheses may be needed.

Definition

Necessary and Sufficient Conditions

If $r$ and $s$ are statements:

• $r$ is a sufficient condition for $s$ means: “if $r$ then $s$.”

• $r$ is necessary condition for $s$ means: “if not $r$ then not $s$.”

Note

• $r$ is a necessary condition for $s$ also means “if $s$ then $r$.”
• $r$ is a necessary and sufficient condition for $s$ means “$r$ if, and only if, $s$.”

Important

1. In logic, a hypothesis and conclusion are not required to have related subject matters.
2. In informal language, simple conditionals are often used to mean biconditionals.

Solutions to chapter exercises

Previous Chapter | Next Chapter