Logic Reference

Propositional Logic and Quantifiers

Logic gives precise rules for combining statements and deciding when an argument is valid.

Solved Examples

Jump directly to a worked example by type.

Fact Table

IdeaMeaningUse or Check
Proposition A statement that is either true or false. Questions and open sentences are not propositions.
Negation The opposite truth value of a statement. Write not p as $\neg p$.
Conjunction and disjunction $p\land q$ means both; $p\lor q$ means at least one. The mathematical “or” is inclusive.
Implication $p\to q$ is false only when $p$ is true and $q$ is false. Its contrapositive $\neg q\to\neg p$ is equivalent.
Quantifiers $\forall$ means for every; $\exists$ means there is at least one. Negation switches the quantifier and negates the condition.

Content Formulas

Conditional
$$p\to q\equiv\neg p\lor q$$
Biconditional
$$p\leftrightarrow q\equiv(p\to q)\land(q\to p)$$
De Morgan
$$\neg(p\land q)\equiv\neg p\lor\neg q$$
Quantifier Negation
$$\neg(\forall x\,P(x))\equiv\exists x\,\neg P(x)$$
A conditional does not claim that its hypothesis is true. It says that whenever the hypothesis holds, the conclusion follows.

Classic Examples

Evaluate a Conditional

Let $p$ be false and $q$ be true. Find the truth value of $p\to q$ and its converse $q\to p$.

Solution Steps
  1. Use the conditional truth rule: only true followed by false makes an implication false.
  2. Evaluate the converse separately; swapping the statements can change the truth value.
$$p\to q=\text{true}$$ $$q\to p=\text{false}$$

Negate a Universal Claim

Negate the statement “Every student submitted the assignment.” Let $S(x)$ mean that student $x$ submitted it.

Solution Steps
  1. Switch “for every” to “there exists.”
  2. Negate the condition for that one student.
$$\neg(\forall x\,S(x))$$ $$\exists x\,\neg S(x)$$ At least one student did not submit the assignment.

Check an Equivalence

Show that $p\to q$ and $\neg p\lor q$ have the same truth values.

Solution Steps
  1. Evaluate both expressions for all four pairs of truth values.
  2. Compare the final columns.
$$\begin{array}{c|c|c|c}p&q&p\to q&\neg p\lor q\\\hline T&T&T&T\\T&F&F&F\\F&T&T&T\\F&F&T&T\end{array}$$ The columns agree in every row, so the statements are equivalent.