Study Notes for Discrete Mathematics Course

Course Overview

• Course Title: Discrete Mathematics for Computer Science

• Course Code: CSE1101

• Credits: 5

• Prerequisites: Intermediate level mathematics

• Lecture-Tutorial-Practical-Credits (L-T-P-C): 3-1-2-5

Course Objectives

1. Foundation in Mathematical Logic

   • Understanding the principles of logic that serve as the basis for reasoning.

   • Learn to analyze complex problems mathematically.

2. Graph Theory and Algebraic Structures

   • Introduce essential concepts that serve as computational tools in computer science.

3. Formal Mathematical Proofs

   • Develop skills in constructing proofs using induction and logical reasoning.

   • Able to articulate and validate mathematical arguments.

4. Application of Discrete Structures

   • Represent and resolve real-world computational problems using discrete mathematics.

Course Syllabus

Module I: Logic and Proof Techniques

• Topics Covered:

  • Propositions

  • Logical connectives

  • Truth tables

  • Conditional statements: converse, contrapositive, and inverse

  • Logical equivalence

  • Tautology and contradiction

  • Contingency

  • Normal forms: conjunctive and disjunctive

  • Translating English sentences into logical expressions

  • Predicate logic

  • Universal and existential quantifiers

  • Methods of proof, including mathematical induction

Module II: Sets, Functions, and Relations

• Topics Covered:

  • Sets and Venn diagrams

  • Set operations, subsets, and identities

  • Cartesian products and power sets

  • Cardinality of sets

  • Counting techniques and the principle of inclusion-exclusion

  • Functions: injections, surjections, and bijections

  • Relations and their properties

  • Equivalence relations, equivalence classes, partitions

  • Partially ordered sets (Posets) and lattices

Module III: Graph Theory

• Topics Covered:

  • Definition and types of graphs

  • Basic terminology in graph theory

  • Handshaking lemma

  • Paths, cycles, and trees in graphs

  • Complete graphs and regular graphs

  • Bipartite and k-partite graphs

  • Graph representations and connectivity

  • Euler and Hamiltonian paths

  • Graph coloring and determining chromatic numbers

Module IV: Algebraic Structures

• Topics Covered:

  • Semigroups and monoids

  • Groups and abelian groups

  • Subgroups and cyclic groups

  • Group homomorphism and isomorphism

  • Rings and fields

Laboratory Practices

1. Generate truth tables for simple and compound propositions.

2. Determine logical equivalence using truth tables.

3. Perform set operations on finite sets.

4. Compute the Cartesian product of sets, determining its cardinality.

5. Verify whether a relation is an equivalence relation.

6. Construct a graph from an edge list and extract its adjacency matrix.

7. Verify the Handshaking Lemma in a graph.

8. Create a Cayley table for a finite set under a defined binary operation.

Course Outcomes

By the end of the course, students will be able to:

1. Utilize rules of propositional logic, predicate logic, and mathematical induction in verifying mathematical arguments and proofs.

2. Solve problems related to sets, functions, counting, and relations to explore partitions and equivalences.

3. Analyze graph structures, evaluating connectivity, paths, trees, and coloring for modeling purposes.

4. Implement algebraic structures like groups, rings, and fields in appropriate mathematical or computational contexts.

Textbooks

1. K. H. Rosen

   • Title: Discrete Mathematics and its Applications

   • Edition: 7th, Year: 2012

   • Publisher: McGraw-Hill

2. Swapan K. Sarkar

   • Title: Textbook of Discrete Mathematics

   • Edition: 1st, Year: 2015

3. B. Kolman, R. C. Busby, S. C. Ross

   • Title: Discrete Mathematical Structures

   • Edition: 6th, Year: 2008

   • Publisher: Pearson

4. C. L. Liu, D. P. Mohapatra

   • Title: Elements of Discrete Mathematics: A Computer Oriented Approach

   • Edition: 4th, Year: 2012

   • Publisher: Tata McGraw-Hill

References

1. NPTEL

   • Course: “Discrete Mathematics for CS”

   • Instructor: Prof. Nitin Saxena, IIT Kanpur

2. MIT OpenCourseWare

   • Course: “Mathematics for Computer Science”, 6.042J

3. Coursera

   • Specialization: “Introduction to Discrete Mathematics for Computer Science.”

Evaluation Scheme

Theory Assessment (60%)

• Continuous Assessment: 25%

• Mid-term: 25%

• End-term: 50%

• Total: 100%

• Note: Continuous Assessment includes four quizzes, one per module, contributing to the overall theory assessment.

Practical Assessment (40%)

• Continuous Assessment: 10%

• End-term Practical: 30%

• Total: 100%

Special Notes

• Students must read the ‘Student Examination Handbook (2025–2026)’ thoroughly.

• All lectures, tutorials, and study materials are accessible in the JUNO ERP system.

• It is important to maintain a dedicated notebook for the course materials and practice regularly. Be ready to present when requested.

• Office Hours:

  • For Division C: Tuesday 09:00 - 10:00

  • For Division D: Monday 09:00 - 10:00

• Office Location: Room 521

Module I: Logic and Proof Techniques

Topics for This Lecture

• Propositions

• Logical Connectives

• Truth Tables

What is Logic?

• Logic is the study of the methods and principles used to distinguish correct reasoning from incorrect reasoning.

• Focus: Propositional Logic

• Definitions:

  • Proposition: A declarative sentence with a truth value of either True (T) or False (F), but never both.

  • Propositional Logic (Propositional Calculus): The branch of logic that studies the properties and relationships of propositions and how they combine using logical connectives.

Examples of Propositions

• Each proposition must have a definite truth value:

  • True Examples:

  • $(2 + 3 = 5)$

  • “New Delhi is the capital of India.”

  • “7 is an even number.”

  • “The sun rises in the east.”

  • Each of these statements hold a definitive truth value (true or false).

Not Propositions

• Some sentences lack a definitive truth value and are not classified as propositions.

  • Examples Not Propositions:

  • “Close the door.” (command)

  • “What time is it?” (question)

  • $x + 5 = 12$ (contains an unknown variable)

  • “Study harder!” (advice)

Propositional Variables and Truth Values

• Propositional Variables: Represented by letters like p, q, r, s, etc.

  • Each variable has a truth value assigned:

  • Example:

    • $p$: “2 is an even number.” (True)

    • $q$: “5 is a prime number.” (True)

    • $r$: “3 + 4 = 10.” (False)

Compound Propositions

• Definition: Propositions can be combined to create compound propositions using logical connectives.

• Example Statement:

  • Let $p$ = “It is raining”

  • Let $q$ = “I am carrying an umbrella”

  • Compound proposition:

  • $p ext{ ∧ } q$ : “It is raining and I am carrying an umbrella.”

• The truth of a compound proposition is conditional upon the truth values of its constituent propositions.

Logical Connectives and Precedence

• Logical Connectives: Symbols used to connect propositions to form compound propositions.

• Precedence Table:

  Symbol	Meaning
  ¬p	Negation: not p
  p ∧ q	Conjunction: p and q
  p ∨ q	Disjunction (inclusive): p or q (or both)
  p ⊕ q	Exclusive or (XOR): exactly one of p, q is true
  p → q	Implication: if p, then q
  p ↔ q	Biconditional: p if and only if q

  • Parentheses can be used to avoid ambiguity in interpretations.

Truth Tables

• Definition: A truth table displays the truth value of a compound proposition for every possible combination of truth values of its variables.

• Example for Negation:

  p	¬p
  T	F
  F	T

  • $<br>eg p$ means “not p,” which reverses the truth value of $p$.

Truth Table Example with OR

• Truth Table for OR ($p ext{ ∨ } q$):

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

  • Observation: $p ext{ ∨ } q$ is only false when both $p$ and $q$ are false.

Truth Table Example with AND

• Truth Table for AND ($p ext{ ∧ } q$):

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

  • Observation: $p ext{ ∧ } q$ is true only when both $p$ and $q$ are true.

Truth Table Example with Exclusive OR (XOR)

