Lecture Notes: Pridicate Logic

1. Introduction

Statements involving variables (e.g., "x > 10", "Book y is sold out") are neither true nor false until the variable is specified. These are called propositional functions or predicates.

• Structure:
  • : The variable (subject).
  • : The predicate (property the subject may have).
• Domain of Discourse (): The set of valid values for the variable .
• Definition: is a propositional function with respect to if for each , is a proposition (i.e., has a truth value).

Example

Let denote " is a positive number" and denote " ".

• is True.
• is False.
• is True.

2. Quantification

Quantification creates a proposition from a propositional function by specifying the extent to which the predicate applies to the domain.

2.1 Universal Quantifier ()

• Definition: The statement "for every , " is a universally quantified statement.
• Notation:
• Reading: "For all ", "For every ".
• Truth Value:
  • True: If is true for every in the domain.
  • False: If there is at least one in the domain for which is false.
• Counterexample: An element for which is false is called a counterexample. It is used to disprove a universal quantification.

Example:
Let be .
is True for all real numbers.

2.2 Existential Quantifier ()

• Definition: The statement "there exists , " is an existentially quantified statement.
• Notation:
• Reading: "There exists an ", "For some ", "There is an ".
• Truth Value:
  • True: If there is at least one element in the domain such that is true.
  • False: If is false for every in the domain.

Example:
Let be for real numbers.
is True (e.g., ).

3. Negation and De Morgan's Laws

Negating quantified statements involves switching the quantifier and negating the predicate.

Laws

1. Negation of Universal:
   
   Meaning: "It is not the case that for all , " is equivalent to "There exists an such that not ".

2. Negation of Existential:
   
   Meaning: "It is not the case that there exists an , " is equivalent to "For all , not ".

Examples

• Statement: "All Malaysians like teh tarik" ().
  • Negation: "At least one Malaysian does not like teh tarik" ().
• Statement: "There is an honest politician" ().
  • Negation: "All politicians are not honest" ().

4. Nested Quantifiers

When a predicate has more than one variable (e.g., ), multiple quantifiers are needed.

• Order Matters: The order of quantifiers is crucial if they are of different types.
  
• Same Type: If quantifiers are the same, order does not change the meaning.
  

Example:
Let be " multiplied by ".

• : True (let ).
• : True (for any , we can find ).

5. Rules of Inference

These rules allow for the derivation of conclusions from premises in predicate logic.

5.1 Universal Instantiation

If is true, then is true for any specific element in the domain.

5.2 Universal Generalization

If is true for an arbitrary element in the domain, then is true.

5.3 Existential Instantiation

If is true, there is some element (unknown but specific) in the domain for which is true.

5.4 Existential Generalization

If is true for a specific element , then is true.

Example Derivation

Premises:

1. (All M are P)
2. (Some M are C)

Conclusion:
(Some P are C)

Step-by-Step Proof:

1. (Existential Instantiation from 2)
2. (Simplification from 1)
3. (Universal Instantiation from 1)
4. (Modus Ponens from 2, 3)
5. (Simplification from 1)
6. (Conjunction from 4, 5)
7. (Existential Generalization from 6)