CSE230-Lecture1

CSE 230 - Discrete Mathematics

1. Definition of Discrete Mathematics

  • Discrete Mathematics: The study of discrete objects (distinct or not connected).

  • Common Property: It is a collective term for branches of mathematics that deal with discrete rather than continuous structures.

2. Discrete vs. Continuous Mathematics

  • Fields of Mathematics are divided into:

    1. Discrete Mathematics

    2. Continuous Mathematics

3. Examples of Discrete and Continuous Objects

  • Discrete Objects:

    • Natural Numbers: 1, 2, 3, 4, 5...

  • Continuous Objects:

    • Real Numbers: Infinite possibilities between any two points (e.g., between 0 and 1).

4. Importance of Studying Discrete Mathematics

  • Foundation Course: Essential for computer science.

  • Skills Developed:

    • Logical Reasoning

    • Analytical Ability

    • Problem-Solving Skills

  • Applications: Useful in advanced fields such as programming and cryptography.

5. Propositional Logic

  • Components of Propositional Logic:

    • Proposition: A declarative sentence that can be TRUE or FALSE.

    • Examples:

      • True: "Delhi is the capital of India."

      • False: "London is in Denmark."

6. Logic

  • Definition of Logic: The science of reasoning, used to understand and reason about mathematical statements.

  • Function: With logic, mathematical statements can be proven or disproven precisely.

7. Examples of Propositions and Non-Propositions

  • Propositions:

    1. "Delhi is the capital of India." (True)

    2. "Water froze this morning." (True)

    3. "1 + 1 = 2." (True)

  • Non-Propositions:

    1. "What time is it?"

    2. "x + 1 = 2" (depends on value of x)

    3. "Send us your resume before 11 PM."

8. Compound Propositions

  • Definitions:

    • Atomic Statements: Basic statements that cannot be broken down further.

    • Logical Connectives: Combine atomic statements (e.g., AND, OR).

  • Examples:

    • Statement 1: "Adam is good in playing football."

    • Statement 2: "Adam is good in playing football and this time he is representing his college at National level."

9. Propositional Variables

  • Example: For statements involving Adam, let:

    • P = "Adam is good in playing football."

    • q = "This time he is representing his college at National level."

    • Combined: P ^ q (P and q).

10. Logical Operators

  • Key Logical Operators:

    1. Negation

    2. Conjunction

    3. Disjunction

    4. Exclusive OR

    5. Implication

    6. Biconditional

11. Negation

  • Definition: The negation of a proposition P, denoted P (or sometimes ¬P), states "It is not the case that P."

    • Example: If P = "Adam and Eve lived together for many years," then ¬P = "It is not the case that Adam and Eve lived together for many years."

12. Truth Tables

  • Truth Table for P and Negation P:

    • P | ¬P

    • T | F

    • F | T

13. Conjunction and Disjunction

  • Conjunction (p ∧ q): True when both p and q are true.

    • Example: "I am at home and it is raining."

  • Disjunction (p ∨ q): True when at least one of p or q is true.

    • Example: "I am at home or it is raining."

14. Exclusive OR

  • Definition: Used in conditions where one option or the other is required, but not both (e.g., in job requirements).

  • Example: C++ or Java experience is mandatory.