Propositional Logic & Logical Equivalences
Let $p$, $q$, and $r$ be propositional variables. Consider the following compound proposition:
$$F = (p \lor \neg q) \rightarrow (q \land r)$$
Part A — Complete the truth table.
Fill in every blank cell. There are $2^3 = 8$ rows.
| $p$ | $q$ | $r$ | $\neg q$ | $p \lor \neg q$ | $q \land r$ | $F$ |
|---|---|---|---|---|---|---|
| T | T | T | … | … | … | … |
| T | T | F | … | … | … | … |
| T | F | T | … | … | … | … |
| T | F | F | … | … | … | … |
| F | T | T | … | … | … | … |
| F | T | F | … | … | … | … |
| F | F | T | … | … | … | … |
| F | F | F | … | … | … | … |
Part B — Classification.
Based on your table, is $F$ a tautology, a contradiction, or a contingency? Justify your answer in one sentence.
Part C — Converse and Contrapositive.
The formula $F$ has the form $A \rightarrow B$. Write the converse, the inverse, and the contrapositive of $F$ using symbolic notation.
Classify each of the following propositions as a tautology, a contradiction, or a contingency. Justify each answer by constructing a short truth table or a logical argument.
$P_1 = p \lor \neg p$
$P_2 = (p \rightarrow q) \land (p \land \neg q)$
$P_3 = (p \rightarrow q) \leftrightarrow (\neg p \lor q)$
The table below lists the main equivalence laws from Lesson 3. You will use them to prove or simplify propositions step by step, citing the law used at each step.
Part A — Verify De Morgan's first law by truth table.
Complete the table to show that $\neg(p \land q) \equiv \neg p \lor \neg q$ for all assignments of $(p, q)$.
| $p$ | $q$ | $p \land q$ | $\neg(p \land q)$ | $\neg p$ | $\neg q$ | $\neg p \lor \neg q$ | Equal? |
|---|---|---|---|---|---|---|---|
| T | T | … | … | … | … | … | … |
| T | F | … | … | … | … | … | … |
| F | T | … | … | … | … | … | … |
| F | F | … | … | … | … | … | … |
Part B — Algebraic simplification.
Simplify the following proposition by applying equivalence laws one step at a time. Show each intermediate step and name the law used.
$$G = \neg(\neg p \lor q) \lor (p \land \neg q)$$
Steps:
Part C — Implication equivalence.
Use the implication equivalence to rewrite $(p \rightarrow q) \rightarrow r$ in a form that uses only $\neg$, $\land$, and $\lor$. Show your steps.
A formula is in Disjunctive Normal Form (DNF) when it is a disjunction of conjunctions of literals.
It is in Conjunctive Normal Form (CNF) when it is a conjunction of disjunctions of literals.
Part A — DNF from a truth table.
The truth table below defines a proposition $H(p, q, r)$. Use the minterms method to write $H$ in DNF.
| $p$ | $q$ | $r$ | $H$ |
|---|---|---|---|
| T | T | T | T |
| T | T | F | F |
| T | F | T | F |
| T | F | F | T |
| F | T | T | F |
| F | T | F | T |
| F | F | T | F |
| F | F | F | F |
DNF of $H$:
Part B — Convert to CNF.
Starting from the DNF you found in Part A, apply De Morgan's laws and other equivalences to obtain the CNF of $H$. Show your derivation.
Part C — Identify the form.
State whether each expression below is already in DNF, CNF, both, or neither. Justify in one sentence.
This exercise combines satisfiability analysis (Lesson 3) with propositional reasoning (Lesson 2).
Part A — Satisfiability.
For each proposition, determine whether it is satisfiable (there exists an assignment making it true). If satisfiable, provide a satisfying assignment; if not, explain why.
$S_1 = (p \rightarrow q) \land p \land \neg q$
$S_2 = (p \lor q) \land (\neg p \lor r) \land (\neg q \lor \neg r)$
Part B — Hypothetical Syllogism.
The hypothetical syllogism rule states: if $p \rightarrow q$ and $q \rightarrow r$ are both true, then $p \rightarrow r$ is true.
Use this rule to derive a conclusion from the following premises, and verify your answer using a truth table for the three variables.
Conclusion:
Verify — fill in the table for the specific row where $r = T$, $w = T$, $s = T$:
| $r$ | $w$ | $s$ | $r \rightarrow w$ | $w \rightarrow s$ | $r \rightarrow s$ |
|---|---|---|---|---|---|
| T | T | T | … | … | … |
Part C — Short proof using equivalences.
Prove that $(p \rightarrow q) \land (q \rightarrow p) \equiv p \leftrightarrow q$ using only known equivalence laws. Show every step.