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'm looking for a function that will replicate logical operators. In particular consider the AND operator. Then I am looking for a function z = f(x,y) such that $$x,y,z \in \{0,1\}$$

f(0,0)=0 f(1,0)=0 f(0,1)=0 f(1,1)=1

More importantly I need to generalize over a space where Xi,Yi ∈ {0,1} and I need to do this for other sorts of operators too. (X XOR Y AND Z for example.)

So given a vector Xi and a vector Yi I need to be able to generate Zi w

share|improve this question
    
Do you mean that $x$, $y$, and $z$ are real numbers strictly between $0$ and $1$, or do you mean that $x$, $y$, and $z$ can each of them be either $0$ or $1$? (That is, $x,y,z\in(0,1)$, or $x,y,z\in\{0,1\}$?) –  Arturo Magidin Oct 26 '10 at 20:50
    
Its a discrete choice set. So just 0 and 1 -> {0,1} –  figuringout Oct 26 '10 at 21:08
    
Do you want to compute the value of a Boolean expression by performing an analog computation? –  Américo Tavares Oct 26 '10 at 21:38
    
yes. I think qiaochu-yuan answers it. Thanks guys! –  figuringout Oct 26 '10 at 23:17

3 Answers 3

up vote 7 down vote accepted

If $x, y \in [0, 1]$ you can take $f(x, y) = xy$. This comes from replacing "true" and "false" with probabilities and from assuming that $x, y$ are probabilities of independent events. Similarly for NOT take $f(x) = 1 - x$, and for OR take $f(x, y) = 1 - (1 - x)(1 - y)$.

If this isn't what you're looking for then you're going to have to be more precise about what you want. If you want to do something with vectors with entries in $\{ 0, 1 \}$, what's wrong with applying the operations pointwise?

share|improve this answer
    
Thanks, this is useful! How does one do X OR Y? Say I wanted to do something like A = X OR (Y AND Z)? I'm going to put this in a maximization formula, so I need to be able to write down nice functions. –  figuringout Oct 26 '10 at 21:10
1  
Like I said, x OR y can be taken to be 1 - (1 - x)(1 - y). So x OR (y AND z) = 1 - (1 - x)(1 - yz). What kind of maximization formula could possibly be applicable to binary variables? –  Qiaochu Yuan Oct 26 '10 at 21:26
    
+1 for the OR function. –  Américo Tavares Oct 26 '10 at 23:04
    
Another way to look at OR is $f(x, y) = x + y - 2xy$, summing and “removing the double-counting case”. This is similar to the inclusion-exclusion principle for counting elements in the union of sets. –  Kevin Reid Oct 28 '10 at 0:25
    
@Kevin: no, it should be f(x, y) = x + y - xy. And it is inclusion-exclusion. –  Qiaochu Yuan Oct 28 '10 at 10:06

In one of the standard approaches to fuzzy logic--used in household appliances everywhere!--the truth values are taken to be real numbers in the unit interval, where $0$ represents false and $1$ represents true, and the Boolean connectives are defined by the following equations:

  • (not) $\neg p = 1-p$
  • (and) $p\wedge q= \text{min}(p,q)$
  • (or) $p\vee q= \text{max}(p,q)$

These values agree with the classical values when restricted to $0$ and $1$, and thus agree with Qiaochu's answer on the classical values, but they disagree on non-classical values. In particular, this version of fuzzy logic gives the same truth value to $p$ as $p\wedge p$, but this isn't the case with the probabilistic formulas, which (inappropriately) interprets $p\wedge p$ as a conjunction of independent events. Similarly, fuzzy logic also says $p$ is equivalent to $p\vee p$, whereas the probabilistic formula does not.

It is a fun exercise to show that fuzzy logic doesn't work with classical tautologies very well. For example, $p\vee \neg p$ is not uniformly value $1$, although it is always at least $\frac 12$. Indeed, a statement is a classical tuatology if and only if it gets fuzzy value at least $\frac 12$ on all input. There are numerous other such fun problems.

There are also numerous variations on the fuzzy theme, however, with many different fuzzy logics, and the Wikipedia page appears extensive.

share|improve this answer

There exists an uncountable family of functions which will work for AND here, and another uncountable family of functions for OR here. Any T-norm will work for AND here, as follows: For any T-norm T(a, 1)=a by "1" as the identity for T, and by commutation T(1, a)=a also. So, if "a" belongs to {0, 1} we have T(1, 1)=T(0, 1)=T(1, 0)=1. 0<=1. So, by monotonicity it follows that T(0, 0)<=T(0, 1)=0. So, T(0, 0)=0. Thus, every t-norm works out such that T(0, 0)=T(0, 1)=T(1, 0), T(1, 1)=1. Any S-norm (or T-conorm) will work here for OR, since S(a, 0)=a by 0 as the identity element for S. By commutation, we have S(0, a)=a. So, if "a" belongs to {0, 1}, S(0, 0)=0, S(1, 0)=1, S(1, 1)=1. 0<=1, so 1=S(0, 1)<=S(1, 1), and thus for any S-norm S(1, 1)=1. So, any S-norm will work here for OR. min for AND, max for OR, and 1-a for NOT generally seem to work best.

share|improve this answer

Your Answer

 
discard

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.