Notes in ETH CS::Discrete Math

To Subscribe, use this Key

Status	Last Update	Fields
Published	11/12/2024	Set laws: What does idempotence mean? (def)
Published	11/12/2024	Set laws:How is this law called? \[A \cap A= A\]\[A \cup A = A\]
Published	11/12/2024	Set laws:How is this law called?\[A \cup B = B \cup A\]\[A \cap B = B \cap A\]
Published	11/12/2024	Set laws:  What does commutativity mean? (def)
Published	11/12/2024	Set laws:  What does associativity mean? (def)
Published	11/12/2024	Set laws:  How do we call this rule?\[A \cup (B \cup C) = (A \cup B) \cup C\]\[A \cap (B \cap C) = (A \cap B) \cap C\]
Published	11/12/2024	Set laws:  How do we call this rule?\[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]\[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]
Published	11/12/2024	Set laws: What does disributivity mean? (def)
Published	11/12/2024	Set laws: What does absorption mean? (def)
Published	11/12/2024	Set laws: What rule is this? \[A \cup (A \cap B) = A\]\[A \cap (A \cup B) = A\]
Published	10/28/2024	For an equivalence relation \(\theta\) on a set \(A\) and for \(a \in A\), the set of elements of \(A\) that are {{…
Published	10/28/2024	If {{c1::any two elements of a poset \((A; \preceq)\) are comparable}}, then \(A\) is called {{c2::totally ordered (or {{c3::linea…
Published	10/28/2024	Let \(\rho\) be a relation from \(A\) to \(B\) and let \(\sigma\) be a relation from \(B\) to \…
Published	11/12/2024	How is a semi-infinite set defined?
Published	11/12/2024	Why is Discrete Maths so important in Computer Science?
Published	11/12/2024	The 3 forms of proven statements
Published	11/12/2024	How are unproven statements called? (Truth value unknown)
Published	11/12/2024	What is a mathematical statement and how is it different from a formula?
Published	11/12/2024	The most important symbols for Statements and Logic/Formulas (important card)
Published	11/12/2024	What is logic equivalence?
Published	11/12/2024	What is a logical consequence?
Published	11/12/2024	What does it mean if 2 formulas F and G are both logical consequences of each other?
Published	11/12/2024	What does it mean for a formula to be a tautology? What does it mean for a formula to be satisfiable or unsatisfiable?
Published	11/12/2024	What are logical circuits in propositional logic?
Published	11/12/2024	The most important basic equivalences of propositional logic
Published	11/12/2024	What is predicate logic? How is it different from propositional logic (what does it add)?
Published	11/12/2024	Rephrase the statement "for every natural number there is a larger prime" in predicate logic
Published	11/12/2024	When can we interpret formulas as statements?
Published	11/12/2024	What does the following statement mean: \(\models A \lor B \lor \lnot A\)
Published	11/12/2024	Useful rules for predicate logic
Published	11/12/2024	Proof pattern: Composition of Implications
Published	11/12/2024	Direct proof of an implication
Published	11/12/2024	Indirect proof of an implication
Published	11/12/2024	Modus Ponens (Proof)
Published	11/12/2024	Proof by case distinction
Published	11/12/2024	Proof by contradiction
Published	11/12/2024	Existence proofs
Published	11/12/2024	Russell's Paradox
Published	11/12/2024	Definition of equivalent sets
Published	11/12/2024	Definition of Subsets
Published	11/12/2024	If A is a subset of B and B a subset of C, then?
Published	11/12/2024	Definition of unions and intersections
Published	11/12/2024	Definition of the difference of sets
Published	11/12/2024	Existence proofs by Pigeonhole principle
Published	11/12/2024	What is the cardinality of a set and how is it denoted?
Published	11/12/2024	The symbols for intersection, union, exclusion in set theory
Published	11/12/2024	Definition of set equality
Published	11/12/2024	Formal definition of subsets
Published	11/12/2024	What to know about the empty set
Published	11/12/2024	The power set of a set and its properties
Published	11/12/2024	The cartesian product of sets and its properties
Published	11/12/2024	Relations on two sets (binary relations)
Published	11/12/2024	The important laws of Unions, Intersections and subsets (Hint: Similiar to Lemma 2.1 ;) )
Published	11/12/2024	Representations on relations
Published	11/12/2024	The set operations on relations
Published	11/12/2024	The special properties of relations
Published	11/12/2024	Transitive Closure of relations
Published	11/12/2024	What are equivalence relations and equivalence classse?
Published	11/12/2024	What are partial order relations?
Published	11/12/2024	Are symmetric and anti-symmetric relations opposites of each other?
Published	11/12/2024	What are partitions of equivalence relations?
Published	11/12/2024	Hasse Diagrams (cover, comparable, illustration)
Published	11/12/2024	Lexicographic order of posets
Published	11/12/2024	Special elements in posets (minimal, least, lower bound, greatest lower bound)
Published	11/12/2024	When is a poset well ordered?
Published	11/12/2024	Functions (looking at them from a perspective of relations, properties, partial functions, image, preimage)
Published	11/12/2024	Injections, Surjections, Bijections
Published	11/12/2024	Equinumerous, dominates, countability of sets
Published	11/12/2024	Countably infinite sets and finite sets
Published	11/12/2024	How to approach countability problems
Published	11/12/2024	Important countable and uncountable sets
Published	11/12/2024	Computable and uncomputable functions
Published	11/12/2024	How to prove uncountability (countability can be proved in a similarly adapted way)
Published	11/12/2024	What is the essence of number theory? What do we try to do?
Published	11/12/2024	What is a ring, what is it's relevance to number theory?
Published	11/12/2024	Definition of the divisors
Published	11/15/2024	Definition of division with remainders
Published	11/15/2024	Why do we want to abstract algebra?
Published	11/15/2024	What are operations on algebraic structures?
Published	11/15/2024	What is an algebra and what are some examples for an algebra?
Published	11/15/2024	The greatest common divisor (gcd). Definition, useful lemmas and how to find it
Published	11/15/2024	Least common multiples
Published	11/15/2024	Fundamental theorem of arithmetic
Published	11/15/2024	Representing the lcm and gcd using the fundamental theorem of arithmetic
Published	11/15/2024	Modular congruences (definition on single variables and congruences on arithmetic operations)
Published	11/15/2024	Modular arithmetic (high-level, key concepts, connection to remainders, tricks for mod 9 and mod 11)
Published	11/15/2024	Multiplicative inverses
Published	11/15/2024	The Chinese Remainder Theorem
Published	11/15/2024	How does the Diffie-Hellmann Key-Agreement work?
Published	11/15/2024	What are (left/right) neutral elements  in algebras?
Published	11/15/2024	Associativity of algebras
Published	11/15/2024	What are monoids?
Published	11/15/2024	What are inverse elements?
Published	11/15/2024	Groups
Published	11/15/2024	Minimality of the group axioms
Published	11/15/2024	The direct product of groups
Published	11/15/2024	Group homormophisms (+ the difference to isomorphisms, examples)
Published	11/15/2024	Subgroups
Published	11/15/2024	Multiplicative notation for operations in group theory
Published	11/15/2024	The order of groups
Published	11/15/2024	Cyclic groups
Published	11/15/2024	What is the order of subgroups (according to Lagrange)?
Published	11/15/2024	What is the order of every element in a group?
Published	11/15/2024	Groups of prime order, features according to Lagrange's theorem
Published	11/15/2024	Definition of the set \(\mathbb{Z}_m^*\). Is it a group?
Published	11/15/2024	Euler function \(\varphi(m)\), result for any m (hint: prime factorization)
Published	11/15/2024	What is x in \(a^{\varphi(m)} \equiv_m x\)?
Published	11/22/2024	When is the group \(\mathbb{Z}_m^*\) cyclic?
Published	11/26/2024	How does RSA work?
Published	11/26/2024	What is a ring?
Published	11/26/2024	What is the charasterictic of a ring?
Published	11/26/2024	What are the units of a ring?
Published	11/26/2024	Divisors of Rings (also greatest common divisor)
Published	11/26/2024	Zerodivisors (Nullteiler) and integral domains (Integritätsbereich)
Published	11/26/2024	Polynomial rings (Definition)
Published	11/26/2024	Addition and multiplication in polynomial rings
Published	11/26/2024	For any commutative ring R, R[x] is a {{c1::commutative ring}}
Published	11/26/2024	Let D be an integral domain. Then: (i.) D[x] is {{c1:: an integral domain}}(ii.) The degree of the product of two polynomials is {{c1:: the sum o…
Published	11/26/2024	What is the definition of a field?
Published	11/26/2024	When is \(\mathbb{Z}_n\) a field and what is it called?
Published	11/26/2024	Why are fields so important?
Published	11/26/2024	Solve the following system of linear equations over \(\mathbb{Z}_{11}\):
Published	11/26/2024	A field is an {{c1::integral}} domain
Published	11/26/2024	A polynomial \(a(x) \in F[x]\) is called monic if {{c1::the leading coefficient is 1}}
Published	11/26/2024	(polynomial fields) If b(x) divides a(x), then so does {{c1:: \(v \cdot b(x)\)}}
Published	11/26/2024	In the polynomial field GF(7)[x], factor the polynomial: \(x^3 + 2x^2 + 5x + 2\)
Published	11/26/2024	When is a polynomial (over a field) called irreducible and what does it mean for a polynomial to be irreducible?
Published	11/26/2024	The greatest common divisor in polynomials over fields
Published	11/26/2024	Let  \(a(x) := x^4 + 2x^3 + 2x + 1\) and let \(b(x) := x^3 + 2x^2 + 1\). Find the \(gcd(a(x), b(x))\) using the euclidea…
Published	11/26/2024	Division with remainders in F[x]
Published	11/26/2024	Let \(a(x) := x^4 + x^3 + x^2 + 1\) and \(b(x) := x^2 + 1\)Calculate q(x) and r(x), s.t. \(a(x) = b(x) \cdot q(x) + r(x)\) an…
Published	11/26/2024	What is polynomial evaluation?
Published	11/26/2024	What are the roots of a polynomial a(x)?
Published	11/26/2024	For a field F, \(\alpha \in F\)  is a root of a(x) if and only if {{c1::\((x - \alpha) \) divdes a(x).}}
Published	11/26/2024	A polynomial a(x) of degree 2 or 3 over a field F is irreducible if and only if {{c1::it has no root.}}
Published	11/26/2024	For a field F, a nonzero polynomial \(a(x) \in F[x]\) has at most {{c1::d}} roots where {{c1::d}} \(\leq\) {{c1::deg(a(x…
Published	11/26/2024	What is polynomial interpolation? How many values of a(x) must be known?
Published	11/29/2024	What is the ring \(F[x]_{m(x)}\)? Is it a ring and what is it's cardinality if F is a finite field?
Published	11/29/2024	"Easily check" that these equations are indeed congruent:
Published	11/29/2024	When does \(a(x) \cdot b(x) \equiv_{m(x)} 1\) have a solution?
Published	11/29/2024	When is the ring \(F[x]_{m(x)}\) a field and why?
Published	11/29/2024	What is the importance of error correcting codes?
Published	11/29/2024	What is a (n,k)-encoding function?
Published	11/29/2024	An (n,k)-error correcting code over the alphabet A with \(\|A\| = q\) {{c1:: is a subset of \(\mathcal{A}^n\)}} of cardinality …
Published	11/29/2024	What is the hamming distance of two strings of equal length?
Published	11/29/2024	What is the minimum distance of an error-correcting code?
Published	11/29/2024	What is a decoding function in error-correcting codes? How many errors \(t\) can this function at most correct in terms of the minimum dista…
Published	11/29/2024	Error correcting codes based on polynomial evaluation
Published	11/29/2024	What is the goal of logic?
Published	11/29/2024	What are syntatic objects in logic?
Published	11/29/2024	What is the truth function in logic? What does it define?
Published	11/29/2024	What is the verification function in logic?
Published	11/29/2024	What is a proof system in logic?
Published	11/29/2024	When is a proof system sound and when is a proof system complete?
Published	11/29/2024	Develop a proof system to show that a given graph has a hamiltonian cycle
Published	11/29/2024	Is it possible to develop a proof system that shows that a given graph has no hamiltonian cycle?
Published	11/29/2024	Which of the following must be efficient in a valid proof system: Proof generation or proof verification?
Published	11/29/2024	Is a proof system limited to a certain type of mathematical statement or can it be easily generalized?
Published	11/29/2024	If there exists a proof system for some type of statement, must there also exist a proof system for the negation of this statement?
Published	11/29/2024	What is the general goal of logic?
Published	11/29/2024	What do the elements \(s \in S, p \in P\) consist of?
Published	11/29/2024	What is a derivation (or deduction) in logic?
Published	11/29/2024	What does a step in a proof consist of?
Published	11/29/2024	Which of the following is carefully defined in a proof system?1. The function \(\tau\)2. The function \(\phi\)
Published	11/29/2024	What in the syntax of a logic?
Published	11/29/2024	What are the semantics of a logic?
Published	11/29/2024	What is the meaning of \(\{ F_1, ..., F_k\} \vdash_R G\)?
Published	11/29/2024	What is the difference between \(\vdash\) and \(\models\) ?
Status	Last Update	Fields