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

$\endgroup$
4
  • $\begingroup$ 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\}$?) $\endgroup$ Oct 26, 2010 at 20:50
  • $\begingroup$ Its a discrete choice set. So just 0 and 1 -> {0,1} $\endgroup$ Oct 26, 2010 at 21:08
  • $\begingroup$ Do you want to compute the value of a Boolean expression by performing an analog computation? $\endgroup$ Oct 26, 2010 at 21:38
  • $\begingroup$ yes. I think qiaochu-yuan answers it. Thanks guys! $\endgroup$ Oct 26, 2010 at 23:17

3 Answers 3

9
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Oct 26, 2010 at 21:10
  • 2
    $\begingroup$ 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? $\endgroup$ Oct 26, 2010 at 21:26
  • $\begingroup$ 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. $\endgroup$
    – Kevin Reid
    Oct 28, 2010 at 0:25
  • $\begingroup$ @Kevin: no, it should be f(x, y) = x + y - xy. And it is inclusion-exclusion. $\endgroup$ Oct 28, 2010 at 10:06
  • $\begingroup$ Oops, yes. $f(x,y) = x + y - 2xy$ is a definition of XOR, not OR. $\endgroup$
    – Kevin Reid
    Oct 28, 2010 at 14:57
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .