37

Recently, I came across a problem that required me to define the logical "OR" operator programmatically, but without using the operator itself.

What I came up with is this:

OR(arg1, arg2)
  if arg1 = True and arg2 = True
     return True

  else if arg1 = True and arg2 = False
     return True

  else if arg1 = False and arg2 = True
     return True

  else:
     return False

Is this logic correct, or did I miss something?

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

  • 10
    @gnat: To be fair, a truth table lists the outputs for each combination of the inputs and the Wikipedia article gives a description of the function. I think what the OP is really asking is how to define a logical OR programmatically without the use of the operator itself. – Blrfl Dec 16 '14 at 16:33
  • 6
    @user3687688 Can you please clarify the primitives we are allowed to use? – fredoverflow Dec 16 '14 at 16:56
  • 4
    this question has started a collective spasm of micro-optimization ;) – Rob Dec 16 '14 at 19:10
  • 7
    You could use the ternary operator return arg1 ? arg1 : arg2; – Matthew Dec 16 '14 at 19:58
  • 4
    I have got to know why you needed to re-define the or operator. – Kyle Strand Dec 17 '14 at 0:20

13 Answers 13

102

I'd say that's correct, but could you not condense it down to something such as this?

or(arg1, arg2)
    if arg1 == true
        return true
    if arg2 == true
        return true

    return false

Since you're doing an or comparison, I don't think you really need to check the combination. It just matters if one of them is true to return true. Otherwise we want to return false.

If you're looking for a shorter version that is less verbose, this will also work:

or(arg1, arg2)
    if arg1
        return arg1
    return arg2
  • 6
    You could also remove the "else" on line 4 (leaving just if arg2 == true). – Dawson Toth Dec 16 '14 at 20:58
  • 1
    @DawsonToth There's many different ways you can spin it, depends if you want to be verbose or condensed really. I'd be happy with the else if but it sounds like this is a pseudo code question so I'd probably leave it like this for clarity. Very true though! – Elliot Blackburn Dec 16 '14 at 21:17
  • @BlueHat It seems slightly inconsistent to use an else if, but not an else at the end. – SBoss Dec 17 '14 at 8:43
  • 1
    @Mehrdad Thanks! I've included the old answer back just because I feel it's a bit more verbose and explains the solution a tiny bit clearer. But your solution is much smaller and does the same job. – Elliot Blackburn Dec 18 '14 at 14:36
  • 1
    even better (worse): or(a, b): a ? a : b – sara Jan 26 '16 at 13:48
147

Here is a solution without or, and, not, comparisons and boolean literals:

or(arg1, arg2)
  if arg1
    return arg1
  else
    return arg2

It probably doesn't get much more fundamental than that ;)

  • 31
    +1 for a slightly shorter answer than mine. However I'd be tempted to drop the "else" as well just for elegance. – Elliot Blackburn Dec 16 '14 at 20:10
  • 10
    @BlueHat But then the two returns would be indented differently ;) – fredoverflow Dec 17 '14 at 10:26
  • 5
    I would like to get an EUR each time someone compares something against true or false. – JensG Dec 17 '14 at 15:51
  • 1
    @JensG Well, where do you think Bill Gates' income comes from? – Kroltan Dec 17 '14 at 16:24
  • 1
    JavaScript || operator in a nutshell (when implemented in a dynamically typed language). – rhino Dec 17 '14 at 19:31
106

One line of code:

return not (not arg1 and not arg2)

No branching, no OR.

In a C-based language, it would be:

return !(!arg1 && !arg2);

This is simply an application of De Morgan's laws: (A || B) == !(!A && !B)

  • 5
    I think this approach is the best solution since (in my opinion) an if/else construct is the same as using OR, just with a different name. – Nick Dec 16 '14 at 21:12
  • 2
    @Nick using if is equivalent to equality. Normally in machine code an if is implemented as arithmetic followed by a comparison to zero with a jump. – user22815 Dec 16 '14 at 21:17
  • 6
    For reference: en.wikipedia.org/wiki/De_Morgan%27s_laws – Mephy Dec 16 '14 at 23:08
  • 1
    I like this approach because it short-circuits IFF and short circuits, thus providing consistency among the operators. – Kyle Strand Dec 17 '14 at 0:21
  • 1
    @Snowman That's true. I meant that if (a) return true; else if (b) return true; seems more or less morally equivalent to if (a OR b) return true;, but that view may well be open to dispute. – Nick Dec 17 '14 at 17:31
13

If you only have and and not, you can use DeMorgan's law to flip around and:

if not (arg1 = False and arg2 = False)
  return True
else
  return False

... or (even more simply)

if arg1 = False and arg2 = False
  return false
else
  return true

...

And since we've all apparently become fixated on optimizing something that is almost always available as a machine instruction anyway, that boils down to:

return not(not arg1 and not arg2)

return arg1 ? true : arg2

etc. etc. etc. etc.

Since most languages provide a conditional-and, odds are the "and" operator implies a branch anyway.

...

If all you have is nand (see wikipedia):

return nand(nand(arg1, arg1), nand(arg2, arg2))

  • 7
    Simplify: return not (not arg1 and not arg2) – user22815 Dec 16 '14 at 17:17
  • @Snowman you should really make that an answer so I could upvote it. You are (currently) the only one here who didn't go with branching. – Lawtonfogle Dec 16 '14 at 18:36
  • 4
    Was going to add the NAND solution, but you beat me to it. Everything should be implemented in terms of NAND. – Andy Dec 16 '14 at 22:31
  • 2
    @Andy: Actually, everything should be defined in terms of NOR. ;-) – Pieter Geerkens Dec 18 '14 at 3:28
  • 1
    Good work with the pure nand solution. – AAT Dec 19 '14 at 15:26
13

Functions (ECMAScript)

All you need are function definitions and function calls. You don't need any branching, conditionals, operators or builtin functions. I will demonstrate an implementation using ECMAScript.

First, let's define two functions called true and false. We could define them any way we want, they are completely arbitrary, but we will define them in a very special way which has some advantages as we will see later:

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els;

tru is a function with two parameters which simply ignores its second argument and returns the first. fls is also a function with two parameters which simply ignores its first argument and returns the second.

Why did we encode tru and fls this way? Well, this way, the two functions not only represent the two concepts of true and false, no, at the same time, they also represent the concept of "choice", in other words, they are also an if/then/else expression! We evaluate the if condition and pass it the then block and the else block as arguments. If the condition evaluates to tru, it will return the then block, if it evaluates to fls, it will return the else block. Here's an example:

tru(23, 42);
// => 23

This returns 23, and this:

fls(23, 42);
// => 42

returns 42, just as you would expect.

There is a wrinkle, however:

tru(console.log("then branch"), console.log("else branch"));
// then branch
// else branch

This prints both then branch and else branch! Why?

Well, it returns the return value of the first argument, but it evaluates both arguments, since ECMAScript is strict and always evaluates all arguments to a function before calling the function. IOW: it evaluates the first argument which is console.log("then branch"), which simply returns undefined and has the side-effect of printing then branch to the console, and it evaluates the second argument, which also returns undefined and prints to the console as a side-effect. Then, it returns the first undefined.

In λ-calculus, where this encoding was invented, that's not a problem: λ-calculus is pure, which means it doesn't have any side-effects; therefore you would never notice that the second argument also gets evaluated. Plus, λ-calculus is lazy (or at least, it is often evaluated under normal order), meaning, it doesn't actually evaluate arguments which aren't needed. So, IOW: in λ-calculus the second argument would never be evaluated, and if it were, we wouldn't notice.

ECMAScript, however, is strict, i.e. it always evaluates all arguments. Well, actually, not always: the if/then/else, for example, only evaluates the then branch if the condition is true and only evaluates the else branch if the condition is false. And we want to replicate this behavior with our iff. Thankfully, even though ECMAScript isn't lazy, it has a way to delay the evaluation of a piece of code, the same way almost every other language does: wrap it in a function, and if you never call that function, the code will never get executed.

So, we wrap both blocks in a function, and at the end call the function that is returned:

tru(() => console.log("then branch"), () => console.log("else branch"))();
// then branch

prints then branch and

fls(() => console.log("then branch"), () => console.log("else branch"))();
// else branch

prints else branch.

We could implement the traditional if/then/else this way:

const iff = (cnd, thn, els) => cnd(thn, els);

iff(tru, 23, 42);
// => 23

iff(fls, 23, 42);
// => 42

Again, we need some extra function wrapping when calling the iff function and the extra function call parentheses in the definition of iff, for the same reason as above:

const iff = (cnd, thn, els) => cnd(thn, els)();

iff(tru, () => console.log("then branch"), () => console.log("else branch"));
// then branch

iff(fls, () => console.log("then branch"), () => console.log("else branch"));
// else branch

Now that we have those two definitions, we can implement or. First, we look at the truth table for or: if the first operand is truthy, then the result of the expression is the same as the first operand. Otherwise, the result of the expression is the result of the second operand. In short: if the first operand is true, we return the first operand, otherwise we return the second operand:

const orr = (a, b) => iff(a, () => a, () => b);

Let's check out that it works:

orr(tru,tru);
// => tru(thn, _) {}

orr(tru,fls);
// => tru(thn, _) {}

orr(fls,tru);
// => tru(thn, _) {}

orr(fls,fls);
// => fls(_, els) {}

Great! However, that definition looks a little ugly. Remember, tru and fls already act like a conditional all by themselves, so really there is no need for iff, and thus all of that function wrapping at all:

const orr = (a, b) => a(a, b);

There you have it: or (plus other boolean operators) defined with nothing but function definitions and function calls in just a handful of lines:

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els,
      orr = (a  , b  ) => a(a, b),
      nnd = (a  , b  ) => a(b, a),
      ntt = a          => a(fls, tru),
      xor = (a  , b  ) => a(ntt(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

Unfortunately, this implementation is rather useless: there are no functions or operators in ECMAScript which return tru or fls, they all return true or false, so we can't use them with our functions. But there's still a lot we can do. For example, this is an implementation of a singly-linked list:

const cons = (hd, tl) => which => which(hd, tl),
      car  = l => l(tru),
      cdr  = l => l(fls);

Objects (Scala)

You may have noticed something peculiar: tru and fls play a double role, they act both as the data values true and false, but at the same time, they also act as a conditional expression. They are data and behavior, bundled up into one … uhm … "thing" … or (dare I say) object!

Indeed, tru and fls are objects. And, if you have ever used Smalltalk, Self, Newspeak or other object-oriented languages, you will have noticed that they implement booleans in exactly the same way. I will demonstrate such an implementation here in Scala:

sealed abstract trait Buul {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def &&&(other: => Buul): Buul
  def |||(other: => Buul): Buul
  def ntt: Buul
}

case object Tru extends Buul {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def &&&(other: => Buul) = other
  override def |||(other: => Buul): this.type = this
  override def ntt = Fls
}

case object Fls extends Buul {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def &&&(other: => Buul): this.type = this
  override def |||(other: => Buul) = other
  override def ntt = Tru
}

object BuulExtension {
  import scala.language.implicitConversions
  implicit def boolean2Buul(b: => Boolean) = if (b) Tru else Fls
}

import BuulExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

This BTW is why the Replace Conditional With Polymorphism Refactoring always works: you can always replace any and every conditional in your program with polymorphic message dispatch, because as we have just shown, polymorphic message dispatch can replace conditionals by simply implementing them. Languages like Smalltalk, Self and Newspeak are existence proof of that, because those languages don't even have conditionals. (They also don't have loops, BTW, or really any sort of language built-in control structures except for polymorphic message dispatch aka virtual method calls.)


Pattern Matching (Haskell)

You could also define or using pattern matching, or something like Haskell's partial function definitions:

True ||| _ = True
_    ||| b = b

Of course, pattern matching is a form of conditional execution, but then again, so is object-oriented message dispatch.

  • 2
    How about False ||| False = False and _ ||| _ = True instead? :) – fredoverflow Dec 17 '14 at 10:25
  • 3
    @FredOverflow: That would require always evaluating the right operand. Usually Boolean operators are expected to be non-strict in their right argument aka "short-circuiting". – Jörg W Mittag Dec 17 '14 at 13:38
  • Ah, of course. I knew there had to be a deeper reason :) – fredoverflow Dec 17 '14 at 18:58
  • The first part reminded me immediately of Eric Lippert's great series about continuation passing style. Purely coincidental but still fun :) – Voo Dec 17 '14 at 20:43
  • 1
    @JörgWMittag FredOverflow's definition is appropriately short-circuiting. Try True ||| undefined yourself in ghci to see! – Daniel Wagner Dec 18 '14 at 7:34
3

Here's another way to define OR, or indeed any logical operator, using the most traditional way of defining it: use a truth table.

This is of course quite trivial to do in higher level languages such as Javascript or Perl but I'm writing this example in C to show that the technique does not depend on high level language features:

#include <stdio.h>

int main (void) {
    // Define truth table for OR:
    int OR[2][2] = {
        {0,   // false, false
         1},  // false, true
        {1,   // true, false
         1}   // true, true
    }

    // Let's test the definition
    printf("false || false = %d\n",OR[1==2]['b'=='a']);
    printf("true || false = %d\n",OR[10==10]['b'=='a']);

    // Usage:
    if (OR[ 1==2 ][ 3==4 ]) {
        printf("at least one is true\n");
    }
    else {
        printf("both are false\n");
    }
}

You can do the same with AND, NOR, NAND, NOT and XOR. The code is clean enough to look like syntax such that you can do stuff like this:

if (OR[ a ][ AND[ b ][ c ] ]) { /* ... */ }
  • I think this is the "purest" approach in certain mathematical sense. The OR-operator is a function after all, and the truth table is really the essence of that function as a relation and a set. Of course this could be written in an amusing OO manner too: BinaryOperator or = new TruthTableBasedBinaryOperator(new TruthTable(false, true, true, true)); – COME FROM Dec 19 '14 at 11:35
3

Another way to express the logical operators as an integer arithmetic expressions (where feasible). This way can avoid lots of branching for a larger expression of many predicates..

Let True be 1 Let False be 0

if the summation of both is greater than 1 then it is true or false to be returned.

boolean isOR(boolean arg1, boolean arg2){

   int L = arg1 ? 1 : 0;
   int R = arg2 ? 1 : 0;

   return (L+R) > 0;

}
  • 6
    booleanExpression ? true : false is trivially equal to booleanExpression. – Keen Dec 16 '14 at 22:02
  • I like your methodology but a simple mistake is that the sum of both arguments must be greater than ZERO to be true, not greater than ONE. – Grantly Dec 16 '14 at 22:15
  • 1
    return (arga+argb)>0 – Grantly Dec 17 '14 at 1:06
  • 1
    I was only correcting your text. Your code is perfect, but could be in one line: return (((arg1 ? 1 : 0)+(arg2 ? 1 : 0)) > 0); :) – Grantly Dec 17 '14 at 1:12
  • 1
    @SenthuSivasambu I have no objections to your use of arg1 ? 1 : 0;. Those are reliable expressions for transforming a Boolean into a number. It's only the return statement that can be trivially refactored. – Keen Dec 18 '14 at 18:09
1

The two forms:

OR(arg1, arg2)
  if arg1
     return True
  else:
     return arg2

OR

OR(arg1, arg2)
  if arg1
     return arg1
  else:
     return arg2

Have as well as the code golf-like advantage of being a bit smaller than the other suggestions so far, one less branch. It's not even that silly a micro-opt to reduce the number of branches if we're considering the creation of a primitive that would hence be very heavily used.

Javascript's definition of || is akin to this, which combined with its loose typing means that the expression false || "abc" has the value "abc" and 42 || "abc" has the value 42.

Though if you already have other logical operators then the likes of nand(not(arg1), not(arg2)) might have the advantage of no branching at all.

  • what's the point of repeating the prior answer (as you admitted)? – gnat Dec 17 '14 at 8:15
  • @gnat it's close enough that I wouldn't have bothered had I seen that answer, but it does still have something to it not found in any of them, so I'm leaving it. – Jon Hanna Dec 17 '14 at 9:55
  • @gnat, actually considering "We're looking for long answers that provide some explanation and context." I'm happier with this answer now. – Jon Hanna Dec 17 '14 at 9:58
1

In addition to all the programmed solutions using the if construct, it's possible to construct an OR gate by combining three NAND gates. If you want to see how it's done in wikipedia, click here.

From this, the expression,

NOT[ NOT( A AND A ) AND NOT( B AND B )]

which uses NOT and AND gives the same answer as OR. Notice that the use of both NOT and AND is just an obscure way of expressing NAND.

  • NOT(A AND A) == NOT(A) ? – Charlie Dec 22 '14 at 10:33
  • Yes, exactly. In the same wikipedia article, you can see how they reduce a NOT gate to NAND gates. Same for an AND gate. I chose not to edit the formula they presented for the OR gate. – Walter Mitty Dec 22 '14 at 12:30
1

All the good answers have already been given. But I won't let that stop me.

// This will break when the arguments are additive inverses.
// It is "cleverness" like this that's behind all the most amazing program errors.
or(arg1, arg2)
    return arg1 + arg2
    // Or if you need explicit conversions:
    // return (bool)((short)arg1 + (short)arg2)

Alternatively:

// Since `0 > -1`, negative numbers will cause weirdness.
or(arg1, arg2)
    return max(arg1, arg2)

I hope no one would ever actually use approaches like these. They're here only to promote awareness of alternatives.

Update:

Since negative numbers can break both of the above approaches, here is another awful suggestion:

or(arg1, arg2)
    return !(!arg1 * !arg2)

This simply uses DeMorgan's Laws and abuses the fact that * is similar to && when true and false are treated like 1 and 0 respectively. (Wait, you're saying this isn't code golf?)

Here's a decent answer:

or(arg1, arg2)
    return arg1 ? arg1 : arg2

But that's essentially identical to other answers already given.

  • 3
    These approaches are fundamentally flawed. Consider -1+1 for arg1+arg2, -1 and 0 for max(arg1,arg2), etc. – fluffy Dec 17 '14 at 4:36
  • @fluffy This approach assumes Boolean arguments, and then it just happens to work correctly with most kinds of garbage input. Good of you to point out that there's still some garbage which produces issues. This kind of thing is exactly why we should seek to model the actual problem domain as directly as possible (and avoid getting carried away by our own cleverness) in practice. – Keen Dec 17 '14 at 15:37
  • If you're doing pure 1-bit boolean values, then addition still doesn't work, since 1+1 = 0. :) – fluffy Dec 17 '14 at 17:14
  • @fluffy That's where the explicit conversions come in. Whether or not they're needed depends on the details of the implementation (which is exactly why this is a silly idea). – Keen Dec 17 '14 at 17:21
0

One way to define or is via a lookup table. We can make this explicit:

bool Or( bool a, bool b } {
  bool retval[] = {b,true}; // or {b,a};
  return retval[a];
}

we create an array with the values that the return value should have depending on what a is. Then we do a lookup. In C++ like languages, bool promotes to a value that can be used as an array index, with true being 1 and false being 0.

We can then extend this to other logical operations:

bool And( bool a, bool b } {
  bool retval[] = {false,b}; // or {a,b};
  return retval[a];
}
bool Xor( bool a, bool b } {
  bool retval[] = {b,!b};
  return retval[a];
}

Now a downside of all of these is that it requires prefix notation.

namespace operators {
  namespace details {
    template<class T> struct is_operator {};
    template<class Lhs, Op> struct half_expression { Lhs&& lhs; };
    template<class Lhs, class Op>
    half_expression< Lhs, Op > operator*( Lhs&&lhs, is_operator<Op> ) {
      return {std::forward<Lhs>(lhs)};
    }
    template<class Lhs, class Op, class Rhs>
    auto operator*( half_expression<Lhs, Op>&& lhs, Rhs&& rhs ) {
    return invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
    }
  }
  using details::is_operator;
}

struct or_tag {};
static const operators::is_operator<or_tag> OR;

bool invoke( bool a, or_tag, bool b ) {
  bool retval[] = {b,true};
  return retval[a];
}

and now you can type true *OR* false and it works.

The above technique requires a language that supports argument dependent lookup, and templates. You could probably do it in a language with generics and ADL.

As an aside, you can extend the *OR* above to work with sets. Simply create a free function invoke in the same namespace as or_tag:

template<class...Ts>
std::set<Ts...> invoke( std::set<Ts...> lhs, or_tag, std::set<Ts...> const& rhs ) {
  lhs.insert( rhs.begin(), rhs.end() );
  return lhs;
}

and now set *OR* set returns the union of the two.

0

This one remembers me the charasteristic functions:

or(a, b)
    return a + b - a*b

This only applies to languages which can treat booleans as (1, 0). Does not apply to Smalltalk or Python since boolean is a class. In smalltalk they go even further (this will be written in sort of a pseudocode):

False::or(a)
    return a

True::or(a)
    return self

And the dual methods exist for and:

False::and(a)
    return self

True::and(a)
    return a

So the "logic" is perfectly valid in the OP statement, althought it is verbose. Beware, it is not bad. It is perfect if you need a function which acts like a mathematical operator based on, say, a kind of matrix. Others would implement an actual cube (like a Quine-McCluskey statement):

or = array[2][2] {
    {0, 1},
    {1, 1}
}

And you will evaluate or[a][b]

So yes, every logic here is valid (except that one posted as using the in-language OR operator xDDDDDDDD).

But my favorite one is the DeMorgan's law: !(!a && !b)

-2

The logic is perfectly correct, but can be simplified:

or(arg1, arg2)
  if arg1 = True
     return True
  else if arg2 = True
     return True
  else
     return False

And presumably your language has an OR operator so - unless it's against the spirit of the question - why not

or(arg1, arg2)
  if arg1 = True or arg2 = True
     return True
  else
     return False
  • if arg1 = True or arg2 = True { return true } else { return false } Better yet, return arg1 = True or arg2 = True. if condition then true else false is redundant. – Doval Dec 16 '14 at 16:27
  • 4
    asker specifically pointed that their requirement was "without using the operator itself" – gnat Dec 16 '14 at 17:10
  • 2
    Um, I didn't say anything of the sort. It was kind of what I meant, but the question didn't say so until it was edited, and she answered it as such, so kind of my fault on that one. – logicNoob Dec 17 '14 at 2:53

protected by Community Dec 16 '14 at 21:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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