(Complete Conceptual Notes)

---

PART A — MATHEMATICAL LOGIC

---

1. PROPOSITIONAL LOGIC

1.1 What is a Proposition? 

A proposition is a declarative sentence that expresses a fact and has a definite truth value:
either True (T) or False (F), but never both at the same time.

✔ Examples of Propositions (Meaningful Facts)

• “7 is a prime number.” → True

• “The Earth has two moons.” → False

✘ Not Propositions (No truth value / not a statement of fact)

• “Shut the door.” (command)

• “Where are you?” (question)

• “x is greater than 10.” (truth depends on x → open sentence)

Why important?
Because logic operates only on propositions with fixed truth values.

---

1.2 Propositional Variables

We use letters like p, q, r to represent propositions.

Example:

• Let p = “It is raining.”

• Let q = “The ground is wet.”

---

2. LOGICAL CONNECTIVES WITH STATEMENTS

Connectives combine propositions to form compound statements.

---

2.1 Negation (¬p)

Statement Form:

“NOT p” means that whatever p asserts, the negation asserts the opposite.

Example:

• p = “The sky is blue.”

• ¬p = “The sky is not blue.”

Truth rule:

• If p is true → ¬p is false

• If p is false → ¬p is true

---

2.2 Conjunction (p ∧ q)

Statement Form:

“p AND q” means both statements must be true simultaneously.

Example:

• p: “The power is on.”

• q: “The fan is running.”

• p ∧ q: “The power is on and the fan is running.”

---

2.3 Disjunction (p ∨ q)

Statement Form:

“p OR q” means at least one of the two statements must be true.

Example:

• p: “I will study.”

• q: “I will watch a movie.”

• p ∨ q: “I will study or watch a movie (or both).”

---

2.4 Implication (p → q)

Statement Form:

“If p is true, then q must also be true.”

Example:

• p: “It rains.”

• q: “The ground gets wet.”

• p → q: “If it rains, then the ground gets wet.”

Exception:
If it does NOT rain, the statement is considered true regardless of the ground’s condition.

---

2.5 Biconditional (p ↔ q)

Statement Form:

“p is true if and only if q is true.”

Example:

• p: “You pass the course.”

• q: “You score ≥ 40.”

• p ↔ q: “You pass the course if and only if you score ≥ 40.”

True when both p and q have the same truth value.

---

3. TRUTH TABLES (Purpose + Use)

Truth tables allow us to compute the truth value of compound propositions under all possible combinations.

---

4. PROPOSITIONAL EQUIVALENCES 

Logical equivalences indicate when two compound statements always have the same truth value.

---

4.1 Double Negation

Statement:

“Saying ‘NOT NOT p’ means the same as saying p.”

Symbolically:
¬(¬p) ≡ p

---

4.2 De Morgan’s Laws 

These describe how negation interacts with AND/OR.

Statements:

• “The negation of ‘p AND q’ is the same as ‘NOT p OR NOT q’.”

• “The negation of ‘p OR q’ is the same as ‘NOT p AND NOT q’.”

---

4.3 Implication Law

Statement:

“‘If p then q’ is equivalent to saying ‘Either p is false OR q is true.’”

p → q ≡ ¬p ∨ q

This is core to CNF/DNF.

---

4.4 Contrapositive (Key Logical Principle)

Statement:

“‘If p then q’ is logically equivalent to ‘If NOT q then NOT p’.”

---

4.5 Biconditional Law

Statement:

“‘p if and only if q’ means both ‘if p then q’ AND ‘if q then p’ must be true.”

5. NORMAL FORMS (CNF, DNF)

5.1 Disjunctive Normal Form (DNF)

Statement:

A formula is in DNF when it is expressed as an OR of AND terms.

Example Statement:
“p AND q is true OR p is false AND r is true.”

Symbolic:
(p ∧ q) ∨ (¬p ∧ r)

---

5.2 Conjunctive Normal Form (CNF)

Statement:

A formula is in CNF when it is expressed as an AND of OR terms.

Example Statement:
“Either p or q is true AND either p or r is true.”

Symbolic:
(p ∨ q) ∧ (p ∨ r)

---

---

PART B — PREDICATE LOGIC

---

6. PREDICATES 

A predicate is an expression involving variables that becomes a proposition when specific values are substituted.

Example:
P(x): “x is divisible by 3.”
— P(6) is True
— P(7) is False

---

 7. QUANTIFIERS 

---

7.1 Universal Quantifier (∀)

Statement Meaning:

“∀x P(x)” means “For every x, P(x) is true.”

Example Statement:
“Every natural number is greater than or equal to 0.”

---

7.2 Existential Quantifier (∃)

Statement Meaning:

“∃x P(x)” means “There exists at least one x such that P(x) is true.”

Example Statement:
“There exists a number divisible by 6.”

---

8. NESTED QUANTIFIERS

Example 1

∀x ∃y P(x,y)

Statement Meaning:

“For every x, there exists a y such that P(x,y) holds.”

Example in math:
“For every number x, there is a number y greater than x.”

---

Example 2

∃y ∀x P(x,y)

Statement Meaning:

“There exists a single y such that for every x, P(x,y) holds.”

Example:
“There is one number y greater than all numbers x.”
→ False (no largest integer)

---

9. NEGATION OF QUANTIFIERS (WITH EXPLANATORY STATEMENTS)

Universal to Existential

¬∀x P(x)

Statement:

“It is NOT true that P(x) holds for all x”
⟹ “There exists at least one x for which P(x) does not hold.”

---

Existential to Universal

¬∃x P(x)

Statement:

“It is NOT true that there exists an x with P(x)”
⟹ “For every x, P(x) is false.”

---

10. RULES OF INFERENCE (WITH NATURAL LANGUAGE MEANINGS)

---

10.1 Modus Ponens

p, and p → q

Statement Meaning:

“If p is true, and p implies q, then q must be true.”

---

10.2 Modus Tollens

¬q, and p → q

Statement Meaning:

“If q is false, and p implies q, then p must be false.”

---

10.3 Hypothetical Syllogism

p → q, q → r

Statement Meaning:

“If p implies q, and q implies r, then p implies r.”

---

10.4 Simplification

p ∧ q
→ p

Statement:

“If both p and q are true, then p is true.”

---

10.5 Addition

p
→ p ∨ q

Statement:

“If p is true, then ‘p OR q’ is automatically true.”

---

10.6 Conjunction

p, q
→ p ∧ q

Statement:

“If p is true and q is true, then ‘p AND q’ is true.”