How to find a total ordering?

78 Views Asked by At

How to find a total ordering $>$ on the ground atoms $A_1,\ldots,A_5$ such that the associated clause ordering $>_c$ orders the following clauses in this way:

$$A_2\lor A_3 >_c A_1\lor A_1\lor\neg A_3 >_c A_3\lor A_5>_c A_3\lor A_4 >_c \neg A_1\lor A_4 >_c\neg A_5$$

1

There are 1 best solutions below

0
On

The multisets of literals associated with the six clauses in the question are

$$\{\!\{A_2,A_3\}\!\},\{\!\{A_1,A_1,\neg A_3\}\!\},\{\!\{A_3,A_5\}\!\},\{\!\{A_3,A_4\}\!\},\{\!\{\neg A_1,A_4\}\!\},\text{ and }\{\!\{\neg A_5\}\!\}\;.$$

Consider the requirement that $\{\!\{A_3,A_5\}\!\}>_C\{\!\{A_3,A_4\}\!\}$. The only literal that appears more often in $\{\!\{A_3,A_4\}\!\}$ than in $\{\!\{A_3,A_5\}\!\}$ is $A_4$, so there must be an $x>A_4$ that appears more often in $\{\!\{A_3,A_5\}\!\}$ than in $\{\!\{A_3,A_4\}\!\}$. The only possibility is $x=A_5$, so we must have $A_5>A_4$.

Similarly, the requirement that $\{\!\{A_3,A_4\}\!\}>_C\{\!\{\neg A_1,A_4\}\!\}$ forces $A_3>_L\neg A_1$, and since $\neg A_1>_L A_1$, this in turn forces $A_3>A_1$.

Applying the same reasoning to the requirement that $\neg A_1\lor A_4 >_C\neg A_5$ leads to the conclusion that either $\neg A_1>_L\neg A_5$, in which case $A_1> A_5$ (why?), or $A_4>_L\neg A_5$, in which case $A_4> A_5$. But we already know that $A_5>A_4$, so we must have $A_1>A_5$.

So far, then, we know that $A_3>A_1>A_5>A_4$. Can you use finish it off to get $A_2$ correctly placed?