Discrete Mathematics

Discrete mathematics is about finite structures, precise statements, and counting. A reliable solution starts by choosing the right representation: truth values for logic, set notation for membership, diagrams or adjacency lists for graphs, and recurrences for repeated processes. Short proofs are useful when they explain why a rule can be trusted; long formal derivations are rarely needed for routine calculations.

Propositional logic and equivalences

Idea. A proposition has a truth value. Negation reverses it; conjunction is true only when both inputs are true; disjunction is inclusive unless stated otherwise. Implication $p\to q$ is false only when $p$ is true and $q$ false, and is equivalent to $\neg p\lor q$. Equivalences apply to propositions, not to vague similarities.

Solved examples.

1. Question. Evaluate $p\to q$ when $p=T,q=F$. Solution. (1) An implication is false only for a true antecedent and false consequent. (2) This assignment matches that case. Answer. False. Trap. “If p then q” does not assert that p is true.
2. Question. Simplify $\neg(p\land q)$. Solution. (1) De Morgan's law distributes negation and changes AND to OR. (2) Thus $\neg(p\land q)\equiv\neg p\lor\neg q$. Answer. $\neg p\lor\neg q$. Shortcut. Negate each component and swap the connective.
3. Question. Is $p\to q$ equivalent to its converse $q\to p$? Solution. (1) Test $p=T,q=F$. (2) $p\to q$ is false. (3) $q\to p$ is true because its antecedent is false. Answer. No. Trap. The contrapositive $\neg q\to\neg p$, not the converse, is equivalent.
4. Question. Simplify $(p\to q)\land p$. Solution. (1) Replace implication with $\neg p\lor q$. (2) Obtain $(\neg p\lor q)\land p$. (3) Distribute: $(\neg p\land p)\lor(q\land p)$. (4) First term is false. Answer. $p\land q$. Shortcut. Modus ponens appears algebraically as eliminating the impossible $p\land\neg p$ term.
5. Question. Determine whether $((p\to q)\land(q\to r))\to(p\to r)$ is a tautology. Solution. (1) Assume the two implications in the antecedent are true. (2) If p is false, $p\to r$ is true. (3) If p is true, first implication gives q; second gives r. (4) In either case the consequent holds. Answer. Tautology. Trap. A chain of implications composes in the same direction.

Predicate logic and quantifiers

Idea. A predicate becomes a proposition after variables are assigned or quantified. For a domain $D$, $\forall x\,P(x)$ means every member satisfies P, while $\exists x\,P(x)$ means at least one does. Negation swaps quantifiers: $\neg\forall xP(x)\equiv\exists x\neg P(x)$ and $\neg\exists xP(x)\equiv\forall x\neg P(x)$.

Solved examples.

1. Question. Over integers, negate “Every multiple of 4 is even.” Solution. (1) The statement is $\forall n(4\mid n\to2\mid n)$. (2) Negation changes universal to existential and negates the property. (3) The counterexample condition is multiple of 4 and not even. Answer. “There exists an integer divisible by 4 that is not even.” Trap. Negate the whole implication: $\neg(A\to B)$ is $A\land\neg B$.
2. Question. Over the real numbers, is $\exists x\,\forall y(x+y=y)$ true? Solution. (1) The equation simplifies to x=0. (2) x=0 works for every real y. (3) The required existential witness exists. Answer. True, with witness x=0. Shortcut. Find a candidate independent of the universally quantified variable.
3. Question. Negate “Some student solved every problem.” Solution. (1) Write $\exists s\,\forall p\,S(s,p)$. (2) Negating the existential gives universal; negating the universal gives existential. (3) Negate S. Answer. “Every student failed to solve at least one problem,” formally $\forall s\exists p\neg S(s,p)$. Trap. Quantifier order is important.
4. Question. Over positive integers, evaluate $\forall n\exists m(m>n)$. Solution. (1) Choose any positive integer n. (2) Set m=n+1. (3) This m is positive and greater than n. Answer. True. Shortcut. For $\forall n\exists m$, the choice of m may depend on n.
5. Question. Compare $\forall x\exists y(x<y)$ and $\exists y\forall x(x<y)$ over integers. Solution. (1) The first permits a different y for each x; choose x+1. (2) It is true. (3) The second asks for one integer larger than every integer. (4) For any proposed y, x=y violates x<y. Answer. First true, second false. Trap. Swapping quantifiers changes meaning.

