Discrete Mathematics

Reject when NOT authenticated OR (NOT hasRole AND NOT isServiceCall). De Morgan's laws flip each connective as the negation moves inward: the outer AND becomes OR, the inner OR becomes AND, and every atom is negated.

One queued job that is never acknowledged refutes the claim completely; a single counterexample is a full disproof. Passing runs only fail to find one. They establish the claim only if they exhaust a finite domain.

Only the contrapositive: 'if the request succeeded, the retry budget was not exhausted'. The converse and the inverse are different claims that can be false while the original rule still holds.

Quantifier order decides whether the handler may vary per request. 'Some handler serves every request' fixes one handler for all of them and is the stronger claim: it implies 'every request has some handler', while the reverse fails.

Material implication is false on exactly one row: antecedent true, consequent false. A request that never exhausted its budget cannot produce that row, so the rule holds vacuously - and a vacuous truth is evidence of nothing.

A 32-bit fingerprint has only 2^32 possible values, so any 2^32 + 1 distinct keys must contain two that share one. That is the pigeonhole principle; a better function cannot avoid it, only a wider field delays it.

Assume the claim fails: that some run exists in which one block is held by two callers at once. That single assumed run is a concrete object you can trace until it forces something impossible.

The contrapositive — if a live pointer refers to a block, that block is not on the free list — states the same claim, but starts from a fact you can trace: a pointer, and the call that produced it.

Only smaller cases, never the case being proved. The step establishes an implication - if the claim holds at k, it holds at k+1 - and the base case supplies the first true instance, so nothing is assumed about the target.

Because a composite splits as n = a times b, where a and b can be far smaller than n - 1. A previous-value hypothesis says nothing about them; the strong form assumes the claim for every value below n, which does cover both factors.

Union gives 'either' — every document carrying at least one of the labels. Intersection gives 'both' — only documents carrying every selected label. As a user ticks more labels a union can only stay the same or grow; an intersection can only stay the same or shrink.

Equality must be an equivalence relation — reflexive, symmetric, transitive — and must stay stable while the key is stored. Equal keys must produce equal hashes; unequal keys are allowed to collide, and a collision never means equality.

Reflexivity, symmetry and transitivity. A rule with all three is an equivalence relation, and only then does it cut the rows into disjoint groups where every row lands in exactly one group, whichever row you start from.

Injective means no two distinct old identifiers are sent to the same new identifier. Lose it and two separate records land on one row in the target: one write overwrites the other, references converge, and no rollback can tell them apart.

Injectivity alone gives an inverse only on the identifiers the remap actually produced. To translate back any identifier the new store holds, the remap must also be surjective onto that set — together, a bijection onto it.

Expanding (1 + x)^n means one (1 + x) factor per engineer, and each factor contributes either 1 (stay off the review) or x (join it). A product becomes x^k exactly when k engineers contributed x, so its coefficient counts k-member sets.

Both totals count one collection: every reviewer set the roster can produce. Grouping that collection by size and adding the groups gives the sum of binomial coefficients; building a set by deciding in or out per engineer gives 2^n. One collection, two tallies, so they are equal.

Subtracting each filter's matches over-corrects records caught by several filters, so pairwise overlaps are added back, triples removed again, and so on. The alternating signs make every record matching at least one filter cancel to exactly zero.

Subtract from 1000 the multiples of 2, 3 and 5, add back the multiples of 6, 10 and 15, then subtract the multiples of 30. That is 1000 - 734 = 266 surviving IDs.

Split on the last slot. Idle leaves any valid (n-1)-schedule; maintenance forces the previous slot idle, leaving any valid (n-2)-schedule. The two cases are disjoint and exhaustive, so their counts add.

Every link has two ends, and each end raises exactly one machine's link count by one. Totalling link counts therefore counts every link twice. This is the handshake lemma: the degree sum equals 2E, so it is always even.

The chromatic number is the fewest colours that label every vertex so no edge has one colour at both ends. On a conflict graph it is the minimum number of time slots any valid schedule can use.

A cut vertex is a site whose removal, together with its spans, leaves the network in more pieces than before; a bridge is a span whose removal alone does that. Both name single points of failure.

Exactly when every span lies in one connected piece and every site has even degree. Each visit to a site uses one span in and one out, so an odd degree makes a closed route over every span impossible.

The degrees would sum to 7 x 3 = 21, which is odd, but every graph's degree sum equals twice its edge count and so must be even. The plan is impossible for any wiring, not just awkward ones.

Only when c and n share no common factor, that is when their greatest common divisor is 1. Otherwise the honest conclusion is a congruent to b modulo n divided by that greatest common divisor, which is weaker.

Addition, subtraction and multiplication survive: the class of a sum or product depends only on the input classes, never on which representatives you picked. Order, cancellation and the exponent position do not survive.

A value a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1. If they share a factor g > 1, every product a*x reduced modulo n is a multiple of g, and 1 never is.

It returns integers x and y with ax + ny = gcd(a, n), by carrying those two coefficients alongside the remainders. When the gcd is 1, reducing modulo n drops the n*y term, so x is the inverse of a.

Euler's theorem gives g^phi(n) congruent to 1 mod n whenever gcd(g, n) = 1, so the powers of g cycle with a period dividing phi(n) and only k mod phi(n) matters. Without that coprimality the reduction is simply invalid.