Unit 1 - Set and Propositions Notes | Discrete Mathematics SPPU

Introduction to Discrete Mathematics

Discrete Mathematics is a branch of mathematics that deals with distinct, separated values rather than continuous ranges. Unlike calculus, which focuses on continuous changes and smooth curves, discrete mathematics works with countable elements like integers, graphs, and logical statements.

The significance of discrete mathematics in computer engineering is immense. Computers operate digitally, meaning they process information in discrete steps (0s and 1s). Everything from designing algorithms, organizing databases, securing data with cryptography, to building computer networks relies heavily on the concepts of discrete mathematics.

Hinglish Explanation: Discrete mathematics un topics par focus karta hai jo fixed aur alag-alag hote hain, jaise counting ya logic. Computer science puri tarah se discrete concepts (0 aur 1) par chalti hai, isiliye programming aur algorithms samajhne ke liye ye subject sabse zaroori hai.

Propositional Logic

Logic is the foundation of mathematical reasoning and computer programming. In discrete mathematics, we begin with Propositional Logic, which deals with propositions.

Definition of a Proposition

A proposition is a declarative sentence that is either strictly True (T) or strictly False (F), but never both.

• Valid Proposition: "Delhi is the capital of India." (True)

• Valid Proposition: "2 + 2 = 5." (False)

• Not a Proposition: "What time is it?" (It is a question, not a statement of fact.)

• Not a Proposition: "x + 5 = 10." (We cannot determine if it is true or false without knowing the value of x.)

Logical Connectives

To build complex logical statements, we combine simple propositions using logical connectives. Let 'p' and 'q' be two propositions.

1. Negation (NOT): Reverses the truth value of a proposition. Denoted by ~p.

   • If p is True, ~p is False.

2. Conjunction (AND): Denoted by p ^ q.

   • It is True only if both p and q are True.

3. Disjunction (OR): Denoted by p v q.

   • It is True if at least one of p or q is True.

4. Implication (IF...THEN): Denoted by p -> q.

   • It is False ONLY when p is True but q is False. In all other cases, it is True.

5. Biconditional (IF AND ONLY IF): Denoted by p <-> q.

   • It is True if both p and q have the exact same truth value.

Hinglish Explanation: Implication (p -> q) thoda confusing ho sakta hai. Ise aise samjhein: Agar condition p (jaise 'baarish hui') true hai, aur result q (jaise 'main chata lunga') false ho gaya, tabhi statement galat (false) maani jayegi. Baaki sab cases mein ye true hoti hai.

Propositional Equivalences

Two logical expressions are considered propositionally equivalent if they have the exact same truth values in all possible scenarios. We denote equivalence using the == symbol or an equal sign with three lines.

Key Classifications

• Tautology: A compound proposition that is always True, no matter what the individual truth values are. Example: p v ~p (It is raining OR it is not raining).

• Contradiction: A compound proposition that is always False. Example: p ^ ~p.

• Contingency: A proposition that is neither a tautology nor a contradiction (it can be true or false depending on the variables).

De Morgan's Laws

These are two highly important rules used to simplify logical expressions in programming and circuit design:

1. ~(p ^ q) == ~p v ~q

2. ~(p v q) == ~p ^ ~q

Application of Propositional Logic: Translating English Sentences

Computers cannot understand human language directly. We must translate English sentences into logical expressions to build expert systems and artificial intelligence.

Example 1:

English: "If it rains today, I will stay at home."

• Let p = "It rains today."

• Let q = "I will stay at home."

• Logical Translation: p -> q

Example 2:

English: "You can access the internet only if you have a password and pay the subscription fee."

• Let a = "You can access the internet."

• Let p = "You have a password."

• Let f = "You pay the subscription fee."

• Logical Translation: a -> (p ^ f)

Proof by Mathematical Induction

Mathematical induction is a powerful proof technique used to prove that a mathematical statement is true for all natural numbers (1, 2, 3, ...).

Standard Mathematical Induction

It involves two main steps:

1. Base Step: Prove that the statement is true for the lowest possible value, usually n = 1.

