Discrete Mathematics

Discrete Mathematics Notes

Module 1: Logic and Proofs

1. Logic

  • Definition: The study of reasoning, specifically concerned with the correctness of reasoning.

  • Usage: Logic is utilized to prove theorems in mathematics.

  • Focus: Emphasizes the relationships among statements, not the content of any single statement.

  • World View: Considers the world as composed of objects that can form collections. Statements that describe the world can be classified as true or false.

2. Statements

  • Definition: A statement is a declarative description of something.

  • Examples of Statements:

    • "I’m 31 years old."

    • "I have 17 children."

    • "I always tell the truth."

    • "I’m lying to you."

  • Questions: Which statements are true? False? Both? Neither?

3. Propositions

  • Definition: A proposition is a declarative statement that is either true or false, but not both.

  • Laws:

    • Law of the Excluded Middle: A proposition cannot be partially true or partially false.

    • Law of Contradiction: A proposition cannot be both true and false.

  • Examples of Propositions:

    1. "The only positive integers that divide 7 are 1 and 7."

    2. "Manny Pacquiao won the fight against Antonio Margarito."

    3. "1 + 1 = 4."

    4. "Our professor is from Mars."

    5. "The Moon revolves around the Earth."

    6. "Elephants can fly."

    7. "3 + 8 = 11."

  • Non-Propositions Examples:

    • Questions (e.g., "Where do you live?")

    • Commands (e.g., "Please erase the board.")

    • Self-referential statements or unknown values (e.g., "This sentence is false," or "A + 1 = 2")

4. Formal Logic

  • Need: In order to formalize logic, we need a system for translating statements into symbols.

  • Propositional Logic:

    • Consists of a collection of propositions denoted as $p, q, r, s, t, p1, p2, …$

    • Compound Propositions: Formed using logical connectives.

5. Symbols of Formal Logic

Operator

Symbol

Usage

Negation

~

not

Conjunction

∧

and

Disjunction

∨

or

Exclusive or

⊕

xor

Conditional

→

if, then

Biconditional

↔

Iff

Logical Equivalence

≡

= =

6. Truth Table

  • Definition: A table that lists the truth values of a compound proposition for all possible values of its primitive propositions.

  • Example of Truth Table with 2 Variables $(p, q)$:

    p

    q

    $p ? q$

    T

    T

    T

    T

    F

    F

    F

    T

    F

    F

    F

    F

  • Truth Values of Conjunction (AND): $p ∧ q = ext{TRUE } iff ext{ both } p ext{ and } q ext{ are true}$.

  • Truth Values of Disjunction (OR): $p ∨ q = ext{TRUE } iff ext{ either } p ext{ or } q ext{ is true or both}$.

7. Examples of Conjunction

  • Example 1: Let $p: 1 + 1 = 3$ (F), $q: A decade is 10 years$ (T).

  • Evaluate: $p ∧ q = F ∧ T = F$.

  • Example 2: Let $p: Benigno Aquino III is the 15th president of the Philippines$ (T), $q: Ogie Alcasid is a singer/composer$ (T), and $r: BobCat is the official mascot of UC$ (F).

  • Evaluate propositions:

    1. $p ∧ q$

    2. $p ∧ r$

    3. $q ∧ r$

    4. $q ∧ p$

8. Truth Values of Negation (Not)


  • Definition: Turns a TRUE proposition to FALSE and vice versa.


  • Truth Table:

    p

    ~p


    T

    F


    F

    T

    9. Applications of Propositions

    • Used in search queries and logical statements to simplify searches (e.g., "Afred Hitchcock AND (Herman OR Waxman) AND (NOT tv)").

    10. Quantification

    • Predicate: A relationship between objects (e.g., $x < 3$, $x + y < 25$).

    • Universal Quantifier: $ orall x, P(x)$ means "For every $x$, $P(x)$".

    • Existential Quantifier: $ herefore x, P(x) $ means "There exists an $x$ such that $P(x)$".

    11. Proofs

    • Definition: A logical argument establishing the truth of a theorem.

    • Methods: Through equivalence rules and inference rules.

    12. Mathematical Induction

    • Principle:

      1. Basic Step: Prove $S(1)$ is true.

      2. Inductive Step: Show if $S(k)$ is true for all $i < n + 1$, then $S(n + 1)$ is true.

    13. Exercises and Problems

    • Truth Table Verification:

      • For different expressions to determine validity.

    • Logic Applications: Solve real-world queries using logical implications and quantifiers.

    14. Set Theory Introduction

    • Definition: The study of sets, collections of objects, which is fundamental in mathematics.

    • Universal Set: The set under consideration which includes all objects.

    15. Set Notation and Properties

    • Roster Notation: Listing elements of a set.

    • Set Builder Notation: Describing conditions or properties that members of a set share.

    • Examples:

      • $A = ext{the set of all vowels in the English alphabet}: V = {a, e, i, o, u}$

    16. Operations on Sets

    • Union: Combined set of elements from both sets.

    • Intersection: Set of elements common to both sets.

    • Difference: Elements in one set but not in another.

    17. Exercises on Operating with Sets

    • Compute operations such as union, intersection, symmetric difference, and set difference.

    • Prove different identities and properties using sets.

    18. Summary

    • Logic and proofs form the foundation of discrete mathematics.

    • Set theory provides a way to format and manipulate collections of objects effectively.

    Continuing Discussions

    • Next topics will include sequences and strings in mathematics.