0

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.

Mujtahid Akon
  • 1

1 Answers1

0

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.

peterwhy
  • 22,256
  • So, apparently, there's no solution here. How about a function of $a$ and $b$ after the operator instead of just $a$, i.e. $(a\wedge b)\operatorname{op} f(a,b) = b$? – Mujtahid Akon Nov 18 '22 at 09:23
  • @MujtahidAkon 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 "$(a\wedge b)\operatorname{op}f(a,b) = b$", so is always possible. – peterwhy Nov 19 '22 at 01:06
  • Both $op$ and $f(x,y)$ are variable if that helps. – Mujtahid Akon Nov 20 '22 at 02:48
  • In your second case, what would be $op$? Or is there any other solution for $op$ and $f(x,y)$? – Mujtahid Akon Nov 20 '22 at 02:54
  • @MujtahidAkon They are both variables which I can choose to satisfy the desired property? Then I can choose $\operatorname{op}$ and $f$ as:

    $$\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}$$

     – peterwhy Nov 20 '22 at 03:20
  • the question is what is that particular $op$ that satisfies $x \operatorname{op}y = y$? – Mujtahid Akon Nov 22 '22 at 06:24