Answer to Question #298725 in Discrete Mathematics for shahana

Question

Determine whether each of these compound propositions

is satisfiable.

a) (p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q)

b) (p → q) ∧ (p → ¬q) ∧ (¬p → q) ∧ (¬p → ¬q)

c) (p ↔ q) ∧ (¬p ↔ q)

Answer 1

A compound proposition is satisfiable if at least one entry of the truth table is TRUE. We find the truth table for each of the given compound propositions.

a) Truth table for (p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q)

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline p & q & p \vee \neg q & \neg p \vee q & \neg p \vee \neg q & \left(p \vee \neg q\right) \wedge \left(\neg p \vee q\right) \wedge \left(\neg p \vee \neg q\right)\\ \hline T & T & T & T & F & F\\ T& F& T& F& T& F\\ F& T& F& T& T& F\\ F& F& T& T& T& T\\ \hline \end{array}$

b) Truth table for (p → q) ∧ (p → ¬q) ∧ (¬p → q) ∧ (¬p → ¬q)

$\begin{array}{|c|c|c|c|c|c|c|} \hline p & q &p \rightarrow q & p \rightarrow \neg q & \neg p \rightarrow q & \neg p \rightarrow \neg q & \left(p \rightarrow q\right) \wedge \left(p \rightarrow \neg q\right)\wedge\\ &&&&&& \left(\neg p \rightarrow q\right) \wedge \left(\neg p \rightarrow \neg q\right)\\ \hline T& T& T& F& T& T& F\\ T& F& F& T& T& T& F\\ F& T& T& T& T& F& F\\ F& F& T& T& F& T& F\\ \hline \end{array}$

c) Truth table for (p ↔ q) ∧ (¬p ↔ q)

$\begin{array}{|c|c|c|c|c|c|} \hline p & q & p \leftrightarrow q & \neg p & \neg p \leftrightarrow q & \left(p \leftrightarrow q\right) \wedge \left(\neg p \leftrightarrow q\right)\\ \hline T& T& T& F& F& F\\ T& F& F& F& T& F\\ F& T& F& T& T& F\\ F& F& T& T& F& F\\ \hline \end{array}$

From the above truth tables, we see that the first compound proposition alone is satisfiable as it contains one TRUE value and the remaining two compound propositions are contradiction as all the truth values are FALSE.