1
$\begingroup$

This is a question about classical propositional logic.

Definitions: If there is a proof from $\alpha$ to $\beta$, we'll write $\alpha \vdash \beta$. We'll say that $\alpha$ is equivalent to $\beta$ if $\alpha \vdash \beta$ and $\beta \vdash \alpha$ and I'll write it $\alpha \equiv \beta$. A literal is a propositional variable or its negation. I'll say that a formula is in conjunctive form if it can be written as a conjunction of literals, for example: $a \land b \land \lnot c$. A disagreement is a case where two formulas $\alpha$ and $\beta$ are in conjunctive form and have a propositional variable such that one is positive in one formula and negative in the other. So for example, the formulas $b \land c$ and $\lnot b \land c$ disagree on the variable $b$.

First, we observe that in cases where $\alpha$ and $\beta$ have a single disagreement, their disjunction may be equivalent to another formula in conjunctive form. For example,

$$ ((a \land b \land c) \lor (a \land b \land \lnot c)) \equiv a \land b$$

Question: Consider three conjunctive forms $\alpha$, $\beta$, and $\varphi$. The formulas $\alpha$ and $\beta$ are over the same propositional variables and have 2 or more disagreements. Is the following ever possible?

$$ (\alpha \lor \beta) \equiv \varphi$$

I believe no such $\varphi$ exists, but my attempts to prove this seem laborious. Is there a short proof of this?

$\endgroup$

1 Answer 1

1
$\begingroup$

Write $\alpha = a_1 \land a_2 \land \cdots \land a_n$, $\beta = b_1 \land b_2 \land \cdots \land b_n$. By properties of $\land$ we may assume $a_i = b_i$ or $a_i = \neg b_i$ for all $i$ and $a_1 = \neg b_1, a_2 = \neg b_2$. We now treat $a_1, a_2, \dots, a_n$ as free variables. Set $\varphi := \alpha \lor \beta$ and assume it is a conjuction. Note that $\varphi$ then consists of the same free variables $a_1, a_2, \dots, a_n$ (so it is a conjuction of some subset of these). Now, we can either construct a truth table for $\varphi$, or see directly from the formula that $\varphi = 1$ iff $a_1 = a_2 = \cdots = a_n = 1$ or $b_1 = b_2 = \cdots = b_n = 1$, so the truth table has exactly two rows for which $\varphi = 1$.

As $\varphi$ is a conjuction, this is only possible if it is independent of exacty one of the variables $a_1, a_2, \dots, a_n$. By this I mean that $\varphi$ is a conjuction of some $n - 1$ of these variables or their negations, e.g. perhaps $\varphi = a_1 \land \neg a_2 \land a_3 \land \neg a_4 \land \cdots \land a_{n - 1}$, but there are definitely exactly $n - 1$ of them. Really, if there were more, then there'd be exactly $n$, so $\varphi$ would be true in exactly one row. If there were fewer, we could assume that $\varphi$ is independent of $a_k, a_{k + 1}, \dots, a_{n - 1}, a_n$. Then it is a conjuction of the first $k - 1$ terms and, as a conjuction, it is true in exactly one interpretation of those terms. But the $n - k + 1$ leftover terms then allow for $2^{n - k + 1}$ different "repetitions" of the interpretation which makes $\varphi$ true in the truth table, making it true for many more than $2$ rows.

So, $\varphi$ depends on exactly $n - 1$ variables. One of these is either $a_1$ or $a_2$, without loss of generality $a_1$. But then $\varphi$ is true both when $a_1 = 1$ and when $a_1 = 0$, which isn't possible for a conjunction. Contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .