# How to define "or" logically

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?

• @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. Dec 16, 2014 at 16:33
• @user3687688 Can you please clarify the primitives we are allowed to use? Dec 16, 2014 at 16:56
• this question has started a collective spasm of micro-optimization ;) Dec 16, 2014 at 19:10
• You could use the ternary operator `return arg1 ? arg1 : arg2;` Dec 16, 2014 at 19:58
• I have got to know why you needed to re-define the `or` operator. Dec 17, 2014 at 0:20

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
``````
• You could also remove the "else" on line 4 (leaving just `if arg2 == true`). Dec 16, 2014 at 20:58
• @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! Dec 16, 2014 at 21:17
• @BlueHat It seems slightly inconsistent to use an else if, but not an else at the end. Dec 17, 2014 at 8:43
• @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. Dec 18, 2014 at 14:36
• even better (worse): `or(a, b): a ? a : b`
– sara
Jan 26, 2016 at 13:48

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 ;)

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

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)`

• 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, 2014 at 21:12
• @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, 2014 at 21:17
• For reference: en.wikipedia.org/wiki/De_Morgan%27s_laws Dec 16, 2014 at 23:08
• I like this approach because it short-circuits IFF `and` short circuits, thus providing consistency among the operators. Dec 17, 2014 at 0:21
• @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, 2014 at 17:31

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))

• Simplify: `return not (not arg1 and not arg2)`
– user22815
Dec 16, 2014 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. Dec 16, 2014 at 18:36
• Was going to add the NAND solution, but you beat me to it. Everything should be implemented in terms of NAND.
– Andy
Dec 16, 2014 at 22:31
• @Andy: Actually, everything should be defined in terms of NOR. ;-) Dec 18, 2014 at 3:28
• Good work with the pure `nand` solution.
– AAT
Dec 19, 2014 at 15:26

# 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.)

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.

• How about `False ||| False = False` and `_ ||| _ = True` instead? :) Dec 17, 2014 at 10:25
• @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". Dec 17, 2014 at 13:38
• Ah, of course. I knew there had to be a deeper reason :) Dec 17, 2014 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, 2014 at 20:43
• @JörgWMittag FredOverflow's definition is appropriately short-circuiting. Try `True ||| undefined` yourself in ghci to see! Dec 18, 2014 at 7:34

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 = {
{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));` Dec 19, 2014 at 11:35

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;

}
``````
• `booleanExpression ? true : false` is trivially equal to `booleanExpression`.
– Keen
Dec 16, 2014 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. Dec 16, 2014 at 22:15
• `return (arga+argb)>0` Dec 17, 2014 at 1:06
• I was only correcting your text. Your code is perfect, but could be in one line: `return (((arg1 ? 1 : 0)+(arg2 ? 1 : 0)) > 0);` :) Dec 17, 2014 at 1:12
• @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, 2014 at 18:09

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, 2014 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. Dec 17, 2014 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. Dec 17, 2014 at 9:58

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) ? Dec 22, 2014 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. Dec 22, 2014 at 12:30

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?)

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

• These approaches are fundamentally flawed. Consider -1+1 for `arg1+arg2`, -1 and 0 for `max(arg1,arg2)`, etc. Dec 17, 2014 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, 2014 at 15:37
• If you're doing pure 1-bit boolean values, then addition still doesn't work, since 1+1 = 0. :) Dec 17, 2014 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, 2014 at 17:21

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.

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 {
{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)`

Look at the Swift standard library and check out their implementation of the shortcut OR and shortcut AND operations, which don’t evaluate the second operands if not needed/allowed.

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. Dec 16, 2014 at 16:27
• asker specifically pointed that their requirement was "without using the operator itself"
– gnat
Dec 16, 2014 at 17:10
• 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. Dec 17, 2014 at 2:53