Jahziah.
العربية

STUDY GUIDE · GKU 3

Discrete structures study guide (Computer Science)

Discrete mathematics is the mathematics of things you can count one by one — bits, records, states, nodes, packets — and it is the language the rest of computer science is written in. This unit has three parts. The first gives the vocabulary: sets, relations and functions, and the logic used to state and check claims precisely. The second gives the tools for proving and counting: direct and indirect proof, induction, counting rules, recurrences and arithmetic modulo . The third models structure and uncertainty: graphs and trees, probability, distributions and Bayes' theorem. Each section opens with a quick-revision card; the worked examples run from easy to exam level, and every count and probability in them was checked by computer.

Continue in the app

Structured by the official ETEC subject standard for this topic: every listed topic and learning outcome, with formulas, figures and worked examples. The full sections are available to members in the app.

SKU 3.1 · Introductory logic, sets, relations and functions

  1. Sets, relations and functions

    Set operations and their sizes, the four properties of a relation and what an equivalence relation does, and functions: one-to-one, onto, composition and inverse.

  2. Propositional and predicate logic

    Connectives and truth tables, logical equivalence, predicates and quantifiers, translating English into logic and back, and negating quantified statements.

  3. Rules of inference and valid arguments

    What makes an argument valid, the standard rules of inference for propositions and quantifiers, the two common fallacies, and formal proofs built from real-life premises.

SKU 3.2 · Proof techniques and basics of counting

  1. Proof techniques and induction

    Direct proof, proof by contrapositive and by contradiction, proof by cases, weak and strong induction, and the well-ordering principle that both rest on.

  2. Counting and combinatorics

    Sum and product rules, permutations and combinations, arrangements with repetition, inclusion–exclusion, arithmetic and geometric sums, and the pigeonhole principle.

  3. Recurrence relations and modular arithmetic

    Solving recurrences by iteration and by the characteristic equation; congruences, fast modular powers, Fermat's little theorem and modular inverses.

SKU 3.3 · Graphs, trees and discrete probability

  1. Graphs and trees

    Kinds of graph, degree and the handshake lemma, paths, connectivity and Euler circuits, isomorphism, trees and their counts, tree traversals, and spanning trees.

  2. Probability and probability distributions

    Sample spaces and events, the addition and complement rules, conditional probability and independence, random variables, expectation and variance, and the binomial distribution.

  3. Bayesian probability and Bayes' theorem

    The law of total probability, Bayes' theorem as the update from prior to posterior, the base-rate effect, and combining independent pieces of evidence.

MORE COMPUTER SCIENCE GUIDES

All study guides

Read the full guide beside your practice questions.

Open the app