Discrete Math Basics & Logic Gates: Propositions, Connectives & Truth Tables

Core Concepts: What is Discrete Mathematics?

Discrete mathematics is the study of mathematical structures that are fundamentally discrete (separate, distinct) rather than continuous. Unlike calculus (which deals with smooth curves and limits), discrete math focuses on objects that can only take specific, separate values. Key areas include:

• Logic (propositions, connectives, truth tables)
• Sets (collections of distinct objects)
• Functions (mappings between sets)
• Graphs (networks of nodes and edges)
• Algorithms (step-by-step problem-solving methods)

In this unit, we focus on logic, the backbone of computer science, programming, and decision-making systems.

1. Propositions and Logical Connectives

What is a Proposition?

A proposition is a declarative statement that is either true (T) or false (F), but not both. It must have a clear truth value.

Examples:

• "The sky is blue." (Proposition, can be evaluated as T/F)
• "Close the door." (Not a proposition, it’s a command)
• "x + 2 = 5" (Proposition only if x is defined, e.g., x=3 makes it T)

Worked Example:

Determine whether the following are propositions:

1. "Nepal is a landlocked country." (Proposition, T)
2. "Let’s go to the park." (Not a proposition)
3. "2 + 2 = 4" (Proposition, T)
4. "x > 10" (Not a proposition unless x is specified)

Logical Connectives (Operators)

Logical connectives combine propositions to form compound propositions. The five primary connectives are:

Worked Example: Evaluating Compound Propositions

Let:

• P: "It is raining." (T)
• Q: "I will carry an umbrella." (F)

Evaluate:

1. P ∧ Q ("It is raining and I will carry an umbrella.") → T ∧ F = F
2. P ∨ Q ("It is raining or I will carry an umbrella.") → T ∨ F = T
3. P → Q ("If it is raining, then I will carry an umbrella.") → T → F = F (only false when P is T and Q is F)
4. P ↔ Q ("It is raining if and only if I carry an umbrella.") → T ↔ F = F

2. Truth Tables: The Heart of Logic

A truth table lists all possible truth values of propositions and the resulting truth value of a compound proposition. For n propositions, there are 2ⁿ rows.

Steps to Construct a Truth Table:

1. List all possible combinations of truth values for the propositions.
2. Evaluate each connective step-by-step.
3. Combine results to get the final truth value.

Example: Truth Table for (P ∧ Q) ∨ ¬R

Assume propositions: P, Q, R.

3. Logical Equivalences: Simplifying Statements

Logical equivalences are statements that are always true, regardless of the truth values of their components. They help simplify complex logical expressions.

Key Equivalences:

Worked Example: Simplify (P → Q) ∧ (P → R)

Using the implication equivalence: P → Q ≡ ¬P ∨ Q P → R ≡ ¬P ∨ R

So, (P → Q) ∧ (P → R) ≡ (¬P ∨ Q) ∧ (¬P ∨ R) Using the distributive law: ≡ ¬P ∨ (Q ∧ R)

Thus, the simplified form is ¬P ∨ (Q ∧ R).

4. Tautologies, Contradictions, and Contingencies

Worked Example: Identify the Type

1. (P ∨ Q) ∧ ¬(P ∨ Q)
   • This is always F (Contradiction).
2. P → P
   • Always T (Tautology).
3. P ∧ ¬Q
   • Depends on P and Q (Contingency).

5. Predicates and Quantifiers

Predicates

A predicate is a statement that contains variables and becomes a proposition when the variables are replaced with specific values.

Example:

• P(x): "x > 5" (Predicate)
  • P(6) is T (6 > 5)
  • P(3) is F (3 > 5 is false)

Quantifiers

Quantifiers specify the scope of a predicate over a domain.

Worked Example: Negating Quantifiers

Original: ∀x (P(x)) Negation: ∃x (¬P(x)) ("Not for all x is P(x) true" means "There exists an x for which P(x) is false")

Original: ∃x (Q(x)) Negation: ∀x (¬Q(x)) ("Not for some x is Q(x) true" means "For all x, Q(x) is false")

6. Applications in Real-World Systems

In the Real World

Discrete mathematics and logic are the invisible backbone of many systems we use daily:

1. eSewa and Khalti (Digital Payments)

   • Idea Used: Propositions and Implications
   • How? When you transfer money via eSewa, the system checks multiple conditions as logical implications:
     • "If (account balance ≥ amount) and (recipient account is valid) and (OTP is correct) then transfer money."
     • This is modeled as: (Balance ≥ Amount) ∧ (ValidRecipient) ∧ (CorrectOTP) → TransferMoney.
   • Example: If your balance is ₹500 and you try to send ₹600, the system evaluates (500 ≥ 600) ∧ ... as F, so the transfer fails.

2. Pathao (Ride-Hailing App)

   • Idea Used: Logical Connectives in Ride Matching
   • How? Pathao matches riders and drivers using logical conditions:
     • "If (rider location = driver location) and (driver is available) and (vehicle type matches) then assign ride."
     • This is: (RiderLoc = DriverLoc) ∧ (DriverAvailable) ∧ (VehicleTypeMatch) → AssignRide.
   • Example: If a rider requests a bike but only car drivers are nearby, (BikeRequest ∧ CarAvailable) evaluates to F, so no match is made.

