Basic MathGuides

Mathematical Logic Explained: The Language of Reasoning in Mathematics

7 hours ago
10 mins
10 Views
0 Comments
Mathematical Logic Comprehensive Notes

Complete Guide to Mathematical Logic

Table of Contents
  1. Introduction to Mathematical Logic
  2. Propositional Logic
  3. Predicate Logic
  4. Truth Tables
  5. Logical Equivalences
  6. Methods of Proof
  7. Rules of Inference
  8. Quantifiers
  9. Interactive Quiz

1. Introduction to Mathematical Logic

Mathematical logic is a subfield of mathematics that explores the applications of formal logic to mathematics. It emerged in the late 19th century and has become fundamental to mathematics, computer science, linguistics, and philosophy.

Key Concepts in Mathematical Logic:
  • Propositions: Declarative statements that are either true or false
  • Logical Operators: Symbols that connect propositions (AND, OR, NOT, etc.)
  • Predicates: Statements that contain variables and become propositions when values are assigned
  • Quantifiers: Expressions that specify the quantity of objects that satisfy a predicate
  • Inference Rules: Patterns of reasoning that allow new statements to be derived from existing ones

Mathematical logic provides the foundation for formal verification, programming language semantics, database query languages, and artificial intelligence reasoning systems.

2. Propositional Logic

Propositional logic deals with propositions (statements that are either true or false) and their combinations using logical connectives.

Logical Connectives

Basic Logical Operators:
  • Negation (NOT, ¬): Reverses the truth value of a proposition
  • Conjunction (AND, ∧): True only when both operands are true
  • Disjunction (OR, ∨): True when at least one operand is true
  • Conditional (IF-THEN, →): False only when the antecedent is true and the consequent is false
  • Biconditional (IF AND ONLY IF, ↔): True when both operands have the same truth value

Examples of Propositions

Example 1: Identifying Propositions

Determine which of the following are propositions:

  1. Paris is the capital of France.
  2. What time is it?
  3. x + 2 = 7
  4. The moon is made of cheese.
  5. Please close the door.