2. Inductive Step:

   • Inductive Hypothesis: Assume that the statement is true for an arbitrary positive integer n = k.

   • Proof: Using the assumption from the hypothesis, mathematically prove that the statement holds true for n = k + 1.

Real-life Analogy: Falling dominoes. If you push the first domino (Base step), and you know that any falling domino will push the one right next to it (Inductive step), you can guarantee that all dominoes will fall.

Hinglish Explanation: Mathematical Induction bilkul dominos girane jaisa hai. Agar pehla domino gira (Base step), aur humne ye man liya ki har domino apne aage wale ko girayega (Inductive hypothesis), toh iska matlab saari line aage tak girti chali jayegi.

Strong Mathematical Induction

Sometimes, assuming the statement is true only for n = k is not enough to prove it for n = k + 1. This is where Strong Mathematical Induction comes in.

• In the Inductive Hypothesis of Strong Induction, we assume that the statement is true for all integer values from the base case up to k (e.g., n = 1, 2, 3, ..., k).

• Then, we use this broader assumption to prove that it is true for n = k + 1.

Sets: Naïve Set Theory vs. Axiomatic Set Theory

A set is an unordered collection of distinct objects, known as elements or members.

Naïve Set Theory (Cantorian Set Theory)

Introduced by Georg Cantor in the late 19th century, Naïve Set Theory defined a set simply as any collection of definite, distinguishable objects that share a common property.

• Limitation: Because the definition was too loose, it allowed for logical paradoxes. The most famous is Russell's Paradox: "Does the set of all sets that do not contain themselves, contain itself?" This created a logical loop that Naïve Set Theory could not solve.

Axiomatic Set Theory

To fix the paradoxes found in Naïve Set Theory, mathematicians developed Axiomatic Set Theory (the most common being the Zermelo-Fraenkel set theory).

• Feature: Instead of saying "any collection can be a set," it provides a strict set of axioms (rules) that dictate exactly how sets can be formed and operated on, preventing logical contradictions.

Set Operations

Let A and B be two sets. We can perform various operations to combine or compare them.

1. Union (A U B): A new set containing all elements that are in A, or in B, or in both. (No duplicates are kept).

2. Intersection (A n B): A new set containing only the elements that are common to both A and B.

3. Difference (A - B): A new set containing elements that are in A but NOT in B.

