I came across the following statement:
$(P∨Q)$ is satisfiable if and only if $(P∨R)∧(Q∨¬R)$ is satisfiable
And I am supposed to say whether it is true or false.
Let $F(x,y,z)$ be a boolean function (or propositional function) involving 3 boolean variables (or 3 atomic propositions) then we can say that, $F$ is satisfiable iff $\exists x \exists y \exists z (F(x,y,z)=\text{True})$
This is what I know about satisfiability in propositional logic.
If I assume the above statement to be represented as $SAT(F(x,y,z))$,which would mean that $F(x,y,z)$ is satisfiable.
Then the statement which I need to analyze becomes:
$SAT(P\lor Q)$ iff $SAT((P∨R)∧(Q∨¬R))$
that means, I need to check the satisfiability of the two compound propositions $(P\lor Q)$ and $(P∨R)∧(Q∨¬R)$ independently… Considering that I drew the truth table and saw that both $(P\lor Q)$ and $(P∨R)∧(Q∨¬R)$ are satisfiable independently… But then the "if and only if" sort does not seem to make sense to me… [as we are working independently]. I just tried to convenience myself that the statement is true when $SAT(P\lor Q)$ and $SAT((P∨R)∧(Q∨¬R))$
has the same value or parity [sort of equivalence check]
So the statement is true.
Or do I need to consider the statement as :
$\exists P \exists Q \exists R$ [$(P∨Q) =\text{True}$ if and only if $(P∨R)∧(Q∨¬R) =\text{True}$ ]
Best Answer
The assignment $(P,Q,R)=$ (true,true,true) shows that both $(P∨Q)$ and $(P∨R)∧(Q∨¬R)$ can be true, i.e., are satisfiable, which in turn shows that the above statement is true.
The satisfiability of a sentence is not a function of a particular assignment, but of the collection of its possible assignments. Thus, in the above, we need $(P∨Q)$ and $(P∨R)∧(Q∨¬R)$ to each, for some assignment (independently), be true, as opposed to requiring them to be true for the same assignment—the two sentences don't even need to have any common atomic proposition.
P.S. Showing unsatisfiability is equivalent to showing validity of negation.