Krdytkyu

I will call the disjunction of literals a disjunction form. Let $Sigma$ be a set of disjunction forms, and $alpha$ is a well-formed formula satisfying $Sigma vDash alpha$. For all propositional variable $p$, assume that $p$ and $neg p$ do not occur in element of $Sigma$ at the same time.

Prove that $exists sigma in Sigma$ such that $sigma vDash alpha$. And the above proposition is true if we change all disjunctions to conjunctions.

Can you help me?

Neither statement is true.

Let $Sigma = {P_1lor P_2, Q_1lor Q_2}$, and $alpha = (P_1lor P_2) land (Q_1lor Q_2)$.

Then $Sigmamodels alpha$, but there is no $sigmain Sigma$ such that $sigmamodels alpha$.

Similarly, for "conjunction forms" instead of "disjunction forms", let $Sigma = {P_1land P_2, Q_1land Q_2}$, and $alpha = (P_1land P_2) land (Q_1land Q_2)$.

Edit: In response to the comments, I'll prove the following.

Suppose $Sigma$ is a nonempty set of disjunctions of literals, such that for every propositional variable $p$, at most one of the literals $p$ and $lnot p$ occurs in $Sigma$. And suppose $alpha$ is a disjunction of literals. If $Sigmamodels alpha$, then there is some $sigmain Sigma$ such that $sigmamodels alpha$.

Case 1: There is some propositional variable $p$ such that both of the literals $p$ and $lnot p$ occur in $alpha$. Then $alpha$ is a tautology, so $sigmamodels alpha$ for any $sigmain Sigma$.

Case 2: There is some $sigmain Sigma$ such that every literal occuring in $sigma$ occurs in $alpha$. Then we are done, since $sigmamodels alpha$.

We will show that if we assume we are not in Case 1 or Case 2, we have a contradiction. Since we are not in Case 2, for every $sigmain Sigma$, we can pick some literal $l_sigma$ which appears in $sigma$ but not in $alpha$.

Let $M$ be a model/interpretation such that the literals ${l_sigmamid sigmain Sigma}$ are all true, and the literals appearing in $alpha$ are all false. We can do this, because:

1. We have arranged that no literal $l_sigma$ appears in $alpha$.


2. Since we are not in Case 1, no literal and its negation both appear in $alpha$.


3. By hypothesis, no literal and its negation both appear in ${l_sigmamid sigmain Sigma}$, since all these literals appear in $Sigma$.

But then for each $sigmain Sigma$, we have $Mmodels l_sigma$, so $Mmodels sigma$, and hence $Mmodels Sigma$. But $Mnotmodels alpha$. So $Sigmanotmodels alpha$, contradiction.

Hint: For every propositional formula $phi$ there is an equivalent formula $psi$ in conjunctive normal form, that is,

$$ psi = bigwedge^{m}_{i=1} (bigvee^{m_i}_{j=1} ell_{ij}) $$

where the $ell_{ij}$'s are literals. And there is a similar result for disjunctive normal forms.