Solution:
  1. This is a proposition (and it's true).
  2. This is not a proposition; it's a question.
  3. This is not a proposition; it's an open sentence that becomes a proposition when x is assigned a value.
  4. This is a proposition (and it's false).
  5. This is not a proposition; it's a command.
Example 2: Translating English to Propositional Logic

Let p = "It is raining" and q = "I will bring an umbrella"

Express the following statements using propositional logic:

  1. It is raining and I will bring an umbrella.
  2. If it is raining, then I will bring an umbrella.
  3. It is not raining or I will bring an umbrella.
  4. I will bring an umbrella if and only if it is raining.
  5. It is raining but I will not bring an umbrella.
Solution:
  1. p ∧ q
  2. p → q
  3. ¬p ∨ q
  4. p ↔ q
  5. p ∧ ¬q
Example 3: Translating Propositional Logic to English

Let p = "The battery is charged", q = "The car starts", and r = "I will be late"

Translate the following logical expressions into English:

  1. p → q
  2. ¬q → r
  3. (p ∧ q) → ¬r
  4. ¬p ∨ (q ∧ ¬r)
Solution:
  1. If the battery is charged, then the car starts.
  2. If the car doesn't start, then I will be late.
  3. If the battery is charged and the car starts, then I will not be late.
  4. Either the battery is not charged or the car starts and I will not be late.

3. Truth Tables

Truth tables display all possible truth values of compound propositions based on the truth values of their components.

Basic Truth Tables

p ¬p
T F
F T
p q p ∧ q
T T T
T F F
F T F
F F F
p q p ∨ q
T T T
T F T
F T T
F F F
p q p → q
T T T
T F F
F T T
F F T
p q p ↔ q
T T T
T F F
F T F
F F T

Constructing Truth Tables for Complex Propositions

Example: Truth Table for (p → q) ∧ ¬p

Construct a complete truth table for the compound proposition (p → q) ∧ ¬p

Solution:

We'll build this step by step:

p q p → q ¬p (p → q) ∧ ¬p
T T T F F
T F F F F
F T T T T
F F T T T
Example: Tautology, Contradiction, and Contingency

Determine whether each of these compound propositions is a tautology, a contradiction, or a contingency:

  1. p ∨ ¬p
  2. p ∧ ¬p
  3. p → p
  4. (p → q) ↔ (¬q → ¬p)
Solution:
  1. p ∨ ¬p is a tautology (always true)
  2. p ∧ ¬p is a contradiction (always false)
  3. p → p is a tautology (always true)
  4. (p → q) ↔ (¬q → ¬p) is a tautology (the contrapositive equivalence)

4. Logical Equivalences

Two compound propositions are logically equivalent if they have the same truth values for all possible truth values of their variables.

Important Logical Equivalences

Law Equivalence
Identity laws p ∧ T ≡ p
p ∨ F ≡ p
Domination laws p ∨ T ≡ T
p ∧ F ≡ F
Idempotent laws p ∧ p ≡ p
p ∨ p ≡ p
Double negation law ¬(¬p) ≡ p
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)
De Morgan's laws ¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Absorption laws p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p
Negation laws p ∧ ¬p ≡ F
p ∨ ¬p ≡ T
Conditional equivalence p → q ≡ ¬p ∨ q
Biconditional equivalence p ↔ q ≡ (p → q) ∧ (q → p)
Contrapositive p → q ≡ ¬q → ¬p
Example: Using Logical Equivalences

Show that ¬(p → q) ≡ p ∧ ¬q using logical equivalences.

Solution:

Step-by-step application of logical equivalences:

  1. ¬(p → q)
  2. ¬(¬p ∨ q) [Using conditional equivalence: p → q ≡ ¬p ∨ q]
  3. ¬(¬p) ∧ ¬q [Using De Morgan's law: ¬(a ∨ b) ≡ ¬a ∧ ¬b]
  4. p ∧ ¬q [Using double negation: ¬(¬p) ≡ p]

Therefore, ¬(p → q) ≡ p ∧ ¬q

Example: Simplifying a Logical Expression

Simplify the logical expression: (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q)

Solution:

Step-by-step simplification:

  1. (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q)
  2. [(p ∧ q) ∨ (p ∧ ¬q)] ∨ (¬p ∧ q) [Associative law]
  3. [p ∧ (q ∨ ¬q)] ∨ (¬p ∧ q) [Distributive law]
  4. [p ∧ T] ∨ (¬p ∧ q) [Negation law: q ∨ ¬q ≡ T]
  5. p ∨ (¬p ∧ q) [Identity law: p ∧ T ≡ p]
  6. (p ∨ ¬p) ∧ (p ∨ q) [Distributive law]
  7. T ∧ (p ∨ q) [Negation law: p ∨ ¬p ≡ T]
  8. p ∨ q [Identity law: T ∧ a ≡ a]

Therefore, (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) ≡ p ∨ q

5. Predicate Logic

Predicate logic extends propositional logic by allowing variables and quantifiers, making it more expressive for mathematical statements.

Predicates and Variables

A predicate is a statement containing variables that becomes a proposition when values are assigned to the variables.

Example: Predicates

Consider the predicate P(x): "x is greater than 5" where x is a variable.

  • P(3) is false because 3 is not greater than 5.
  • P(7) is true because 7 is greater than 5.
Example: Multiple Variables

Let Q(x, y): "x + y = 10" where x and y are variables.

  • Q(3, 7) is true because 3 + 7 = 10.
  • Q(4, 4) is false because 4 + 4 = 8, which is not equal to 10.
Example: Expressing English Statements as Predicates

Express the following statements using predicates:

  1. "x is a prime number"
  2. "x is divisible by y"
  3. "x is between y and z"
Solution:
  1. P(x): "x is a prime number"
  2. D(x, y): "x is divisible by y"
  3. B(x, y, z): "x is between y and z"

Domains and Compound Predicates

The domain (universe of discourse) is the set of all possible values for the variables in a predicate.

Example: Compound Predicates

Let P(x): "x > 0" and Q(x): "x is even" where the domain is the set of integers.

Express the following compound predicates:

  1. "x is positive and even"
  2. "x is positive or even"
  3. "if x is positive, then x is even"
Solution:
  1. P(x) ∧ Q(x)
  2. P(x) ∨ Q(x)
  3. P(x) → Q(x)

6. Quantifiers

Quantifiers specify how many elements in the domain satisfy a predicate.

Universal and Existential Quantifiers

Universal Quantifier (∀)

∀x P(x) means "For all x, P(x) is true" or "P(x) is true for every x in the domain."

Existential Quantifier (∃)

∃x P(x) means "There exists an x such that P(x) is true" or "P(x) is true for at least one x in the domain."

Example: Translating English to Quantified Statements

Let P(x): "x is a student" and Q(x): "x passed the exam". Translate:

  1. "All students passed the exam."
  2. "Some students passed the exam."
  3. "No students passed the exam."
  4. "Not all students passed the exam."
Solution:
  1. ∀x (P(x) → Q(x))
  2. ∃x (P(x) ∧ Q(x))
  3. ¬∃x (P(x) ∧ Q(x)) or equivalently ∀x (P(x) → ¬Q(x))
  4. ¬∀x (P(x) → Q(x)) or equivalently ∃x (P(x) ∧ ¬Q(x))

Multiple Quantifiers

Example: Nested Quantifiers

Let L(x, y): "x loves y" where the domain consists of all people. Translate:

  1. "Everyone loves someone."
  2. "Someone loves everyone."
  3. "Everyone is loved by someone."
  4. "There is someone who is loved by everyone."
Solution:
  1. ∀x ∃y L(x, y) - For every person x, there exists a person y such that x loves y.
  2. ∃x ∀y L(x, y) - There exists a person x such that for every person y, x loves y.
  3. ∀x ∃y L(y, x) - For every person x, there exists a person y such that y loves x.
  4. ∃x ∀y L(y, x) - There exists a person x such that for every person y, y loves x.

Note: The order of quantifiers is crucial. ∀x ∃y and ∃y ∀x generally mean different things.

Negating Quantified Statements

Example: Negation Rules for Quantifiers

Find the negation of each quantified statement:

  1. ∀x P(x)
  2. ∃x P(x)
  3. ∀x ∃y R(x, y)
Solution:
  1. ¬(∀x P(x)) ≡ ∃x ¬P(x)
  2. ¬(∃x P(x)) ≡ ∀x ¬P(x)
  3. ¬(∀x ∃y R(x, y)) ≡ ∃x ∀y ¬R(x, y)

To negate a quantified statement, negate the quantifier (∀ becomes ∃ and vice versa) and negate the predicate.

7. Rules of Inference

Rules of inference are templates for constructing valid arguments. They allow us to derive new true statements from existing ones.

Basic Rules of Inference

Rule Name Tautology Argument Form
Modus Ponens (p → q) ∧ p → q p → q
p
∴ q
Modus Tollens (p → q) ∧ ¬q → ¬p p → q
¬q
∴ ¬p
Hypothetical Syllogism (p → q) ∧ (q → r) → (p → r) p → q
q → r
∴ p → r
Disjunctive Syllogism (p ∨ q) ∧ ¬p → q p ∨ q
¬p
∴ q
Addition p → (p ∨ q) p
∴ p ∨ q
Simplification p ∧ q → p p ∧ q
∴ p
Conjunction p, q → p ∧ q p
q
∴ p ∧ q
Resolution (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) p ∨ q
¬p ∨ r
∴ q ∨ r
Example: Using Rules of Inference

Given the premises "If it rains, the picnic will be canceled", "It is raining", determine the conclusion using a valid rule of inference.

Solution:

Let p = "It is raining" and q = "The picnic will be canceled".

Then we have:

  1. p → q (If it rains, the picnic will be canceled)
  2. p (It is raining)

Using Modus Ponens: (p → q) ∧ p → q

Conclusion: q (The picnic will be canceled)

Example: Proving Argument Validity

Determine if the following argument is valid:

  1. If I study, I will pass the exam.
  2. If I pass the exam, I will graduate.
  3. I did not graduate.
  4. Therefore, I did not study.
Solution:

Let p = "I study", q = "I pass the exam", and r = "I graduate".

The premises are:

  1. p → q (If I study, I will pass the exam)
  2. q → r (If I pass the exam, I will graduate)
  3. ¬r (I did not graduate)

Step 1: From premises 1 and 2, using Hypothetical Syllogism, we get p → r.

Step 2: From p → r and ¬r, using Modus Tollens, we get ¬p.

Therefore, the conclusion "I did not study" (¬p) is valid.

8. Methods of Proof

Different techniques are used to prove mathematical statements, depending on their structure.

Direct Proof

A direct proof assumes the hypothesis and uses logical reasoning to reach the conclusion.

Example: Direct Proof

Prove: "If n is an odd integer, then n² is odd."

Solution:

Since n is odd, we can write n = 2k + 1 for some integer k.

Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1

Since 2k² + 2k is an integer, n² is in the form 2m + 1 where m = 2k² + 2k is an integer.

Therefore, n² is odd.

Proof by Contraposition

To prove p → q, prove its contrapositive ¬q → ¬p instead.

Example: Proof by Contraposition

Prove: "If n² is even, then n is even."

Solution:

We'll prove the contrapositive: "If n is not even (i.e., n is odd), then n² is not even (i.e., n² is odd)."

If n is odd, then n = 2k + 1 for some integer k.

Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1

Since 2(2k² + 2k) is even, n² = 2(2k² + 2k) + 1 is odd.

Therefore, n² is odd, which means it is not even.

Since the contrapositive is true, the original statement is also true.

Proof by Contradiction

Assume the negation of what you want to prove, then derive a contradiction.

Example: Proof by Contradiction

Prove: "√2 is irrational."

Solution:

Assume, for the sake of contradiction, that √2 is rational. Then √2 = a/b where a and b are integers with no common factors and b ≠ 0.

√2 = a/b

2 = a²/b²

2b² = a²

Therefore, a² is even, which means a is even (as we proved earlier).

So a = 2k for some integer k.

Then 2b² = (2k)² = 4k²

b² = 2k²

Therefore, b² is even, which means b is even.

But if both a and b are even, they have a common factor of 2, which contradicts our assumption that a and b have no common factors.

This contradiction shows that our assumption was wrong, so √2 must be irrational.

Proof by Cases

Break down the proof into several cases and prove each case separately.

Example: Proof by Cases

Prove: "For any integer n, the value of n² - n + 41 is prime for n = 1, 2, 3, ..., 10."

Solution:

We need to check each case n = 1 through n = 10:

  1. n = 1: 1² - 1 + 41 = 1 - 1 + 41 = 41 (prime)
  2. n = 2: 2² - 2 + 41 = 4 - 2 + 41 = 43 (prime)
  3. n = 3: 3² - 3 + 41 = 9 - 3 + 41 = 47 (prime)
  4. n = 4: 4² - 4 + 41 = 16 - 4 + 41 = 53 (prime)
  5. n = 5: 5² - 5 + 41 = 25 - 5 + 41 = 61 (prime)
  6. n = 6: 6² - 6 + 41 = 36 - 6 + 41 = 71 (prime)
  7. n = 7: 7² - 7 + 41 = 49 - 7 + 41 = 83 (prime)
  8. n = 8: 8² - 8 + 41 = 64 - 8 + 41 = 97 (prime)
  9. n = 9: 9² - 9 + 41 = 81 - 9 + 41 = 113 (prime)
  10. n = 10: 10² - 10 + 41 = 100 - 10 + 41 = 131 (prime)

Since n² - n + 41 is prime for each value of n from 1 to 10, the statement is true.

(Note: This formula actually gives primes for n = 1 to 40, but fails at n = 41.)

9. Interactive Quiz

1. What is the logical equivalent of p → q?

2. Which of the following compound propositions is a tautology?

3. What is the negation of ∀x∃y P(x, y)?

4. Which rule of inference has the form "p → q, q → r, therefore p → r"?

5. What is the contrapositive of "If it rains, then the ground gets wet"?

6. Which of the following is the negation of "Some students passed all exams"?

7. What is the truth value of (p → q) ∧ (¬q ∧ p)?

8. Which of the following is NOT a valid proof technique?

9. What is De Morgan's law for ¬(p ∧ q)?

10. Which of the following statements is equivalent to "If I study, then I will pass the exam"?

Tags:
Shares:

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *