Discrete Structures | Semester 3 Core Notes
Semester 3 - Page 3: Discrete Structures. 36 numbered topics, highlighted definitions, worked examples, answered exam questions, three diagrams and four complete Python 3 checks. General common-core BTech CSE guide, not an official assessed syllabus or past-paper prediction. Compare your assigned outline.
Topic map
- Propositions and connectives
- Implication and equivalence
- Truth tables and normal forms
- Logical laws and inference
- Predicates and quantifiers
- Proof methods
- Sets and operations
- Power sets and products
- Functions and mappings
- Composition, inverse and cardinality
- Relations and their properties
- Relation matrices and closure
- Equivalence and partitions
- Partial orders and Hasse diagrams
- Lattices and bounds
- Boolean algebra
- Addition and multiplication rules
- Permutations and combinations
- Repetition and stars-and-bars
- Binomial theorem and identities
- Inclusion-exclusion
- Pigeonhole principle
- Finite probability
- Mathematical induction
- Strong induction and invariants
- Recurrences and solving
- Generating functions
- Divisibility and Euclidean algorithm
- Modular arithmetic
- Algebraic structures
- Graphs and degree sum
- Paths, connectivity and trees
- Euler and Hamilton routes
- Coloring, bipartite and planarity
- Directed graphs and matching
- Exam revision and limits
1. Propositions and connectives
A proposition has a truth value. Negation, conjunction, disjunction, implication and biconditional combine propositions.
Answer: Not until its variable is assigned or quantified over a domain.
2. Implication and equivalence
p implies q is equivalent to NOT p OR q. It is false only for true p and false q. Biconditional requires equal truth values.
Answer: No. p implies q does not generally imply q implies p.
3. Truth tables and normal forms
A truth table examines every Boolean valuation. A tautology is always true, contradiction always false, contingency sometimes true. DNF is an OR of AND terms; CNF an AND of OR clauses.
Answer: 2 to the power n; avoid omitting valuations.
Truth-table check
from itertools import product
def implies(p, q):
if type(p) is not bool or type(q) is not bool:
raise TypeError("Boolean inputs required")
return (not p) or q
print("p q and implies de_morgan")
for p, q in product([True, False], repeat=2):
law = (not (p and q)) == ((not p) or (not q))
print(int(p), int(q), int(p and q), int(implies(p, q)), int(law))
try:
implies(1, False)
except TypeError:
print("non-Boolean rejected")Checked output:
p q and implies de_morgan 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 non-Boolean rejected
4. Logical laws and inference
De Morgan swaps AND/OR under negation. Modus ponens uses p and p implies q to conclude q; modus tollens uses NOT q to conclude NOT p.
Answer: No. q and p implies q do not force p.
5. Predicates and quantifiers
Always state the domain. For all x and there exists x are different. Negating a quantifier swaps it and negates its predicate.
Answer: No. For all x there exists y can differ from there exists y for all x.
6. Proof methods
Direct proof starts with hypotheses; contrapositive proves NOT q implies NOT p; contradiction assumes the claim false; a counterexample disproves a universal statement..
Answer: No. They support intuition but do not cover all cases.
7. Sets and operations
Union, intersection, difference and complement depend on a stated universe. Empty set and a set containing the empty set differ.
Answer: Yes. There is no element that violates the subset condition.
8. Power sets and products
An n-element finite set has 2^n subsets. A Cartesian product uses ordered pairs and has size(A)*size(B) elements for finite sets.
Answer: No. Ordered coordinates have different roles.
9. Functions and mappings
A function assigns exactly one codomain value to each domain element. Injective means distinct inputs have distinct outputs; surjective means every codomain element is reached.
Answer: Yes. Extra unreached codomain elements make it non-surjective.
10. Composition, inverse and cardinality
Composition g after f requires f's outputs to lie in g's domain. A two-sided inverse function exists exactly for a bijection. Finite equal cardinality alone does not make a given map bijective.
Answer: No. Integers are countable, while real numbers are uncountable.
11. Relations and their properties
A relation on A is a subset of A times A. Check reflexive, symmetric, antisymmetric and transitive independently.
Answer: No. Equality is both symmetric and antisymmetric.
12. Relation matrices and closure
A finite relation can use a 0/1 matrix. Boolean composition checks intermediate elements. Reflexive closure adds diagonal pairs; transitive closure adds pairs reachable by paths.
Answer: No. Reflexive-transitive closure does; transitive closure adds self-reachability only when a positive-length cycle exists.
Finite relation properties and transitive closure
def relation_check(domain, relation):
# Domain elements and pairs must be hashable.
domain, relation = set(domain), set(relation)
if any(not isinstance(pair, tuple) or len(pair) != 2 or
pair[0] not in domain or pair[1] not in domain
for pair in relation):
raise ValueError("pairs must stay inside the domain")
reflexive = all((a, a) in relation for a in domain)
symmetric = all((b, a) in relation for a, b in relation)
antisymmetric = all(a == b or (b, a) not in relation
for a, b in relation)
transitive = all((a, c) in relation for a in domain
for b in domain for c in domain
if (a, b) in relation and (b, c) in relation)
return reflexive, symmetric, antisymmetric, transitive
def closure(domain, relation):
domain, result = set(domain), set(relation)
relation_check(domain, result) # validate before computing
for k in domain:
for i in domain:
for j in domain:
if (i, k) in result and (k, j) in result:
result.add((i, j))
return result # positive-length reachability, not automatic reflexivity
D = {0, 1, 2}
R = {(0, 1), (1, 2)}
print("reflexive symmetric antisymmetric transitive:", relation_check(D, R))
print("closure:", sorted(closure(D, R)))
E = {(a, b) for a in range(6) for b in range(6) if (a - b) % 3 == 0}
print("mod 3 properties:", relation_check(range(6), E))
try:
relation_check(D, {(0, 9)})
except ValueError:
print("outside-domain pair rejected")Checked output:
reflexive symmetric antisymmetric transitive: (False, False, True, False) closure: [(0, 1), (0, 2), (1, 2)] mod 3 properties: (True, True, False, True) outside-domain pair rejected
13. Equivalence and partitions
An equivalence relation is reflexive, symmetric and transitive. Its classes form disjoint nonempty blocks covering the domain.
Answer: No. An overlap forces them to be the same class.
14. Partial orders and Hasse diagrams
A partial order is reflexive, antisymmetric and transitive. Hasse diagrams omit loops and transitive edges, drawing larger elements higher under the chosen order.
Answer: No. A total order requires every pair to be comparable.
15. Lattices and bounds
A lattice has a unique greatest lower bound and least upper bound for every pair. Minimum/maximum elements differ from merely minimal/maximal elements.
Answer: No. Some pairs lack a meet or join within the set.
16. Boolean algebra
Boolean operations obey distributive and complement laws. Power-set union/intersection/complement give a Boolean algebra relative to a universe.
Answer: No. Boolean 1 OR 1 is 1, while arithmetic 1+1 is 2.
17. Addition and multiplication rules
Add disjoint alternatives; multiply successive choices when the number of choices per stage is stated. Overlap needs correction.
Answer: No. Elements in the overlap would be counted twice.
18. Permutations and combinations
For distinct objects, ordered r-selections are n!/(n-r)!; unordered choices are n!/(r!(n-r)!). State repetition and distinguishability.
Answer: Each r-element subset appears in r! different orders.
Counting and recurrence checks
from itertools import combinations, permutations, product
from math import comb, factorial
def fibonacci(count):
if type(count) is not int or count < 0:
raise ValueError("nonnegative integer count required")
result, a, b = [], 0, 1
for _ in range(count):
result.append(a)
a, b = b, a + b
return result
print("4 books orders:", factorial(4), len(list(permutations(range(4)))))
print("choose 2:", comb(4, 2), len(list(combinations(range(4), 2))))
solutions = [(a, b, c) for a, b, c in product(range(5), repeat=3)
if a + b + c == 4]
print("three bins, total 4:", len(solutions), comb(6, 2))
print("F0 through F7:", fibonacci(8))
print("sum 1..10:", sum(range(1, 11)), 10 * 11 // 2)
coefficients = [0] * 5
for i in range(3):
for j in range(3):
coefficients[i + j] += 1
print("(1+x+x^2)^2:", coefficients)
try:
fibonacci(-1)
except ValueError:
print("invalid count rejected")Checked output:
4 books orders: 24 24 choose 2: 6 6 three bins, total 4: 15 15 F0 through F7: [0, 1, 1, 2, 3, 5, 8, 13] sum 1..10: 55 55 (1+x+x^2)^2: [1, 2, 3, 2, 1] invalid count rejected
19. Repetition and stars-and-bars
Length r strings over n symbols number n^r. Nonnegative solutions to x1+...+xk=r number C(r+k-1,k-1). Positive variables first subtract one from each.
Answer: No. It counts distributions among labeled bins under its constraints.
20. Binomial theorem and identities
(x+y)^n has coefficients C(n,k). Pascal identity splits choices by including a distinguished item. Sum of all coefficients is 2^n.
Answer: No. Many have a combinatorial counting proof.
21. Inclusion-exclusion
Two-set union count is size(A)+size(B)-size(intersection). Three sets subtract pair intersections then add the triple intersection.
Answer: The three-set subtraction removes its membership too many times.
22. Pigeonhole principle
More objects than bins forces a repeated bin. In general n objects in k nonempty available bins force one bin with at least ceiling(n/k) objects.
Answer: No. It guarantees existence, not which bin.
23. Finite probability
For equally likely finite outcomes, probability is favorable/total. Conditional P(A given B)=P(A intersection B)/P(B) for positive P(B); independence means joint probability factors.
Answer: No. Their intersection is zero, unlike the positive product.
24. Mathematical induction
State base case, induction hypothesis and step. The hypothesis applies only as stated; the step must establish the next case.
Answer: No. A working step without an established starting case proves nothing in the intended range.
25. Strong induction and invariants
Strong induction assumes earlier cases up to k. An invariant holds initially and is preserved by each allowed transition.
Answer: No. Prove initialization and preservation for all permitted transitions.
26. Recurrences and solving
A recurrence needs base values and index domain. First-order constant-increment recurrences expand to arithmetic progressions; second-order recurrences may require two bases.
Answer: Not generally; two independent base values are needed.
27. Generating functions
An ordinary generating function packages coefficients as sum an*x^n. Treat formal series identities as coefficient statements, without needing analytic convergence.
Answer: No. Formal coefficient algebra and convergence are different questions.
28. Divisibility and Euclidean algorithm
a divides b means b=a*k for an integer k. GCD uses repeated remainders; gcd(a,b)=gcd(b,a mod b). State sign and zero conventions.
Answer: Handle it explicitly; division and modulo by zero are not defined.
29. Modular arithmetic
Congruence mod m means the difference is divisible by positive m. Inverses exist for residues coprime to m; ordinary cancellation may fail.
Answer: No. Modulus6 has nonzero nonunits such as2.
30. Algebraic structures
Semigroup: associative closed operation. Monoid adds identity. Group adds inverses; abelian group also commutes. A ring has compatible addition/multiplication; a field is a commutative ring with 1!=0 and every nonzero element invertible.
Answer: No. Every element also needs an inverse.
31. Graphs and degree sum
State directedness, loops and parallel-edge conventions. In a finite undirected graph degree sum is2*edge_count, counting a loop twice.
Answer: No. The number of odd-degree vertices is even.
Simple undirected graph checks
from collections import deque
def graph_check(vertices, edges):
vertices = set(vertices)
edges = list(edges)
adjacency = {v: set() for v in vertices}
seen_edges = set()
for pair in edges:
if not isinstance(pair, tuple) or len(pair) != 2:
raise ValueError("edge pairs required")
u, v = pair
key = frozenset((u, v))
if u not in vertices or v not in vertices or u == v or key in seen_edges:
raise ValueError("simple undirected edges required")
seen_edges.add(key)
adjacency[u].add(v)
adjacency[v].add(u)
degrees = {v: len(adjacency[v]) for v in vertices}
components, bipartite, color = 0, True, {}
for start in vertices:
if start in color:
continue
components += 1
color[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in adjacency[u]:
if v not in color:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
bipartite = False
tree = bool(vertices) and components == 1 and len(edges) == len(vertices) - 1
return degrees, components, bipartite, tree
for label, edges in [
("path", [(0, 1), (1, 2), (2, 3)]),
("triangle plus isolated", [(0, 1), (1, 2), (2, 0)])
]:
degrees, components, bipartite, tree = graph_check(range(4), edges)
print(label, "degrees:", sorted(degrees.items()))
print("sum:", sum(degrees.values()), "2E:", 2 * len(edges))
print("components:", components, "bipartite:", bipartite, "tree:", tree)
try:
graph_check(range(2), [(0, 1), (1, 0)])
except ValueError:
print("duplicate edge rejected")Checked output:
path degrees: [(0, 1), (1, 2), (2, 2), (3, 1)] sum: 6 2E: 6 components: 1 bipartite: True tree: True triangle plus isolated degrees: [(0, 2), (1, 2), (2, 2), (3, 0)] sum: 6 2E: 6 components: 2 bipartite: False tree: False duplicate edge rejected
32. Paths, connectivity and trees
A tree is connected and acyclic; a finite n-vertex nonempty tree has n-1 edges. A forest with n vertices and c components has n-c edges.
Answer: No. Connectivity or acyclicity must also be established under the finite undirected model.
33. Euler and Hamilton routes
Euler uses every edge exactly once; Hamilton visits every vertex exactly once under the stated path/cycle convention. For an undirected graph, connected nonzero-degree vertices and zero/two odd degrees characterize Euler circuit/trail existence.
Answer: No. Hamilton existence is a different problem.
34. Coloring, bipartite and planarity
Proper vertex coloring gives adjacent vertices different colors. Bipartite iff no odd cycle. For a connected planar embedding, V-E+F=2, counting the outer face.
Answer: No. It is necessary, not sufficient.
35. Directed graphs and matching
Directed reachability respects orientation. A DAG admits a topological order. A matching has disjoint edge endpoints; a maximum matching has largest cardinality, while maximal only means no edge can be added.
Answer: No. A locally non-extendable matching can be smaller than another matching.
36. Exam revision and limits
State domains, models and hypotheses before formulas. Program enumeration verifies finite cases, not a universal theorem. General notes do not certify an assessed syllabus.
Answer: A precise claim, assumptions, valid steps and a conclusion covering the requested domain.
Truth-table reference
| p | q | AND | OR | p implies q | p iff q |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |
Checked answer reference
| Task | Answer | Condition |
|---|---|---|
| Four distinct books, all orders | 24 | All distinct, order matters |
| Choose two of four | 6 | No order, no repetition |
| Three bins, total four | 15 | Nonnegative counts, labeled bins |
| Power set of three elements | 8 | Distinct elements |
| Modulo3 classes on0..5 | {0,3},{1,4},{2,5} | Congruence equivalence |
| Divisibility meet/join of2,3 | 1 and6 | Domain {1,2,3,6} |
| Coefficient x^4 in(1+x+x^2)^2 | 1 | Formal polynomial product |
| GCD84,30 | 6 | Positive integers |
| Inverse3 modulo7 | 5 | Coprime |
| Six-vertex tree | 5 edges | Finite, connected, acyclic |
| Two fair coin tosses, one head | 1/2 | Four equally likely outcomes |
Revision checklist
- Build all truth-table rows and distinguish converse from contrapositive.
- Negate quantified claims with a stated domain.
- Check every relation property independently.
- State order, repetition and overlap rules before counting.
- Give induction base, hypothesis and valid step.
- State graph model before degree, tree, Euler and planar formulas.
- Distinguish finite test evidence from a universal proof.
Sources
References support definitions and theorem hypotheses. Explanations, fixed examples, diagrams and programs here are original teaching material, not copied textbook sections.
Comments
Post a Comment