TU BSc CSIT Entrance flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Contrapositive equivalence

The statement p→q is logically equivalent to its contrapositive ¬q→¬p. Its converse q→p and inverse ¬p→¬q are not equivalent to the original implication.

Power set cardinality

A set with n distinct elements has exactly 2^n subsets, counting the empty set and the set itself. Its proper subsets number 2^n − 1.

Combination formula

C(n,r) = n!/(r!(n−r)!) counts unordered selections of r items from n distinct items. Order does not matter, so it is smaller than the permutation count P(n,r).

Circular permutation count

The number of distinct arrangements of n distinct objects around a circle is (n−1)!. Fixing one object removes rotational duplicates, leaving (n−1)! orderings of the rest.

Sum of geometric series

For a geometric progression with first term a and ratio r ≠ 1, the sum of n terms is a(r^n−1)/(r−1). The infinite sum exists only when |r| < 1.

Conditional probability rule

P(A|B) = P(A∩B)/P(B), defined when P(B) > 0. Two events are independent exactly when P(A∩B) = P(A)·P(B), which makes P(A|B) equal P(A).

Bayes' theorem

P(A|B) = P(B|A)·P(A)/P(B). It converts a known conditional probability into the reverse conditional by weighting with prior probabilities of the events.

2×2 matrix inverse

For A = [[a,b],[c,d]], the inverse exists only if ad−bc ≠ 0 and equals (1/(ad−bc))·[[d,−b],[−c,a]]. A zero determinant means the matrix is singular.

Determinant and solvability

A square linear system Ax = b has a unique solution if and only if det(A) ≠ 0. If the determinant is zero, the system has either no solution or infinitely many.

Derivative of sine and cosine

d/dx(sin x) = cos x and d/dx(cos x) = −sin x, valid when x is measured in radians. Differentiating sine twice returns −sin x.

Product rule

For differentiable functions u and v, (uv)' = u'v + uv'. The derivative of a product is not the product of the derivatives; each factor is differentiated in turn.

Power rule integration

∫x^n dx = x^(n+1)/(n+1) + C for every n ≠ −1. The exceptional case n = −1 gives ∫(1/x)dx = ln|x| + C instead.

Binary to decimal conversion

Multiply each binary digit by the corresponding power of 2 and add. For example, 1011₂ = 1·8 + 0·4 + 1·2 + 1·1 = 11 in decimal.

Two's complement negation

To negate a fixed-width binary integer, invert every bit and add 1. This representation gives a single zero and lets subtraction be performed as addition of the negated value.

Hexadecimal digit values

Hexadecimal uses base 16 with digits 0–9 plus A=10, B=11, C=12, D=13, E=14, F=15. Each hex digit maps to exactly four binary bits.

Modulus of a complex number

For z = a + bi, the modulus |z| = √(a² + b²), the distance from the origin in the complex plane. It equals √(z·z̄) where z̄ is the conjugate.

De Moivre's theorem

(cos θ + i sin θ)^n = cos(nθ) + i sin(nθ) for integer n. It turns powers of complex numbers into simple angle multiplication, useful for roots and identities.

Injective function test

A function is one-to-one if f(a) = f(b) implies a = b. Horizontal-line test: no horizontal line meets the graph more than once.

Limit definition of derivative

f'(x) = lim(h→0) [f(x+h) − f(x)]/h, provided the limit exists. The derivative gives the instantaneous rate of change and the slope of the tangent line.

Arithmetic mean and standard deviation

Mean = (sum of values)/n. Standard deviation is the square root of the average of squared deviations from the mean, measuring spread in the same units as the data.

Empty set and subset relations

The empty set is a subset of every set, including itself, and has cardinality zero. Every set is a subset of itself, but only proper subsets exclude the set itself.

Set De Morgan laws

(A∪B)' = A'∩B' and (A∩B)' = A'∪B'. Complementing a union yields an intersection of complements, and complementing an intersection yields a union.

Logarithm product rule

log_b(xy) = log_b(x) + log_b(y) and log_b(x/y) = log_b(x) − log_b(y). Also log_b(x^k) = k·log_b(x), and change of base is log_b(x) = ln x / ln b.

Quadratic discriminant rule

For ax² + bx + c = 0, the discriminant is b² − 4ac. Positive gives two distinct real roots, zero gives one repeated real root, negative gives complex conjugate roots.

Sum of first n integers

1 + 2 + … + n = n(n+1)/2. The sum of the first n squares is n(n+1)(2n+1)/6, and of the first n cubes is [n(n+1)/2]².

Infinite geometric convergence

An infinite geometric series with ratio r converges only when |r| < 1, and then sums to a/(1−r) where a is the first term. Otherwise it diverges.

Permutation with repetition

The number of arrangements of a multiset of n items with repeated types is n! divided by the product of the factorials of each type's frequency.

Function composition order

(f∘g)(x) = f(g(x)) means apply g first, then f. Composition is generally not commutative, so f∘g and g∘f usually differ.

Pigeonhole principle

If n items are placed into m containers with n > m, at least one container holds more than one item. More generally, some container holds at least ⌈n/m⌉ items.

Truth table row count

A propositional formula with k distinct propositional variables requires 2^k rows in a complete truth table. Tautologies have true in every row; contradictions false in every row.

Binary addition carry

In binary, 1 + 1 = 10, producing a 0 digit and a carry of 1. Adding three 1s gives 11, so binary addition uses carries just as decimal arithmetic does.

Domain and range

The domain is the set of all valid inputs of a function; the range is the set of actual outputs. For f(x) = √x over the reals, the domain is x ≥ 0.