Tag: Unit – 1 : Discrete Structures and Optimization

UGC NETComputer Science Unit 1 – Counting, Mathematical Induction and Discrete Probability
Go back to UGC NET COMUPTER SCIENCE

UNIT 1 — Counting, Mathematical Induction and Discrete Probability

(UGC NET)

(Counting • Pigeonhole Principle • Permutations • Combinations • Inclusion–Exclusion • Mathematical Induction • Probability • Bayes’ Theorem)

1. BASICS OF COUNTING — DEFINITIONS

Definition 1: Counting Principle (Product Rule)

If an action consists of k independent stages, and the stages can be performed in

$n_{1}, n_{2}, \dots, n_{k} ways respectively,$

then the total number of ways of performing the action is

$n_{1} \times n_{2} \times \dots \times n_{k} .$

Definition 2: Sum Rule (Addition Principle)

If an action can be performed in m ways or n ways, and the two sets of possibilities are mutually exclusive,

$Total ways = m + n .$

Definition 3: Factorial (n!)

For any positive integer n:

$n! = n (n - 1) (n - 2) \dots 1$

and by definition

$0! = 1.$

2. PERMUTATIONS — DEFINITIONS

Definition 4: Permutation

A permutation is an arrangement of objects in a specific order.

Definition 5: r-Permutation of n Objects

The number of ways to arrange r objects out of n:

$^{n} P_{r} = \frac{n!}{(n - r)!}$

Definition 6: Permutation with Repetition

If among n objects,
- $n_{1}$ are alike,
- $n_{2}$ are alike, etc.,
then number of distinct permutations:

$\frac{n!}{n_{1}! n_{2}! \dots}$

3. COMBINATIONS — DEFINITIONS

Definition 7: Combination

A combination is a selection of r objects from n objects where order does not matter.

Definition 8: r-Combination of n Objects

$^{n} C_{r} = \frac{n!}{r! (n - r)!}$

Key Relation

$^{n} P_{r} =^{n} C_{r} \cdot r!$

4. PIGEONHOLE PRINCIPLE — DEFINITIONS & STATEMENTS

Definition 9: Pigeonhole Principle (Basic)

If more than n objects are placed into n boxes, then at least one box contains more than one object.

Formal Statement:
If $n + 1$ objects are placed into $n$ boxes, at least one box contains ≥ 2 objects.

Definition 10: Generalized Pigeonhole Principle

If N objects are placed into k boxes, then at least one box contains

$⌈ \frac{N}{k} ⌉$

objects.

5. INCLUSION–EXCLUSION PRINCIPLE — STATEMENTS

Definition 11: Inclusion–Exclusion Principle (Two Sets)

For any two sets A and B,

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣ .$

Definition 12: Inclusion–Exclusion (Three Sets)

$∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣ .$

6. MATHEMATICAL INDUCTION — DEFINITIONS & STEPS

Definition 13: Principle of Mathematical Induction

Let $P (n)$ be a statement depending on a natural number n.
If:
1. Base Step: $P (1)$ is true.
2. Induction Step: $P (k) \Rightarrow P (k + 1)$ for all natural numbers k,
Then $P (n)$ is true for all natural numbers.

Definition 14: Strong Induction

A statement $P (n)$ is true for all natural numbers n if:
1. $P (1)$ is true.
2. Assuming all of $P (1), P (2), \dots, P (k)$ are true implies $P (k + 1)$ .
7. PROBABILITY — DEFINITIONS

Definition 15: Sample Space (S)

The set of all possible outcomes of an experiment.

Definition 16: Event (E)

Any subset of the sample space.

Definition 17: Probability of an Event

If all outcomes are equally likely:

$P (E) = \frac{∣ E ∣}{∣ S ∣}$

Definition 18: Complement of an Event

