Discrete Mathematics For AIML - Chapter 2 Logic & Propositional Calculus

Chapter 2 — Logic & Propositional Calculus

This chapter introduces logic and propositional calculus, essential for reasoning, knowledge representation, and designing rule-based AI/ML systems.

2.1 Propositions & Truth Values

A proposition is a statement that is either true or false, but not both. AI/ML Context: Propositions can represent conditions, rules, or feature presence in datasets.

True (T) or False (F) values.
Example: "The email contains 'offer'" → True or False.

2.2 Logical Connectives

Combine or modify propositions using logical connectives.

AND ( ∧ ): True if both propositions are true.
OR ( ∨ ): True if at least one proposition is true.
NOT ( ¬ ): Negates the proposition.
Implication ( → ): If p then q.
Biconditional ( ↔ ): True if both propositions have the same truth value.

AI/ML Context: Used in rule-based decision systems, Boolean feature engineering, and logical constraints.

2.3 Truth Tables

Truth tables show all possible truth values for propositions and their combinations.

# Example in Python
p = [True, True, False, False]
q = [True, False, True, False]

# AND operation
and_result = [p[i] and q[i] for i in range(4)]
# OR operation
or_result = [p[i] or q[i] for i in range(4)]

print("AND:", and_result)
print("OR:", or_result)

2.4 Predicates & Quantifiers

Extend propositions to express statements about elements of sets.

Predicate: A function that returns True or False for elements (e.g., P(x): x > 0).
Universal Quantifier ( ∀ ): "For all" elements, P(x) holds.
Existential Quantifier ( ∃ ): "There exists" at least one element for which P(x) holds.

AI/ML Context: Useful for feature constraints, filtering, and rule-based logic systems.

2.5 Logical Equivalence & Laws

Logical equivalences simplify expressions and help reason about rules.

De Morgan’s Laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q, ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Distributive: P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Associative: (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)

AI/ML Context: Simplifying Boolean expressions for feature engineering and knowledge representation in expert systems.

2.6 Practical Python Examples

# Propositions as Boolean variables
p = True
q = False

# Logical operations
print("AND:", p and q)
print("OR:", p or q)
print("NOT p:", not p)
print("Implication (p -> q):", (not p) or q)
print("Biconditional (p <-> q):", (p and q) or (not p and not q))

# Using predicates and quantifiers
data = [2, 4, 6, 8]
all_even = all(x % 2 == 0 for x in data)  # ∀x P(x)
some_even = any(x % 2 == 0 for x in data)  # ∃x P(x)
print("All even?", all_even)
print("Some even?", some_even)

2.7 Why Logic & Propositional Calculus Matter in AI/ML

Logic is crucial for:

Designing rule-based systems and expert systems.
Boolean feature engineering in ML models.
Knowledge representation in AI applications like reasoning engines and chatbots.

2.8 Exercises

Construct truth tables for the expression ¬(P ∨ Q) and verify De Morgan’s Law.
Implement a predicate to check if elements in a list are prime and use quantifiers.
Create a simple Boolean rule-based classifier using Python.

Hints / Solutions

Use Python lists and Boolean operations to create truth tables.
Define a function is_prime(x) and use all() or any() for quantifiers.
Use if-else logic to implement Boolean rules.

2.9 Further Reading & Videos

Discrete Mathematics and Its Applications – Kenneth H. Rosen
Khan Academy – Logic and Truth Tables
YouTube – "Discrete Mathematics for Computer Science" by WilliamFiset

Next Chapter: Combinatorics — Counting principles, permutations, and combinations used in probability, feature combinations, and ML dataset design.

IndianTechnoEra