• Truth Table for XOR ($p ⊕ q$):

  p	q	p ⊕ q
  T	T	F
  T	F	T
  F	T	T
  F	F	F

  • Observation: $p ⊕ q$ is true only when either $p$ or $q$ is true, but not both.

Implication

• 
  
  

• Definition: The implication is represented as $p → q$, read as “If p, then q.”

• 
  
  

• It is false only when $p$ is true and $q$ is false.

• 
  
  

• Truth Table for Implication:
  
  

  
  

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

  Biconditional

  
  

  • 
    
    

  • Definition: Biconditional is expressed as $p ↔ q$ meaning “p if and only if q.”

  • 
    
    

  • It holds true when both $p$ and $q$ have the same truth value.

  • 
    
    

  • Truth Table for Biconditional:
    
    

    
    

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

    Example for Logical Statements

    • Let $p:$ “It is raining”

    • Let $q:$ “I carry an umbrella”

      • Expressions Using Logical Connectives:

      • $<br>eg p:$ “It is not raining.”

      • $p ext{ ∧ } q:$ “It is raining and I am carrying an umbrella.”

      • $p ext{ ∨ } q:$ “It is raining or I carry an umbrella.”

      • $p ⊕ q:$ “Either it is raining or I carry an umbrella, but not both.”

      • $p → q:$ “If it is raining, then I carry an umbrella.”

      • $p ↔ q:$ “I carry an umbrella if and only if it is raining.”

    ---

    Exercises

    Propositions

    • Decide whether the following sentences are propositions, and if they are, specify the truth value:

      1. $2 + 5 = 9$

      2. “Close the window.”

      3. “Every prime number is odd.”

      4. $x + 3 = 10$

      5. “Paris is the capital of France.”

    Negation

    • Write the negation of the following statements:

      1. “The class starts at 9:00.”

      2. “The student submitted the assignment.”

      3. “The number 7 is even.”

      4. “All computers in the lab are working.”

    Conjunction and Disjunction

    • Express and evaluate the following sentences using symbols:

      1. “It is raining and it is cold.”

      2. “She is a teacher or she is a doctor.”

      3. “The bus is late and the road is empty.”

      4. “He will pass the exam or he will repeat the course.”

    Exclusive OR

    • Rewrite the following sentences using exclusive or (⊕):

      1. “You can choose tea or coffee, but not both.”

      2. “The room will be locked by Alice or Bob, but not both.”

      3. “The light is on in exactly one of the two rooms.”

    Implication

    • Translate the following into symbolic form:

      1. “If it rains, the match will be canceled.”

      2. “If a number is even, then it is divisible by 2.”

      3. “If the student studies, then the student passes.”

    Biconditional

    • Write each sentence as a biconditional statement:

      1. “A figure is a square if and only if it has four equal sides and four right angles.”

      2. “You may enter the lab if and only if you have your ID card.”

      3. “A number is even if and only if it is divisible by 2.”

    ---

    Module I: Logic and Proof Techniques

    Topics for This Lecture

    • Conditional statements

    • Converse

    • Contrapositive

    • Inverse

    ---

    Conditional Statements

    • Definition: A conditional statement takes the form $p → q$ and is read as “If p, then q.”

    • Here, $p$ is called the hypothesis (antecedent) and $q$ is the conclusion (consequent).

    • Example Statement:

      • “If a number is divisible by 4, then it is even.”

    ---

    Truth of a Conditional

    
    

    • 
      
      

    • Truth Value Condition: The conditional $p → q$ is false only when $p$ is true and $q$ is false.

    • 
      
      

    • Truth Table for Conditional:
      
      

      
      

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

      Converse, Inverse, Contrapositive

      • For a given conditional statement $p → q$:

        • Converse: $q → p$

        • Inverse: $¬p → ¬q$

        • Contrapositive: $¬q → ¬p$

      • Important: The statements $p → q$ and $¬q → ¬p$ share the same truth value.

      ---

      Example — Converse, Inverse, Contrapositive

      • Original Statement: “If it is raining, then the ground is wet.”

      • Converse: “If the ground is wet, then it is raining.”

      • Inverse: “If it is not raining, then the ground is not wet.”

      • Contrapositive: “If the ground is not wet, then it is not raining.”

      ---

      Logical Equivalence

      • Definition: Two compound propositions are logically equivalent if they have the same truth value in every possible scenario.

      • Symbol for Logical Equivalence:

        • $p ≡ q$ means “p and q are logically equivalent.”

      • Example: $¬(p ∧ q) ≡ ¬p ∨ ¬q$ (This is one of De Morgan’s laws.)

      ---

      Truth Table: Conditional, Converse, Inverse, Contrapositive

      • Truth Table Format:
        
        

        p	q	p → q	q → p	¬p → ¬q	¬q → ¬p
        T	T	T	T	T	T
        T	F	F	T	T	F
        F	T	T	F	T	T
        F	F	T	T	T	T
        Observation:

        • $p → q ≡ ¬q → ¬p$ and $q → p ≡ ¬p → ¬q$.

      ---

      Logical Equivalence Using Truth Tables

      
      

      • 
        
        

      • Example Volume: $p → q ext{ is equivalent to } ¬p ∨ q$

      • 
        
        

      • Truth Table Format:
        
        

        
        

        p	q	p → q	¬p	¬p ∨ q
        T	T	T	F	T
        T	F	F	F	F
        F	T	T	T	T
        F	F	T	T	T
        Conclusion: Both columns are identical, hence statements are logically equivalent.

        Module I: Logic and Proof Techniques

        Topics for This Lecture

        • Tautology

        • Contradiction

        • Contingency

        ---

        Tautology, Contradiction, and Contingency

        • Definitions:

          • Tautology: A statement that is always true.

          • Contradiction: A statement that is always false.

          • Contingency: A statement that can be either true or false.

        • Examples:

          • $p ∨ ¬p$: Tautology

          • $p ∧ ¬p$: Contradiction

        ---

        Logical Equivalence

        • Definition: Two propositions are logically equivalent if they always possess the same truth value expressed as
          $p ≡ q$ which means: “these two statements have identical truth tables.”

        • Another Formulation:

          • $(p ↔ q)$ is a tautology.

        • Example:

          • $p → q ≡ ¬p ∨ q$

        ---

        Logical Equivalences

        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 Laws

        • $¬(¬p) ≡ p$

        ---

        More Logical Equivalences

        Commutative Laws

        • $p ∨ q ≡ q ∨ p$

        • $p ∧ q ≡ q ∧ p$

        Associative Laws

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

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

        ---

        Distribution of Logical Equivalences

        Distributive Laws

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

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

        De Morgan Laws

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

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

        ---

        Final Logical Equivalences

        Absorption Laws

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

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

        Negation Laws

        • $p ∨ ¬p ≡ T$

        • $p ∧ ¬p ≡ F$

        ---

        Logical Equivalences Involving Conditionals

        • $p → q ≡ ¬p ∨ q$

        • $p → q ≡ ¬q → ¬p$

        • $¬(p → q) ≡ p ∧ ¬q$

        • $(p → q) ∧ (p → r) ≡ p → (q ∧ r)$

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

        ---

        Equivalences Involving Biconditionals

        • $p ↔ q ≡ (p → q) ∧ (q → p)$

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

        • $¬(p ↔ q) ≡ p ↔ ¬q$

        ---

        Exercises on Logical Equivalence

        • Avoid using truth tables; use logical equivalence laws to demonstrate the following:

          1. Show that $¬(p → q)$ is logically equivalent to $p ∧ ¬q$.

          2. Demonstrate that $¬(p ∨ (¬p ∧ q))$ is logically equivalent to $¬p ∧ ¬q$ by constructing a series of logical equivalences.

          3. Prove that $(p ∧ q) → (p ∨ q)$ is a tautology.

        ---

        Building Blocks in Logic

        • Literals: A propositional variable or its negation, e.g., $p$, $¬p$

        • Conjunction: An AND of literals, e.g., $(p ∧ q ∧ ¬r)$

        • Disjunction: An OR of literals, e.g., $(p ∨ ¬q ∨ r)$

        • A conjunction or disjunction may contain one or many literals.

        ---

        Disjunctive Normal Form (DNF)

        • Definition: A formula is in disjunctive normal form if it is a disjunction of one or more conjunctions of literals.

        • General Form: $(p ∧ q ∧ r) ∨ (¬p ∧ q) ∨ …$

        • Each conjunction represents a complete condition for the formula to hold true.

        ---

        Examples of DNF

        • Examples include:

          • $(p ∧ q) ∨ (¬r ∧ s)$

          • $(p ∧ q ∧ ¬r) ∨ (s ∧ t)$

          • $p ∨ (q ∧ r)$

        • Each expression is an OR of one or more AND-clauses.

        ---

        Conjunctive Normal Form (CNF)

        • Definition: A formula is in conjunctive normal form if it is a conjunction of one or more disjunctions of literals.

        • General Form: $(p ∨ q ∨ r) ∧ (¬p ∨ r) ∧ …$

        • Each disjunction reduces one way in which a formula could be false.

        ---

        Examples of CNF

        • Examples include:

          • $(p ∨ q) ∧ (¬r ∨ s)$

          • $(p ∨ ¬q ∨ r) ∧ (¬p ∨ r)$

          • $p ∧ (q ∨ r ∨ s)$

        • Each expression is an AND of one or more OR-clauses.

        ---

        Example: Converting to DNF

        • Conversion Example: Convert $(p ∨ q) ∧ (r ∨ s)$ to DNF.

          • Apply Distribution:

          • $(p ∧ r) ∨ (q ∧ r) ∨ (p ∧ s) ∨ (q ∧ s)$

        • Result: DNF is satisfied as a disjunction of conjunctions of literals.

        ---

        Example: Converting to CNF

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

          • Apply Distribution:

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

        • Result: Expressed as a conjunction of disjunctions of literals.

        ---

        Exercises: Identification

        • Classify each expression as CNF, DNF, both, or neither:

          1. $(p ∧ q ∧ r) ∨ (¬p ∧ s)$

          2. $(p ∨ q ∨ r) ∧ (¬p ∨ s) ∧ t$

          3. $(p ∧ q) ∨ (r ∨ s)$

          4. $¬(p ∨ q)$

        ---

        Exercises: Conversion

        • Convert each expression as required:

          1. Convert to DNF: $p ∧ (q → r)$

          2. Convert to CNF: $(p ∧ q) ∨ (r ∧ s)$

          3. Rewrite in both CNF and DNF: $(p ∨ q) → r$

        ---

        Module I: Logic and Proof Techniques

        Topics for This Lecture

        • Predicates

        • Quantifiers

        ---

        Predicate Logic

        • Definition: Propositional logic cannot adequately describe statements involving variables.

        • Predicate Logic extends propositional logic by introducing variables, predicates, and quantifiers:

          • Predicate Example:

          • $P(x): ext{“x is even”}$

        ---

        Predicates and Domains

        • A predicate becomes a proposition when a value is assigned to its variable.

        • Domain: The set from which variables take their values.

        • Example Predicates:

          • $P(x): x > 3$

          • Domain: Integers

          • $Q(x, y): x + y = 10$

          • Domain: Real numbers

        ---

        Universal Quantifier

        • Symbol: $∀$

        • Meaning: For all x, $P(x)$ is true.

        • Example:

          • $∀x (x^2 ext{ ≥ } 0)$

        ---

        Universal Quantifier — Examples

        • More examples:

          • $∀x (x + 1 > x)$ (domain: real numbers)

          • $∀n (n^2 ≥ n)$ (domain: integers)

          • Dependence: The truth of $∀x P(x)$ hinges on the domain chosen.

        ---

        Existential Quantifier

        • Symbol: $∃$

        • Meaning: There exists an x such that $P(x)$ is true.

        • Example:

          • $∃x (x^2 = 4)$

        ---

        Existential Quantifier — Examples

        • More examples:

          • $∃x (x^2 = 2)$ (domain: real numbers)

          • $∃n (n ext{ is prime and even})$

          • $∃x (x < 0)$

        ---

        Translating English Sentences

        • Quantifier Words:

          • Universal: all, every

          • Existential: some, there exists

          • None: translates to negation of existential quantifier

        ---

        Translation Examples

        • Let the domain be integers:

          • “Every integer is even or odd” translates to $∀x (x ext{ is even} ∨ x ext{ is odd})$

          • “There exists an integer that is even and prime” translates to $∃x (x ext{ is even} ∧ x ext{ is prime})$

        ---

        More Translation Examples

        • Let the domain be students:

          • “Every student has an ID card” translates to $∀x (x ext{ is a student} → x ext{ has ID card})$

          • “Some student has not submitted the assignment” translates to $∃x (x ext{ is a student} ∧ ¬S(x))$

        ---

        Exercises — Predicate Logic and Quantifiers

        • Translate into logical expressions (and state the domain clearly):

          1. “Every real number has a square greater than or equal to zero.”

          2. “There exists an integer that is divisible by both 2 and 3.”

          3. “Every student in the class has submitted the assignment.”

          4. “Some student in the class has not attended the lecture.”

        ---

        Exercises — Truth and Meaning

        1. Determine whether $∀x (x^2 > x)$ is true for the domains:

           • Integers

           • Real Numbers

        2. Determine whether $∃x (x^2 = x)$ is true for integers.

        3. Provide an instance where $∀x P(x)$ is false, but $∃x P(x)$ is true.

        ---

        Module I: Logic and Proof Techniques

        Topics for This Lecture

        • Methods of Proof

        • Mathematical Induction

        ---

        Methods of Proof

        • In mathematics, statements are established using logical arguments called proofs.

        • Common methods include:

          • Direct proof

          • Proof by contrapositive

          • Proof by contradiction

          • Proof by cases

          • Disproof by counterexample

          • Mathematical induction

        ---

        Direct Proof

        • Definition: A direct proof assumes the hypothesis is true and provides logical reasoning to show the conclusion follows.

        • Typical Form Format:

          • $p → q$

        • Example:

          • If $n$ is an even integer, then $n^2$ is also even.

        ---

        Direct Proof — Example

        • Assumption: Let $n$ be even, meaning $n = 2k$ for some integer $k$.

        • Proof Steps:

          • $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$

        • Conclusion: Hence, $n^2$ is even.

        ---

        Proof by Contrapositive

        • Definition: To prove $p → q$, instead prove the logically equivalent statement $¬q → ¬p$. This is useful when the contrapositive is easier to prove.

        • Example: “If $n^2$ is odd, then $n$ is odd.”

        ---

        Proof by Contrapositive — Example

        • Contrapositive Proof: Show that “If $n$ is even, then $n^2$ is even.”

        • Assumption: $n = 2k$. Then $n^2 = 4k^2$ - thus, $n^2$ is even. Therefore, if $n^2$ is odd, then $n$ must be odd.

        ---

        Proof by Contradiction

        • Definition: To prove $p$, assume $¬p$ is true, deriving a contradiction must show $(r ∧ ¬r)$.

        • Example Statement: “There is no smallest positive rational number.”

        ---

        Proof by Contradiction — Example

        • Assumption: Assume there exists a smallest positive rational number, $r$.

        • If we examine $rac{r}{2}$, it remains a positive rational number which contradicts $r$ being the smallest. Hence, such a smallest positive rational number cannot exist.

        ---

        Proof by Cases

        • Definition: A statement proved by categorizing the argument into finite cases, and proving each case’s validity.

        • Example: “For every integer $n$, $n^2 ≥ n$.”

        ---

        Proof by Cases — Example

        • Cases:

          • Case 1: $n ≥ 1$ - So, $n^2 ≥ n$

          • Case 2: $n = 0$ - Hence, $n^2 = n = 0$

          • Case 3: $n ≤ 0$ - Then, $n^2 ≥ 0 ≥ n$

        • Conclusion: Thus, $n^2 ≥ n$ for all integers $n$.

        ---

        Disproof by Counterexample

        • Definition: A universal statement negated by a single counterexample.

        • Example Statement: “All prime numbers are odd.”

        • Counterexample: 2 is both prime and even.

        ---

        Mathematical Induction

        • Description: A method to prove statements of the form $P(n)$ holds for all integers $n ≥ n_0$.

        • Consists of Two Steps:

          • Base Step: Verify $P(n_0)$ is true.

          • Inductive Step: Assume $P(k)$ is true, then show $P(k + 1)$ follows.

        ---

        Principle of Mathematical Induction

        • Requirements:

          1. Base step: Show $P(n_0)$ is true.

          2. Inductive hypothesis: Assume $P(k)$ is true.

          3. Inductive step: Prove $P(k + 1)$ is valid.

        • If both conditions hold, then $P(n)$ is valid for all $n ≥ n_0$.

        ---

        Induction — Example

        • Statement: Prove that $1 + 2 + … + n = rac{n(n + 1)}{2}$ for all integers $n ≥ 1$.

        • Base step (n = 1):

          • $1 = rac{1(1 + 1)}{2}$

        • Inductive hypothesis: Assume true for $n = k$

          • $1 + 2 + … + k = rac{k(k + 1)}{2}$

        • Inductive step:

          • Show for $P(k + 1):$
            $1 + 2 + … + k + (k + 1) = rac{k(k + 1)}{2} + (k + 1) = rac{(k + 1)(k + 2)}{2}$

        ---

        Exercises: Methods of Proof

        1. Directly prove that the sum of two even integers is even.

        2. Contrapositive: If $n^2$ is divisible by 3, then $n$ is divisible by 3.

        3. Prove by contradiction that $ext{√2 is irrational}$.

        4. Disprove the statement: For all integers $n$, $n^2 + n + 41$ is prime.

        5. Prove by cases that $|x| ≥ 0$ for all real numbers $x$.

        ---

        Exercises: Mathematical Induction

        1. Prove that $1 + 3 + 5 + … + (2n - 1) = n^2$ for all $n ≥ 1$ using induction.

        2. Prove $2^n ≥ n + 1$ for integers $n ≥ 1$ using induction.

        3. Show: $3 | (n^3 − n)$ for all integers $n ≥ 1$.

        ---

        Module I: Logic and Proof Techniques

        Tutorial

        ---

        Exercises: Propositions

        1. Determine which sentences are propositions, and justify the answer.

           • “The sum of two even integers is even.”

           • $n^2 - 1 = 0.$

           • “There are infinitely many prime numbers.”

        2. Give two different propositions that share the same truth value.

        ---

        Exercises: Logical Connectives

        • Let p: “The server is running.”

        • Let q: “The network is available.”

        • Let r: “The website is accessible.”

        1. Write the following statements using symbols:

           • “The server is running and the network is available.”

           • “The website is accessible only if the server is running.”

           • “Either the network is available or the website is accessible, but not both.”

        2. Write an English sentence corresponding to: $(p ∧ q) → r$.

        ---

        Exercises: Truth Tables

        1. Construct the truth table for: $(p ∨ q) ∧ ¬r$

        2. Construct the truth table for: $¬(p ∧ q) → r$

        3. From the truth table, assess whether $(p ∨ q) → (q ∨ p)$ is a tautology.

        ---

        Exercises: Conditional Statements

        1. Write the converse, inverse, and contrapositive of: “If a function is differentiable, then it is continuous.”

        2. Identify which of the four statements (original, converse, inverse, contrapositive) are logically equivalent.

        ---

        Exercises: Logical Equivalence

        • Avoid truth tables; use logical equivalence laws to show:

        1. $p ∨ (q ∧ p) ≡ p$

        2. $(p → r) ∧ (q → r) ≡ (p ∨ q) → r$

        3. Determine if $(p ↔ q) ∧ (q ↔ r)$ is logically equivalent to $p ↔ r$.

        ---

        Exercises: Logical Equivalence

        • Avoid truth tables; apply logical equivalence laws only:

        1. Prove that $¬(p ∧ (p ∨ q)) ≡ ¬p$.

        2. Show that $(p → q) ∧ (p → r) ≡ p → (q ∧ r)$.

        3. Prove that $(p ∨ q) ∧ (¬p ∨ r) ≡ (p → r) ∨ q$.

        4. Assess whether $(p ↔ q) ∨ (p ↔ ¬q)$ is a tautology.

        5. Prove that $¬(p ∨ q) ∨ (p ∧ q) ≡ ¬p ↔ ¬q$.

        6. Test whether $(p → q) ↔ (¬q → ¬p)$ is a tautology.

        ---

        Exercises: Tautology, Contradiction, Contingency

        1. Classify these propositions:

           • $(p ∧ q) → p$

           • $(p ∧ ¬p) ∨ q$

           • $p ↔ ¬p$

        2. Provide a proposition with two variables neither classified as a tautology nor contradiction.

        ---

        Exercises: CNF and DNF

        • Rewrite the following propositions in the required normal form:

        1. Convert to disjunctive normal form: $(p ∨ q) ∧ (r ∨ s)$

        2. Convert to conjunctive normal form: $p ∨ (q ∧ r)$

        3. Rewrite the following in disjunctive normal form: $¬(p → q)$.

        ---

        Exercises: CNF and DNF

        • Rewrite as indicated:

        1. Convert to conjunctive normal form: $(p ∧ q) ∨ r$

        2. Convert into both CNF and DNF: $(p ∨ q) → r$

        3. Classify the expression $(p ∨ q) ∧ (¬p ∨ r)$ as CNF, DNF, both, or neither.

        ---

        Exercises: Translating English Sentences

        • Translate into logical notation. Specify the domain:

        1. “Every rational number has a decimal expansion.”

        2. “There exists a natural number that is divisible by every natural number.”

        3. “No employee in the company works on all days of the week.”

        4. “There is a machine that can perform every assigned task.”

        ---

        Exercises: Predicate Logic and Quantifiers

        1. Let $P(x):$ “x is divisible by 3.”

           • Write in symbols: “Every integer greater than 6 is divisible by 3.”

           • “Some integer greater than 6 is divisible by 3.”

        2. Write the negation of: $∃x ∀y (x ≤ y)$.

        3. Establish whether the following statement is true or false; justify:
           $∀x ∃y (x + y = 0)$.

        ---

        Exercises: Direct Proof

        1. Prove directly that the sum of two odd integers is even.

        2. Prove: if $n$ is an integer divisible by 6, then $n$ is also divisible by 3.

        3. Prove the product of two consecutive integers is even.

        ---

        Exercises: Proof by Contrapositive

        1. Prove by contrapositive: if $n^2$ is even, then $n$ is even.

        2. Prove by contrapositive: if $ab$ is irrational, then at least one of $a$ or $b$ is irrational.

        3. Prove by contrapositive: if $n$ is not divisible by 3, then $n^2$ is not divisible by 3.

        ---

        Exercises: Proof by Contradiction

        1. Prove by contradiction that $ext{√3 is irrational}$.

        2. Show there is no smallest positive real number.

        3. Prove that there exists an infinite number of prime numbers.

        ---

        Exercises: Proof by Cases

        1. Prove by cases that for every integer $n$, $n^2 ≥ n$.

        2. Prove that $|x| = x$ if $x ≥ 0$ and $|x| = -x$ if $x < 0$.

        3. Prove by cases that $n^2$ is either even or odd for every integer $n$.

        ---

        Exercises: Disproof by Counterexample

        1. Disprove: “All integers of the form $n^2 + n + 41$ are prime.”

        2. Disprove: “For all real numbers $x$, $ext{√}x^2 = x$.”

        3. Disprove: “Every continuous function is differentiable.”

        ---

        Exercises: Mathematical Induction

        1. Prove using induction that $1 + 2 + 4 + … + 2^n = 2^{n+1} − 1$ for all integers $n ≥ 0$.

        2. Prove using induction that $n! ≥ 2^{n−1}$ for all integers $n ≥ 1$.

        3. Prove that $1^2 + 2^2 + … + n^2 = rac{n(n + 1)(2n + 1)}{6}$ for all integers $n ≥ 1$.