# What is name of “random boolean” algebra with set containing 0, random, and 1?

I imagine an algebra on the set of three values with an addition operation like this:

0 + 0 = 0
0 + 1 = random value 0 or 1 with 50/50 probability
1 + 0 = random value 0 or 1 with 50/50 probability
1 + 1 = 1


The idea is that if this were implemented as an electronic gate where the two inputs were binary 0 or 1, the output is off, half-on, or full-on, representing a kind of summation. The half-on value would vary randomly very fast to represent a PWM-like half-amplitude.

Without having thought far, I suspect that (since the actual output values are just 0 and 1) this output could be fed into other similar gates, resulting in a variety of intermediate random-PWM-amplitude levels.

Is there a name for this mathematical concept? I would like to read about it.

-
It sounds like you want some kind of fuzzy logic or probabilistic logic. – Zhen Lin Sep 5 '11 at 16:48
The addition is supposed to be commutative, and $a+0=0+a=a$ for every element of the algebra. – Asaf Karagila Sep 5 '11 at 16:49
The set up you describe sounds very much like Markov chain... – Sasha Sep 5 '11 at 17:27
Thank you for clarifying this is not a "boolean algebra". And, probabilistic logic and Markov chain are generally the correct idea for me to dig into. I figured out that I could make a real Markov chain by replacing the probability with oscillating states 0 and 1. – Ezekiel Eaton Sep 6 '11 at 11:07

What you describe is not a Boolean algebra, for several reasons:

1. Boolean algebra has three operations, $+,\cdot,-$ and two constants $0,1$. You only specified addition and constants.

2. Addition is commutative, so $a+0=0+a$, unlike how you stated $0+1\neq 1+0$.

3. The $0$ element is a neutral element with respect to addition, that is $0+a=a$, against in contradiction to $1\neq 1+0\neq 0+1\neq 1$.

You could consider the Boolean algebra defined on $\{0,1,a,b\}$ such that:

• $0,1$ are the usual constants;
• $-a=b$ (and so $-b=a$);
• $a\cdot b=0$ and $a+b=1$.

One can consider this as $\mathcal P(\{a,b\})$ defined with the usual intersection, union and complement. In which case $0=\varnothing$ and $1=\{a,b\}$. Furthermore, every Boolean algebra which has exactly four elements is isomorphic to this one.

This algebra is complete, so it is very convenient to define Boolean-valued logic on this algebra.

This is somewhat similar the ideas met in usual logic, only now there is a new way to define how true is a sentence. We can consider this as measuring how true is something. It does not correspond very well to any real life intuition that I can provide, so my advice is to stick with formal proofs until you get the hang of the idea.

The truth value of a sentence in this logic would be defined, as usually, by induction. We denote it as $||\varphi||$, for convenience. (This is not limited to the Boolean algebra discussed above, of course.)

• $||\varphi_1\lor\varphi_2||=||\varphi_1||+||\varphi_2||$;
• $||\varphi_1\land\varphi_2||=||\varphi_1||\cdot||\varphi_2||$;
• $||\lnot\varphi||=-||\varphi||$;

For adding the definition for quantifier we need to use the completeness.

• $\displaystyle||\exists x\varphi||=\sum ||\varphi[t]||$, that is the supremum (union if we think about the power set representation) of all possible values for placing something into $\varphi$ and evaluating the sentence.
• $\displaystyle||\forall x\varphi||=\prod ||\varphi[t]||$, that is the infimum (intersection if we think about power set) of possible values as before.

To see how this corresponds to the usual two-valued logic, $\exists x\varphi$ is true if and only if there exists some element which witnesses $\varphi$ - that is for some element in the model $||\varphi[x]||=1$, so the supremum is indeed $1$; and similarly for $\forall x\varphi$ we take the least element.

This approach is less familiar than fuzzy logic, but has a very important use in set theory when constructing forcing extensions.

I am not sure it answers your question, however it shows how to create a Boolean-valued model. Suppose you declare that the function which returns truth values for assignments into formulae is non-deterministic, or probabilistic, then you can have yourself a nice probabilistic logic, or fuzzy logic, and so on.

-