Mathematical Logic: Propositional and Predicate Logic

Mathematical logic is the foundation upon which much of computer science is built. It provides a formal system for reasoning about propositions (statements that are either true or false) and the relationships between them. Understanding logical structures is crucial for designing algorithms, verifying software, and building artificial intelligence systems. We will explore two main branches: propositional logic and predicate logic.

Propositional Logic

Propositional logic deals with propositions and logical connectives. A proposition is a declarative sentence that is either true or false.

Basic Propositions

Simple statements are represented by propositional variables, typically denoted by letters like p, q, r, etc.

• Example: 'p' can represent "The sky is blue."
• Example: 'q' can represent "It is raining."

Logical Connectives

These are operators used to combine or modify propositions. The truth value of a compound proposition depends on the truth values of its components and the connectives used.

Negation (¬ or ~)

The negation of a proposition p, denoted by ¬p, is true when p is false and false when p is true.

• Example: If p is "It is raining," then ¬p is "It is not raining."

Truth Table for Negation:

p	¬p
T	F
F	T

Conjunction (∧ or AND)

The conjunction of propositions p and q, denoted by p ∧ q, is true if and only if both p and q are true.

• Example: If p is "The sun is shining" and q is "The birds are singing," then p ∧ q is "The sun is shining and the birds are singing."

Truth Table for Conjunction:

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction (∨ or OR)

The disjunction of propositions p and q, denoted by p ∨ q, is true if and only if at least one of p or q (or both) is true. This is an inclusive OR.

• Example: If p is "You have a pen" and q is "You have a pencil," then p ∨ q is "You have a pen or you have a pencil (or both)."

Truth Table for Disjunction:

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

Implication (→ or IF...THEN)

The implication p → q is false if and only if p is true and q is false. In all other cases, it is true. p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).

• Example: If p is "It is raining" and q is "The ground is wet," then p → q is "If it is raining, then the ground is wet."
• This statement is only false when it *is* raining (p is T) but the ground is *not* wet (q is F). If it's not raining (p is F), the statement is considered true, regardless of whether the ground is wet or not.

Truth Table for Implication:

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional (↔ or IF AND ONLY IF)

The biconditional p ↔ q is true if and only if p and q have the same truth value. It is equivalent to (p → q) ∧ (q → p).

• Example: If p is "You will pass the exam" and q is "You study hard," then p ↔ q is "You will pass the exam if and only if you study hard."

Truth Table for Biconditional:

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

Predicate Logic

Predicate logic, also known as first-order logic, extends propositional logic by introducing predicates and quantifiers. This allows us to reason about objects and their properties, and to make statements about collections of objects.

Predicates

A predicate is a statement that contains variables. When values are assigned to these variables, the predicate becomes a proposition. Predicates represent properties of objects or relationships between objects.

• Example: P(x): "x is greater than 3."
• If we assign x = 5, P(5) is "5 is greater than 3," which is True.
• If we assign x = 2, P(2) is "2 is greater than 3," which is False.
• Example: Q(x, y): "x is the capital of y."
• Q(Delhi, India) is "Delhi is the capital of India," which is True.
• Q(Mumbai, India) is "Mumbai is the capital of India," which is False.

Quantifiers

Quantifiers are used to specify the quantity of elements for which a predicate is true. The two main quantifiers are the universal quantifier and the existential quantifier.

Universal Quantifier (∀)

The universal quantifier, denoted by ∀, means "for all" or "for every." A statement of the form ∀x P(x) asserts that P(x) is true for every element x in the domain of discourse.

• Example: ∀x (x > 0 → x > -1)
• This statement means: "For every number x, if x is greater than 0, then x is greater than -1." This is true for all real numbers.

Existential Quantifier (∃)

The existential quantifier, denoted by ∃, means "there exists" or "for some." A statement of the form ∃x P(x) asserts that there is at least one element x in the domain of discourse for which P(x) is true.

• Example: ∃x (x² = 4)
• This statement means: "There exists a number x such that x squared is equal to 4." This is true because x = 2 (or x = -2) satisfies the condition.

Nested Quantifiers

It is possible to have statements with multiple quantifiers. The order of quantifiers can significantly change the meaning of the statement.

