1. **Problem Statement:** Show that $R \to S$ can be derived from the premises $P \to (Q \to S)$, $\neg R \lor P$, and $Q$. 2. **Understanding the premises:** - $P \to (Q \to S)$ means if $P$ is true, then if $Q$ is true, $S$ must be true. - $\neg R \lor P$ means either $R$ is false or $P$ is true. - $Q$ is true. 3. **Goal:** Prove $R \to S$, which means if $R$ is true, then $S$ must be true. 4. **Step-by-step derivation:** 1. Assume $R$ is true (to prove $R \to S$ by conditional proof). 2. From $\neg R \lor P$ and $R$ true, $\neg R$ is false, so $P$ must be true (disjunctive syllogism). 3. From $P$ true and $P \to (Q \to S)$, we get $Q \to S$ (modus ponens). 4. Given $Q$ is true, from $Q \to S$ and $Q$, we get $S$ (modus ponens). 5. **Conclusion:** Assuming $R$ leads to $S$, so $R \to S$ is derived. --- **Next, obtain PDNF and PCNF of $(P \land Q) \lor (\neg P \land R)$:** 1. **PDNF (Perfect Disjunctive Normal Form):** - The formula is already a disjunction of conjunctions of literals. - So PDNF is $(P \land Q) \lor (\neg P \land R)$. 2. **PCNF (Perfect Conjunctive Normal Form):** - Use distributive laws to convert to CNF. - Rewrite formula: $$ (P \land Q) \lor (\neg P \land R) = ((P \lor \neg P) \land (P \lor R)) \land ((Q \lor \neg P) \land (Q \lor R)) $$ - Since $P \lor \neg P$ is a tautology, it can be removed: $$ (P \lor R) \land (Q \lor \neg P) \land (Q \lor R) $$ - So PCNF is $(P \lor R) \land (Q \lor \neg P) \land (Q \lor R)$. --- **Construct Truth Table for $(P \land (Q \land R)) \lor \neg ((P \lor Q) \land (R \lor S))$:** | P | Q | R | S | $Q \land R$ | $P \land (Q \land R)$ | $P \lor Q$ | $R \lor S$ | $(P \lor Q) \land (R \lor S)$ | $\neg ((P \lor Q) \land (R \lor S))$ | Final Formula | |---|---|---|---|-------------|------------------------|------------|------------|-------------------------------|------------------------------------|--------------| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | --- **Show that $Q \lor (P \land Q) \lor (\neg P \land Q)$ is a tautology without truth table:** 1. Factor $Q$ out: $$ Q \lor (P \land Q) \lor (\neg P \land Q) = Q \lor Q \land (P \lor \neg P) $$ 2. Since $P \lor \neg P$ is always true (law of excluded middle), $$ Q \lor Q \land \text{true} = Q \lor Q = Q $$ 3. So the formula simplifies to $Q$, but since $Q$ appears in all terms, the entire formula is true whenever $Q$ is true. 4. But the original formula is $Q$ or something else involving $Q$, so it is always true when $Q$ is true. 5. If $Q$ is false, then all terms are false, but since the formula is $Q$ or terms with $Q$, it is false only if $Q$ is false. 6. However, the formula is $Q \lor (P \land Q) \lor (\neg P \land Q)$, which is logically equivalent to $Q$. 7. So the formula is a tautology if $Q$ is always true, or in other words, the formula is logically equivalent to $Q$. --- **Summary:** - Derived $R \to S$ from given premises. - Found PDNF and PCNF of $(P \land Q) \lor (\neg P \land R)$. - Constructed truth table for the given formula. - Showed the formula $Q \lor (P \land Q) \lor (\neg P \land Q)$ is logically equivalent to $Q$ and thus a tautology if $Q$ is true. This completes the solution for the first question.