2
$\begingroup$

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

  • 0
    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\}$?)2010-10-26
  • 0
    Its a discrete choice set. So just 0 and 1 -> {0,1}2010-10-26
  • 0
    Do you want to compute the value of a Boolean expression by performing an analog computation?2010-10-26
  • 0
    yes. I think qiaochu-yuan answers it. Thanks guys!2010-10-26

3 Answers 3

8

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?

  • 0
    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.2010-10-26
  • 2
    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?2010-10-26
  • 0
    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](http://en.wikipedia.org/wiki/Inclusion–exclusion_principle) for counting elements in the union of sets.2010-10-28
  • 0
    @Kevin: no, it should be f(x, y) = x + y - xy. And it _is_ inclusion-exclusion.2010-10-28
  • 0
    Oops, yes. $f(x,y) = x + y - 2xy$ is a definition of XOR, not OR.2010-10-28
2

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.

0

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.