Mathematical Foundations for Computer Science

# Propositional logic operations
def and_(p, q):
    return p and q

def or_(p, q):
    return p or q

def not_(p):
    return not p

def implies(p, q):
    return not p or q

# Truth table generator
def truth_table(variables, expression):
    """
    Generate truth table for a propositional expression.
    variables: list of variable names
    expression: function that takes values and returns boolean
    """
    n = len(variables)
    results = []
    
    for i in range(2**n):
        values = [(i >> j) & 1 for j in range(n)]
        assignment = dict(zip(variables, values))
        result = expression(**assignment)
        results.append((assignment, result))
    
    return results

# Example: (p AND q) OR NOT r
expr = lambda p, q, r: (p and q) or (not r)
table = truth_table(['p', 'q', 'r'], expr)

# Boolean algebra laws
laws = {
    "identity": {
        "AND": "A AND 1 = A",
        "OR": "A OR 0 = A"
    },
    "null": {
        "AND": "A AND 0 = 0",
        "OR": "A OR 1 = 1"
    },
    "idempotent": {
        "AND": "A AND A = A",
        "OR": "A OR A = A"
    },
    "complement": {
        "AND": "A AND NOT A = 0",
        "OR": "A OR NOT A = 1"
    },
    "commutative": {
        "AND": "A AND B = B AND A",
        "OR": "A OR B = B OR A"
    },
    "associative": {
        "AND": "(A AND B) AND C = A AND (B AND C)",
        "OR": "(A OR B) OR C = A OR (B OR C)"
    },
    "distributive": {
        "AND": "A AND (B OR C) = (A AND B) OR (A AND C)",
        "OR": "A OR (B AND C) = (A OR B) AND (A OR C)"
    },
    "de_morgan": {
        "NOT_A_AND_B": "NOT(A AND B) = NOT A OR NOT B",
        "NOT_A_OR_B": "NOT(A OR B) = NOT A AND NOT B"
    }
}

# Simplify boolean expressions using Karnaugh maps
def simplify_kmap(expression, variables):
    """
    Simplify boolean expression using Karnaugh map method.
    """
    # Implementation would involve:
    # 1. Create K-map grid
    # 2. Group adjacent 1s in powers of 2
    # 3. Extract simplified terms
    pass

class Set:
    def __init__(self, elements=None):
        self.elements = set(elements) if elements else set()
    
    def union(self, other):
        return Set(self.elements | other.elements)
    
    def intersection(self, other):
        return Set(self.elements & other.elements)
    
    def difference(self, other):
        return Set(self.elements - other.elements)
    
    def complement(self, universal):
        return Set(universal.elements - self.elements)
    
    def cartesian_product(self, other):
        return Set((a, b) for a in self.elements for b in other.elements)
    
    def power_set(self):
        from itertools import combinations
        elements = list(self.elements)
        power = Set()
        for r in range(len(elements) + 1):
            for combo in combinations(elements, r):
                power.elements.add(frozenset(combo))
        return power

# Example
A = Set([1, 2, 3, 4])
B = Set([3, 4, 5, 6])
print(A.union(B).elements)  # {1, 2, 3, 4, 5, 6}
print(A.intersection(B).elements)  # {3, 4}

from collections import defaultdict, deque

