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, p<em>1, p</em>2, …$

  • Compound Propositions: Formed using logical connectives.

5. Symbols of Formal Logic

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.