Cheap and Secure Web Hosting Provider : See Now

[Solved]: Meaning of empty clause

, , No Comments
Problem Detail: 

Why does the empty clause is logically equivalent to a contraddiction: $\square \cup \square \Longleftrightarrow \perp$

and why the empty cube is logically equivalent to a tautology: $\square \cap \square \Longleftrightarrow \top$ ?

Asked By : alessandro

Answered By : zarathustra

You have to understand that this is a convention. Conjunctions and disjunctions are supposed to be applied to formulas. Sometimes we want to keep things general, so that we may have to allow "empty disjunctions" and "empty conjunctions", and to that purpose we define what they are.

Here is one way to see why this convention is used. Let us consider a binary commutative associative operation $\oplus\colon A\times A\rightarrow A$ on some set $A$. Suppose moreover that there exists an element $e\in A$ such that $\forall a\in A, a\oplus e = e\oplus a = a$.

Since the operation is associative, we can make sense of the expresion $\bigoplus_{i\in I} a_i $ when $I$ is a finite non-empty set, which we define to be $(\dots(a_{i_1}\oplus a_{i_2})\oplus\ldots\oplus a_{i_{n-1}})\oplus a_{i_n}$. Since we don't want to always have to specify what happens when $I$ is empty, we take the convention that $\bigoplus_{i\in I} a_i = e$ when $I=\emptyset$. Why is this convention useful? It allows to write things like $$\left(\bigoplus_{i\in I} a_i\right) \oplus \left(\bigoplus_{i\in J} a_i\right) = \bigoplus_{i\in I\cup J} a_i$$ even if $I,J$ are allowed to be empty sets (where we implicitly replace $J$ by some other enumeration $J'$ that is so that $J'\cap I=\emptyset$). If we were to take some other convention, we would always have to be careful when writing the expression above.

See how this general situation occurs a lot in mathematical writing:

  • the empty sum $\sum_{i\in I} a_i$ is taken to be $0$ when $I=\emptyset$, as $0$ is a neutral element for the addition of real numbers,
  • the empty product $\prod_{i\in I} a_i$ is taken to be $1$ when $I=\emptyset$,
  • in the example of formulas, consider the binary operator $\lor$. A clause is a disjunction of propositional variables, as you say, hence it can be written as $\bigvee_{i\in I} p_i$. When $I$ is empty, we want to define the empty disjunction as the neutral element for $\lor$. This element is $\bot$ (up to logical equivalence), as $p\lor \bot \Leftrightarrow \bot\lor p\Leftrightarrow p$ holds.
  • in the example of formulas and cubes, we want to give a meaning to $\bigwedge_{i\in I}p_i$. Following the same convention, we use the neutral element for $\land$, which is $\top$: indeed, for any proposition variable it holds that $p\land\top\Leftrightarrow\top\land p\Leftrightarrow p$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30539

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback