Set Operations, Bit Strings & Boolean Matrix Operations

Explanation

Set theory provides the foundational ontology for discrete mathematics and computer science databases. Representing finite sets as bit vectors allows memory-efficient storage and enables high-speed bit-parallel microprocessor register execution for union, intersection, and set membership testing. Boolean matrices map binary relations and graph adjacencies directly into algebraic structures.

Key points

• Power set P(S) contains all subsets of S; if |S| = n, then |P(S)| = 2^n.
• Bit String representation: For universal set U = {e₁, e₂, ..., e_n}, a subset A is represented by an n-bit vector where bit_i = 1 if e_i ∈ A, else 0. Set operations reduce to bitwise OR, AND, and XOR.
• Zero-One (Boolean) Matrices: Matrices whose entries are either 0 or 1, representing relations and graphs.
• Boolean matrix operations: Join (A ∨ B where c_{ij} = a_{ij} ∨ b_{ij}), Meet (A ∧ B where c_{ij} = a_{ij} ∧ b_{ij}), and Boolean Product (A ⊙ B where c_{ij} = ⋁{k=1}^m (a{ik} ∧ b_{kj})).

Example

Code examples

// C++ Bit String Set Representation & Boolean Join/Meet
#include <iostream>
#include <vector>
using namespace std;

// Boolean Matrix Multiplication (A ⊙ B)
vector<vector<int>> booleanProduct(const vector<vector<int>>& A, const vector<vector<int>>& B) {
    int r = A.size(), m = B.size(), c = B[0].size();
    vector<vector<int>> C(r, vector<int>(c, 0));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = 0; k < m; k++) {
                if (A[i][k] && B[k][j]) { C[i][j] = 1; break; }
            }
        }
    }
    return C;
}

Exam questions

• [7 Marks] State and prove the Principle of Inclusion-Exclusion for three sets A, B, and C.
• [7 Marks] Let A and B be zero-one matrices of size 3x3. Compute the Join, Meet, and Boolean Product of A and B.