```html

Mathematical Logic

Mathematical logic is the foundation of many areas in computer science, including algorithm design, database theory, artificial intelligence, and circuit design. It provides a formal system for reasoning about propositions and statements.

Propositional Logic

Propositional logic, also known as sentential logic, deals with propositions and logical connectives. A proposition is a declarative statement that is either true or false.

Propositions and Truth Values

A proposition is a simple statement. For example, "The sky is blue" is a proposition. Its truth value is true. "2 + 2 = 5" is also a proposition, but its truth value is false.

We often use letters like P, Q, R to represent propositions.

Logical Connectives

Logical connectives are used to combine propositions to form more complex statements. The common connectives are:

  • Negation (¬ or ~): Reverses the truth value of a proposition. If P is true, ¬P is false, and vice versa.
  • Conjunction (∧ or AND): True only if both propositions are true. P ∧ Q is true if and only if P is true and Q is true.
  • Disjunction (∨ or OR): True if at least one of the propositions is true. P ∨ Q is true if P is true, or Q is true, or both are true.
  • Implication (→ or ⇒): "If P, then Q". P → Q is false only when P is true and Q is false. In all other cases, it is true.
  • Biconditional (↔ or ⇔): "P if and only if Q". P ↔ Q is true when P and Q have the same truth value (both true or both false).

Truth Tables

Truth tables are used to systematically determine the truth value of a compound proposition for all possible combinations of truth values of its constituent propositions. Let's look at the truth tables for the common connectives:

P Q ¬P P ∧ Q P ∨ Q P → Q P ↔ Q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T

Tautologies, Contradictions, and Contingencies

  • Tautology: A compound proposition that is always true, regardless of the truth values of its individual propositions.
  • Contradiction: A compound proposition that is always false.
  • Contingency: A compound proposition that is neither a tautology nor a contradiction; its truth value depends on the truth values of its individual propositions.

Propositional Equivalences

Two compound propositions are logically equivalent if they have the same truth value for all possible truth value assignments to their propositional variables. We denote logical equivalence by ≡.

Understanding equivalences allows us to simplify complex logical statements and to substitute equivalent expressions. Here are some fundamental equivalences:

Equivalence Name Formula
Commutative Laws (P ∨ Q) ≡ (Q ∨ P)
(P ∧ Q) ≡ (Q ∧ P)
Associative Laws (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
Distributive Laws P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Identity Laws P ∨ F ≡ P
P ∧ T ≡ P
Domination Laws P ∨ T ≡ T
P ∧ F ≡ F
Idempotent Laws P ∨ P ≡ P
P ∧ P ≡ P
Double Negation Law ¬(¬P) ≡ P
Negation Laws P ∨ ¬P ≡ T
P ∧ ¬P ≡ F
Implication Law P → Q ≡ ¬P ∨ Q
Biconditional Law P ↔ Q ≡ (P → Q) ∧ (Q → P)
De Morgan's Laws ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Absorption Laws P ∨ (P ∧ Q) ≡ P
P ∧ (P ∨ Q) ≡ P
Exportation Law (P ∧ Q) → R ≡ P → (Q → R)
Contrapositive P → Q ≡ ¬Q → ¬P

Example: Let's prove ¬(P ∨ Q) ≡ ¬P ∧ ¬Q using logical equivalences.

¬(P ∨ Q) ≡ ¬P ∧ ¬Q (De Morgan's Law)

This is a direct application of De Morgan's Law.

Example: Let's prove (P → Q) ∨ (P → R) ≡ P → (Q ∨ R).

  1. (P → Q) ∨ (P → R) ≡ (¬P ∨ Q) ∨ (¬P ∨ R) (Implication Law)
  2. ≡ ¬P ∨ Q ∨ ¬P ∨ R (Associative Law for ∨)
  3. ≡ ¬P ∨ ¬P ∨ Q ∨ R (Commutative and Associative Laws for ∨)
  4. ≡ ¬P ∨ Q ∨ R (Idempotent Law for ∨)
  5. ≡ ¬P ∨ (Q ∨ R) (Associative Law for ∨)
  6. ≡ P → (Q ∨ R) (Implication Law)
Shortcut: When simplifying complex logical expressions, try to apply De Morgan's Laws and the Implication Law (P → Q ≡ ¬P ∨ Q) first to convert implications into disjunctions and to push negations inwards. Then, use Commutative and Associative Laws to group terms, and Idempotent Laws to remove repetitions.

Normal Forms

Normal forms are standardized ways of writing logical expressions. The two most common normal forms are Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF).

Disjunctive Normal Form (DNF)

A propositional formula is in DNF if it is a disjunction of one or more conjunctions of literals, where a literal is a propositional variable or its negation.

Example: (P ∧ ¬Q) ∨ (¬P ∧ Q ∧ R)

Any propositional formula can be converted into an equivalent DNF. This is often done by constructing a truth table and then creating a formula that is true exactly when the original formula is true.

Conjunctive Normal Form (CNF)

A propositional formula is in CNF if it is a conjunction of one or more clauses, where each clause is a disjunction of literals.

Example: (P ∨ ¬Q) ∧ (¬P ∨ Q ∨ R)

Any propositional formula can be converted into an equivalent CNF. This is related to finding a formula that is false exactly when the original formula is false.

Conversion to CNF/DNF:

  1. Eliminate implications and biconditionals using equivalences like P → Q ≡ ¬P ∨ Q.
  2. Move negations inward using De Morgan's Laws until they only apply to propositional variables (literals).
  3. Apply distributive laws to achieve the desired form (CNF or DNF).

Example: Convert (P → Q) ∧ R to CNF.

  1. (¬P ∨ Q) ∧ R (Implication Law)
  2. This is already in CNF, as it's a conjunction of clauses: (¬P ∨ Q) and (R). The second clause (R) is a disjunction of one literal.

Example: Convert (P ∨ Q) → R to DNF.

  1. ¬(P ∨ Q) ∨ R (Implication Law)
  2. (¬P ∧ ¬Q) ∨ R (De Morgan's Law)
  3. This is in DNF. It's a disjunction of two conjunctions: (¬P ∧ ¬Q) and (R).
Key Point: CNF is particularly important for automated theorem proving and SAT solvers because many logical inference rules operate efficiently on clauses.

Predicate Logic (First-Order Logic)

Predicate logic extends propositional logic by introducing predicates, variables, and quantifiers. It allows us to reason about objects, their properties, and their relationships.

Predicates and Variables

A predicate is a property that applies to one or more objects. For example, "is a student" can be a predicate. We can write this as Student(x), where x is a variable representing an object.

Examples:

  • Likes(John, Mary) - John likes Mary.
  • IsEven(n) - n is an even number.
  • Greater(x, y) - x is greater than y.

In predicate logic, statements can involve variables. For instance, "x is a student" can be represented as Student(x).

Quantifiers

Quantifiers are used to specify the range or quantity of elements for which a predicate is true.

  • Universal Quantifier (∀): "For all" or "For every". ∀x P(x) means "P(x) is true for all values of x in the domain."
  • Existential Quantifier (∃): "There exists" or "For some". ∃x P(x) means "There is at least one value of x in the domain for which P(x) is true."

Translating English to Predicate Logic

Let's consider the domain of all people.

  • "Everyone is kind." → ∀x Kind(x)
  • "Someone is kind." → ∃x Kind(x)
  • "No one is kind." → ¬∃x Kind(x) (which is equivalent to ∀x ¬Kind(x))
  • "Not everyone is kind." → ¬∀x Kind(x) (which is equivalent to ∃x ¬Kind(x))

Let's consider the domain of all numbers.

  • "For every number x, x squared is non-negative." → ∀x (x^2 ≥ 0)
  • "There exists a number x such that x squared is 9." → ∃x (x^2 = 9)

Quantifiers and Connectives

Quantifiers are often used in conjunction with logical connectives.

  • ∀x (P(x) ∧ Q(x)) : For all x, P(x) is true AND Q(x) is true.
  • ∃x (P(x) ∨ Q(x)) : There exists an x such that P(x) is true OR Q(x) is true.
  • ∀x (P(x) → Q(x)) : For all x, IF P(x) is true, THEN Q(x) is true. (This is a common structure for implications.)
  • ∃x (P(x) ∧ Q(x)) : There exists an x such that P(x) is true AND Q(x) is true.

Important Note on Negation:

  • ¬∀x P(x) ≡ ∃x ¬P(x) (It is not true for all x that P(x) holds, means there exists an x for which P(x) does not hold.)
  • ¬∃x P(x) ≡ ∀x ¬P(x) (There does not exist an x for which P(x) holds, means for all x, P(x) does not hold.)
Mnemonic: Think of negating "all" (∀) as requiring only "one" (∃) exception. Think of negating "there exists" (∃) as requiring "none" (∀) to satisfy it.

Nested Quantifiers

Nested quantifiers involve multiple quantifiers in a statement. The order of quantifiers matters, especially when they are of different types.

Example 1: ∀x ∀y (x + y = y + x) (For all numbers x and y, x + y equals y + x. Commutative property of addition.)

Example 2: ∃x ∃y (x + y = 0) (There exists a number x and a number y such that their sum is 0. For instance, x=2, y=-2.)

Example 3: ∀x ∃y (x + y = 0) (For every number x, there exists a number y such that x + y = 0. This y is the additive inverse, -x.)

Example 4: ∃y ∀x (x + y = 0) (There exists a number y such that for all numbers x, x + y = 0. This statement is FALSE. There is no single y that works for ALL x. For x=1, y must be -1. For x=2, y must be -2. y cannot be both.)

Notice how the meaning changes drastically between Example 3 and Example 4.

Scope of Quantifiers

The scope of a quantifier is the part of the statement to which it applies. In ∀x P(x) ∧ Q(x), the scope of ∀x is P(x). In ∀x (P(x) ∧ Q(x)), the scope of ∀x is the entire expression P(x) ∧ Q(x).

A variable x is bound if it is within the scope of a quantifier ∀x or ∃x. A variable is free if it is not bound.

A statement with no free variables is a proposition, meaning it has a definite truth value.

Translating Nested Quantifiers

Let the domain be the set of all people.

  • "Every person likes someone." → ∀x ∃y Likes(x, y) (For every person x, there exists a person y that x likes.)
  • "Someone likes every person." → ∃y ∀x Likes(y, x) (There exists a person y such that for every person x, y likes x.)
  • "Everyone likes everyone." → ∀x ∀y Likes(x, y)
  • "Someone likes someone." → ∃x ∃y Likes(x, y)

Important Distinction:

  • ∀x ∃y P(x, y) does NOT mean ∃y ∀x P(x, y). The former means for each x, there is a y (which might depend on x). The latter means there is a single y that works for all x.
Common Pitfall: Confusing ∀x ∃y with ∃y ∀x. Remember that in ∀x ∃y, the 'y' can be different for each 'x'. In ∃y ∀x, the 'y' must be the same for all 'x'.

Rules of Inference

Rules of inference are valid argument forms that allow us to derive conclusions from premises. An argument is a sequence of statements, where the initial statements are premises and the final statement is the conclusion.

An argument is valid if whenever all the premises are true, the conclusion must also be true. We can use propositional logic to determine the validity of arguments.

Rules of Inference for Propositional Logic

Here are some common rules of inference:

Rule Name Premises Conclusion Description
Modus Ponens P → Q
P		 Q If P implies Q, and P is true, then Q must be true.
Modus Tollens P → Q
¬Q		 ¬P If P implies Q, and Q is false, then P must be false.
Hypothetical Syllogism P → Q
Q → R		 P → R If P implies Q, and Q implies R, then P implies R. (Chain rule)
Disjunctive Syllogism P ∨ Q
¬P		 Q If P or Q is true, and P is false, then Q must be true.
Addition P P ∨ Q If P is true, then P or Q is true (for any Q).
Simplification P ∧ Q P If P and Q are true, then P must be true.
Conjunction P
Q		 P ∧ Q If P is true and Q is true, then P and Q are true.
Resolution P ∨ Q
¬P ∨ R		 Q ∨ R A powerful rule used in automated reasoning.

Example using Modus Ponens:

Premise 1: If it is raining (P), then the ground is wet (Q). (P → Q)

Premise 2: It is raining (P).

Conclusion: Therefore, the ground is wet (Q).

Example using Modus Tollens:

Premise 1: If a number is divisible by 4 (P), then it is divisible by 2 (Q). (P → Q)

Premise 2: The number is not divisible by 2 (¬Q).

Conclusion: Therefore, the number is not divisible by 4 (¬P).

Rules of Inference for Predicate Logic

These rules extend the propositional rules to handle predicates and quantifiers.

Rule Name Premises Conclusion Conditions
Universal Instantiation ∀x P(x) P(c) c is any specific element in the domain.
Universal Generalization P(c) ∀x P(x) If P(c) is true for an arbitrary element c.
Existential Instantiation ∃x P(x) P(c) c is a specific element for which P(x) is true (but c is not known beforehand).
Existential Generalization P(c) ∃x P(x) If P(c) is true for some element c.

Using Predicate Logic Rules:

Consider the following argument:

Premise 1: All humans are mortal. (∀x (Human(x) → Mortal(x)))

Premise 2: Socrates is a human. (Human(Socrates))

Conclusion: Socrates is mortal. (Mortal(Socrates))

Proof:

  1. ∀x (Human(x) → Mortal(x)) (Premise 1)
  2. Human(Socrates) (Premise 2)
  3. Human(Socrates) → Mortal(Socrates) (Universal Instantiation from 1)
  4. Mortal(Socrates) (Modus Ponens from 2 and 3)

Consider this argument:

Premise 1: Some students are intelligent. (∃x (Student(x) ∧ Intelligent(x)))

Premise 2: All intelligent people are wealthy. (∀x (Intelligent(x) → Wealthy(x)))

Conclusion: Some students are wealthy. (∃x (Student(x) ∧ Wealthy(x)))

Proof:

  1. ∃x (Student(x) ∧ Intelligent(x)) (Premise 1)
  2. Student(a) ∧ Intelligent(a) (Existential Instantiation from 1, for some student 'a')
  3. Student(a) (Simplification from 2)
  4. Intelligent(a) (Simplification from 2)
  5. ∀x (Intelligent(x) → Wealthy(x)) (Premise 2)
  6. Intelligent(a) → Wealthy(a) (Universal Instantiation from 5)
  7. Wealthy(a) (Modus Ponens from 4 and 6)
  8. Student(a) ∧ Wealthy(a) (Conjunction from 3 and 7)
  9. ∃x (Student(x) ∧ Wealthy(x)) (Existential Generalization from 8)
Exam Tip: For predicate logic proofs, first apply Universal Instantiation to remove ∀ and Existential Instantiation to introduce a specific instance (often using a new variable name like 'a'). Then, use propositional rules of inference. Finally, use Universal Generalization or Existential Generalization to reintroduce quantifiers if needed to match the conclusion.
```
All E-Books
Online Test Mathematical logic: propositional and predicate logic, propositional equivalences, normal forms, predicates and quantifiers, nested quantifiers, rules of inference. One Line Questions Mathematical logic: propositional and predicate logic, propositional equivalences, normal forms, predicates and quantifiers, nested quantifiers, rules of inference. Question Bank Mathematical logic: propositional and predicate logic, propositional equivalences, normal forms, predicates and quantifiers, nested quantifiers, rules of inference.