How to define "or" logically

by logicNoob   Last Updated October 10, 2019 12:05 PM

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?

Tags :

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
``````
Julia Hayward
December 16, 2014 16:24 PM

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
``````
Elliot Blackburn
December 16, 2014 16:25 PM

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

Rob
December 16, 2014 16:27 PM

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

fredoverflow
December 16, 2014 16:47 PM

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.

Jon Hanna
December 16, 2014 18:15 PM

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

user22815
December 16, 2014 19:21 PM

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

Keen
December 16, 2014 19:29 PM

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;

}
``````
Senthu Sivasambu
December 16, 2014 21:10 PM

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.

Jörg W Mittag
December 17, 2014 03:01 AM

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.

Walter Mitty
December 17, 2014 13:33 PM

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.

Yakk
December 17, 2014 21:32 PM

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 ] ]) { /* ... */ }
``````
slebetman
December 18, 2014 07:24 AM

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

Luis Masuelli
December 19, 2014 19:29 PM

Related Questions

Updated May 01, 2017 14:05 PM

Updated January 26, 2018 18:05 PM

Updated May 21, 2015 22:02 PM

Updated March 02, 2017 21:05 PM

Updated July 15, 2018 10:05 AM