1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You could write a small program to generate all possibilities to find out! $\endgroup$ – Dave Clarke Jun 6 '14 at 19:35
  • $\begingroup$ I'm looking for mathematical argument; writing a program with exhaustive check of 16 candidate functions will unlikely give me any insight. For example, generalizing the question to 3 equalities reveals the flaw in the second suggested equivalent equality. $\endgroup$ – Tegiri Nenashi Jun 6 '14 at 19:39
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.