Binary Operations: AND, OR, XOR, NOR — and Their Deep Relationships

Public
/software-computational-architecture

Binary operations are the foundation of computation. At the lowest level, everything reduces to simple operations on bits: true (1) and false (0).

In this article, we explore the core logical operations:

  • AND
  • OR
  • XOR
  • NOR
  • XAND (XNOR)

We’ll also look at how they relate to each other — and why XOR can be expressed using only NAND-like constructions.

1. Basic Definitions

Let’s define the core operations for two boolean values A and B.

A B AND OR XOR NOR XAND (XNOR)
0 0 0 0 0 1 1
0 1 0 1 1 0 0
1 0 0 1 1 0 0
1 1 1 1 0 0 1

Intuition

  • AND (&&) → both must be true
  • OR (||) → at least one is true
  • XOR (!=) → exactly one is true
  • NOR (!(A || B)) → none are true
  • XAND / XNOR (!(A != B)) → both are equal

2. Vectorized Implementations in C++

Here are implementations operating element-wise on boolean vectors:

  
  
#include <iostream>
#include <vector>
#include <stdexcept>

std::vector<bool> and_n(const std::vector<bool>& vec1, 
                const std::vector<bool>& vec2) {

  std::vector<bool> rtn_v(vec1.size());

  if (vec1.size() > vec2.size()) {
    throw std::invalid_argument("vec1 must have same or lower size than vec2");
  };

  for (int i = 0; i < vec1.size(); i += 1) {
    rtn_v[i] = (vec1[i] && vec2[i]);
  };

  return rtn_v;
}

std::vector<bool> or_n(const std::vector<bool>& vec1, 
                const std::vector<bool>& vec2) {

  std::vector<bool> rtn_v(vec1.size());

  if (vec1.size() > vec2.size()) {
    throw std::invalid_argument("vec1 must have same or lower size than vec2");
  };

  for (int i = 0; i < vec1.size(); i += 1) {
    rtn_v[i] = (vec1[i] || vec2[i]);
  };

  return rtn_v;
}

std::vector<bool> nor_n(const std::vector<bool>& vec1, 
                const std::vector<bool>& vec2) {

  std::vector<bool> rtn_v(vec1.size());

  if (vec1.size() > vec2.size()) {
    throw std::invalid_argument("vec1 must have same or lower size than vec2");
  };

  for (int i = 0; i < vec1.size(); i += 1) {
    rtn_v[i] = !(vec1[i] || vec2[i]);
  };

  return rtn_v;
}

std::vector<bool> xor_n(const std::vector<bool>& vec1, 
                const std::vector<bool>& vec2) {

  std::vector<bool> rtn_v(vec1.size());
  if (vec1.size() > vec2.size()) {
    throw std::invalid_argument("vec1 must have same or lower size than vec2");
  };

  for (int i = 0; i < vec1.size(); i += 1) {
    rtn_v[i] = (vec1[i] != vec2[i]);
  };

  return rtn_v;
}

std::vector<bool> xand_n(const std::vector<bool>& vec1, 
                const std::vector<bool>& vec2) {

  std::vector<bool> rtn_v(vec1.size());

  if (vec1.size() > vec2.size()) {
    throw std::invalid_argument("vec1 must have same or lower size than vec2");
  };

  for (int i = 0; i < vec1.size(); i += 1) {
    rtn_v[i] = !(vec1[i] != vec2[i]);
  };

  return rtn_v;
}

int main() {
    return 0;
}

3. Relationships Between Operations

3.1 XOR and XAND

These are perfect opposites:

  
  
XAND(A, B) = NOT(XOR(A, B))
XOR(A, B)  = NOT(XAND(A, B))

3.2 NOR as a Universal Gate

NOR is powerful because it can express everything:

  
  
NOT(A)     = NOR(A, A)
OR(A, B)   = NOT(NOR(A, B))
AND(A, B)  = NOR(NOT(A), NOT(B))

3.3 XOR Decomposition

XOR can be rewritten using AND, OR, and NOT:

  
  
XOR(A, B) = (A AND NOT(B)) OR (NOT(A) AND B)

This is the key identity behind its behavior: difference detection.

4. XOR as a NAND Construction

NAND is known to be functionally complete, meaning all logic can be built from it.

XOR can be expressed using only NAND:

  
  
Let:
N1 = NAND(A, B)
N2 = NAND(A, N1)
N3 = NAND(B, N1)

XOR(A, B) = NAND(N2, N3)

This is why XOR is sometimes described as a structured NAND composition.

5. Conceptual Insight

  • AND / OR → aggregation operations
  • XOR → difference detector
  • XAND → equality detector
  • NOR / NAND → universal building blocks

The deeper idea:

XOR is not just another operator — it encodes change, mismatch, and information.

This is why XOR appears everywhere:

  • cryptography
  • hashing
  • parity checks
  • diffing algorithms

6. Memo Technique

Start from AND and OR.

Negate those operations so we got NAND and NOR

Now one last thing you jus need to know one of the following:

  • XOR -> A != B
  • XAND -> A == B

And now negate again one or the other to obtain its "opposite" wether XAND or XOR

You just have to know 3 expressions, everything else is negation!

(N stands for Negation and XAND and XOR are true "opposite" :))

  • XOR -> difference pattern
  • XAND -> equality pattern

7. Final Perspective

All boolean logic collapses into a small set of primitives. Among them:

  • NAND and NOR → construction tools
  • XOR → information extractor

And your C++ implementations reflect this beautifully:

  • != → XOR
  • !( != ) → XAND
  • !( || ) → NOR

Minimal syntax, maximum meaning.