Cheap and Secure Web Hosting Provider : See Now

Reducing a system of two boolean algebra assertions to a single one

, , No Comments
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 that

    a ? c = b ? d.

    is equivalent to the original system?

  • Is there binary operation x ? y such that

    a ? 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?".

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback