Logic, Propositions, Truth Tables & Boolean Algebra

Propositional Logic: The Building Blocks

What is a Proposition?

A proposition is a declarative statement that is either true (T) or false (F), but not both. It must be unambiguous and verifiable.

| P | Q |
|---|---|
| T | F |
| F | T |

Key Points:

• Not all sentences are propositions. Questions, commands, and exclamations are not propositions.
• Example: "Nepal is a landlocked country." (True) vs. "The sky is green." (False)

---

Logical Connectives: Combining Propositions

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

A combined truth table for all five connectives (Image: WatchduckYou can name the author as 'T. Piesk', 'Tilman Pies, Public domain, via Wikimedia Commons)

---

Worked Example: Evaluating Compound Propositions

Problem: Evaluate the truth value of (¬P ∨ Q) → (P ∧ ¬Q) when P is true and Q is false.

Solution:

1. ¬P = ¬(T) = F
2. ¬P ∨ Q = F ∨ F = F
3. P ∧ ¬Q = T ∧ T = T
4. (¬P ∨ Q) → (P ∧ ¬Q) = F → T = T

---

Tautologies, Contradictions, and Contingencies

---

Logical Equivalences and Laws

Logical equivalences allow us to simplify or transform propositions without changing their truth value.

---

Boolean Algebra: The Algebra of Logic

Boolean algebra is a branch of algebra where the values of the variables are the truth values true and false, and the operations are logical connectives.

Key Properties:

1. Closure: The result of applying a logical connective to propositions is always a proposition.
2. Identity: P ∨ F ≡ P and P ∧ T ≡ P.
3. Commutativity: P ∨ Q ≡ Q ∨ P and P ∧ Q ≡ Q ∧ P.
4. Associativity: (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) and (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R).
5. Distributivity: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) and P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R).
6. Complement: P ∨ ¬P ≡ T and P ∧ ¬P ≡ F.

---

Worked Example: Simplifying Boolean Expressions

Problem: Simplify the expression (P ∨ ¬Q) ∧ (P ∨ Q) ∧ (¬P ∨ Q).

Solution:

1. Apply the distributive law to the first two terms: (P ∨ ¬Q) ∧ (P ∨ Q) = P ∨ (¬Q ∧ Q)
2. ¬Q ∧ Q is always F (contradiction), so: P ∨ F ≡ P
3. Now the expression is P ∧ (¬P ∨ Q).
4. Apply the distributive law again: P ∧ (¬P ∨ Q) = (P ∧ ¬P) ∨ (P ∧ Q)
5. P ∧ ¬P is always F, so: F ∨ (P ∧ Q) ≡ P ∧ Q

Final Simplified Expression: P ∧ Q

---

Truth Tables for Complex Propositions

Truth tables are used to determine the truth value of complex propositions for all possible truth values of their components.

Example: Construct a truth table for (P → Q) ∧ (¬P ∨ R).

---

In the Real World

1. eSewa and Kathmandu Traffic Management:
   • Propositional Logic in Traffic Light Control: eSewa and the Kathmandu Metropolitan City use logic gates (based on propositional calculus) to control traffic lights. For example, a traffic light at a busy intersection might follow this logic:
     • IF (Sensor1 detects car AND Sensor2 detects car) THEN GreenLight1 = ON AND GreenLight2 = OFF
     • This ensures that only one direction gets the green light at a time, preventing collisions. The logic can be represented using implication (→) and conjunction (∧).

2. Khalti and Online Payment Verification:

   • Boolean Algebra in Transaction Processing: When you make a payment via Khalti, the system checks multiple conditions to verify the transaction. For example:
     • (User_Authenticated ∧ Account_Balanced) → Transaction_Approved
     • ¬(Transaction_Approved) → Send_Alert_To_User Here, logical AND (∧), implication (→), and negation (¬) are used to ensure secure and valid transactions.

3. WhatsApp Group Messages and Filtering:

   • Logical Connectives in Spam Detection: WhatsApp uses propositional logic to filter out spam messages. For instance:
     • IF (Message_Contains_Keyword AND Sender_Not_Verified) THEN Mark_As_Spam
     • This can be broken down using logical AND (∧) and implication (→). The system evaluates these conditions in real-time to protect users from unwanted messages.

---

Exam Tip

What to Expect in the Exam:

1. Definitions and Concepts:

   • Be ready to define propositions, logical connectives, tautologies, contradictions, and logical equivalences.
   • Example question: "Define a tautology and give an example."

2. Truth Tables:

   • You will be asked to construct truth tables for given logical expressions.
   • Example question: "Construct a truth table for (P ∧ Q) → (¬P ∨ R)."

3. Logical Equivalences:

   • Prove that two logical expressions are equivalent using laws of Boolean algebra.
   • Example question: "Show that P → Q is equivalent to ¬P ∨ Q."

4. Simplification:

   • Simplify complex logical expressions using Boolean algebra laws.
   • Example question: "Simplify the expression (P ∨ ¬Q) ∧ (P ∨ Q)."

5. Applications:

   • Explain real-world applications of propositional logic, such as in traffic management systems, payment verification, or spam detection.
   • Example question: "How is propositional logic used in online payment systems like Khalti?"

Tips for Success:

• Practice Constructing Truth Tables: This is a fundamental skill. Start with simple expressions and gradually move to more complex ones.
• Memorize Logical Equivalences: Laws like De Morgan’s, distributive laws, and implication equivalences are frequently tested.
• Understand the Real-World Applications: Connecting theoretical concepts to practical scenarios (like traffic lights or payment systems) can help you remember the material better and perform well in application-based questions.
• Work on Simplification Problems: These problems require a good grasp of Boolean algebra. Practice regularly to build confidence.

---