• Example 1: ∀x ∃y (x + y = 0)
• Meaning: "For every number x, there exists a number y such that x + y = 0." (This is true; y is -x).
• Example 2: ∃y ∀x (x + y = 0)
• Meaning: "There exists a number y such that for every number x, x + y = 0." (This is false. If y were 0, then x + 0 = 0 would only be true for x=0. If y were any other number, it wouldn't work for all x).

The domain of discourse is important when interpreting nested quantifiers. For instance, if the domain is positive integers, the truth values of these statements might change.

Translating English Sentences into Predicate Logic

This is a key skill. We need to identify propositions, predicates, variables, quantifiers, and connectives.

• "Every student has a student ID."
• Let S(x) be "x is a student."
• Let I(x) be "x has a student ID."
• Domain: All people.
• Translation: ∀x (S(x) → I(x))
• Alternatively, if the domain is restricted to students: ∀x I(x)
• "There is a student who has a laptop."
• Let S(x) be "x is a student."
• Let L(x) be "x has a laptop."
• Domain: All people.
• Translation: ∃x (S(x) ∧ L(x))

Negating Quantified Statements

The negation of a universally quantified statement is an existentially quantified statement, and vice versa.

• ¬(∀x P(x)) is equivalent to ∃x ¬P(x)
• ¬(∃x P(x)) is equivalent to ∀x ¬P(x)

Example:

• Statement: "All dogs are friendly." (∀x (D(x) → F(x)))
• Negation: "There exists a dog that is not friendly." (∃x (D(x) ∧ ¬F(x)))

Example:

• Statement: "There is a number that is even." (∃x E(x))
• Negation: "All numbers are not even (i.e., all numbers are odd)." (∀x ¬E(x))

Propositional Equivalences

In logic, two propositions are considered equivalent if they have the same truth value in all possible cases. This means their truth tables are identical. Propositional equivalences are fundamental for simplifying logical expressions and proving theorems.

Tautologies and Contradictions

A tautology is a proposition that is always true, regardless of the truth values of its components. A contradiction is a proposition that is always false.

• Example Tautology: p ∨ ¬p (Law of the Excluded Middle)
• Example Contradiction: p ∧ ¬p

Key Equivalences

Here are some of the most important propositional equivalences. We'll use 'p', 'q', and 'r' as propositional variables, and 'T' for a tautology and 'F' for a contradiction.

Commutative Laws

• (p ∧ q) ≡ (q ∧ p)
• (p ∨ q) ≡ (q ∨ p)

The order of operands doesn't matter for AND and OR.

Associative Laws

• (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
• (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

The grouping of operands doesn't matter for AND and OR when the operator is the same.

Distributive Laws

• p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

These are similar to the distributive property in algebra (e.g., a(b+c) = ab + ac).

Identity Laws

• p ∧ T ≡ p
• p ∨ F ≡ p

ANDing with True or ORing with False doesn't change the proposition.

Idempotent Laws

• p ∧ p ≡ p
• p ∨ p ≡ p

ANDing or ORing a proposition with itself results in the same proposition.

Negation Laws

• p ∨ ¬p ≡ T
• p ∧ ¬p ≡ F

A proposition and its negation are opposites; one must be true, the other false.

Double Negation Law

• ¬(¬p) ≡ p

Negating a proposition twice returns the original proposition.

Universal Laws (or Domination Laws)

• p ∨ T ≡ T
• p ∧ F ≡ F

ORing with True always results in True. ANDing with False always results in False.

Absorption Laws

• p ∨ (p ∧ q) ≡ p
• p ∧ (p ∨ q) ≡ p

These show how a proposition can be "absorbed" into an expression involving itself.

De Morgan's Laws

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q

These laws are crucial for negating conjunctions and disjunctions. They state that the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations.

Implication Law

• p → q ≡ ¬p ∨ q

An implication can be rewritten using negation and disjunction. This is very useful for proofs and manipulations.

Biconditional Law

• p ↔ q ≡ (p → q) ∧ (q → p)
• p ↔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p)
• p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)

A biconditional is true when both sides have the same truth value.

Contrapositive Law

• p → q ≡ ¬q → ¬p

An implication is logically equivalent to its contrapositive. This is extremely useful in proofs.

Contradiction Law for Implication

• p → q ≡ ¬p ∨ q
• (p ∧ ¬p) → q ≡ T
• p → (q ∧ ¬q) ≡ ¬p

Using Equivalences to Prove Other Equivalences

We can use a chain of established equivalences to show that two complex propositions are equivalent. Start with one side and transform it step-by-step until you reach the other side.

Example: Show that ¬(p → q) ≡ p ∧ ¬q

1. ¬(p → q)
2. ≡ ¬(¬p ∨ q) (Implication Law)
3. ≡ ¬(¬p) ∧ ¬q (De Morgan's Law)
4. ≡ p ∧ ¬q (Double Negation Law)

This proves the equivalence.

Equivalence with respect to Predicates

For predicate logic, we have similar equivalences involving quantifiers.

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

These are fundamental for negating quantified statements.

Normal Forms

In logic and computer science, normal forms are standardized ways of writing logical expressions. They are useful for simplifying expressions, comparing them, and for use in algorithms like those for circuit design or automated theorem proving. The most common normal forms are Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF).

Disjunctive Normal Form (DNF)

A proposition is in Disjunctive Normal Form (DNF) if it is a disjunction (OR) of one or more conjunctions (AND) of literals. A literal is either a propositional variable or its negation.

General Structure of DNF: (Literal₁ ∧ Literal₂ ∧ ...) ∨ (Literal_a ∧ Literal_b ∧ ...) ∨ ...

• Example: (p ∧ ¬q) ∨ (¬p ∧ q ∧ r) ∨ (p)
• Example: p ∧ q (This is a single conjunction, which is a valid DNF)
• Example: p ∨ q (This is a disjunction of two conjunctions, each with one literal)

How to Convert to DNF

The general method to convert any propositional formula into DNF involves using truth tables or a series of logical equivalences.

Method using Truth Tables:

1. Construct the truth table for the given propositional formula.
2. Identify the rows where the formula evaluates to True (T).
3. For each such row, create a conjunction of literals. Include a variable 'x' if it is True in that row, and '¬x' if it is False in that row.
4. The DNF is the disjunction (OR) of all these conjunctions.

Example: Convert p → q into DNF.

Truth Table for p → q:

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

The formula is True in rows 1, 3, and 4.

• Row 1 (T, T): p ∧ q
• Row 3 (F, T): ¬p ∧ q
• Row 4 (F, F): ¬p ∧ ¬q

The DNF is: (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q).

We can simplify this using equivalences:

1. (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)
2. ≡ q ∧ (p ∨ ¬p) ∨ (¬p ∧ ¬q) (Distributive Law, factoring q from first two terms)
3. ≡ q ∧ T ∨ (¬p ∧ ¬q) (Negation Law: p ∨ ¬p ≡ T)
4. ≡ q ∨ (¬p ∧ ¬q) (Identity Law: q ∧ T ≡ q)

So, a simplified DNF is q ∨ (¬p ∧ ¬q). The first form derived directly from the truth table is called the "full" or "canonical" DNF.

Conjunctive Normal Form (CNF)

A proposition is in Conjunctive Normal Form (CNF) if it is a conjunction (AND) of one or more disjunctions (OR) of literals.

General Structure of CNF: (Literal₁ ∨ Literal₂ ∨ ...) ∧ (Literal_a ∨ Literal_b ∨ ...) ∧ ...

• Example: (p ∨ ¬q) ∧ (¬p ∨ q ∨ r) ∧ (p)
• Example: p ∧ q (This is a conjunction of two disjunctions, each with one literal)
• Example: p ∨ q (This is a single disjunction, which is a valid CNF)

How to Convert to CNF

Similar to DNF, conversion to CNF can be done using truth tables or logical equivalences.

Method using Truth Tables:

1. Construct the truth table for the given propositional formula.
2. Identify the rows where the formula evaluates to False (F).
3. For each such row, create a disjunction of literals. Include '¬x' if 'x' is True in that row, and 'x' if 'x' is False in that row. (Essentially, negate the truth value of each variable for that row).
4. The CNF is the conjunction (AND) of all these disjunctions.

Example: Convert p → q into CNF.

Using the same truth table for p → q:

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

The formula is False only in row 2.

• Row 2 (T, F): The formula is F. We need a disjunction that is F here. This happens if both literals are F. So, we use ¬p (since p is T) and q (since q is F). The disjunction is ¬p ∨ q.

The CNF is: (¬p ∨ q).

This matches the implication law p → q ≡ ¬p ∨ q.

Conversion using Equivalences

To convert an arbitrary formula to CNF or DNF using only equivalences, you typically follow these steps:

1. Eliminate implications and biconditionals using p → q ≡ ¬p ∨ q and p ↔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p).
2. Move negations inward using De Morgan's laws and the double negation law.
3. Distribute OR over AND (or AND over OR) to achieve the desired form.