class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
    
    def add_edge(self, u, v, weight=None):
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def bfs(self, start):
        """Breadth-first search"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        result = []
        
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor, _ in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return result
    
    def dfs(self, start, visited=None):
        """Depth-first search"""
        if visited is None:
            visited = set()
        
        visited.add(start)
        result = [start]
        
        for neighbor, _ in self.graph[start]:
            if neighbor not in visited:
                result.extend(self.dfs(neighbor, visited))
        
        return result
    
    def dijkstra(self, start, end):
        """Shortest path with weights"""
        import heapq
        
        distances = {node: float('inf') for node in self.graph}
        distances[start] = 0
        pq = [(0, start)]
        
        while pq:
            dist, node = heapq.heappop(pq)
            
            if node == end:
                return dist
            
            if dist > distances[node]:
                continue
            
            for neighbor, weight in self.graph[node]:
                new_dist = dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
        
        return float('inf')

# Example: Social network
social = Graph()
social.add_edge("Alice", "Bob")
social.add_edge("Alice", "Charlie")
social.add_edge("Bob", "David")
social.add_edge("Charlie", "David")

print(social.bfs("Alice"))  # ['Alice', 'Bob', 'Charlie', 'David']

import numpy as np

class Matrix:
    def __init__(self, data):
        self.data = np.array(data)
        self.rows, self.cols = self.data.shape
    
    def __add__(self, other):
        return Matrix(self.data + other.data)
    
    def __mul__(self, other):
        if isinstance(other, Matrix):
            return Matrix(np.dot(self.data, other.data))
        return Matrix(self.data * other)
    
    def transpose(self):
        return Matrix(self.data.T)
    
    def determinant(self):
        return np.linalg.det(self.data)
    
    def inverse(self):
        return Matrix(np.linalg.inv(self.data))
    
    def eigenvalues(self):
        return np.linalg.eigvals(self.data)

# Example: Linear transformation
def rotate_2d(angle):
    """Create rotation matrix"""
    c, s = np.cos(angle), np.sin(angle)
    return Matrix([[c, -s], [s, c]])

def scale_2d(sx, sy):
    """Create scaling matrix"""
    return Matrix([[sx, 0], [0, sy]])

# Rotate then scale
transform = scale_2d(2, 2) * rotate_2d(np.pi/4)
print(transform.data)

class Vector:
    def __init__(self, data):
        self.data = np.array(data)
    
    def __add__(self, other):
        return Vector(self.data + other.data)
    
    def __sub__(self, other):
        return Vector(self.data - other.data)
    
    def __mul__(self, scalar):
        return Vector(self.data * scalar)
    
    def dot(self, other):
        return np.dot(self.data, other.data)
    
    def magnitude(self):
        return np.linalg.norm(self.data)
    
    def normalize(self):
        return Vector(self.data / self.magnitude())
    
    def angle(self, other):
        """Angle between two vectors in radians"""
        return np.arccos(self.dot(other) / (self.magnitude() * other.magnitude()))
    
    def project_onto(self, basis):
        """Project vector onto basis vector"""
        return basis * (self.dot(basis) / basis.dot(basis))

# Example: Gram-Schmidt orthogonalization
def gram_schmidt(vectors):
    """Orthogonalize a set of vectors"""
    orthogonal = []
    
    for v in vectors:
        v_vec = Vector(v)
        for u in orthogonal:
            projection = v_vec.project_onto(Vector(u))
            v_vec = v_vec - Vector(projection.data * u[0] if len(u) == len(projection.data) else projection.data)
        
        if v_vec.magnitude() > 1e-10:
            orthogonal.append(v_vec.normalize().data)
    
    return [Vector(v) for v in orthogonal]

import random
from collections import Counter

class Probability:
    @staticmethod
    def factorial(n):
        if n <= 1:
            return 1
        return n * Probability.factorial(n - 1)
    
    @staticmethod
    def permutations(n, k):
        """P(n,k) = n! / (n-k)!"""
        return Probability.factorial(n) // Probability.factorial(n - k)
    
    @staticmethod
    def combinations(n, k):
        """C(n,k) = n! / (k! * (n-k)!"""
        return Probability.factorial(n) // (Probability.factorial(k) * Probability.factorial(n - k))
    
    @staticmethod
    def binomial_probability(n, k, p):
        """P(X=k) = C(n,k) * p^k * (1-p)^(n-k)"""
        return Probability.combinations(n, k) * (p ** k) * ((1 - p) ** (n - k))

# Monte Carlo simulation
def monte_carlo_pi(n_points):
    """Estimate π using random sampling"""
    inside = 0
    
    for _ in range(n_points):
        x, y = random.random(), random.random()
        if x**2 + y**2 <= 1:
            inside += 1
    
    return 4 * inside / n_points

# Example
print(f"π ≈ {monte_carlo_pi(1000000):.6f}")

def bayes_theorem(p_a_b, p_b, p_a):
    """
    P(A|B) = P(B|A) * P(A) / P(B)
    """
    return (p_a_b * p_a) / p_b

# Example: Medical diagnosis
# P(Disease|Test+) = P(Test+|Disease) * P(Disease) / P(Test+)

def medical_diagnosis():
    p_disease = 0.01  # 1% of population has disease
    p_no_disease = 0.99
    
    p_test_positive_given_disease = 0.99  # 99% sensitivity
    p_test_positive_given_no_disease = 0.05  # 5% false positive
    
    p_test_positive = (p_test_positive_given_disease * p_disease + 
                       p_test_positive_given_no_disease * p_no_disease)
    
    p_disease_given_positive = (p_test_positive_given_disease * p_disease) / p_test_positive
    
    return p_disease_given_positive

print(f"P(Disease|Test+) = {medical_diagnosis():.4f}")

import numpy as np
import matplotlib.pyplot as plt

class Distributions:
    @staticmethod
    def binomial(n, p, size):
        """Binomial distribution"""
        return np.random.binomial(n, p, size)
    
    @staticmethod
    def poisson(lam, size):
        """Poisson distribution"""
        return np.random.poisson(lam, size)
    
    @staticmethod
    def exponential(scale, size):
        """Exponential distribution"""
        return np.random.exponential(scale, size)
    
    @staticmethod
    def normal(mean, std, size):
        """Normal distribution"""
        return np.random.normal(mean, std, size)

# Example: Queue simulation
def queue_simulation(arrival_rate, service_rate, n_customers):
    """
    Simulate M/M/1 queue
    """
    arrival_times = np.cumsum(np.random.exponential(1/arrival_rate, n_customers))
    service_times = np.random.exponential(1/service_rate, n_customers)
    
    departure_times = []
    current_time = 0
    
    for arrival, service in zip(arrival_times, service_times):
        current_time = max(current_time, arrival)
        current_time += service
        departure_times.append(current_time)
    
    waiting_times = [max(0, d - a) for a, d in zip(arrival_times, departure_times)]
    
    return {
        'avg_waiting': np.mean(waiting_times),
        'max_waiting': np.max(waiting_times),
        'avg_system_time': np.mean([d - a for a, d in zip(arrival_times, departure_times)])
    }

# Common time complexities
complexities = {
    "O(1)": "Constant - hash table lookup",
    "O(log n)": "Logarithmic - binary search",
    "O(n)": "Linear - simple loop",
    "O(n log n)": "Linearithmic - merge sort",
    "O(n²)": "Quadratic - nested loops",
    "O(2ⁿ)": "Exponential - recursive Fibonacci",
    "O(n!)": "Factorial - permutation generation"
}

def analyze_complexity(func):
    """
    Decorator to analyze function complexity empirically
    """
    import time
    
    def wrapper(*args, **kwargs):
        # Run with increasing input sizes
        sizes = [10, 100, 1000, 10000]
        times = []
        
        for n in sizes:
            start = time.time()
            func(n)
            times.append(time.time() - start)
        
        # Determine complexity
        ratios = []
        for i in range(1, len(times)):
            if times[i-1] > 0:
                ratio = times[i] / times[i-1]
                ratios.append(ratio)
        
        avg_ratio = sum(ratios) / len(ratios)
        
        if avg_ratio < 1.5:
            return "O(n)"
        elif avg_ratio < 5:
            return "O(n log n)"
        elif avg_ratio < 50:
            return "O(n²)"
        else:
            return "O(2ⁿ)"
    
    return wrapper

def master_theorem(a, b, f_n):
    """
    Master Theorem for divide-and-conquer recurrences:
    T(n) = aT(n/b) + f(n)
    
    Returns the time complexity.
    """
    import math
    
    n = 1000  # arbitrary large n
    log_b_a = math.log(a, b)
    
    # Compare f(n) with n^log_b_a
    if abs(f_n(n) - n**log_b_a) < 0.001 * n**log_b_a:
        return f"Θ(n^{log_b_a})"
    elif f_n(n) < n**log_b_a:
        return f"Θ(n^{log_b_a})"
    elif f_n(n) > n**log_b_a:
        if f_n(n) < n**(log_b_a + epsilon):
            return f"Θ(n^{log_b_a} log n)"
        else:
            return f"Θ(f(n))"
    
    return "Master theorem does not apply"

# Example: Merge sort
# T(n) = 2T(n/2) + Θ(n)
print(master_theorem(2, 2, lambda n: n))  # Θ(n log n)

def extended_gcd(a, b):
    """Extended Euclidean Algorithm"""
    if a == 0:
        return b, 0, 1
    
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return gcd, x, y

def modular_inverse(a, m):
    """Find modular multiplicative inverse"""
    gcd, x, y = extended_gcd(a, m)
    
    if gcd != 1:
        return None  # Inverse doesn't exist
    
    return (x % m + m) % m

def fermat_prime_test(n, k=5):
    """Probabilistic prime test"""
    import random
    
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    
    return True

# RSA key generation concepts
def rsa_keygen(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # Choose e
    e = 65537  # Common choice
    
    # Calculate d
    d = modular_inverse(e, phi)
    
    return (e, n), (d, n)  # Public key, private key