Discrete Mathematics – Complete Study Notes

Let p = "you study hard", q = "you will pass".

(a) Converse: q→p = "If you pass, you studied hard." (NOT equivalent)

(b) Inverse: ¬p→¬q = "If you do not study hard, you will not pass." (NOT equivalent; ≡ converse)

(c) Contrapositive: ¬q→¬p = "If you do not pass, you did not study hard." (EQUIVALENT to original)

Columns 3 and 6 are identical. ✓ Proved.

No. A true conditional does NOT guarantee a true converse.

Example: p→q = "If a number is divisible by 4, it is divisible by 2." TRUE.

Converse q→p = "If a number is divisible by 2, it is divisible by 4." FALSE (e.g., 6 is divisible by 2 but not 4).

p→q ≡ ¬p∨q  [standard rewrite]

¬p∨q ≡ ¬(p∧¬q)  [De Morgan's: ¬(A∧B) = ¬A∨¬B, reversed]

Answer: p→q ≡ ¬(p ∧ ¬q)

Try p=T, q=F, r=T:

(T∨F) ∧ (F∨T) ∧ (T∨F) = T ∧ T ∧ T = T ✓

Yes, satisfiable. Assignment: p=T, q=F, r=T satisfies all three clauses.

From ¬p and ¬q: p=F, q=F.

Then p∨q = F∨F = F. So (p∨q)∧¬p∧¬q = F.

No other assignments are possible since ¬p and ¬q force p=F, q=F.

No, unsatisfiable (contradiction).

p↔q is true when p and q have the same value.

Satisfying assignments: (T,T) and (F,F) — exactly 2 out of 4.

Answer: 2 satisfying assignments.

Solution: We need: whenever (p∨q)∧¬p is T, q must also be T.

(p∨q)∧¬p is T only when p=F and q=T (¬p=T requires p=F; p∨q=T requires q=T when p=F).

In that case q=T, so the implication holds. In all other cases the hypothesis is F → implication is automatically T.

Yes, it is a tautology (this is Disjunctive Syllogism).

Let p = "It rains", q = "The ground is wet". Original: p → q.

Contrapositive: ¬q → ¬p.

Answer: "If the ground is not wet, then it did not rain."

The contrapositive is logically equivalent to the original.

p → q ≡ ¬p ∨ q

¬(p → q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q  [De Morgan's]

Answer: p ∧ ¬q (p is true AND q is false — the only case when an implication fails).

If p∧q is T → both p and q are T → p is T → implication is T.

If p∧q is F → false antecedent → implication is T.

Yes, it is a tautology (Simplification rule of inference).

Let L(x) = "x has a laptop", domain = students.

Original: ∀x L(x). Negation: ¬(∀x L(x)) ≡ ∃x ¬L(x).

Answer: "There exists a student who does not have a laptop."

Let B(x) = "x is a bird", F(x) = "x can fly".

Answer: ∃x (B(x) ∧ ¬F(x))

Important: Use ∧ (not →) with ∃. Writing ∃x (B(x) → ¬F(x)) would be true even if there are no birds, which is wrong!

¬(∀x ∀y (x≠y → P(x,y)))

≡ ∃x ∃y ¬(x≠y → P(x,y))

≡ ∃x ∃y (x≠y ∧ ¬P(x,y))  [since ¬(A→B) ≡ A∧¬B]

Answer: "There exist two distinct elements for which P(x,y) does not hold."

DNF: f = 1 only at row 2 (A=1,B=0). Minterm m₂ = AB'.

f = Σm(2) = AB'

CNF: f = 0 at rows 0,1,3. Maxterms: M₀=A+B, M₁=A+B', M₃=A'+B'.

f = ΠM(0,1,3) = (A+B)(A+B')(A'+B')

DNF uses minterms at rows 1,4,5,7. So CNF uses maxterms at ALL OTHER rows: 0,2,3,6.

Rows where f=0: 0,2,3,6.

Maxterms (3 variables A,B,C):

M₀ = A+B+C (row 000)

M₂ = A+B'+C (row 010)

M₃ = A+B'+C' (row 011)

M₆ = A'+B+C' (row 110)

f = ΠM(0,2,3,6) = (A+B+C)(A+B'+C)(A+B'+C')(A'+B+C')

For n=3 variables (A,B,C): 2³ = 8 minterms (m₀ to m₇) and 8 maxterms (M₀ to M₇).

And there are 2^8 = 256 possible distinct Boolean functions of 3 variables.

Fill K-map:

         BC=00  BC=01  BC=11  BC=10
  A=0  [  1   |  0   |  0   |  1   ]   m₀=1, m₁=0, m₃=0, m₂=1
  A=1  [  1   |  0   |  0   |  1   ]   m₄=1, m₅=0, m₇=0, m₆=1
      

Group all four 1s: m₀,m₂,m₄,m₆ — these are BC=00 and BC=10 columns, both rows.

In these cells: A varies (0,1), B varies (0,1), C = 0 always.

The common factor: C' (C=0)

f = C' — the function is simply 1 whenever C=0.

         BC=00  BC=01  BC=11  BC=10
  A=0  [  0   |  1   |  1   |  0   ]   m₁=1, m₃=1
  A=1  [  0   |  1   |  1   |  0   ]   m₅=1, m₇=1
      

Group all four 1s: m₁,m₃,m₅,m₇ — BC=01 and BC=11 columns, both rows.

In all these cells: C=1 always. A and B vary.

f = C — true whenever C=1.

         BC=00  BC=01  BC=11  BC=10
  A=0  [  1   |  1   |  1   |  1   ]   m₀,m₁,m₃,m₂ = all 1
  A=1  [  1   |  0   |  0   |  1   ]   m₄=1, m₅=0, m₇=0, m₆=1
      

Group 1 (size 4): Entire A=0 row → m₀,m₁,m₂,m₃ → A=0 → term: A'

Group 2 (size 2): m₀,m₄ (BC=00 column) → B=0,C=0 → term: B'C'

Group 3 (size 2): m₂,m₆ (BC=10 column) → B=1,C=0 → term: BC'

Note: m₀ is covered by both Group 1 and 2 (allowed). m₂ covered by both Group 1 and 3.

f = A' + B'C' + BC'

This can further simplify: B'C' + BC' = C'(B'+B) = C'. So f = A' + C'.

Because we need to eliminate exactly one variable per doubling. Each time a group doubles in size, one variable changes across the group (0→1 or 1→0), so it can be eliminated from the simplified term.

For example: a group of 2 cells → 1 variable eliminated. Group of 4 → 2 variables eliminated. Group of 3 cells would not correspond to any clean Boolean simplification.

F = A + A'B

= (A + A')(A + B)  [Distributive: x + yz = (x+y)(x+z)]

= 1 · (A + B) = A + B

Answer: F = A + B

Circuit (4 NAND gates):

G1 = NAND(A, B)

G2 = NAND(A, G1)

G3 = NAND(B, G1)

Output = NAND(G2, G3)

Proof: NAND(G2,G3) = (G2·G3)' = ((A·G1)'·(B·G1)')' = A⊕B ✓

Columns 4 and 7 are identical. ✓ Proved.

This is the Fallacy of Affirming the Consequent.

Invalid form: p→q, q ⊬ p.

The match could have been cancelled for other reasons (pitch damage, no players, etc.).

Contrast with valid Modus Ponens (p→q, p ∴ q) — affirm the antecedent, not consequent.

Premises: H ∨ S, ¬H.

By Disjunctive Syllogism: From H∨S and ¬H → conclude S.

Answer: It is sunny.

Let a = 2m+1 and b = 2n+1 be two odd integers.

a + b = (2m+1) + (2n+1) = 2m + 2n + 2 = 2(m+n+1).

Since m+n+1 is an integer, a+b is even. ∎

Base case n=1: LHS=1, RHS=1·2·3/6=1. ✓

IH: Assume true for k.

Prove for k+1:

\(\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1)}{6} + (k+1)\right]\)

\(= (k+1) \cdot \frac{k(2k+1) + 6(k+1)}{6} = (k+1) \cdot \frac{2k^2+7k+6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}\) ✓ ∎

Assume finitely many primes: p₁, p₂, …, pₙ.

Let N = p₁·p₂·⋯·pₙ + 1.

N is not divisible by any pᵢ (remainder 1 each time).

So N is either prime (a new prime!) or has a prime factor not in our list. Either way, contradicts our assumption. ∎

low=0; high=n-1
while (low <= high):
    mid = (low+high)/2
    if A[mid]==target: return mid
    elif A[mid] < target: low = mid+1
    else: high = mid-1
return -1

Invariant: If target exists in A, it lies within A[low..high].

Init: Before loop, A[low..high] = entire array. Invariant trivially holds. ✓

Maintenance: If A[mid] < target, target must be in right half → set low=mid+1 preserves invariant. Similarly for the other branch. ✓

Termination: low > high means search space is empty → target not present → return −1 is correct. ✓

If U = set of all sets exists, then R = {S ∈ U : S ∉ S} would be a valid set by the Separation Axiom.

But then R ∈ R ↔ R ∉ R — Russell's paradox again.

Therefore, a "set of all sets" cannot exist consistently. Instead, we use a "proper class" (collection too large to be a set) which is not itself a set and cannot be an element of other collections.

Yes! A program is a finite string over a finite character set (ASCII).

The set of all finite strings over a finite alphabet is countable — list them in order of increasing length, then lexicographically.

Deep implication: There are only countably many programs, but uncountably many functions ℕ→ℕ (since 𝒫(ℕ) is uncountable). Therefore, most mathematical functions cannot be computed by any program!

Suppose 𝒫(ℕ) is countable: list all subsets as S₁, S₂, S₃, …

Define the diagonal set: D = {n ∈ ℕ : n ∉ Sₙ}.

For each n: n ∈ D ↔ n ∉ Sₙ, so D ≠ Sₙ for any n.

But D ⊆ ℕ, so D should appear somewhere in the list. Contradiction!

∴ 𝒫(ℕ) is uncountable.

Closure: 1×1=1, 1×(−1)=−1, (−1)×(−1)=1. All in {1,−1}. ✓

Associativity: Multiplication is associative. ✓

Identity: 1 is identity: 1×a = a×1 = a. ✓

Inverse: 1⁻¹=1 and (−1)⁻¹=−1 (since (−1)×(−1)=1). ✓

Also commutative → Abelian group. ✓

ℤ₁₀* = {a : 1 ≤ a ≤ 9, gcd(a,10)=1}

gcd(1,10)=1 ✓, gcd(3,10)=1 ✓, gcd(7,10)=1 ✓, gcd(9,10)=1 ✓

ℤ₁₀* = {1, 3, 7, 9}

φ(10) = φ(2)×φ(5) = 1×4 = 4. So |ℤ₁₀*| = 4. ✓

|ℤ₇*| = φ(7) = 6. By Lagrange, element orders must divide 6.

Divisors of 6: 1, 2, 3, 6.

Possible orders: 1, 2, 3, or 6.

p = 7 (prime), 7 ∤ 2. By Fermat: 2^6 ≡ 1 (mod 7).

100 = 6×16 + 4, so 2^100 = (2^6)^16 × 2^4 ≡ 1^16 × 16 ≡ 16 mod 7 ≡ 2 (mod 7).

Answer: 2^100 ≡ 2 (mod 7).

|S₃| = 3! = 6. By Lagrange, the order of ⟨g⟩ (a cyclic subgroup) must divide |S₃| = 6.

Since ord(g) = |⟨g⟩|, it follows that ord(g) | 6 for every g ∈ S₃. ✓

The eavesdropper sees: p, g, A = g^a mod p, B = g^b mod p.

To compute K = g^(ab) mod p, they need either a or b.

Finding a from A = g^a mod p is exactly the Discrete Logarithm Problem, which has no known efficient (polynomial-time) classical algorithm for large p.

Note: Shor's quantum algorithm CAN solve DLP efficiently, which is why post-quantum cryptography (lattice-based, hash-based) is being standardized by NIST.

By Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) for prime p and gcd(a,p)=1.

gcd(3,11)=1 and 11 is prime.

3^(11-1) = 3^10 ≡ 1 (mod 11).

Answer: 1. (No computation needed — FLT gives it directly.)

a=3, b=3 → c* = log₃3 = 1. f(n)=n = Θ(n¹) = Θ(n^c*).

Case 2 with k=0: T(n) = Θ(n log n).

a=9, b=3 → c* = log₃9 = 2. f(n)=n = O(n^(2−1)) = O(n^1).

f grows strictly slower than n^c*=n²: Case 1.

T(n) = Θ(n²).

a=2, b=2 → c* = 1. f(n) = n log n = Θ(n¹ · log¹n) = Θ(n^c* · log¹n).

Case 2 with k=1: T(n) = Θ(n log² n).

\(\dfrac{1}{(1-x)^3} = \sum_{n=0}^{\infty} \dbinom{n+2}{2} x^n\)

For n=5: \(\dbinom{7}{2} = 21.\)

Answer: 21.

Combinatorial meaning: ways to distribute 5 identical items into 3 distinct bins = C(7,2) = 21.

Let A(x) = Σ aₙxⁿ.

A(x) − a₀ = 2x·A(x) → A(x) − 1 = 2xA(x)

A(x)(1−2x) = 1 → A(x) = 1/(1−2x) = Σ 2ⁿxⁿ

Answer: aₙ = 2ⁿ.

Substitution: let yᵢ = xᵢ − 1 ≥ 0. Then y₁+y₂+y₃+y₄ = 10 − 4 = 6.

GF = 1/(1−x)⁴. Answer = [x⁶] 1/(1−x)⁴ = C(6+3,3) = C(9,3) = 84.

Answer: 84 ways.

Let A(x) = Σ aₙxⁿ. Multiply recurrence by xⁿ, sum for n≥2:

A(x) − x − 5x·A(x) + 6x²·A(x) = 0

A(x)(1 − 5x + 6x²) = x

A(x) = x / (1−5x+6x²) = x / ((1−2x)(1−3x))

Partial fractions: x/((1−2x)(1−3x)) = A/(1−2x) + B/(1−3x)

Set x=1/2: 1/2 = A(1/2) → A=−1. Set x=1/3: 1/3 = B(1/3) → B=1.

A(x) = −1/(1−2x) + 1/(1−3x) = Σ (−2ⁿ + 3ⁿ)xⁿ

Answer: aₙ = 3ⁿ − 2ⁿ. Verify: a₀=1−1=0 ✓, a₁=3−2=1 ✓.

Each part is between 0 and 4, and we have 3 parts (order matters here; if order doesn't matter it's harder).

Treating parts as ordered (compositions): GF for one part = 1 + x + x² + x³ + x⁴ = (1−x⁵)/(1−x).

GF for 3 ordered parts: \(\left(\frac{1-x^5}{1-x}\right)^3\).

Coefficient of xⁿ in this product gives the count. For example, [x⁵] = number of ways = 18 (can verify by enumeration).