Mathematical logic is a branch of mathematics that deals with formal systems, reasoning, and the principles of valid inference. It provides the foundation for various fields, including computer science, artificial intelligence, and philosophy. The study of mathematical logic is essential for understanding algorithms, programming languages, and automated reasoning systems.

1. Propositional Logic

1.1 Definition

Propositional logic, also known as sentential logic, deals with propositions—statements that are either true or false. It uses logical operators to form complex expressions and evaluate their truth values.

1.2 Basic Elements

1. Propositions: Statements that can be either true (T) or false (F). Example:
2. "The sky is blue." (True)
3. "2 + 2 = 5." (False)
4. Logical Operators:
5. Negation (¬): Reverses the truth value. Example: ¬P (If P is true, then ¬P is false.)
6. Conjunction (∧): True if both propositions are true. Example: P ∧ Q ("It is raining AND it is cold.")
7. Disjunction (∨): True if at least one proposition is true. Example: P ∨ Q ("It is raining OR it is sunny.")
8. Implication (→): If the first proposition is true, then the second must also be true. Example: P → Q ("If it rains, then the ground is wet.")
9. Biconditional (↔): True if both propositions have the same truth value. Example: P ↔ Q ("It is snowing if and only if it is cold.")

1.3 Truth Table

Truth tables show how different logical operators affect the truth values of propositions.

1.4 Applications of Propositional Logic

1. Used in digital circuits (logic gates: AND, OR, NOT).
2. Helps in artificial intelligence for decision-making.
3. Used in programming languages for logical expressions.

2. Predicate Logic

2.1 Definition

Predicate logic (also called first-order logic) extends propositional logic by introducing variables, quantifiers, and predicates. This allows for more complex expressions involving multiple objects.

2.2 Basic Elements

1. Predicates: Statements containing variables, which become propositions when specific values are assigned. Example:
2. "x is a prime number." → P(x)
3. "y is greater than 10." → Q(y)
4. Quantifiers:
5. Universal Quantifier (∀): Denotes that a statement is true for all elements in a domain. Example: ∀x P(x) ("For all x, x is a prime number.")
6. Existential Quantifier (∃): Denotes that a statement is true for at least one element in a domain. Example: ∃y Q(y) ("There exists a y such that y is greater than 10.")

2.3 Example Statements

1. Using Universal Quantifier:
2. "All humans are mortal."
3. ∀x (Human(x) → Mortal(x))
4. Using Existential Quantifier:
5. "There exists a student who scored above 90%."
6. ∃x (Student(x) ∧ Score(x) > 90)

2.4 Applications of Predicate Logic

1. Used in artificial intelligence for knowledge representation.
2. Forms the basis for database query languages like SQL.
3. Helps in automated theorem proving.

3. Propositional Equivalences

A propositional equivalence refers to two logical statements that have the same truth value under all possible interpretations. Propositional logic consists of statements that can be either true or false.

Types of Propositional Equivalences:

1. Logical Equivalence: Two propositions p and q are logically equivalent if they always have the same truth value.
2. Denoted as p ≡ q or p ⇔ q.
3. Example: ¬ (¬ p) ≡ p (Double Negation Law).
4. Tautology: A statement that is always true regardless of the truth values of its components.
5. Example: p ∨ ¬p (Law of Excluded Middle).
6. Contradiction: A statement that is always false.
7. Example: p ∧ ¬p (Contradiction Law).
8. Contingency: A statement that is neither always true nor always false.

Important Logical Equivalences:

1. Identity Laws: p ∧ T≡ p , p ∨ F≡ p.
2. Domination Laws: p ∨ T ≡ T , p ∧ F≡ F.
3. Idempotent Laws: p ∨ p ≡ p , p ∧ p ≡ p.
4. De Morgan’s Laws:
5. ¬(p ∨ q) ≡ ¬p ∧ ¬q.
6. ¬(p ∧ q) ≡ ¬p ∨ ¬q.
7. Distributive Laws:
8. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
9. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).

4. Normal Forms

A normal form is a way of writing logical expressions in a standardized structure. Two commonly used normal forms are:

1. Conjunctive Normal Form (CNF):
2. A logical expression is in CNF if it is a conjunction (∧) of disjunctions (∨) of literals.
3. Example: (p ∨ q) ∧ (¬p ∨ r).
4. Disjunctive Normal Form (DNF):
5. A logical expression is in DNF if it is a disjunction (∨\vee∨) of conjunctions (∧\wedge∧) of literals.
6. Example: (p ∧ q) ∨ (¬p ∧ r).
7. Conversion to Normal Forms:
8. Use De Morgan’s Laws and distribution rules to transform a given logical statement into CNF or DNF.
9. CNF is widely used in Boolean satisfiability problems (SAT Solvers).

5. Predicates and Quantifiers

1. Predicates:
2. A predicate is a function that takes variables and returns a truth value (true or false).
3. Example: P(x) where P(x) could be “x is an even number.”
4. If x=2, P(2) is true; if x=3, P(3) is false.
5. Quantifiers:
6. Quantifiers specify how predicates apply to a range of values. The two main types are:
7. Universal Quantifier (∀): Expresses that a predicate holds for all values in a given domain.
8. Example: ∀x P(x) means “For all x, P(x) is true.”
9. Example: “All humans are mortal” is written as: ∀x (Human(x)⇒Mortal(x))
10. Existential Quantifier (∃): Expresses that there is at least one value in the domain for which the predicate is true.
11. Example: ∃x P(x)means “There exists an x such that P(x) is true.”
12. Example: “Some numbers are even” is written as: ∃x Even(x)
13. Negation of Quantifiers:
14. Using De Morgan’s Laws, we can negate quantifiers:
15. ¬∀x P(x)≡∃x ¬P(x)
16. ¬∃x P(x)≡∀x ¬P(x)

6. Nested Quantifiers

Sometimes, we use multiple quantifiers in a single statement. These are called nested quantifiers.

Examples of Nested Quantifiers:

1. Order Matters:
2. ∀x ∃y P(x,y) means “For every x, there exists some y such that P(x,y) is true.”
3. ∃y ∀x P(x,y) means “There exists some y such that for all x, P(x,y) is true.”
4. These two statements do not mean the same thing.
5. Example:
6. “Every student has a favorite subject.”
7. ∀x ∃y FavoriteSubject(x,y)
8. “There is one subject that all students like.”
9. ∃y ∀x FavoriteSubject(x,y)

7. Rules of Inference

Rules of inference are used to derive conclusions logically from premises. They form the foundation of mathematical proofs and logical reasoning.

Common Rules of Inference:

1. Modus Ponens:
2. If p⇒q is true and p is true, then q is true.
3. Example:
4. “If it rains, the ground gets wet.”
5. “It is raining.”
6. Conclusion: “The ground is wet.”
7. Modus Tollens:
8. If p⇒q is true and q is false, then p is false.
9. Example:
10. “If it rains, the ground gets wet.”
11. “The ground is not wet.”
12. Conclusion: “It did not rain.”
13. Hypothetical Syllogism:
14. If p⇒q and q⇒r, then p⇒r.
15. Disjunctive Syllogism:
16. If p∨q is true and ¬p is true, then q is true.
17. Universal Instantiation:
18. From ∀x P(x), we can conclude P(a) for a specific a.