Introduction to Boolean Algebra
Boolean algebra is the mathematical foundation of digital logic and computer science. Named after George Boole, it deals with variables that have only two possible values: true (1) and false (0). This algebraic system is fundamental to understanding how computers work, from simple logic gates to complex algorithms.
Key Concepts
- Binary Values: Only two values - True (1) and False (0)
- Logic Operations: AND, OR, NOT, NAND, NOR, XOR, XNOR
- Truth Tables: Tabular representation of logic functions
- Laws and Theorems: Rules for simplifying logical expressions
- Applications: Digital circuits, programming conditions, database queries
1. Basic Boolean Operations
The Three Fundamental Operations
NOT (Inversion)
NOT operation (¬A or A' or ~A) Input | Output -------|------- 0 | 1 1 | 0 A | NOT A --|------- 0 | 1 1 | 0
# NOT operation in Python def NOT(a): return not a # Examples print(NOT(True)) # False print(NOT(False)) # True # Bitwise NOT in programming (two's complement) print(~0) # -1 (in Python, ~0 = -1) print(~1) # -2 print(~0 & 1) # 1 (for single bit)
AND (Conjunction)
AND operation (A ∧ B or A·B or A&B) Inputs | Output -------|------- 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1 A | B | A AND B --|---|-------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1
# AND operation in Python def AND(a, b): return a and b # Examples print(AND(True, True)) # True print(AND(True, False)) # False # Bitwise AND print(5 & 3) # 1 (0101 & 0011 = 0001)
OR (Disjunction)
OR operation (A ∨ B or A+B) Inputs | Output -------|------- 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1 A | B | A OR B --|---|-------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1
# OR operation in Python def OR(a, b): return a or b # Examples print(OR(True, False)) # True print(OR(False, False)) # False # Bitwise OR print(5 | 3) # 7 (0101 | 0011 = 0111)
Derived Operations
NAND (NOT AND)
NAND operation (A ↑ B or NOT(A AND B)) A | B | NAND --|---|----- 0 | 0 | 1 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 Expression: NAND = NOT (A AND B)
# NAND operation
def NAND(a, b):
return not (a and b)
# Truth table
print(f"0 NAND 0 = {NAND(0,0)}") # 1
print(f"0 NAND 1 = {NAND(0,1)}") # 1
print(f"1 NAND 0 = {NAND(1,0)}") # 1
print(f"1 NAND 1 = {NAND(1,1)}") # 0
NOR (NOT OR)
NOR operation (A ↓ B or NOT(A OR B)) A | B | NOR --|---|----- 0 | 0 | 1 0 | 1 | 0 1 | 0 | 0 1 | 1 | 0 Expression: NOR = NOT (A OR B)
# NOR operation
def NOR(a, b):
return not (a or b)
# Truth table
print(f"0 NOR 0 = {NOR(0,0)}") # 1
print(f"0 NOR 1 = {NOR(0,1)}") # 0
print(f"1 NOR 0 = {NOR(1,0)}") # 0
print(f"1 NOR 1 = {NOR(1,1)}") # 0
XOR (Exclusive OR)
XOR operation (A ⊕ B) A | B | XOR --|---|----- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 Expression: XOR = (A AND NOT B) OR (NOT A AND B)
# XOR operation
def XOR(a, b):
return (a and not b) or (not a and b)
# Alternative (using !=)
def XOR_alt(a, b):
return a != b
# Truth table
print(f"0 XOR 0 = {XOR(0,0)}") # 0
print(f"0 XOR 1 = {XOR(0,1)}") # 1
print(f"1 XOR 0 = {XOR(1,0)}") # 1
print(f"1 XOR 1 = {XOR(1,1)}") # 0
# Bitwise XOR
print(5 ^ 3) # 6 (0101 ^ 0011 = 0110)
XNOR (Equivalence)
XNOR operation (A ⊙ B or NOT XOR) A | B | XNOR --|---|------ 0 | 0 | 1 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 Expression: XNOR = (A AND B) OR (NOT A AND NOT B)
# XNOR operation
def XNOR(a, b):
return (a and b) or (not a and not b)
# Alternative (using ==)
def XNOR_alt(a, b):
return a == b
# Truth table
print(f"0 XNOR 0 = {XNOR(0,0)}") # 1
print(f"0 XNOR 1 = {XNOR(0,1)}") # 0
print(f"1 XNOR 0 = {XNOR(1,0)}") # 0
print(f"1 XNOR 1 = {XNOR(1,1)}") # 1
2. Truth Tables
Basic Truth Tables
def print_truth_table(operation, name):
"""Print truth table for a binary operation"""
print(f"\n{name} Truth Table:")
print("A | B | Result")
print("--|---|-------")
for a in [0, 1]:
for b in [0, 1]:
result = operation(a, b)
print(f"{a} | {b} | {int(result)}")
# Example
print_truth_table(lambda a,b: a and b, "AND")
print_truth_table(lambda a,b: a or b, "OR")
print_truth_table(lambda a,b: a ^ b, "XOR")
Multi-Input Truth Tables
def truth_table_3_inputs(operation, name):
"""Print truth table for 3-input operation"""
print(f"\n{name} Truth Table (3 inputs):")
print("A | B | C | Result")
print("--|---|---|-------")
for a in [0, 1]:
for b in [0, 1]:
for c in [0, 1]:
result = operation(a, b, c)
print(f"{a} | {b} | {c} | {int(result)}")
# Example: Majority function
def majority(a, b, c):
return (a and b) or (a and c) or (b and c)
truth_table_3_inputs(majority, "MAJORITY")
3. Laws of Boolean Algebra
Identity Laws
# Identity Laws
def identity_laws():
print("Identity Laws:")
print(f"A AND 1 = A: {1 and 1 == 1}, {1 and 0 == 0}")
print(f"A OR 0 = A: {1 or 0 == 1}, {0 or 0 == 0}")
print(f"A OR 1 = 1: {1 or 1 == 1}, {0 or 1 == 1}")
print(f"A AND 0 = 0: {1 and 0 == 0}, {0 and 0 == 0}")
identity_laws()
Complement Laws
# Complement Laws
def complement_laws():
print("\nComplement Laws:")
print(f"A AND NOT A = 0: {1 and not 1 == 0}, {0 and not 0 == 0}")
print(f"A OR NOT A = 1: {1 or not 1 == 1}, {0 or not 0 == 1}")
print(f"NOT(NOT A) = A: {not not 1 == 1}, {not not 0 == 0}")
complement_laws()
Idempotent Laws
# Idempotent Laws
def idempotent_laws():
print("\nIdempotent Laws:")
print(f"A AND A = A: {1 and 1 == 1}, {0 and 0 == 0}")
print(f"A OR A = A: {1 or 1 == 1}, {0 or 0 == 0}")
idempotent_laws()
Commutative Laws
# Commutative Laws
def commutative_laws():
print("\nCommutative Laws:")
print(f"A AND B = B AND A: {(1 and 0) == (0 and 1)}")
print(f"A OR B = B OR A: {(1 or 0) == (0 or 1)}")
commutative_laws()
Associative Laws
# Associative Laws
def associative_laws():
print("\nAssociative Laws:")
# (A AND B) AND C = A AND (B AND C)
a, b, c = 1, 0, 1
left = (a and b) and c
right = a and (b and c)
print(f"(A AND B) AND C = A AND (B AND C): {left == right}")
# (A OR B) OR C = A OR (B OR C)
left = (a or b) or c
right = a or (b or c)
print(f"(A OR B) OR C = A OR (B OR C): {left == right}")
associative_laws()
Distributive Laws
# Distributive Laws
def distributive_laws():
print("\nDistributive Laws:")
# A AND (B OR C) = (A AND B) OR (A AND C)
a, b, c = 1, 0, 1
left = a and (b or c)
right = (a and b) or (a and c)
print(f"A AND (B OR C) = (A AND B) OR (A AND C): {left == right}")
# A OR (B AND C) = (A OR B) AND (A OR C)
left = a or (b and c)
right = (a or b) and (a or c)
print(f"A OR (B AND C) = (A OR B) AND (A OR C): {left == right}")
distributive_laws()
Absorption Laws
# Absorption Laws
def absorption_laws():
print("\nAbsorption Laws:")
# A OR (A AND B) = A
print(f"A OR (A AND B) = A: {1 or (1 and 0) == 1}, {0 or (0 and 1) == 0}")
# A AND (A OR B) = A
print(f"A AND (A OR B) = A: {1 and (1 or 0) == 1}, {0 and (0 or 1) == 0}")
absorption_laws()
De Morgan's Laws
# De Morgan's Laws (most important for digital logic)
def demorgan_laws():
print("\nDe Morgan's Laws:")
# NOT (A AND B) = (NOT A) OR (NOT B)
print(f"NOT(A AND B) = (NOT A) OR (NOT B)")
for a in [0, 1]:
for b in [0, 1]:
left = not (a and b)
right = (not a) or (not b)
print(f" A={a}, B={b}: {left} == {right} -> {left == right}")
print()
# NOT (A OR B) = (NOT A) AND (NOT B)
print(f"NOT(A OR B) = (NOT A) AND (NOT B)")
for a in [0, 1]:
for b in [0, 1]:
left = not (a or b)
right = (not a) and (not b)
print(f" A={a}, B={b}: {left} == {right} -> {left == right}")
demorgan_laws()
4. Boolean Expressions and Simplification
Canonical Forms
# Sum of Products (SOP) and Product of Sums (POS)
def sop_expression(variables, minterms):
"""
Sum of Products from minterms
variables: list of variable names
minterms: list of minterm indices
"""
n = len(variables)
terms = []
for minterm in minterms:
term = []
for i in range(n):
if (minterm >> (n-1-i)) & 1:
term.append(variables[i])
else:
term.append(f"NOT {variables[i]}")
terms.append(" AND ".join(term))
return " OR ".join(terms)
def pos_expression(variables, maxterms):
"""
Product of Sums from maxterms
variables: list of variable names
maxterms: list of maxterm indices
"""
n = len(variables)
terms = []
for maxterm in maxterms:
term = []
for i in range(n):
if (maxterm >> (n-1-i)) & 1:
term.append(f"NOT {variables[i]}")
else:
term.append(variables[i])
terms.append(" OR ".join(term))
return " AND ".join(terms)
# Example: 3-variable function
variables = ['A', 'B', 'C']
# Function that is true for minterms 0, 3, 5, 6
minterms = [0, 3, 5, 6]
print(f"SOP: {sop_expression(variables, minterms)}")
print(f"POS: {pos_expression(variables, [0,1,2,3,4,5,6,7])}") # Full expression
Karnaugh Maps (K-Maps)
def k_map_2d(variables, function):
"""
Simple 2-variable Karnaugh map visualization
variables: list of two variable names
function: truth table as dict or list
"""
a, b = variables
print(f"\n2-Variable K-Map for {a} and {b}")
print(f"{'':>4} {b}=0 {b}=1")
print(f"{a}=0 {function[0][0]:>2} {function[0][1]:>2}")
print(f"{a}=1 {function[1][0]:>2} {function[1][1]:>2}")
def k_map_3d(variables, function):
"""
3-variable Karnaugh map visualization
variables: list of three variable names
function: truth table as 2x4 array (rows: A, columns: BC)
"""
a, b, c = variables
print(f"\n3-Variable K-Map for {a}, {b}, {c}")
print(f"{'':>4} {b}{c}=00 {b}{c}=01 {b}{c}=11 {b}{c}=10")
print(f"{a}=0 {function[0][0]:>2} {function[0][1]:>2} {function[0][2]:>2} {function[0][3]:>2}")
print(f"{a}=1 {function[1][0]:>2} {function[1][1]:>2} {function[1][2]:>2} {function[1][3]:>2}")
# Example function: Majority of 3 inputs
def majority_truth_table():
# BC order: 00, 01, 11, 10
return [
[0, 0, 1, 0], # A=0
[0, 1, 1, 1] # A=1
]
k_map_3d(['A', 'B', 'C'], majority_truth_table())
Expression Simplification
# Boolean expression simplifier (simple version)
class BooleanSimplifier:
def __init__(self):
self.rules = [
# (X AND X) = X
(lambda e: isinstance(e, tuple) and e[0] == 'AND' and e[1] == e[2],
lambda e: e[1]),
# (X OR X) = X
(lambda e: isinstance(e, tuple) and e[0] == 'OR' and e[1] == e[2],
lambda e: e[1]),
# (X AND NOT X) = 0
(lambda e: isinstance(e, tuple) and e[0] == 'AND' and
((e[1] == ('NOT', e[2])) or (e[2] == ('NOT', e[1]))),
lambda e: 0),
# (X OR NOT X) = 1
(lambda e: isinstance(e, tuple) and e[0] == 'OR' and
((e[1] == ('NOT', e[2])) or (e[2] == ('NOT', e[1]))),
lambda e: 1),
]
def simplify(self, expr):
"""Simplify a boolean expression"""
changed = True
while changed:
changed = False
for condition, action in self.rules:
if condition(expr):
expr = action(expr)
changed = True
break
return expr
# Example expressions
# NOT (A AND B) = (NOT A) OR (NOT B)
# A AND (B OR C) = (A AND B) OR (A AND C)
5. Applications in Programming
Conditional Logic
# Boolean expressions in conditions
def check_access(user_role, is_admin, is_owner):
"""
Check if user has access to resource
Access granted if:
- User is admin, OR
- User is owner, OR
- User has appropriate role (editor or reviewer)
"""
# Boolean expression
has_access = is_admin or is_owner or user_role in ['editor', 'reviewer']
return has_access
# Complex conditions
def validate_form(data):
"""Validate form data using boolean logic"""
# All fields must be valid
is_valid = (
len(data.get('name', '')) > 0 and
'@' in data.get('email', '') and
data.get('age', 0) >= 18 and
data.get('terms', False)
)
return is_valid
Bit Flags and Masks
# Using boolean algebra for bit flags
class Permissions:
READ = 1 << 0 # 1 (binary: 001)
WRITE = 1 << 1 # 2 (binary: 010)
EXECUTE = 1 << 2 # 4 (binary: 100)
DELETE = 1 << 3 # 8 (binary: 1000)
def __init__(self, permissions=0):
self.permissions = permissions
def add(self, *perms):
"""Add permissions using OR"""
for perm in perms:
self.permissions |= perm
def remove(self, *perms):
"""Remove permissions using AND with NOT"""
for perm in perms:
self.permissions &= ~perm
def has(self, perm):
"""Check permission using AND"""
return (self.permissions & perm) != 0
def toggle(self, perm):
"""Toggle permission using XOR"""
self.permissions ^= perm
# Usage
perms = Permissions()
perms.add(Permissions.READ, Permissions.WRITE)
print(f"Has READ: {perms.has(Permissions.READ)}") # True
print(f"Has EXECUTE: {perms.has(Permissions.EXECUTE)}") # False
perms.toggle(Permissions.EXECUTE)
print(f"After toggle, has EXECUTE: {perms.has(Permissions.EXECUTE)}") # True
Set Operations
# Boolean algebra in set theory
class SetOperations:
@staticmethod
def union(set_a, set_b):
"""A ∪ B - union of sets"""
return set_a | set_b
@staticmethod
def intersection(set_a, set_b):
"""A ∩ B - intersection of sets"""
return set_a & set_b
@staticmethod
def difference(set_a, set_b):
"""A \ B - set difference"""
return set_a - set_b
@staticmethod
def symmetric_difference(set_a, set_b):
"""A ∆ B - symmetric difference (XOR)"""
return set_a ^ set_b
@staticmethod
def is_subset(set_a, set_b):
"""A ⊆ B - subset check"""
return set_a <= set_b
# Example
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(f"Union: {SetOperations.union(A, B)}") # {1,2,3,4,5,6}
print(f"Intersection: {SetOperations.intersection(A, B)}") # {3,4}
print(f"Difference (A-B): {SetOperations.difference(A, B)}") # {1,2}
print(f"Symmetric diff: {SetOperations.symmetric_difference(A, B)}") # {1,2,5,6}
Database Query Optimization
# Boolean logic in query optimization class QueryOptimizer: @staticmethod def simplify_where(conditions): """ Simplify WHERE clause conditions using boolean algebra conditions: list of (field, operator, value) tuples """ # Identity: field = value AND field = value -> field = value # NOT (field = value) -> field != value # De Morgan's: NOT (A AND B) = NOT A OR NOT B pass @staticmethod def predicate_pushdown(filters, data_sources): """ Push predicates down to reduce data transfer Uses boolean algebra to determine which filters apply to which sources """ # Example: (age > 18 AND country = 'US') OR (age > 21) # Simplifies to: age > 18 (since age > 21 implies age > 18) pass # Example: Simplify query conditions def optimize_query(conditions): """Apply boolean optimization to query""" # Remove redundant conditions # A AND A = A # A OR A = A # A AND True = A # A OR False = A pass
6. Logic Gates and Digital Circuits
Basic Logic Gates
class LogicGate:
"""Base class for logic gates"""
def __init__(self, name):
self.name = name
def output(self, inputs):
raise NotImplementedError
class ANDGate(LogicGate):
def __init__(self):
super().__init__("AND")
def output(self, inputs):
return all(inputs)
class ORGate(LogicGate):
def __init__(self):
super().__init__("OR")
def output(self, inputs):
return any(inputs)
class NOTGate(LogicGate):
def __init__(self):
super().__init__("NOT")
def output(self, inputs):
return not inputs[0]
class XORGate(LogicGate):
def __init__(self):
super().__init__("XOR")
def output(self, inputs):
return inputs[0] != inputs[1]
# Using gates to build circuits
def half_adder(a, b):
"""Half adder circuit"""
sum_gate = XORGate()
carry_gate = ANDGate()
sum = sum_gate.output([a, b])
carry = carry_gate.output([a, b])
return sum, carry
def full_adder(a, b, carry_in):
"""Full adder circuit"""
xor1 = XORGate()
xor2 = XORGate()
and1 = ANDGate()
and2 = ANDGate()
or_gate = ORGate()
sum1 = xor1.output([a, b])
sum = xor2.output([sum1, carry_in])
carry1 = and1.output([a, b])
carry2 = and2.output([sum1, carry_in])
carry_out = or_gate.output([carry1, carry2])
return sum, carry_out
# Test adder
print("Half Adder:")
for a in [0, 1]:
for b in [0, 1]:
s, c = half_adder(a, b)
print(f"{a} + {b} = {c}{s}")
print("\nFull Adder:")
for a in [0, 1]:
for b in [0, 1]:
for cin in [0, 1]:
s, cout = full_adder(a, b, cin)
print(f"{a} + {b} + {cin} = {cout}{s}")
Multiplexer
class Multiplexer:
"""2-to-1 multiplexer using boolean logic"""
def __init__(self):
self.not_gate = NOTGate()
self.and1 = ANDGate()
self.and2 = ANDGate()
self.or_gate = ORGate()
def output(self, select, input0, input1):
"""
MUX output:
if select = 0: output = input0
if select = 1: output = input1
"""
not_select = self.not_gate.output([select])
term0 = self.and1.output([not_select, input0])
term1 = self.and2.output([select, input1])
return self.or_gate.output([term0, term1])
# Test multiplexer
mux = Multiplexer()
print("\nMultiplexer:")
for sel in [0, 1]:
for i0 in [0, 1]:
for i1 in [0, 1]:
out = mux.output(sel, i0, i1)
print(f"SEL={sel}, I0={i0}, I1={i1} -> OUT={out}")
7. Advanced Boolean Concepts
Boolean Function Minimization
class BooleanMinimizer:
def __init__(self, variables):
self.variables = variables
self.n = len(variables)
def binary_to_term(self, binary):
"""Convert binary string to term representation"""
term = []
for i, bit in enumerate(binary):
if bit == '0':
term.append(f"¬{self.variables[i]}")
elif bit == '1':
term.append(self.variables[i])
return "∧".join(term) if term else "1"
def quine_mccluskey(self, minterms):
"""
Quine-McCluskey algorithm for boolean minimization
minterms: list of minterm indices
"""
# Group minterms by number of 1's
groups = [[] for _ in range(self.n + 1)]
for minterm in minterms:
ones = bin(minterm).count('1')
groups[ones].append(minterm)
# Compare and combine groups
prime_implicants = set()
# Simplified implementation
# Full implementation would combine terms systematically
return prime_implicants
# Example
minimizer = BooleanMinimizer(['A', 'B', 'C'])
minterms = [0, 3, 5, 6] # Binary: 000, 011, 101, 110
print("\nMinimizing function: f(A,B,C) = Σ(0,3,5,6)")
# Result would be: f = ¬A¬B¬C + ¬A B C + A ¬B C + A B ¬C
Don't Care Conditions
def with_dont_care(minterms, dont_cares): """ Boolean function with don't care conditions minterms: required true conditions dont_cares: optional conditions (can be 0 or 1) """ def evaluate_function(input_value): if input_value in minterms: return 1 elif input_value in dont_cares: return 'X' # Don't care else: return 0 return evaluate_function # Example: BCD to 7-segment decoder bcd_to_7seg = with_dont_care( minterms=[0,1,2,3,4,5,6,7,8,9], # BCD digits 0-9 dont_cares=list(range(10, 16)) # Invalid BCD inputs 10-15 )
8. Practical Programming Examples
Boolean Expression Evaluator
class BooleanEvaluator:
"""Evaluate boolean expressions with variables"""
def __init__(self, expression):
self.expression = expression
def evaluate(self, variables):
"""
Evaluate expression with given variable assignments
variables: dict of variable:value pairs
"""
# Replace variables with values
expr = self.expression
for var, val in variables.items():
expr = expr.replace(var, str(val))
# Evaluate using Python's boolean logic
return eval(expr)
# Example
evaluator = BooleanEvaluator("(A and B) or (not A and C)")
print(evaluator.evaluate({'A': True, 'B': False, 'C': True})) # True
print(evaluator.evaluate({'A': False, 'B': False, 'C': False})) # False
Logic Circuit Simulator
class LogicCircuit:
"""Simple logic circuit simulator"""
def __init__(self):
self.wires = {}
self.gates = []
def add_gate(self, gate_type, inputs, output):
"""Add a gate to the circuit"""
self.gates.append({
'type': gate_type,
'inputs': inputs,
'output': output
})
def simulate(self, inputs):
"""Simulate the circuit with given inputs"""
self.wires = inputs.copy()
# Process gates in order
for gate in self.gates:
gate_inputs = [self.wires[i] for i in gate['inputs']]
if gate['type'] == 'AND':
result = all(gate_inputs)
elif gate['type'] == 'OR':
result = any(gate_inputs)
elif gate['type'] == 'NOT':
result = not gate_inputs[0]
elif gate['type'] == 'XOR':
result = gate_inputs[0] != gate_inputs[1]
else:
raise ValueError(f"Unknown gate type: {gate['type']}")
self.wires[gate['output']] = result
return self.wires
# Example: Half adder circuit
circuit = LogicCircuit()
# Inputs: A, B
# Outputs: Sum, Carry
circuit.add_gate('XOR', ['A', 'B'], 'Sum')
circuit.add_gate('AND', ['A', 'B'], 'Carry')
# Test all inputs
for a in [0, 1]:
for b in [0, 1]:
result = circuit.simulate({'A': bool(a), 'B': bool(b)})
print(f"A={a}, B={b}: Sum={int(result['Sum'])}, Carry={int(result['Carry'])}")
Boolean Search Engine
class BooleanSearch:
"""Boolean search engine for documents"""
def __init__(self, documents):
self.documents = documents
self.index = self._build_index()
def _build_index(self):
"""Build inverted index of documents"""
index = {}
for doc_id, text in enumerate(self.documents):
words = set(text.lower().split())
for word in words:
if word not in index:
index[word] = set()
index[word].add(doc_id)
return index
def search(self, query):
"""
Search using boolean operators (AND, OR, NOT)
Example: "python AND NOT java"
"""
# Parse query (simplified)
parts = query.upper().split()
result_set = None
current_op = None
for part in parts:
if part == 'AND':
current_op = 'AND'
elif part == 'OR':
current_op = 'OR'
elif part == 'NOT':
current_op = 'NOT'
else:
term_set = self.index.get(part.lower(), set())
if result_set is None:
result_set = term_set
elif current_op == 'AND':
result_set &= term_set
elif current_op == 'OR':
result_set |= term_set
elif current_op == 'NOT':
all_docs = set(range(len(self.documents)))
result_set = all_docs - term_set
return result_set if result_set else set()
# Example
documents = [
"Python programming is fun",
"Java is also fun",
"Python and Java are both great",
"Ruby is different"
]
search = BooleanSearch(documents)
print(search.search("Python AND Java")) # {2}
print(search.search("Python OR Java")) # {0, 1, 2}
print(search.search("Python NOT Java")) # {0}
print(search.search("NOT Python")) # {1, 3}
9. Common Boolean Identities
Reference Table
| Law | AND Form | OR Form |
|---|---|---|
| Identity | A·1 = A | A+0 = A |
| Null | A·0 = 0 | A+1 = 1 |
| Idempotent | A·A = A | A+A = A |
| Inverse | A·Ā = 0 | A+Ā = 1 |
| Commutative | A·B = B·A | A+B = B+A |
| Associative | (A·B)·C = A·(B·C) | (A+B)+C = A+(B+C) |
| Distributive | A·(B+C) = A·B + A·C | A + B·C = (A+B)·(A+C) |
| Absorption | A·(A+B) = A | A + A·B = A |
| De Morgan | (A·B)' = A' + B' | (A+B)' = A'·B' |
| Double Negation | (A')' = A |
Python Implementation
class BooleanProof:
"""Demonstrate Boolean algebra laws"""
@staticmethod
def prove_law(law_name, law_func):
"""Prove a Boolean law by testing all input combinations"""
print(f"\nProving {law_name}:")
for a in [0, 1]:
for b in [0, 1]:
left, right = law_func(a, b)
result = "✓" if left == right else "✗"
print(f" a={a}, b={b}: {left} == {right} {result}")
# Example: Prove De Morgan's law
def demorgan_and(a, b):
"""(A AND B)' = A' OR B'"""
left = not (a and b)
right = (not a) or (not b)
return left, right
def demorgan_or(a, b):
"""(A OR B)' = A' AND B'"""
left = not (a or b)
right = (not a) and (not b)
return left, right
BooleanProof.prove_law("De Morgan's AND", demorgan_and)
BooleanProof.prove_law("De Morgan's OR", demorgan_or)
10. Boolean Algebra in Different Languages
Python
# Boolean in Python x = True y = False # Logical operators print(x and y) # False print(x or y) # True print(not x) # False # Bitwise operators print(5 & 3) # 1 (bitwise AND) print(5 | 3) # 7 (bitwise OR) print(5 ^ 3) # 6 (bitwise XOR) print(~5) # -6 (bitwise NOT) # Truthiness print(bool(0)) # False print(bool(1)) # True print(bool([])) # False print(bool([1,2])) # True
JavaScript
// Boolean in JavaScript
let x = true;
let y = false;
// Logical operators
console.log(x && y); // false
console.log(x || y); // true
console.log(!x); // false
// Bitwise operators (32-bit signed)
console.log(5 & 3); // 1
console.log(5 | 3); // 7
console.log(5 ^ 3); // 6
console.log(~5); // -6
console.log(5 << 1); // 10
// Truthiness
console.log(Boolean(0)); // false
console.log(Boolean("")); // false
console.log(Boolean([])); // true (objects are truthy)
console.log(Boolean({})); // true
C/C++
// Boolean in C (using stdbool.h)
#include <stdbool.h>
#include <stdio.h>
int main() {
bool x = true;
bool y = false;
// Logical operators
printf("%d\n", x && y); // 0
printf("%d\n", x || y); // 1
printf("%d\n", !x); // 0
// Bitwise operators
printf("%d\n", 5 & 3); // 1
printf("%d\n", 5 | 3); // 7
printf("%d\n", 5 ^ 3); // 6
printf("%d\n", ~5); // -6
return 0;
}
Rust
// Boolean in Rust
fn main() {
let x = true;
let y = false;
// Logical operators
println!("{}", x && y); // false
println!("{}", x || y); // true
println!("{}", !x); // false
// Bitwise operators (only on integers)
println!("{}", 5 & 3); // 1
println!("{}", 5 | 3); // 7
println!("{}", 5 ^ 3); // 6
println!("{}", !5); // -6
// Truthiness (Rust has no truthy/falsy - must be explicit)
let num = 0;
let is_true = num != 0; // Explicit comparison required
}
11. Common Mistakes and Pitfalls
Short-Circuit Evaluation
# Short-circuit evaluation can cause side effects
def expensive_operation():
print("Expensive operation executed")
return True
# AND short-circuits: if first is False, second is not evaluated
result = False and expensive_operation() # expensive_operation not called
print(f"Result: {result}")
# OR short-circuits: if first is True, second is not evaluated
result = True or expensive_operation() # expensive_operation not called
print(f"Result: {result}")
# Be careful with side effects
def update_counter():
global counter
counter += 1
return True
counter = 0
# This may or may not update the counter
condition = False and update_counter()
print(f"Counter: {counter}") # 0
Operator Precedence
# Boolean operator precedence (highest to lowest)
# NOT > AND > OR
# Without parentheses
result = True or False and False
# Evaluated as: True or (False and False)
# = True or False = True
# With parentheses (explicit)
result = (True or False) and False
# = True and False = False
print(f"Without parentheses: {True or False and False}") # True
print(f"With parentheses: {(True or False) and False}") # False
# Best practice: use parentheses for clarity
condition = (a or b) and (c or d) # Clear intention
Truthy vs Falsy Confusion
# Python truthy/falsy values
# Falsy: False, None, 0, 0.0, [], (), {}, set(), ""
# Truthy: everything else
def check_value(value):
if value:
print(f"{value} is truthy")
else:
print(f"{value} is falsy")
check_value(0) # falsy
check_value(1) # truthy
check_value([]) # falsy
check_value([1]) # truthy
check_value("") # falsy
check_value("a") # truthy
# Potential bug: 0 is falsy, but might be valid input
def process_count(count):
if count:
print(f"Processing {count} items")
else:
print("No items to process")
process_count(0) # "No items to process" (correct)
process_count(5) # "Processing 5 items"
Conclusion
Boolean algebra is fundamental to computer science and programming. Understanding its principles enables you to write more efficient code, design better digital circuits, and solve logical problems systematically.
Key Takeaways
- Three Basic Operations: AND, OR, NOT form the foundation
- Derived Operations: NAND, NOR, XOR, XNOR built from basics
- Boolean Laws: Identity, complement, idempotent, commutative, associative, distributive, absorption, De Morgan's
- Applications: Digital circuits, programming logic, database queries, search engines
- Bitwise Operations: Direct application of Boolean algebra to bits
- Short-Circuit Evaluation: Important performance consideration
Quick Reference
| Operation | Symbol | Truth Table | Programming |
|---|---|---|---|
| AND | · or ∧ | 0·0=0, 0·1=0, 1·0=0, 1·1=1 | and, & |
| OR | + or ∨ | 0+0=0, 0+1=1, 1+0=1, 1+1=1 | or, | |
| NOT | ' or ¬ | ¬0=1, ¬1=0 | not, ~ |
| XOR | ⊕ | 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0 | !=, ^ |
| NAND | ↑ | 0↑0=1, 0↑1=1, 1↑0=1, 1↑1=0 | not and |
| NOR | ↓ | 0↓0=1, 0↓1=0, 1↓0=0, 1↓1=0 | not or |
Boolean algebra is not just a mathematical curiosity—it's the language of digital logic that powers every computer, smartphone, and digital device. Master it, and you'll have a deeper understanding of how computers actually work!