4. Complement (A'): A set containing all elements in the universal set that are NOT present in set A.

Cardinality of a Set

The cardinality of a set refers to the total number of distinct elements present inside it. It is denoted by |A|.

• If A = {2, 4, 6, 8}, then the cardinality is |A| = 4.

Principle of Inclusion and Exclusion (PIE)

When calculating the cardinality of the union of two sets, simply adding their cardinalities might count the overlapping elements twice. The Principle of Inclusion and Exclusion corrects this.

Formula for two sets:

|A U B| = |A| + |B| - |A n B|

Practical Example:

In a class, 30 students play cricket (Set A) and 20 play football (Set B). 5 students play both (A n B). How many total unique students play at least one sport?

• |A U B| = 30 + 20 - 5 = 45 students.

Hinglish Explanation: Principle of Inclusion and Exclusion isiliye use hota hai taaki common elements do baar count na ho jayein. Cricket aur football wale example mein, jo 5 bachhe dono khelte hain, wo 30 mein bhi aagaye aur 20 mein bhi. Isiliye hum unhe ek baar minus (subtract) kar dete hain.

Types of Sets

1. Bounded and Unbounded Sets

• Bounded Set: A set is bounded if there are limits (upper and lower bounds) to the values its elements can take. For example, the set of numbers between 1 and 100.

• Unbounded Set: A set is unbounded if it extends infinitely in one or both directions without any limits. For example, the set of all positive integers (1, 2, 3, ... goes on forever).

2. Finite and Infinite Sets

• Finite Set: A set with a specific, countable number of elements. The counting process will eventually come to an end. Example: Vowels in the English alphabet = {a, e, i, o, u}.

• Infinite Set: A set where the elements go on forever. You can never finish counting them. Example: The set of all odd numbers.

3. Power Set

The Power Set of a given set A is the set of ALL possible subsets of A, including the empty set and the set A itself.

• Formula: If a set has 'n' elements, its power set will have 2^n elements.

• Example: Let A = {1, 2}. The subsets are {}, {1}, {2}, {1, 2}. The Power Set has 2^2 = 4 elements.

Advanced Cardinality: Countable and Uncountable Sets

Not all infinite sets are the same size. Discrete mathematics categorizes infinity into two types based on countability.

Countably Infinite Sets

A set is countably infinite if you can arrange its elements in a sequence and assign a unique natural number (1, 2, 3...) to each element. Even though the set is infinite, you can systematically "count" through it.

• Example: The set of Integers (..., -2, -1, 0, 1, 2, ...). You can map them to natural numbers like this: 0 -> 1, 1 -> 2, -1 -> 3, 2 -> 4, -2 -> 5, and so on.

Uncountably Infinite Sets

A set is uncountably infinite if its elements cannot be paired up with the natural numbers. There are simply "too many" elements, and any attempt to list them will always leave some out.

• Example: The set of Real Numbers between 0 and 1. Between any two fractions or decimals, there are infinitely more decimals.

The Diagonalization Argument

To prove that real numbers are uncountably infinite, Georg Cantor introduced the Diagonalization Argument.

How it works (Simple concept):

1. Assume you have successfully created a complete, infinite list of every possible decimal number between 0 and 1.

2. Cantor proved this assumption wrong by constructing a completely "new" number.

3. He looked at the diagonal digits of the numbers in your list: the 1st digit of the 1st number, the 2nd digit of the 2nd number, the 3rd digit of the 3rd number, and so on.

4. He then changed every single one of those diagonal digits (e.g., if it was a 4, he made it a 5).

5. The resulting new decimal number is guaranteed to be different from the 1st number (because its 1st digit is different), different from the 2nd number (because its 2nd digit is different), and so on.

6. Since a new number was created that was not on your "complete" list, it proves that it is impossible to list all real numbers. Thus, they are uncountably infinite.

Hinglish Explanation: Cantor ka Diagonalization Argument prove karta hai ki real numbers ko gina nahi ja sakta. Usne ek trick lagayi: maan lijiye aapne saare decimal numbers ki ek list bana li. Cantor ne us list ke har number ka diagonal digit badal kar ek naya number bana diya. Ab kyunki ye naya number list mein nahi tha, ye sabit ho gaya ki aap real numbers ki koi complete list bana hi nahi sakte.

Important Note

Understanding the difference between countably infinite (like integers) and uncountably infinite (like real numbers) is crucial for advanced computer science topics like the Theory of Computation. Computers are finite machines, and recognizing what cannot be computed or counted (uncountable sets) helps engineers understand the theoretical limits of computation.

Key Points Summary (Revision)

• Propositional Logic: Deals with True/False statements manipulated by AND, OR, NOT, Implication, and Biconditional connectives.

• Mathematical Induction: Proves a statement for all natural numbers using a Base Step and an Inductive Step. Strong induction assumes the statement is true for all previous values up to k.

• Axiomatic Set Theory: Solves the logical paradoxes present in Naïve Set Theory by enforcing strict rules.

• Principle of Inclusion and Exclusion: Formula used to count elements in unions without double-counting the intersections.

• Diagonalization Argument: Cantor’s brilliant method proving that the set of real numbers is uncountably infinite.

Short Conclusion

Discrete Mathematics provides the vocabulary and logical framework required for computer engineering. From translating real-world conditions into machine logic using propositional equivalences, to understanding the limits of data through set theory and countability, mastering these concepts equips students with the exact analytical skills needed to design efficient algorithms, secure systems, and powerful databases.

SEO Keywords Section

Search keywords related to this topic:

Discrete Mathematics basics, Propositional Logic in discrete math, Logical connectives AND OR NOT, Propositional Equivalences Tautology Contradiction, Translating English Sentences into Propositional Logic, Proof by Mathematical Induction steps, Difference between Mathematical Induction and Strong Induction, Naïve Set Theory vs Axiomatic Set Theory, Principle of inclusion and exclusion examples, Bounded and Unbounded Sets, Cantor Diagonalization Argument explained simply, Countably Infinite and Uncountably Infinite Sets, Power set formula, Discrete math computer science notes, Set operations and Cardinality.