Constructive proof layers-norm (propositional logic)

Question

I have to write a constructive proof that for every propositional formula has an equivalent formula in Layers-Norm

We define Layer-Norm for propositional formulas as follows:

1. Literals are in Layer-Norm.

2. Are $\phi$ and $\psi$ in Layers-Norm we call $(\phi \lor \psi)$ a U- Formula.

3. Are $\phi$ and $\psi$ both U-Formulas is $(\phi \land \psi)$ in Layers-Norm.

Could someone advice me on this one? I can't come up with anything. First off I don't get it how to transform any formula into layers norm.

Second, I don't really understand the definition confused about it.

Edit 1: Now i have the following

For literals : S(L):= L U(L):= L∨L S(ϕ∧ψ):=U(ϕ)∧U(ψ), U(ϕ∨ψ):=S(ϕ)∨S(ψ), S(ϕ ∨ ψ) := U(ϕ ∨ ψ) ∧ U(ϕ ∨ ψ), U(ϕ∧ψ) := S(ϕ∧ψ) ∨ S(ϕ∧ψ)

Any advice now how to construct the proof for that?

Answer 1

Any truth-function, no matter how complex, can be expressed with $\land$, $\lor$, and $\neg$.

You can see this by thinking about truth-tables, which is just a special way of representing any truth-function.

For example, suppose we have a truth-function whose truth-conditions are given by the following table:

\begin{array}{ccc|c} P&Q&R&f(P,Q,R)\\ \hline T&T&T&F\\ T&T&F&T\\ T&F&T&F\\ T&F&F&T\\ F&T&T&T\\ F&T&F&F\\ F&F&T&F\\ F&F&F&F\\ \end{array}

This function is true in rows 2,4, and 5, and thus we generate the terms $P \land Q \land \neg R$, $P \land \neg Q \land \neg R$, and $\neg P \land Q \land R$ respectively. Disjuncting them gives us:

$$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)$$

This particular formula is said to be in Disjunctive Normal Form (DNF): it is a generalized disjunction, where each disjunct is a generalized conjunction of literals, and where a literal is either an atomic variable or the negation thereof.

Now, even though this is just an example, I think it should also be pretty clear that this should work for any truth-function: For every row where the function evaluates to $T$, just write a conjunction of literals corresponding to the truth-values of the atomic claims for that particular row. And, once you have those for all rows,, then disjunct them all together. The result will be in DNF, and will capture the original function,

Now, there is also something called the Conjunctive Normal Form (CNF): this is a generalized conjunction, where each conjunct is a generalized disjunction of literals.

And, just as any function can be written using a DNF expression (it can be 'turned into' DNF), it can also be shown that any truth-function can be expressed using a CNF expression.

I mention the CNF, because the CNF feeels very much like the 'Layers-Norm' that you are dealing with (and, the 'U-formula' feels like a DNF). For example, the expression:

$$(P \lor \neg Q) \land (\neg R \lor S)$$

is in CNF, and also in 'Layers-Norm' format.

However, the two are nor the same. There are two important differences between CNF and Layers-Norm:

1. A CNF expression is a very 'flat' expression. Expressed in tree notation, there would basically be $3$ layers to them: First, there are the literals. The next 'layer' is disjunctions of literals, and the final 'layer' is a (single) conjunction of those disjunctions.

On the other hand, in a 'Layers-Norm' expression, while you once again have literals as your 'leaves', you can keep going back and forth between layers of disjunctions and conjunctions to arbitrary depth. For example, the following expression would be in 'Layers-Norm', though not in CNF:

$$[(P \lor \neg Q) \land (\neg R \lor S)] \lor T$$

2. A CNF uses generalized disjunctions and conjunctions. That is, any disjunction (or conjunction) in a CNF expression can have any number of disjuncts (conjuncts)

However, the 'Layers-Norm' format requires that every disjunction has exactly two disjuncts, and that every conjunction has exactly two conjuncts. Thus, the following expression is in CNF, but not in 'Layers-Norm':

$$P \land Q \land R$$

Still, with the literals as the 'leaves' in DNF CNF, as well as 'Layers-Norm', you would think that one should be able to transform the one format into the other fairly easily. And this is indeed the case. For example, the above expression can be put into 'Layers-Norm' as follows:

$$((P \land Q) \lor (P \land Q)) \land (R \lor R)$$

And if we have another conjunct:

$$P \land Q \land R \land S$$

we simply add one more layer:

$$(((P \land Q) \lor (P \land Q)) \land (R \lor R)) \lor (((P \land Q) \lor (P \land Q)) \land (R \lor R)) \land (S \lor S)$$

See how that works?

As a recursive function that transforms any geralized conjunction of literals $\phi$ into a Layer-Norm:

$Layers-Norm(\phi) = \phi$

$Layers-Norm(\phi_1 \land \phi_2) = \phi_1 \land \phi_2$

and for $n > 2$:

$Layers-Norm(\phi_1 \land ... \land \phi_{n-1} \land \phi_n) = (Layers-Norm(\phi_1 \land ... \land \phi_{n-1}) \lor Layers-Norm(\phi_1 \land ... \land \phi_{n-1})) \land (\phi_n \lor \phi_n)$

(if you want a more 'balanced' tree, you can of course keep breaking up near the middle rather than breaking off one conjunct at a time ... but for this problem we just need to show that there is some 'Layers-Norm' ... not necessarily a 'nice' one or 'efficient' one)

We can do something similar with disjunctions. For example:

$$P \lor Q \lor R$$

can be put into a U-expression like so:

$$((P \lor Q) \land (P \lor Q)) \lor R$$

and that becomes a 'Layers-Norm' simply by:

$$(((P \lor Q) \land (P \lor Q)) \lor R) \land (((P \lor Q) \land (P \lor Q)) \lor R)$$

So, where all $\phi_i$ are generalized conjunctions of literals:

$Layers-Norm(\phi_1 \lor ... \lor \phi_{n-1} \lor \phi_n) = (U-Expression(\phi_1 \lor... \lor\phi_{n-1} \lor \phi_n)) \land (U-Expression(\phi_1 \lor... \lor\phi_{n-1} \lor \phi_n)) $

where:

$U-Expression(\phi) = Layers-Norm (\phi)$

$U-Expression(\phi_1 \lor \phi_2) = Layers-Norm(\phi_1) \lor Layers-Norm(\phi_2)$

and for $n>2$:

$U-Expression(\phi_1 \lor... \lor\phi_{n-1} \lor \phi_n) = (U-Expression(\phi_1 \lor... \lor\phi_{n-1}) \land U-Expression(\phi_1 \lor... \lor\phi_{n-1})) \lor Layers-Norm(\phi_n)$

Let's apply this algorithm to the expression of the earlier example:

$$(P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R)$$

Here goes (I'll use $LN$ for $Layers-Norm$ and $U$ for $U-Expression$):

$$LN((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R))=$$

$$U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R))\land U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R))=$$

$$(U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R)) \land U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R))) \lor LN(\neg P \land Q \land R))\land (U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R)) \land U((P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R))) \lor LN(\neg P \land Q \land R))=$$

$$((LN(P \land Q \land \neg R) \lor LN(P \land \neg Q \land \neg R)) \land (LN(P \land Q \land \neg R) \lor LN(P \land \neg Q \land \neg R))) \lor LN(\neg P \land Q \land R))\land ((LN(P \land Q \land \neg R) \lor LN(P \land \neg Q \land \neg R)) \land (LN(P \land Q \land \neg R) \lor LN(P \land \neg Q \land \neg R))) \lor LN(\neg P \land Q \land R))=$$

$$(((LN(P \land Q) \lor LN(P \land Q))\land \neg R) \lor (LN(P \land \neg Q)\lor LN(P \land \neg Q)) \land \neg R)) \land ((LN(P \land Q) \lor LN(P \land Q))\land \neg R) \lor (LN(P \land \neg Q)\lor LN(P \land \neg Q)) \land \neg R))) \lor ((LN(\neg P \land Q) \lor LN(\neg P \land Q)) \land R))\land (((LN(P \land Q) \lor LN(P \land Q))\land \neg R) \lor (LN(P \land \neg Q)\lor LN(P \land \neg Q)) \land \neg R)) \land ((LN(P \land Q) \lor LN(P \land Q))\land \neg R) \lor (LN(P \land \neg Q)\lor LN(P \land \neg Q)) \land \neg R))) \lor ((LN(\neg P \land Q) \lor LN(\neg P \land Q)) \land R))=$$

$$((((P \land Q) \lor (P \land Q))\land \neg R) \lor ((P \land \neg Q)\lor (P \land \neg Q)) \land \neg R)) \land (((P \land Q) \lor (P \land Q))\land \neg R) \lor ((P \land \neg Q)\lor (P \land \neg Q)) \land \neg R))) \lor (((\neg P \land Q) \lor (\neg P \land Q)) \land R))\land ((((P \land Q) \lor (P \land Q))\land \neg R) \lor ((P \land \neg Q)\lor (P \land \neg Q)) \land \neg R)) \land (((P \land Q) \lor (P \land Q))\land \neg R) \lor ((P \land \neg Q)\lor (P \land \neg Q)) \land \neg R))) \lor (((\neg P \land Q) \lor (\neg P \land Q)) \land R))$$

Yikes! ... but it works!

Answer 2

Formulas in Layer-norm are exactly formulas in conjunctive normal form, i.e. conjunctions of one or more clauses (or U-formulas), where a clause is a disjunction of literals.

Formally, a formula in conjunctive normal form is written as $$ ( l_{11} \lor \ldots \lor l_{1n_1} ) \land \ldots \land ( l_{m1} \lor \ldots \lor l_{mn_m} ) $$ where $l_{ij}$ are literals, i.e. propositional variables or their negation.

For instance, given the variables $p, q, r$, the following are formulas in conjunctive normal form (i.e. in Layer-norm): \begin{align} p && p \lor \lnot q && (p \lor q) \land \lnot r && (p \lor \lnot q) \land (r \lor p \lor q) \end{align} while the following formulas are not in conjunctive normal form: \begin{align} \lnot(p \land q) && \lnot(p \lor q) && (p \land q) \lor r && p \land (q \lor (r \land r)) \end{align}

---

The theorem that you have to prove states that every formula can be converted into an equivalent formula that is in conjunctive normal form (i.e. in Layer-norm).

A nice constructive proof of this statement is sketched here. The starting point of the proof is that two formulas are logically equivalent if they are false under the same conditions (which imply that they are true under the same conditions). Here conditions mean truth-assignments to their propositinal variables. Now, given a formula $\phi$, consider all its possible truth-assignments, i.e. its truth table. If $n$ distinct propositional variables occur in $\phi$, then there are $2^n$ possible truth-assignments for $\phi$ (i.e. $2^n$ rows in its truth table). Look only at the rows such that $\phi$ is false. For each of these rows, construct a disjunction $(l_1 \lor \dots \lor l_n)$ where, for all $1 \leq i \leq n$, $l_i$ is the $n^\text{th}$ propositional variable if it is false in such a row, otherwise $l_i$ is the negation of such a variable. Take the conjunction of all these disjunctions built from the rows where $\phi$ is false. It is immediate to prove that the formula you obtain is:

1. in conjunctive normal form (i.e. in Layer-norm), and
2. logically equivalent to $\phi$.

For instance, let $\phi = p \leftrightarrow q$, where $p$ and $q$ are propositional variables. The truth table of $\phi$ is

\begin{array}{c|c|c} p & q & p \leftrightarrow q\\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array}

and a formula in conjunctive normal form (i.e. in Layer-norm) built up following the method above is $$ (\lnot p \lor q) \land (p \lor \lnot q) $$ where the first disjunction $(\lnot p \lor q)$ corresponds to the second row of the truth table of $\phi$, and the disjunction $(p \lor \lnot q)$ corresponds to the third row of the truth table of $\phi$.

---

Another constructive proof that every formula can be converted into an equivalent formula that is in conjunctive normal form (i.e. in Layer-norm) is to apply the following procedure:

1. eliminate implications and equivalences: repeatedly replace $\phi → \psi$ with $\lnot \phi \lor \psi$; repeatedly replace $\phi \leftrightarrow \psi$ with $( \phi \lor \lnot \psi ) \land ( \lnot \phi \lor \psi )$;
2. Move $\lnot$ inwards by repeatedly applying De Morgan's Law; specifically, replace $\lnot (\phi \lor \psi)$ with $(\lnot \phi) \land (\lnot \psi)$; replace $\lnot (\phi \land \psi)$ with $(\lnot \phi)\lor (\lnot \psi)$; and replace $\lnot\lnot \phi$ with $\phi$;
3. Distribute $\lor$ inwards over $\land$: repeatedly replace $\phi \lor (\psi \land \chi)$ with $(\phi \lor \psi)\land (\phi \lor \chi)$.

Then you have to prove this procedure eventually terminates in a conjunctive normal form (i.e. in a Layer-norm), which is not trivial.