# Two questions about the lattice derived from 0th-order formulas

It's not clear to me if the definitions I've been given are common. Therefore I will give a brief overview of the constructions I'll need to talk about the objects I want to.

### Prerequisite:

Given any set of of single-sentence symbols (some may call them propositional variables?) $A = \{\, a_i \mid i \in I\, \}$ one can define the set of $0$th-order formulas $\mathcal{F}(A)$ over $A$:

1. $a_i \in \mathcal{F}(A)$ for every $i \in I$,
2. if $a \in \mathcal{F}(A)$ then $\neg a \in \mathcal{F}(A)$ and
3. if $a,b \in \mathcal{F}(A)$ then $(a\circ b) \in \mathcal{F}(A)$ where $\circ \in \{\wedge,\vee,\rightarrow, \leftrightarrow\}$.

Then one is able to apply some semantics via an interpretation $\omega : \mathcal{F}(A) \rightarrow \{0,1\}\cong \mathbb{Z}_2$ which is a function with the following properties:

• $\omega(\neg a) = 1-\omega(a)$
• $\omega((a\wedge b)) = \omega(a)\omega(b)$
• $\omega((a\vee b)) = \omega(a)+\omega(b)+\omega(a)\omega(b)$
• $\omega((a\rightarrow b)) = \omega((\neg a \vee b))$
• $\omega((a\leftrightarrow b)) = \omega((a\rightarrow b))\omega((a\leftarrow b))$

Based upon such interpretations one defines the equivalence relation $a \sim b$ on $\mathcal{F}(A)$:

\begin{align*} a \sim b \text{ iff for all interpretations } \omega : \mathcal{F}(A)\rightarrow\{0,1\} \text{ it holds that } \omega(a\leftrightarrow b) = 1. \end{align*} This seems to be the same like $a\sim b :\Leftrightarrow \omega(a) = \omega(b)$ for all interpretations $\omega$.

Now it turns out that $\mathcal{F}(A)\big/{\sim}$ is a complementary distributiv lattice with the derived operations $\wedge, \vee$ and the constants $0 = \{\,a \in\mathcal{F}(A) \mid \forall \omega: \omega(a) = 0\,\}$ (the equivalence class of all contradictions) and $1 = \{\,a \in \mathcal{F}(A)\mid\forall\omega:\omega(a) = 1\,\}$ (the equivalence class of all tautologies).

Then, if one defines

\begin{align*} [a]\cdot[b] &:= [a]\wedge [b] = [a\wedge b]\\ [a] + [b] &:= (\overline{[a]}\wedge [b]) \vee ([a]\wedge\overline{[b]}) \end{align*}

where $\overline{[a]} = [\neg a]$, then $R(A) := \left(\mathcal{F}(A)\big/{\sim}, +, \cdot, 0, 1\right)$ is a commutative ring.

### First question:

Now, I've tried to proof that if $\mathcal{F}(A)\big/{\sim}$ hasn't the distributive property, then also $R(A)$ hasn't it. But I didn't know how to get through. A piece of the puzzle is the following question: within the structure of $R(A)$, how can one express $\overline{[a]}$? I.e. use the operators from $R(A)$ to state $\overline{[a]} = \ldots$. Is it possible if this isn't solvable? As far as I can see this question is equivalent to: is it possible to express $\neg$ up to equivalence with $\wedge$ and $(XOR)$? I would say no, but I might be wrong.

### Second question:

It turns out the $R(A)$ is idempotent, so it's a boolean Algebra. Now does this mean that \begin{align*} R(A) \cong \mathbb{F}_2[a_i \mid i\in I]/(a_i^2-a_i \mid i \in I)? \end{align*} How does the isomorphism look like? I cannot show that these rings are isomorphic.

Thanks.

• The "specificatio" of $\omega$ for the case $\lor$ is not correct : if $a$ and $b$ are both true then $\omega(a \lor b) = 3$. – Mauro ALLEGRANZA Feb 17 '14 at 14:45
• I'm sorry. With $\{0,1\}\cong\mathbb{Z}_2$ I meant that all operations are $\pmod 2$. So $3 \equiv 1 \pmod 2$. – aphorisme Feb 17 '14 at 14:50
• The standard definition are : $\omega(a \lor b) = max (\omega(a), \omega(b))$; $\omega (a \land b) = min (\omega(a), \omega(b))$ and $\omega(a \rightarrow b) = 1 − \omega(a) + \omega(a)\omega(b)$. – Mauro ALLEGRANZA Feb 17 '14 at 14:52
• $\lnot$ is expressible with NAND, i.e. Sheffer stroke as $p|p$. – Mauro ALLEGRANZA Feb 17 '14 at 15:07
• But how would one express a NAND with XOR and AND? – aphorisme Feb 17 '14 at 15:19

You have $1 \in R(A)$ and therefore $$1+[a] = (\overline 1 \wedge [a]) \vee (1\wedge \overline{[a]}) = \overline{[a]},$$ so you can express negation in $R(A)$ pretty easily.
For the distributive property I wonder why you might assert that $\mathcal F(A)\big/{\sim}$ might not have it, doesn't $\mathcal F(A)\big/{\sim}$ always have the distributive property?
The isomorphism $R(A) \cong \mathbb F_2[a_i\ |\ i\in I]/\langle a_i^2-a_i\ |\ i\in I\rangle$ can be given by $[a_i]\mapsto [a_i]$, which already enforces $\overline{[a_i]}\mapsto 1+[a_i]$ by the previous calculation. These two already define the images of all formulas.
• So, since $[\neg a] = 1 + [a]$ one have $[a \vee b] \mapsto 1 - ((1-a)\cdot(1-b))$. Ah, fine. : ) – aphorisme Feb 17 '14 at 20:03