To show that a compound proposition is satisfiable, we need to find a particular

Question

To show that a compound proposition is satisfiable, we need to find a particular assignment of truth values to its variables that makes it true. However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Determine (without using a truth table) whether each of the following compound propositions is satisfiable. Justify your answer. a. (p q) Lambda (p q) Lambda (p q) b. (p q) Lambda (p q) Lambda (q r) Lambda (q r) Lambda (q r) c. (p doubleheadarrow q) Lambda (q doubleheadarrow q) A truth table can be used to determine whether a compound proposition is satisfiable. However, as the number of variables in a compound proposition grows, using a truth table to determine whether it is satisfiable becomes impractical. No algorithm is known to determine in a reasonable amount of time whether an arbitrary compound proposition with a large number of variables (i.e., thousands, millions) is satisfiable. This is an important unsolved problem in Computer Science.

Explanation / Answer

3
a.
(p or NOT q) AND (NOT p or q) is true either when p = 1 and q = 1 or when p = 0 and q = 0 i.e p = q

now to (NOT p OR NOT q) is true when either p or q or both are 0

so if and only if p and q both are zero/false, the equation is true

b.
(q or r) AND (NOT q or NOT r) is true if and only if q is not equal to r

(q or NOT r) and also considering the previous condition, to get true value, q must be true and r must be false

so till now conclusion--> q = true, r = 0

as said in part a
(p or NOT q) AND (NOT p or q) is true either when p = 1 and q = 1 or when p = 0 and q = 0 i.e p = q

given q = true, p should also be true.

so the equation is satisfiable if p = q = true, and r = false

c
(p <-> q) is true is p and q are equal, but
(NOT p <-> q) is true is p and q are not equal

since they contradict each other, the statement cannot be true.

I hope this is what you needed. Let me know if you need any changes. I shall be glad to help you.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.