Sets, relations, and functions

Idea. A set is determined by its members. The power set $\mathcal P(A)$ contains all subsets and has size $2^{|A|}$ for finite A. A relation on A is a subset of $A\times A$. A function assigns each domain element exactly one codomain element; injective means distinct inputs have distinct outputs, and surjective means every codomain element is reached.

Solved examples.

1. Question. If $A=\{a,b,c\}$, list the size of $\mathcal P(A)$ and identify the empty set and A as members. Solution. (1) A set with 3 elements has $2^3=8$ subsets. (2) The empty set is a subset. (3) A is also a subset of itself. Answer. $|\mathcal P(A)|=8$; both $\emptyset$ and A belong. Trap. The empty set is one subset, not “no subset.”
2. Question. For $A=\{1,2,3\}$, let R contain $(x,y)$ when x divides y. List R. Solution. (1) 1 divides every member: (1,1),(1,2),(1,3). (2) 2 divides only 2 among these: (2,2). (3) 3 divides only 3: (3,3). Answer. $\{(1,1),(1,2),(1,3),(2,2),(3,3)\}$. Trap. Divisibility here is restricted to pairs in A.
3. Question. On integers define $xRy$ iff $x-y$ is even. Show the relation is an equivalence relation. Solution. (1) Reflexive: $x-x=0$ is even. (2) Symmetric: if x-y is even, its negative y-x is even. (3) Transitive: $(x-y)+(y-z)=x-z$ is even. Answer. R is reflexive, symmetric, and transitive. Useful proof. Closure of even integers under negation and addition gives the last two steps.
4. Question. Is $f:\mathbb Z\to\mathbb Z$, $f(x)=x^2$, injective? Is it surjective? Solution. (1) $f(1)=f(-1)=1$ with distinct inputs, so it is not injective. (2) No negative integer is a square, so negative codomain elements are missed. Answer. Neither. Trap. Domain and codomain are part of the function specification.
5. Question. Let $g:\mathbb R\to\mathbb R$, $g(x)=3x-2$. Find its inverse and state bijectivity. Solution. (1) Set y=3x-2 and solve x=(y+2)/3. (2) Every real y has exactly one preimage. Answer. $g^{-1}(y)=(y+2)/3$; g is bijective. Shortcut. A nonzero-slope affine map on the reals is one-to-one and onto.

Partial orders and lattices

Idea. A partial order is reflexive, antisymmetric, and transitive. Distinct elements may be incomparable. A lattice is a partially ordered set in which every pair has a greatest lower bound (meet) and least upper bound (join). In the subset order, meet is intersection and join is union.

Solved examples.

1. Question. Is divisibility a partial order on positive integers? Solution. (1) Every n divides itself. (2) If a|b and b|a for positive integers, then a=b. (3) If a|b and b|c, then a|c. Answer. Yes. Trap. On all integers, divisibility is not antisymmetric because 1 divides -1 and vice versa.
2. Question. In $(\mathcal P(\{a,b\}),\subseteq)$, find meet and join of $\{a\}$ and $\{b\}$. Solution. (1) Greatest common subset is their intersection, $\emptyset$. (2) Least containing subset is union, $\{a,b\}$. Answer. Meet $\emptyset$, join $\{a,b\}$. Shortcut. Under subset order use $\cap$ and $\cup$.
3. Question. In divisors of 12 ordered by divisibility, find meet and join of 4 and 6. Solution. (1) Lower bounds are common divisors; the greatest under divisibility is gcd(4,6)=2. (2) Upper bounds among divisors of 12 are common multiples that divide 12; the least is lcm(4,6)=12. Answer. Meet 2; join 12. Trap. The ambient poset restricts allowed upper bounds.
4. Question. In a set ordered by divisibility, are 4 and 9 comparable? Solution. (1) 4 does not divide 9. (2) 9 does not divide 4. Answer. No; they are incomparable. Trap. A partial order does not require every pair to compare.
5. Question. A finite poset has a unique least element 0 and a unique greatest element 1. Does every pair necessarily have a meet and join? Solution. (1) Having global bottom and top supplies some lower and upper bounds. (2) It does not guarantee a greatest lower bound or least upper bound for each pair. (3) Two incomparable maximal common lower bounds can prevent a meet. Answer. No. Trap. A bounded poset need not be a lattice.