3. NTC (Telecom Network Routing)

   • Idea Used: Propositions in Network Packets
   • How? Data packets in NTC’s network are routed based on logical conditions:
     • "If (packet destination = Kathmandu) and (Kathmandu server is up) then route via fiber optic cable A."
     • This is: (Destination = Kathmandu) ∧ (ServerUp) → RouteViaA.
   • Example: If a packet’s destination is Pokhara but the Pokhara server is down, the system evaluates (Destination = Pokhara) ∧ (ServerDown) as F and routes via an alternative path.

4. Bank Loan Approval (Nepal Bank Limited)

   • Idea Used: Compound Propositions in Decision Trees
   • How? Banks use logical conditions to approve loans:
     • "If (income ≥ ₹50,000) and (credit score ≥ 650) and (loan amount ≤ 50% of income) then approve loan."
     • This is: (Income ≥ 50000) ∧ (CreditScore ≥ 650) ∧ (LoanAmount ≤ 0.5 * Income) → ApproveLoan.
   • Worked Example: For a salary of ₹60,000 and a loan request of ₹25,000:
     • (60000 ≥ 50000) ∧ (700 ≥ 650) ∧ (25000 ≤ 0.5 * 60000)
     • T ∧ T ∧ T → ApproveLoan (T).

7. Logic Gates and Digital Circuits

Logic gates are physical implementations of logical connectives in computers and electronic circuits. Here’s how they map:

| Logical Connective | Gate Symbol | Truth Table (A B | Output) | |--------------------|-------------|-------------------| | AND (∧) | | T T | T <br> T F | F <br> F T | F <br> F F | F | | OR (∨) | | T T | T <br> T F | T <br> F T | T <br> F F | F | | NOT (¬) | | T | F <br> F | T | | NAND (¬(A ∧ B)) | | T T | F <br> T F | T <br> F T | T <br> F F | T | | NOR (¬(A ∨ B)) | | T T | F <br> T F | F <br> F T | F <br> F F | T | | XOR (Exclusive OR) | | T T | F <br> T F | T <br> F T | T <br> F F | F |

Worked Example: Design a Circuit for (P ∨ Q) ∧ ¬R

1. First, construct P ∨ Q using an OR gate.
2. Then, construct ¬R using a NOT gate.
3. Finally, feed the outputs of the OR gate and NOT gate into an AND gate.

graph LR
    P["P"] --OR--> OR1["P ∨ Q"]
    Q["Q"]
    R["R"] --NOT--> NOT1["¬R"]
    OR1 --AND--> AND1["(P ∨ Q) ∧ ¬R"]
    NOT1

8. Exam Tip: How to Score Full Marks

Common Pitfalls to Avoid:

1. Misidentifying Propositions

   • Wrong: Calling "Open the door." a proposition.
   • Right: Only declarative statements with clear truth values are propositions.

2. Incorrect Truth Table Construction

   • Wrong: Missing rows or columns in the truth table.
   • Right: Always list all possible combinations (2ⁿ rows for n propositions).

3. Logical Equivalence Errors

   • Wrong: Assuming P → Q is the same as Q → P.
   • Right: Use equivalence rules (e.g., P → Q ≡ ¬P ∨ Q) to simplify.

4. Quantifier Negation Mistakes

   • Wrong: Negating ∀x P(x) as ∀x ¬P(x).
   • Right: Negation is ∃x ¬P(x).

How to Answer Exam Questions:

• For proposition evaluation: Clearly state the truth values of P, Q, etc., and evaluate step-by-step.
• For truth tables: Label columns properly and show intermediate steps.
• For logical equivalences: Start with the original expression and apply rules one by one, justifying each step.
• For real-world applications: Relate logic to systems like eSewa, Pathao, or bank loans by mapping conditions to logical statements.

Sample Exam Question and Answer:

Question: Construct the truth table for (P ∧ Q) → (¬P ∨ R).

Answer:

1. List all combinations of P, Q, R (8 rows).
2. Evaluate P ∧ Q.
3. Evaluate ¬P.
4. Evaluate ¬P ∨ R.
5. Finally, evaluate (P ∧ Q) → (¬P ∨ R) using the implication rule (A → B ≡ ¬A ∨ B).

Summary Table: Key Concepts at a Glance

Final Worked Example: Real-World Application

Scenario: A bank in Nepal uses the following rules to approve a loan:

1. The applicant’s income must be ≥ ₹40,000.
2. The applicant’s credit score must be ≥ 600.
3. The loan amount must be ≤ 40% of the income.
4. The applicant must not have any outstanding loans.

Model this using logical connectives and evaluate for:

• Income = ₹50,000
• Credit score = 650
• Loan amount = ₹18,000
• Outstanding loans = None

Solution: Let:

• P: Income ≥ 40,000 (T)
• Q: Credit score ≥ 600 (T)
• R: Loan amount ≤ 40% of income (18,000 ≤ 0.4 * 50,000 → 18,000 ≤ 20,000) (T)
• S: No outstanding loans (T)

The approval condition is: P ∧ Q ∧ R ∧ S.

Evaluate: P ∧ Q ∧ R ∧ S = T ∧ T ∧ T ∧ T = T → Loan approved.

Exam Tip Recap

• Propositions: Only declarative statements with truth values.
• Truth Tables: Systematic evaluation of all combinations.
• Equivalences: Simplify using rules (e.g., P → Q ≡ ¬P ∨ Q).
• Quantifiers: Negate carefully (∀ becomes ∃ with ¬).
• Real-World Links: Relate logic to apps like eSewa, Pathao, or bank systems by mapping conditions to logical statements.