$P (E^{'}) = 1 - P (E)$

Definition 19: Conditional Probability

$P (A ∣ B) = \frac{P (A \cap B)}{P (B)}, P (B) > 0$

Definition 20: Independent Events

Two events A and B are independent if:

$P (A \cap B) = P (A) P (B)$

8. BAYES’ THEOREM — STATEMENT

Definition 21: Bayes’ Theorem

If $A_{1}, A_{2}, \dots, A_{n}$ form a partition of the sample space and B is any event with $P (B) > 0$ , then:

$P (A_{i} ∣ B) = \frac{P (B ∣ A_{i}) P (A_{i})}{\sum_{j = 1}^{n} P (B ∣ A_{j}) P (A_{j})}$

This theorem is used to reverse conditional probability.
December 4, 2025
UGC NET Computer Science UNIT 1 – Mathematical Logic
Go back to UGC NET COMUPTER SCIENCE

UNIT – 1 : DISCRETE STRUCTURES & LOGIC

Mathematical Logic
(Complete Conceptual Notes)

PART A — MATHEMATICAL LOGIC

1. PROPOSITIONAL LOGIC

1.1 What is a Proposition?

A proposition is a declarative sentence that expresses a fact and has a definite truth value:
either True (T) or False (F), but never both at the same time.

✔ Examples of Propositions (Meaningful Facts)
- “7 is a prime number.” → True
- “The Earth has two moons.” → False
✘ Not Propositions (No truth value / not a statement of fact)
- “Shut the door.” (command)
- “Where are you?” (question)
- “x is greater than 10.” (truth depends on x → open sentence)
Why important?
Because logic operates only on propositions with fixed truth values.

1.2 Propositional Variables

We use letters like p, q, r to represent propositions.

Example:
- Let p = “It is raining.”
- Let q = “The ground is wet.”
2. LOGICAL CONNECTIVES WITH STATEMENTS

Connectives combine propositions to form compound statements.

2.1 Negation (¬p)

Statement Form:

“NOT p” means that whatever p asserts, the negation asserts the opposite.

Example:
- p = “The sky is blue.”
- ¬p = “The sky is not blue.”
Truth rule:
- If p is true → ¬p is false
- If p is false → ¬p is true
2.2 Conjunction (p ∧ q)

Statement Form:

“p AND q” means both statements must be true simultaneously.

Example:
- p: “The power is on.”
- q: “The fan is running.”
- p ∧ q: “The power is on and the fan is running.”
2.3 Disjunction (p ∨ q)

Statement Form:

“p OR q” means at least one of the two statements must be true.

Example:
- p: “I will study.”
- q: “I will watch a movie.”
- p ∨ q: “I will study or watch a movie (or both).”
2.4 Implication (p → q)

Statement Form:

“If p is true, then q must also be true.”

Example:
- p: “It rains.”
- q: “The ground gets wet.”
- p → q: “If it rains, then the ground gets wet.”
Exception:
If it does NOT rain, the statement is considered true regardless of the ground’s condition.

2.5 Biconditional (p ↔ q)

Statement Form:

“p is true if and only if q is true.”

Example:
- p: “You pass the course.”
- q: “You score ≥ 40.”
- p ↔ q: “You pass the course if and only if you score ≥ 40.”
True when both p and q have the same truth value.

3. TRUTH TABLES (Purpose + Use)

Truth tables allow us to compute the truth value of compound propositions under all possible combinations.

4. PROPOSITIONAL EQUIVALENCES

Logical equivalences indicate when two compound statements always have the same truth value.

4.1 Double Negation

Statement:

“Saying ‘NOT NOT p’ means the same as saying p.”

Symbolically:
¬(¬p) ≡ p

4.2 De Morgan’s Laws

These describe how negation interacts with AND/OR.

Statements:
- “The negation of ‘p AND q’ is the same as ‘NOT p OR NOT q’.”
- “The negation of ‘p OR q’ is the same as ‘NOT p AND NOT q’.”
4.3 Implication Law

Statement:

“‘If p then q’ is equivalent to saying ‘Either p is false OR q is true.’”

p → q ≡ ¬p ∨ q

This is core to CNF/DNF.

4.4 Contrapositive (Key Logical Principle)

Statement:

“‘If p then q’ is logically equivalent to ‘If NOT q then NOT p’.”

4.5 Biconditional Law

Statement:

“‘p if and only if q’ means both ‘if p then q’ AND ‘if q then p’ must be true.”

5. NORMAL FORMS (CNF, DNF)

5.1 Disjunctive Normal Form (DNF)

Statement:

A formula is in DNF when it is expressed as an OR of AND terms.

Example Statement:
“p AND q is true OR p is false AND r is true.”

Symbolic:
(p ∧ q) ∨ (¬p ∧ r)

5.2 Conjunctive Normal Form (CNF)

Statement:

A formula is in CNF when it is expressed as an AND of OR terms.

Example Statement:
“Either p or q is true AND either p or r is true.”

Symbolic:
(p ∨ q) ∧ (p ∨ r)

PART B — PREDICATE LOGIC

6. PREDICATES

A predicate is an expression involving variables that becomes a proposition when specific values are substituted.

Example:
P(x): “x is divisible by 3.”
— P(6) is True
— P(7) is False

7. QUANTIFIERS

7.1 Universal Quantifier (∀)

Statement Meaning:

“∀x P(x)” means “For every x, P(x) is true.”

Example Statement:
“Every natural number is greater than or equal to 0.”

7.2 Existential Quantifier (∃)

Statement Meaning:

“∃x P(x)” means “There exists at least one x such that P(x) is true.”

Example Statement:
“There exists a number divisible by 6.”

8. NESTED QUANTIFIERS

Example 1

∀x ∃y P(x,y)

Statement Meaning:

“For every x, there exists a y such that P(x,y) holds.”

Example in math:
“For every number x, there is a number y greater than x.”

Example 2

∃y ∀x P(x,y)

Statement Meaning:

“There exists a single y such that for every x, P(x,y) holds.”

Example:
“There is one number y greater than all numbers x.”
→ False (no largest integer)

9. NEGATION OF QUANTIFIERS (WITH EXPLANATORY STATEMENTS)

Universal to Existential

¬∀x P(x)

Statement:

“It is NOT true that P(x) holds for all x”
⟹ “There exists at least one x for which P(x) does not hold.”

Existential to Universal

¬∃x P(x)

Statement:

“It is NOT true that there exists an x with P(x)”
⟹ “For every x, P(x) is false.”

10. RULES OF INFERENCE (WITH NATURAL LANGUAGE MEANINGS)

10.1 Modus Ponens

p, and p → q

Statement Meaning:

“If p is true, and p implies q, then q must be true.”

10.2 Modus Tollens

¬q, and p → q

Statement Meaning:

“If q is false, and p implies q, then p must be false.”

10.3 Hypothetical Syllogism

p → q, q → r

Statement Meaning:

“If p implies q, and q implies r, then p implies r.”

10.4 Simplification

p ∧ q
→ p

Statement:

“If both p and q are true, then p is true.”

10.5 Addition

p
→ p ∨ q

Statement:

“If p is true, then ‘p OR q’ is automatically true.”

10.6 Conjunction

p, q
→ p ∧ q

Statement:

“If p is true and q is true, then ‘p AND q’ is true.”
December 3, 2025

Tag: Unit – 1 : Discrete Structures and Optimization

UGC NETComputer Science Unit 1 – Counting, Mathematical Induction and Discrete Probability

Go back to UGC NET COMUPTER SCIENCE

(UGC NET)

(Counting • Pigeonhole Principle • Permutations • Combinations • Inclusion–Exclusion • Mathematical Induction • Probability • Bayes’ Theorem)

1. BASICS OF COUNTING — DEFINITIONS

Definition 1: Counting Principle (Product Rule)

Definition 2: Sum Rule (Addition Principle)

Definition 3: Factorial (n!)

2. PERMUTATIONS — DEFINITIONS

Definition 4: Permutation

Definition 5: r-Permutation of n Objects

Definition 6: Permutation with Repetition

3. COMBINATIONS — DEFINITIONS

Definition 7: Combination

Definition 8: r-Combination of n Objects

Key Relation

4. PIGEONHOLE PRINCIPLE — DEFINITIONS & STATEMENTS

Definition 9: Pigeonhole Principle (Basic)

Definition 10: Generalized Pigeonhole Principle

5. INCLUSION–EXCLUSION PRINCIPLE — STATEMENTS

Definition 11: Inclusion–Exclusion Principle (Two Sets)

Definition 12: Inclusion–Exclusion (Three Sets)

6. MATHEMATICAL INDUCTION — DEFINITIONS & STEPS

Definition 13: Principle of Mathematical Induction

Definition 14: Strong Induction

7. PROBABILITY — DEFINITIONS

Definition 15: Sample Space (S)

Definition 16: Event (E)

Definition 17: Probability of an Event

Definition 18: Complement of an Event

Definition 19: Conditional Probability

Definition 20: Independent Events

8. BAYES’ THEOREM — STATEMENT

Definition 21: Bayes’ Theorem

UGC NET Computer Science UNIT 1 – Mathematical Logic

Go back to UGC NET COMUPTER SCIENCE

UNIT – 1 : DISCRETE STRUCTURES & LOGIC

Mathematical Logic

(Complete Conceptual Notes)

PART A — MATHEMATICAL LOGIC

1. PROPOSITIONAL LOGIC

1.1 What is a Proposition?

✔ Examples of Propositions (Meaningful Facts)

✘ Not Propositions (No truth value / not a statement of fact)

1.2 Propositional Variables

2. LOGICAL CONNECTIVES WITH STATEMENTS

2.1 Negation (¬p)

Statement Form:

2.2 Conjunction (p ∧ q)

Statement Form:

2.3 Disjunction (p ∨ q)

Statement Form:

2.4 Implication (p → q)

Statement Form:

2.5 Biconditional (p ↔ q)

Statement Form:

3. TRUTH TABLES (Purpose + Use)

4. PROPOSITIONAL EQUIVALENCES

4.1 Double Negation

Statement:

4.2 De Morgan’s Laws

Statements:

4.3 Implication Law

Statement:

4.4 Contrapositive (Key Logical Principle)

Statement:

4.5 Biconditional Law

Statement:

5. NORMAL FORMS (CNF, DNF)

5.1 Disjunctive Normal Form (DNF)

Statement:

5.2 Conjunctive Normal Form (CNF)

Statement:

PART B — PREDICATE LOGIC

6. PREDICATES

7. QUANTIFIERS

7.1 Universal Quantifier (∀)

Statement Meaning:

7.2 Existential Quantifier (∃)