Logic and Sets: Propositions, Connectives, Set Theory, Venn Diagrams

TAKEAWAYS:

• Learn to identify propositions (true/false statements) and use logical connectives (AND, OR, NOT, IMPLIES) with truth tables.
• Master set operations (union, intersection, complement) and draw Venn diagrams for any scenario.
• Apply De Morgan’s laws to simplify logical expressions and set statements.
• Understand quantifiers (∀, ∃) and their role in translating word problems into math.
• Solve real-world problems using set theory (e.g., survey data, probability).
• Practice NEB-style proofs for set identities and logical equivalences.

---

### **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.
**Examples:**
- "The sky is blue." → Proposition (can be true/false).
- "Close the door." → **Not** a proposition (it’s a command).
- "x + 2 = 5" → Proposition **only if x is given a value** (e.g., if x=3, it’s true).

#### **Logical Connectives**
We combine propositions using **connectives** to form **compound propositions**. The main connectives are:

| Connective | Symbol | Name          | Truth Table (P, Q) |
|------------|--------|---------------|--------------------|
| AND        | ∧      | Conjunction   | T ∧ T = T          |
|            |        |               | T ∧ F = F          |
|            |        |               | F ∧ T = F          |
|            |        |               | F ∧ F = F          |
| OR         | ∨      | Disjunction   | T ∨ T = T          |
|            |        |               | T ∨ F = T          |
|            |        |               | F ∨ T = T          |
|            |        |               | F ∨ F = F          |
| NOT        | ¬      | Negation      | ¬T = F             |
|            |        |               | ¬F = T             |
| IMPLIES    | →      | Implication   | T → T = T          |
|            |        |               | T → F = F          |
|            |        |               | F → T = T          |
|            |        |               | F → F = T          |
| IFF        | ↔      | Biconditional| T ↔ T = T          |
|            |        |               | T ↔ F = F          |
|            |        |               | F ↔ T = F          |
|            |        |               | F ↔ F = T          |

**Example:**
Let P = "It is raining," Q = "I carry an umbrella."
- P ∧ Q = "It is raining **and** I carry an umbrella."
- P ∨ Q = "It is raining **or** I carry an umbrella."
- P → Q = "If it is raining, then I carry an umbrella."

#### **Worked Example: Truth Table**
Construct the truth table for: **¬(P ∨ Q) ∧ R**, where R is another proposition.

**Key Observation:**
The expression is **only true when P and Q are both false, and R is true**.

---


---

### **2. Set Theory Basics**
#### **What is a Set?**
A **set** is a well-defined collection of distinct objects, called **elements**.
**Examples:**
- A = {1, 2, 3, 4} (set of numbers)
- B = {a, e, i, o, u} (set of vowels)
- C = {x | x is a prime number < 10} = {2, 3, 5, 7}

#### **Types of Sets**
| Type               | Description                          | Example                     |
|--------------------|--------------------------------------|-----------------------------|
| **Finite Set**     | Limited number of elements.          | A = {1, 2, 3}               |
| **Infinite Set**   | Unlimited elements.                  | B = {x | x is an integer}         |
| **Empty Set (∅)**  | No elements.                         | C = {}                      |
| **Universal Set (U)** | Contains all possible elements.    | U = {1, 2, ..., 10}         |
| **Subset (⊆)**     | All elements of A are in B.          | {1, 2} ⊆ {1, 2, 3}          |

#### **Set Operations**
| Operation       | Symbol | Description                          | Example (A = {1, 2, 3}, B = {3, 4, 5}) |
|-----------------|--------|--------------------------------------|----------------------------------------|
| **Union**       | ∪      | All elements in A or B.             | A ∪ B = {1, 2, 3, 4, 5}               |
| **Intersection**| ∩      | Elements common to A and B.         | A ∩ B = {3}                           |
| **Complement**  | A'     | Elements in U but not in A.         | If U = {1, 2, ..., 5}, A' = {4, 5}   |
| **Difference**  | A \ B  | Elements in A but not in B.         | A \ B = {1, 2}                       |

