Logic problem about set of disjunction forms(Fixed)

Question

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?

Answer 1

Neither statement is true.

Let $\Sigma = \{P_1\lor P_2, Q_1\lor Q_2\}$, and $\alpha = (P_1\lor P_2) \land (Q_1\lor Q_2)$.

Then $\Sigma\models \alpha$, but there is no $\sigma\in \Sigma$ such that $\sigma\models \alpha$.

Similarly, for "conjunction forms" instead of "disjunction forms", let $\Sigma = \{P_1\land P_2, Q_1\land Q_2\}$, and $\alpha = (P_1\land P_2) \land (Q_1\land 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 $\Sigma\models \alpha$, then there is some $\sigma\in \Sigma$ such that $\sigma\models \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 $\sigma\models \alpha$ for any $\sigma\in \Sigma$.

Case 2: There is some $\sigma\in \Sigma$ such that every literal occuring in $\sigma$ occurs in $\alpha$. Then we are done, since $\sigma\models \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 $\sigma\in \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_\sigma\mid \sigma\in \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_\sigma\mid \sigma\in \Sigma\}$, since all these literals appear in $\Sigma$.

But then for each $\sigma\in \Sigma$, we have $M\models l_\sigma$, so $M\models \sigma$, and hence $M\models \Sigma$. But $M\not\models \alpha$. So $\Sigma\not\models \alpha$, contradiction.

Answer 2

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.