Logic, Propositions, and Foundations of Discrete Math

TAKEAWAYS:

• Propositions are statements with a definite truth value (true/false), forming the building blocks of logic.
• Logical operators (AND, OR, NOT, IMPLIES) combine propositions to create complex expressions, visualized in truth tables.
• Quantifiers (∀, ∃) specify scope over sets, critical for database queries (e.g., "All users in eSewa have verified IDs").
• Truth tables systematically evaluate compound propositions, ensuring correctness in circuit design (e.g., WhatsApp’s message encryption logic).
• Tautologies and contradictions identify always-true/false statements, used in algorithm validation (e.g., Daraz’s order fulfillment guarantees).
• Real-world ties: Logic underpins apps like Khalti’s fraud detection (propositional rules) and NTC’s network reliability (predicate logic for path validation).

---

1. Propositions: The Building Blocks of Logic

A proposition is a declarative statement that is either true (T) or false (F), but not both. It cannot be a question, command, or ambiguous statement.

Examples of Propositions

• "Nepal is a landlocked country." (True)
• "2 + 3 = 7." (False)
• "The sky is blue." (Context-dependent; avoid unless specified)

Non-Propositions

• "Close the door." (Command)
• "Is it raining?" (Question)
• "x + 2 = 5." (Truth depends on x; not a proposition unless x is defined)

Worked Example: eSewa Transaction

• Proposition: "If the user’s balance ≥ 1000, then the transaction is approved."
  • P: "User’s balance ≥ 1000" (True/False)
  • Q: "Transaction is approved" (True/False)
  • Combined: P → Q (read as "P implies Q").

---

2. Logical Operators and Truth Tables

Logical operators combine propositions to form compound propositions. Truth tables list all possible truth values of the components and the result.

Key Operators

Worked Example: Pathao’s Delivery Logic

• P: "Driver is available."
• Q: "Order distance ≤ 5 km."
• Compound Proposition: "If the driver is available AND the distance ≤ 5 km, then deliver the order."
  • P ∧ Q → Deliver
  • Truth table ensures only valid combinations trigger delivery.

---

3. Quantifiers: Universal (∀) and Existential (∃)

Quantifiers extend propositions over sets or domains.

Negation Rules

• ¬(∀x, P(x)) ≡ ∃x, ¬P(x)
• ¬(∃x, P(x)) ≡ ∀x, ¬P(x)

Worked Example: Ncell Network Coverage

• Proposition: "All base stations in Kathmandu have 4G coverage."
  • ∀x ∈ BaseStations, Coverage(x) = 4G
  • Negation: "There exists a base station without 4G coverage."
    • ∃x ∈ BaseStations, Coverage(x) ≠ 4G

---

4. Tautologies, Contradictions, and Contingencies

• Tautology: Always true (e.g., P ∨ ¬P).
• Contradiction: Always false (e.g., P ∧ ¬P).
• Contingency: Truth depends on inputs (e.g., P ∧ Q).

Worked Example: NEPSE Stock Alerts

• Proposition: "If the stock price rises AND volume > 1000, then trigger an alert."
  • P ∧ Q → Alert
  • This is a contingency (alert depends on P and Q).

---

5. Logical Equivalences and Laws

Logical equivalences simplify expressions using identities like De Morgan’s Laws.

Key Laws

1. Double Negation: ¬(¬P) ≡ P
2. Commutative:
   • P ∧ Q ≡ Q ∧ P
   • P ∨ Q ≡ Q ∨ P
3. Associative:
   • (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
   • (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
4. Distributive:
   • P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
   • P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
5. De Morgan’s:
   • ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
   • ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
6. Absorption:
   • P ∨ (P ∧ Q) ≡ P
   • P ∧ (P ∨ Q) ≡ P

Worked Example: Bank Loan Approval

• Original: "The loan is approved if the applicant has a salary ≥ 50,000 OR a guarantor AND good credit."
  • P ∨ (Q ∧ R)
• Simplified using distributive law:
  • (P ∨ Q) ∧ (P ∨ R)

---

6. Predicate Logic and Nested Quantifiers

Predicate logic extends propositions with variables and quantifiers over domains.

Example: Daraz Order Processing

• Domain: Orders = {O₁, O₂, ..., Oₙ}
• Proposition: "For every order, if it’s urgent AND paid, then ship it."
  • ∀x ∈ Orders, (Urgent(x) ∧ Paid(x)) → Ship(x)

Nested Quantifiers

• ∀x ∃y, P(x, y): "For every x, there exists a y such that P(x, y) holds."
• ∃x ∀y, Q(x, y): "There exists an x such that for all y, Q(x, y) holds."

Worked Example: WhatsApp Group Rules

• ∀user ∈ Group, ∃admin, admin can ban user
  • "Every user in the group can be banned by some admin."

---

In the Real World

1. eSewa’s Transaction Validation

   • Uses propositional logic to check:
     • "(User authenticated ∧ Balance ≥ Amount) → Process payment"
   • Truth tables ensure no fraudulent transactions slip through.

2. Khalti’s Fraud Detection

   • Predicate logic flags suspicious transactions:
     • "∃transaction ∈ T, (Amount > 100,000 ∧ Location ≠ User’s City) → Block"

3. NTC’s Network Path Planning

   • Graph theory + logic determines optimal routes:
     • "∀node ∈ Network, ∃path to Destination ∧ (Delay < Threshold)"

---

Exam Tip

• Propositions: Always check if a statement is declarative and has a clear truth value.
• Truth Tables: For compound propositions, list all possible combinations (2ⁿ rows for n variables).
• Quantifiers: Practice negating statements (e.g., "Not all students passed" → "There exists a student who failed").
• Equivalences: Memorize De Morgan’s and distributive laws—they appear in simplification questions.
• Real-World Links: Connect logic to apps like eSewa (propositions), Pathao (implications), or Ncell (quantifiers) in explanations.

---

Visual Summary

In the real world

• eSewa Transaction Validation: Uses propositional logic ((User authenticated ∧ Balance ≥ Amount) → Process payment) to ensure secure transactions. The truth table for this compound proposition is evaluated in real-time to approve/reject payments.
• NTC Network Path Planning: Applies predicate logic (∀node ∈ Network, ∃path to Destination ∧ (Delay < Threshold)) to optimize data routing across Kathmandu’s fiber-optic backbone, ensuring low-latency connectivity for Ncell and NEPSE services.
• WhatsApp Group Rules: Implements nested quantifiers (∀user ∈ Group, ∃admin, admin can ban user) to enforce moderation hierarchies, where every user’s actions are governed by at least one admin’s authority.