**Problem Detail:**

Given a system of two Boolean Algebra equalities

`a = b. c = d. `

one can exhibit a single equation

`F(a,b,c,d) = 0. `

which is equivalent to the former system. (Symmetric difference is pivotal for constructing such quaternary operation F(a,b,c,d)).

Questions:

Is there binary operation

`x ? y`

(infix notation) such thata ? c = b ? d.

is equivalent to the original system?

Is there binary operation

`x ? y`

such thata ? b = c ? d.

is equivalent to the original system?

*Edit (June 13):* The question is more subtle than I managed to convey. Boolean algebra is a finitely definable variety. I was wondering if we can get a single axiom system by combining identities. Padmanabhan proved in 1968 that every definable class of lattices (such as BA) can be defined by a single identity within the class of lattices. The key observation in his method is equipping the identities

`a = b. c = d. `

with *disjoint* sets of variables. Then, simple disjunction

`a v c = b v d. `

would do.

###### Asked By : Tegiri Nenashi

###### Answered By : D.W.

No. There is no such binary operation.

This is easy to prove with a counting argument. Given a candidate binary operation $?$, count the number $n$ of boolean values $x,y$ such that $x?y$ is true. Out of the 16 possible values for $a,b,c,d$, exactly $m=n^2+(4-n)^2$ of them will satisfy $a?c = b?d$. The possible values for $m$ are $m \in \{16,10,8\}$. However, there are only 4 possible values of $a,b,c,d$ such that $a=b$ and $c=d$, which is not in the set of possible values for $m$.

Or, you could do as David Clarke suggests and write a tiny program to enumerate all possibilities. Frankly, you probably should have done that before asking in any case; that would have helped you ask a more specific question, such as "I know no such binary operation exists; can you give me any insight why not?".

Question Source : http://cs.stackexchange.com/questions/26472

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback