# Prove that the set $\{((p\to q)\lor r),(p\lor(q\lor s))\}$ is satisfiable?

Am I using the correct logic in my proof below?

Rewriting the first element in the set using Logical equivalence involving Conditional statement yields: $$(\neg p\lor q)\lor r$$ – this can be further rewritten to: $$\neg p\lor (q \lor r)$$ by applying the commutative and associate laws.

Let $$A=(q\lor r)$$

Let $$B=(q\lor s)$$

The above set can be considered satisfiable if $$\neg p\lor A,p\lor B \vDash_{taut} (A\lor B)$$

1. Let $$v(\neg p \lor A)=v(p\lor B)=t$$

Case 1: $$v(p)=t$$: by (1), $$v(A)=t$$. But then $$v(A\lor B)$$=t.

Case 2: $$v(p)=f$$: by (1), $$v(B)=t$$. But then $$v(A\lor B)=t$$

QED

• It would be easier to just observe that both disjunctions would be satisfied if the common disjunct, $q$, were true. – Graham Kemp May 12 at 23:33
• I'm trying to apply stuff I've read, so I'm not sure if I'm over complicating it, but would this make sense to prove? Let $A=(p\to q)\lor r,B=p\lor (q\lor s)$ The set is satisfiable if $A,B\vDash_{taut} (A\land B)$ then prove $v(A)=t, v(B)=t$ when $v(q)=t$. – Elliott de Launay May 13 at 18:03

Knowing the truth table of ( X v Y) one can see that :

(1) R being true is a sufficient condition for ( P-->Q) v R to be true.

(2) P being true is a sufficient condition for P v ( Q v S) to be true.

So any interpretation assigning the truth value " true" to R and to P makes the 2 formulas true at the same time , for example :

P --> true

Q --> false

R --> true

S --> false

So there is at least one interpretation in which both formulas are true at the same time.

It looks like what you're doing is proving that if the original pair of formulas, $$(p\to q)\lor r$$ and $$p\lor(q\lor s)$$, are (simultaneously) satisfied, then so is the single formula $$A\lor B$$. But that's not what you are asked to do. In short, you seem to be assuming the requested conclusion, and obtaining some other, unrequested conclusion.

All you need to do, instead, is show that some assignment of true/false values to $$p$$, $$q$$, $$r$$, and $$s$$ make the two formulas $$(p\to q)\lor r$$ and $$p\lor(q\lor s)$$ both true. As Graham Kemp notes in comments below the OP, setting $$q$$'s value to true makes both formulas true, regardless of the values for $$p$$, $$r$$, and $$s$$. Alternatively, setting the values of both $$r$$ and $$s$$ to true does the trick as well. Indeed, the only assignments for $$(p,q,r,s)$$ that do not satisfy the two formulas are $$(t,f,f,f)$$ and $$(f,f,f,f)$$, since, as you found, their conjunction is tautologically equivalent to $$A\lor B=(q\lor r)\lor(q\lor s)=q\lor r\lor s$$.