Example: Convert p → (q ∨ r) to CNF.

1. p → (q ∨ r)
2. ≡ ¬p ∨ (q ∨ r) (Implication Law)

This is already in CNF because it's a disjunction of literals (¬p, q, r).

Example: Convert (p ∧ q) → r to CNF.

1. (p ∧ q) → r
2. ≡ ¬(p ∧ q) ∨ r (Implication Law)
3. ≡ (¬p ∨ ¬q) ∨ r (De Morgan's Law)
4. ≡ ¬p ∨ ¬q ∨ r (Associative Law)

This is also already in CNF.

Example: Convert p ∨ (q ∧ r) to CNF.

1. p ∨ (q ∧ r)
2. ≡ (p ∨ q) ∧ (p ∨ r) (Distributive Law)

This is now in CNF.

Example: Convert p ∧ (q ∨ r) to DNF.

1. p ∧ (q ∨ r)
2. ≡ (p ∧ q) ∨ (p ∧ r) (Distributive Law)

This is now in DNF.

Applications of Normal Forms

• Circuit Design: CNF corresponds to AND-OR logic circuits, and DNF corresponds to OR-AND logic circuits.
• Automated Theorem Proving: Many theorem provers work with formulas in CNF (e.g., resolution principle).
• Database Querying: Logical expressions are often manipulated into normal forms for efficient query processing.
• Satisfiability (SAT) Problems: Determining if a propositional formula can be made true is a fundamental problem, and SAT solvers often work with CNF.

Predicates and Quantifiers

Propositional logic is powerful but limited. It cannot express statements about general properties or collections of objects. Predicate logic, also known as first-order logic, overcomes this limitation by introducing predicates and quantifiers.

Predicates

A predicate is a statement that involves variables. When values are assigned to these variables from a specific domain (called the domain of discourse), the predicate becomes a proposition (either true or false). Predicates can express properties of objects or relationships between objects.

• Notation: We use P(x) to denote a predicate P with one variable x. P(x₁, x₂, ..., x_n) denotes a predicate with n variables.
• Example 1: Let P(x) be the predicate "x is an even number."
• If the domain of discourse is the set of integers {..., -2, -1, 0, 1, 2, ...}:
• P(4) is "4 is an even number," which is True.
• P(7) is "7 is an even number," which is False.
• Example 2: Let Q(x, y) be the predicate "x is greater than y."
• If the domain is integers:
• Q(5, 3) is "5 is greater than 3," which is True.
• Q(3, 5) is "3 is greater than 5," which is False.
• Example 3: Let R(x, y, z) be the predicate "x + y = z."
• If the domain is integers:
• R(2, 3, 5) is "2 + 3 = 5," which is True.
• R(2, 3, 6) is "2 + 3 = 6," which is False.

Quantifiers

Quantifiers allow us to make statements about the quantity of elements in the domain of discourse for which a predicate holds true.

Universal Quantifier (∀)

The universal quantifier, denoted by ∀, means "for all" or "for every." A statement of the form ∀x P(x) asserts that the predicate P(x) is true for every element x in the domain of discourse.

• Reading: "For all x, P(x) is true." or "P(x) holds for every x."
• Example: ∀x (x² ≥ 0)
• If the domain is the set of real numbers, this statement means "For every real number x, x squared is greater than or equal to 0." This is True.
• Example: ∀x (x + 1 > x)
• If the domain is the set of integers, this means "For every integer x, x plus 1 is greater than x." This is True.

Existential Quantifier (∃)

The existential quantifier, denoted by ∃, means "there exists," "for some," or "at least one." A statement of the form ∃x P(x) asserts that there is at least one element x in the domain of discourse for which P(x) is true.

• Reading: "There exists an x such that P(x) is true." or "For some x, P(x) is true."
• Example: ∃x (x² = 9)
• If the domain is the set of integers, this statement means "There exists an integer x such that x squared is equal to 9." This is True, because x=3 or x=-3 satisfies the condition.
• Example: ∃x (x is a prime number divisible by 4)
• If the domain is the set of integers, this statement is False, as no prime number is divisible by 4.

Variables and Scope

In a quantified statement like ∀x P(x) or ∃x P(x), the variable x is called a bound variable. The part of the statement to which the quantifier applies is called the scope of the quantifier. Variables that are not bound by quantifiers are called free variables. A statement with free variables is not a proposition; its truth value depends on the values assigned to the free variables.

Translating Statements

Translating English sentences into predicate logic requires careful identification of predicates, domains, and quantifiers.

• Sentence: "All students in this class have taken a course in mathematics."
• Let D(x) be "x is a student in this class."
• Let M(x) be "x has taken a course in mathematics."
• Domain of Discourse: People.
• Translation: ∀x (D(x) → M(x))
• This reads: "For every person x, if x is a student in this class, then x has taken a course in mathematics."
• Note: We use implication (→) for "all" statements. If x is not a student in this class (D(x) is False), the implication is True, which is correct.
• Sentence: "There is a student in this class who has taken a course in physics."
• Let D(x) be "x is a student in this class."
• Let P(x) be "x has taken a course in physics."
• Domain of Discourse: People.
• Translation: ∃x (D(x) ∧ P(x))
• This reads: "There exists a person x such that x is a student in this class AND x has taken a course in physics."
• Note: We use conjunction (∧) for "there is a... who" statements. We are looking for an individual who satisfies *both* conditions.
• Sentence: "Every positive integer has a unique prime factor."
• Let P(x) be "x is a positive integer."
• Let Q(x, y) be "y is a prime factor of x."
• Domain of Discourse: Integers.
• Translation: ∀x (P(x) → ∃!y (Q(x, y)))
• The notation ∃!y means "there exists a unique y." This statement asserts that for every positive integer x, there is exactly one y such that y is a prime factor of x. (This statement is actually false, e.g., 12 has prime factors 2 and 3. The statement should be "Every positive integer greater than 1 has at least one prime factor." or "Every positive integer greater than 1 has a unique prime factorization.")

Negating Quantified Statements

The negation of a universally quantified statement is an existentially quantified statement with the predicate negated, and vice versa.

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

Example:

• Statement: "All birds can fly." (∀x (B(x) → F(x)))
• Negation: "There exists a bird that cannot fly." (∃x (B(x) ∧ ¬F(x)))
• Let's verify this using equivalence:
• ¬(∀x (B(x) → F(x)))
• ≡ ∃x ¬(B(x) → F(x)) (Negating universal quantifier)
• ≡ ∃x ¬(¬B(x) ∨ F(x)) (Implication Law)
• ≡ ∃x (¬(¬B(x)) ∧ ¬F(x)) (De Morgan's Law)
• ≡ ∃x (B(x) ∧ ¬F(x)) (Double Negation Law)
• This confirms the equivalence.

Example:

• Statement: "There is a number divisible by 2." (∃x (Integer(x) ∧ DivisibleBy(x, 2)))
• Negation: "There is no number divisible by 2." or "All numbers are not divisible by 2." (∀x ¬(Integer(x) ∧ DivisibleBy(x, 2)))
• Which simplifies to: ∀x (Integer(x) → ¬DivisibleBy(x, 2))

Nested Quantifiers

Just as we can combine propositions using multiple logical connectives, we can combine predicates using multiple quantifiers. Statements with multiple quantifiers are called nested quantifiers. The order in which quantifiers appear is crucial and significantly affects the meaning of the statement.

Understanding Nested Quantifiers

Consider two predicates P(x, y) and Q(x, y). We can form statements like:

• ∀x ∀y P(x, y)
• ∀x ∃y P(x, y)
• ∃x ∀y P(x, y)
• ∃x ∃y P(x, y)

The domain of discourse for each variable must be considered. For simplicity, let's often assume the domain is the set of real numbers (ℝ) or integers (ℤ).

Example 1: ∀x ∀y P(x, y)

Meaning: "For every x, and for every y, P(x, y) is true."

Example: ∀x ∀y (x² + y² ≥ 0)

If the domain is ℝ, this means "For every real number x, and for every real number y, the sum of their squares is greater than or equal to 0." This is True.

This is equivalent to saying that P(x, y) is true for all possible pairs (x, y) in the domain.

Example 2: ∃x ∃y P(x, y)

Meaning: "There exists an x, and there exists a y, such that P(x, y) is true."

Example: ∃x ∃y (x² + y² = 0)

If the domain is ℝ, this means "There exists a real number x, and there exists a real number y, such that the sum of their squares is 0." This is True, because x=0 and y=0 satisfy the condition.

This is equivalent to saying that there is at least one pair (x, y) for which P(x, y) is true.

Example 3: ∀x ∃y P(x, y)

Meaning: "For every x, there exists a y such that P(x, y) is true."

Example: ∀x ∃y (x + y = 0)

If the domain is ℝ, this means "For every real number x, there exists a real number y such that x + y = 0." This is True. For any given x, we can choose y = -x.

Example: ∀x ∃y (y > x)

If the domain is ℝ (or ℤ), this means "For every real number x, there exists a real number y such that y is greater than x." This is True. For any x, we can pick y = x + 1.

Key Point: The 'y' that exists for a given 'x' can depend on 'x'.

Example 4: ∃x ∀y P(x, y)

Meaning: "There exists an x such that for every y, P(x, y) is true."

Example: ∃x ∀y (x + y = y)

If the domain is ℝ, this means "There exists a real number x such that for every real number y, x + y = y." This is True. The value x=0 satisfies this condition, because 0 + y = y for all y.

Example: ∃x ∀y (y > x)

If the domain is ℝ, this means "There exists a real number x such that for every real number y, y is greater than x." This is False. There is no single real number x that is smaller than all other real numbers.

Key Point: The 'x' that exists must work for ALL 'y's. This is a much stronger condition than ∀x ∃y.

Comparing Nested Quantifier Orders

The order of quantifiers matters greatly.

• ∀x ∃y P(x, y) is NOT equivalent to ∃y ∀x P(x, y).

Let's illustrate with the example: P(x, y) is "x + y = y". Domain is ℝ.

• Statement 1: ∀x ∃y (x + y = y)
• Meaning: "For every x, there exists a y such that x + y = y."
• Truth Value: True (as shown before, y = 0 works for all x).
• Statement 2: ∃y ∀x (x + y = y)
• Meaning: "There exists a y such that for every x, x + y = y."
• Truth Value: True (the y = 0 works).
• In this specific case, both are True. Let's try another predicate.

Let P(x, y) be "y > x". Domain is ℝ.

• Statement 1: ∀x ∃y (y > x)
• Meaning: "For every x, there exists a y such that y > x."
• Truth Value: True (for any x, pick y = x + 1).
• Statement 2: ∃y ∀x (y > x)
• Meaning: "There exists a y such that for every x, y > x."
• Truth Value: False (there is no single real number y that is greater than all real numbers).
• Here, the truth values differ. ∀x ∃y is True, while ∃y ∀x is False. This shows they are not equivalent in general.

Negating Nested Quantifiers

We apply the rules for negating quantifiers iteratively.

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

Example: Negate the statement "Every person x has a friend y."

• Let F(x, y) be "y is a friend of x." Domain: People.
• Statement: ∀x ∃y F(x, y)
• Negation: ¬(∀x ∃y F(x, y))
• ≡ ∃x ¬(∃y F(x, y))
• ≡ ∃x ∀y ¬F(x, y)
• Meaning: "There exists a person x such that for every person y, y is not a friend of x." (i.e., "There is someone who has no friends.")

Translating Complex English Statements

Nested quantifiers are essential for expressing subtle relationships.

• Statement: "For every real number x, there is a real number y such that y is greater than x."
• Translation: ∀x ∃y (y > x)
• Truth Value: True.
• Statement: "There is a real number y such that for every real number x, y is greater than x."
• Translation: ∃y ∀x (y > x)
• Truth Value: False.
• Statement: "There is a number that divides every integer."
• Let D(x, y) be "x divides y." Domain: Integers.
• Translation: ∃x ∀y D(x, y)
• Truth Value: False. (No single integer divides all other integers. For example, if x=1, it divides all integers. If x=2, it doesn't divide 3. If x=0, division by zero is undefined. The statement implies a non-zero x.)
• If the domain were {1}, then it would be true. Context is key.
• Statement: "Every integer has a divisor that is unique to it." (This is a bit ambiguous in English, let's assume it means "For every integer x, there exists a unique integer y such that y divides x.")
• Let Divides(y, x) be "y divides x." Domain: Integers.
• Translation: ∀x ∃!y Divides(y, x)
• Truth Value: False. For x=6, divisors are ±1, ±2, ±3, ±6. For x=0, any non-zero integer divides 0.

Rules of Inference

Rules of inference are the fundamental building blocks of logical reasoning. They are templates for valid arguments, allowing us to deduce new true statements from existing true statements. In propositional logic, these rules help us determine if a conclusion logically follows from a set of premises.

What is a Valid Argument?

An argument is a sequence of statements, where the initial statements are premises, and the final statement is the conclusion. An argument is considered valid if and only if whenever all the premises are true, the conclusion must also be true. It's impossible for the premises to be true and the conclusion false in a valid argument.

Rules of Inference for Propositional Logic

Here are some of the most common and useful rules of inference. We use 'p' and 'q' to represent propositions.

1. Modus Ponens (Law of Detachment)

This is perhaps the most fundamental rule. If we know that an implication 'p → q' is true, and we also know that the hypothesis 'p' is true, then we can conclude that the conclusion 'q' must be true.

Form:

Premise 1: p → q
Premise 2: p
Conclusion: q

Example:

• Premise 1: If it is raining (p), then the ground is wet (q).
• Premise 2: It is raining (p).
• Conclusion: Therefore, the ground is wet (q).

2. Modus Tollens (Law of Contrapositive)

This rule is based on the contrapositive equivalence (p → q ≡ ¬q → ¬p). If we know that 'p → q' is true, and we know that the conclusion 'q' is false (i.e., ¬q is true), then the hypothesis 'p' must also be false (i.e., ¬p is true).

Form:

Premise 1: p → q
Premise 2: ¬q
Conclusion: ¬p

Example:

• Premise 1: If you study hard (p), then you will pass the exam (q).
• Premise 2: You did not pass the exam (¬q).
• Conclusion: Therefore, you did not study hard (¬p).

3. Hypothetical Syllogism

This rule allows us to chain implications together. If we have two implications where the conclusion of the first matches the hypothesis of the second, we can form a new implication connecting the hypothesis of the first to the conclusion of the second.

Form:

Premise 1: p → q
Premise 2: q → r
Conclusion: p → r

Example:

• Premise 1: If it is sunny (p), then we go to the beach (q).
• Premise 2: If we go to the beach (q), then we will swim (r).
• Conclusion: Therefore, if it is sunny (p), then we will swim (r).

4. Disjunctive Syllogism

This rule deals with disjunctions (OR statements). If we know that 'p ∨ q' is true, and we know that one of the disjuncts is false (say, ¬p is true), then the other disjunct must be true (q must be true).

Form:

Premise 1: p ∨ q
Premise 2: ¬p
Conclusion: q

Example:

• Premise 1: The alarm is ringing (p) or the power is out (q).
• Premise 2: The alarm is not ringing (¬p).
• Conclusion: Therefore, the power is out (q).

5. Addition (Rule of Summation)

This rule allows us to introduce a new disjunct. If we know that 'p' is true, we can conclude that 'p ∨ q' is true for any proposition 'q'.

Form:

Premise: p
Conclusion: p ∨ q

Example:

• Premise: The cat is on the mat.
• Conclusion: Therefore, the cat is on the mat or the dog is barking.

This seems trivial, but it's important for constructing longer proofs where you might need to introduce a disjunction.

6. Simplification (Rule of Conjunction)

This rule is the opposite of Addition. If we know that a conjunction 'p ∧ q' is true, then we can conclude that 'p' is true, and we can also conclude that 'q' is true.

Form:

Premise: p ∧ q
Conclusion: p

(Or, alternatively, the conclusion can be q).

Example:

• Premise: It is sunny and warm.
• Conclusion: Therefore, it is sunny.

7. Conjunction (Rule of Product)

This rule allows us to combine two known true propositions into a conjunction. If we know 'p' is true and 'q' is true, we can conclude that 'p ∧ q' is true.

Form:

Premise 1: p
Premise 2: q
Conclusion: p ∧ q

Example:

• Premise 1: The sky is blue.
• Premise 2: The grass is green.
• Conclusion: Therefore, the sky is blue and the grass is green.

Rules of Inference for Predicate Logic

These rules extend the propositional rules to handle quantifiers.

1. Universal Instantiation

If a property holds for all elements in the domain, it holds for any specific element in the domain.

Form:

Premise: ∀x P(x)
Conclusion: P(c)

Here, 'c' represents any specific constant or term in the domain.

Example:

• Premise: All humans are mortal. (∀x (Human(x) → Mortal(x)))
• Conclusion: Socrates is mortal. (Mortal(Socrates))
• (Here, c = Socrates)

2. Universal Generalization

This is the inverse of Universal Instantiation. If we can show that a property P(x) holds for an *arbitrary* element x from the domain (without making any special assumptions about x), then we can conclude that the property holds for all elements.

Form:

Premise: P(x) (where x is arbitrary)
Conclusion: ∀x P(x)

Example: To prove that the sum of two even numbers is even.

• Let x be an arbitrary integer. Assume x is even. (x = 2k for some integer k).
• Let y be an arbitrary integer. Assume y is even. (y = 2m for some integer m).
• Then x + y = 2k + 2m = 2(k + m).
• Since k + m is an integer, x + y is of the form 2 * (integer), so x + y is even.
• Conclusion: ∀x ∀y ((Even(x) ∧ Even(y)) → Even(x+y))

3. Existential Instantiation

If we know that there exists an element for which a property holds, we can introduce a new constant symbol to represent such an element.

Form:

Premise: ∃x P(x)
Conclusion: P(c)

Here, 'c' is a *new* constant symbol that has not been used before.

Example:

• Premise: There is a number that is prime and greater than 100. (∃x (Prime(x) ∧ GreaterThan(x, 100)))
• Conclusion: Let 'p' be such a number. Then Prime(p) ∧ GreaterThan(p, 100).
• (Here, 'p' is a new constant representing one such number).

4. Existential Generalization

If we know that a property P(c) holds for a specific element 'c', then we can conclude that there exists at least one element (namely 'c') for which the property holds.

Form:

Premise: P(c)
Conclusion: ∃x P(x)

Example:

• Premise: 7 is a prime number. (Prime(7))
• Conclusion: There exists a number that is prime. (∃x Prime(x))

Constructing Proofs

A formal proof is a sequence of steps, where each step is either a premise or is derived from previous steps using a rule of inference. The goal is to reach the desired conclusion.

Example Proof: Prove that if p → q and ¬q are true, then ¬p is true.

1. p → q (Premise)
2. ¬q (Premise)
3. ¬p (Modus Tollens, from 1 and 2)

This is a proof using Modus Tollens.

Example Proof: Prove that if p ∨ q and p → r and q → s are true, then r ∨ s is true.

1. p ∨ q (Premise)
2. p → r (Premise)
3. q → s (Premise)
4. r (Modus Ponens, from 2 and If p is true)
5. s (Modus Ponens, from 3 and If q is true)
6. r ∨ s (Addition, from 4)
7. r ∨ s (Addition, from 5)

This proof uses a technique called "proof by cases." We consider the two cases from the disjunction p ∨ q:

• Case 1: Assume p is true. Using Modus Ponens with p → r, we get r. Then by Addition, we get r ∨ s.
• Case 2: Assume q is true. Using Modus Ponens with q → s, we get s. Then by Addition, we get r ∨ s.

Since in both possible cases (p is true or q is true), we can deduce r ∨ s, the conclusion r ∨ s must be true.