0
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Simple after all ... :/ $\endgroup$ – aphorisme Feb 17 '14 at 20:00
  • $\begingroup$ So, since $[\neg a] = 1 + [a]$ one have $[a \vee b] \mapsto 1 - ((1-a)\cdot(1-b))$. Ah, fine. : ) $\endgroup$ – aphorisme Feb 17 '14 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.