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

119 Views Asked by At

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

2

There are 2 best solutions below

0
On

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$.

0
On

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.