---
```figure
{"type":"venn2","sets":{"A":[1,2,3],"B":[3,4,5]},"u":[1,2,3,4,5],"shade":"union","caption":"A ∪ B = {1, 2, 3, 4, 5}"}

---

3. Venn Diagrams and Set Problems

Drawing Venn Diagrams

Venn diagrams visually represent sets and their operations. Example: Let U = {1, 2, 3, 4, 5, 6}, A = {1, 2, 3}, B = {3, 4, 5}.

---

Worked Example: Word Problem

In a class of 40 students:

• 20 study Maths (M),
• 15 study Physics (P),
• 10 study both.

Find:

1. Students studying only Maths.
2. Students studying neither.

Solution:

1. Only Maths = Total Maths − Both = 20 − 10 = 10.
2. Neither = Total − (Only M + Only P + Both) = 40 − (10 + 5 + 10) = 15.

---

---

4. De Morgan’s Laws

De Morgan’s Laws relate the complement of sets and logical expressions.

Example: Let A = {1, 2}, B = {2, 3}, U = {1, 2, 3, 4}.

• (A ∪ B)' = {4} (since A ∪ B = {1, 2, 3})
• A' ∩ B' = {3, 4} ∩ {1, 4} = {4} ✔️

---

---

5. Quantifiers (∀ and ∃)

• ∀ (Universal Quantifier): "For all" or "Every." Example: ∀x ∈ A, x > 0 → "All elements in A are greater than 0."
• ∃ (Existential Quantifier): "There exists." Example: ∃x ∈ B, x = 5 → "There is an element in B equal to 5."

Negation Rules:

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

Example: Original: "All students passed the exam." Negation: "There exists a student who did not pass."

---

6. Applications of Logic and Sets

1. Computer Science:
   • Boolean algebra (used in digital circuits).
   • SQL queries (WHERE clauses use AND/OR).
2. Mathematics:
   • Proofs (e.g., proving set identities).
   • Probability (Venn diagrams for events).
3. Daily Life:
   • Decision-making (e.g., "If it rains, take an umbrella").

---

Exam Tip

1. Propositions and Truth Tables:

   • Always list all possible combinations (2ⁿ for n variables).
   • NEB often asks for equivalent expressions (e.g., simplify P → Q to ¬P ∨ Q).

2. Set Problems:

   • Draw Venn diagrams for word problems.
   • Remember:
     • n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
     • n(A') = n(U) − n(A).

3. De Morgan’s Laws:

   • Convert between set and logical forms.
   • Example question: "If (A ∩ B)' = {1, 2}, A = {1, 3, 4}, find B."

4. Quantifiers:

   • Translate English to symbols (e.g., "No student failed" → ∀x, P(x)).

5. Common Mistakes:

   • Confusing ∪ (OR) with ∩ (AND).
   • Forgetting to shade the correct region in Venn diagrams.

---

NEB Board-Style Questions

Section A: Short Answer (2 marks each)

1. Write the truth table for: P ∧ (Q ∨ ¬R).
2. If A = {1, 2, 3}, B = {3, 4, 5}, find A ∪ B and A ∩ B.
3. State De Morgan’s Law for sets in words.
4. Negate: "Some students play football."

Section B: Long Answer (5 marks each)

5. In a survey of 50 people:

   • 25 like tea (T),
   • 20 like coffee (C),
   • 10 like both. Draw a Venn diagram and find: a) People who like only tea. b) People who like neither.

6. Prove using De Morgan’s Law: (A ∪ B ∪ C)' = A' ∩ B' ∩ C'.

7. Construct a truth table for: (P → Q) ∧ (¬P ∨ R). When is the statement false?

---

Final Advice:

• Practice drawing Venn diagrams for every set problem.
• Memorize truth tables for common connectives.
• For proofs, start with the given and apply laws step-by-step.

---

Venn diagrams for logical connectives (Image: ZanderSchubert (talk), CC BY 3.0, via Wikimedia Commons) Truth table for P, Q, R (Image: Wvbailey (talk), CC BY-SA 3.0, via Wikimedia Commons)