Logic: propositions, AND/OR/NOT, implication, truth tables, quantifiers and their negation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is |A × B| if |A| = 3 and |B| = 5? from Lesson 0.2.2
2. Why can a relation not contain the same tuple twice? from Lesson 0.2.2
3. What does logical data independence protect? from Lesson 0.1.3

1 · The Hook

"Find students who are in CS and have CGPA above 8." "Find students who have taken every CS course." "Find students who have not taken any course." Every database question is a logical condition. GATE's hardest query questions (division, relational calculus, NOT EXISTS in SQL) are really questions about "for all" and "there exists". Get the logic right here and those become routine.

2 · Predict First

"Every student passed" is false. Which of these must then be true: (a) every student failed; (b) at least one student did not pass; (c) no student passed?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

(b). The opposite of "every student passed" is "some student did not pass". It does not mean everyone failed. This rule, ¬(for all x, P) = (there exists x with ¬P), is the key to "for all" queries.

Propositions and connectives

A proposition is a statement that is either true (T) or false (F): "Asha is in CS".

• ∧ is true only when both are true. ∨ is true when at least one is true.
• Implication p → q is false only when p is true and q is false. When p is false, p → q is true ("vacuously"). Key identity: p → q ≡ ¬p ∨ q.
• ≡ means "always has the same truth value".

De Morgan's laws

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q
• ¬¬p ≡ p, and ¬(p → q) ≡ p ∧ ¬q.

Predicates and quantifiers

A predicate P(x) is a statement about x that becomes true or false once x is chosen: P(x) = "x is in CS".

• ∀x P(x) ("for all x, P(x)"): true if P is true for every x in the domain.
• ∃x P(x) ("there exists x such that P(x)"): true if P is true for at least one x.

Over an empty domain, ∀x P(x) is true (nothing to check) and ∃x P(x) is false (nothing to find).

Negating quantifiers

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

The trick behind every "for all" query: ∀x P(x) ≡ ¬∃x ¬P(x). "Asha has taken every CS course" = "there is no CS course that Asha has not taken". Databases find "there exists" easily, so "for all" is computed as "not exists … not". Watch for this again in Lessons 3.1.5, 3.2.2 and 3.3.9.

Restricted quantifiers

"Every CS course is taken by Asha": ∀c (c is a CS course → Asha took c). The implication matters: for a non-CS course, the condition is vacuously true, so only CS courses are actually checked. "Some CS course is taken by Asha": ∃c (c is a CS course ∧ Asha took c). ∀ goes with →, ∃ goes with ∧.

4 · Visual

NEGATION LADDER (push ¬ inward, flip as you go)

  ¬ ∀x ( P(x) → Q(x) )
= ∃x ¬( P(x) → Q(x) )        ¬∀ becomes ∃¬
= ∃x ( P(x) ∧ ¬Q(x) )        ¬(p → q) = p ∧ ¬q

"Not every CS course is taken by Asha"
= "Some CS course is not taken by Asha"

5 · Worked Examples

Example 1 Easy

p = "Asha is in CS" (T), q = "Asha's CGPA > 9" (T), r = "Asha is in hostel" (F). Evaluate p ∧ r, p ∨ r, r → q, q → r.

Solution

p ∧ r = T ∧ F = F. p ∨ r = T. r → q: false premise → T. q → r: T → F = F.

Example 2 Medium

Write the negation of "Every student in CS has CGPA above 8" without a ¬ in front.

Solution

∀x (CS(x) → cgpa(x) > 8). Negation: ∃x (CS(x) ∧ cgpa(x) ≤ 8): "some CS student has CGPA at most 8".

Example 3 GATE

Domain: the college's courses. T(c) = "c is taught by Prof. Rao". The college has no course taught by Prof. Rao. What are the values of ∀c (T(c) → Hard(c)) and ∃c (T(c) ∧ Hard(c))?

Solution

For every course T(c) is false, so T(c) → Hard(c) is true for every c: the ∀ statement is true (vacuously). The ∃ statement needs some c with T(c) true: false. This is exactly why "students who took every course taught by Rao" returns all students when Rao teaches nothing (Lesson 3.1.5).

8 · Connect the Dots

Lesson 0.2.2 defined a relation as a set of tuples; this lesson gave the logic for describing which tuples we want. Last toolkit lesson next: counting combinations and overlaps, needed for counting keys, schedules and tree capacities later.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Implication

p → q is false exactly when:

1. (A) p is true and q is false
2. (B) p is false and q is true
3. (C) both are false
4. (D) both are true

Q2 · MCQ · 1 mark(s) — De Morgan

¬(p ∨ q) is equivalent to:

1. (A) ¬p ∨ ¬q
2. (B) ¬p ∧ ¬q
3. (C) ¬p ∨ q
4. (D) p ∧ q

Q3 · MCQ · 2 mark(s) — Quantifiers

The negation of ∀x (P(x) → Q(x)) is:

1. (A) ∃x (P(x) ∧ ¬Q(x))
2. (B) ∀x (¬P(x) ∧ Q(x))
3. (C) ∃x (¬P(x) → Q(x))
4. (D) ∀x (P(x) → ¬Q(x))

Q4 · MSQ · 2 mark(s) — Empty domain

The domain is empty. Which are true?

1. (A) ∃x P(x)
2. (B) ∀x P(x)
3. (C) ∀x ¬P(x)
4. (D) ¬∃x P(x)

Q5 · MCQ · 1 mark(s) — Equivalence

p → q is logically equivalent to:

1. (A) q → p
2. (B) ¬q ∨ p
3. (C) p ∧ ¬q
4. (D) ¬p ∨ q

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

proposition¬ ∧ ∨implication →truth table≡ (equivalent)De Morgan's lawspredicate∀ (for all)∃ (there exists)quantifier negationvacuous truth∀x P ≡ ¬∃x ¬P