Logical equivalence

Did you know that for expressing all logical conditions you don't need both operators of && and || ? The point is that you just need one of them,- second logical operator can be emulated and thus is just a syntax sugar for developers.

Let's write a helper function which generates a truth table for a given logical expression :

function generateTruthTable($expression) {
  $code =<<< STR
  \$input = [true, false];
  \$result = [];
  foreach (\$input as \$p) {
    foreach (\$input as \$q) {
      \$result[] = [(int)\$p, (int)\$q, (int)({$expression})];
    }       
  }
  return \$result;
STR;
  return eval($code);
}

Now, lets check logical equivalence for statements :

var_dump(generateTruthTable('$p && $q') === 
         generateTruthTable('!(!$p || !$q)')
        );

Prints TRUE, because :

$p && $q is like saying "both values are true"

!(!$p || !$q) is like saying "neither $p and neither $q is false"

In this way we can replace && operator with || and logical negation operators.

Now let's check another one example :

var_dump(generateTruthTable('$p || $q') === 
         generateTruthTable('!(!$p && !$q)')
);

Prints TRUE, because:

$p || $q is like saying "one of values is true"

!(!$p && !$q) is like saying "NOT both values are false"

In this way we can replace || operator with && and logical negation operators.

Now I hope, you will feel stronger when some language will be missing one of [AND,OR] operators. If it is missing logical negation operator too - throw it out of the window, because inversion operators are most important in the language :-)

Comments (4)

Add a comment
Mark's photo

Interesting :-)

You can probably replace negation with == false or something so it might not be the most important after all...

Also interesting to note that short-circuiting still works with the transformed versions, so they really are equivalent. That is, a() || b() will only evaluate a() if a() is true. The same is true for !(!a() && !b()): if a() is true then !a() is false and b() need not be evaluated, since false && !b() cannot be true.

Show all replies
Agnius Vasiliauskas's photo

I think that's because it's very easy for a user to define XOR boolean operator, like so (pseudocode) : XOR(p,q) = return p != q;

As about implication, well ... there's no one language that suits all needs. If we need a lot of logic processing - then we grab a Prolog programming language. Even Prolog has limitations, because it is based on deductive logic mostly. There is an on-going research for making a logic compiler which could use abduction and induction logic too. pdfs.semanticscholar.org/ba34/d7a2f4b691fa6.. So there's still a lot to create in programming languages and in my opinion it will always be like so ...