Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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