Find the correct operator or function to satisfy a boolean equation

82 Views Asked by At

I have been working with a boolean model and got stuck on the following problem.

I have a chain of boolean variables connected with an and like this: $a \land b \land c ... \land z$. I need to eliminate a particular variable from this chain using some operations to that variable only. So basically I need to find the correct operator or function to satisfy the following boolean equation: $$(a \land b \land c ... \land z) \text{[a boolean operator/function]} a = (b \land c ... \land z) $$ Here [] refers to a boolean operator/function to be identified.

A solution to the following should also work for me: $$(a \land b) \text{[a boolean function on a and b]} = b $$ Is there any solution to this problem? I am not sure, how I should approach to reach a solution.

1

There are 1 best solutions below

6
On

If $a$ is false, then for the two possible values of $b$ there are two cases that the operator can't possibly distinguish:

$$(a\wedge b)\operatorname{op} a = F \operatorname{op} F = b$$

This means the operator unfortunately does not depend only on the two inputs, but has to know the value of $b$ to answer $F \operatorname{op} F$.

$$\begin{align*} F \operatorname{op} F &= (F\wedge T) \operatorname{op} F = T\tag1\\ F \operatorname{op} F &= (F\wedge F) \operatorname{op} F = F\tag2\\ F &= T \end{align*}$$

Equations $(1)$ and $(2)$ come from the desired property of the operator, and they lead to a contradiction.


Is function $f$ given and fixed? In one extreme, if $f(a,b)=a$ then this is still impossible as before. But if $f(a,b)=b$, then picking "$x\operatorname{op} y=y$" gives

$$\begin{align*} x \operatorname{op} y &= y\\ f(x,y) &= y\\ (a\wedge b)\operatorname{op}f(a,b)&= f(a,b) = b \end{align*}$$

so is always possible.