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/15/2024	When is the group \(\mathbb{Z}_m^*\) cyclic?
Published	11/15/2024	How does RSA work?
Published	11/15/2024	What is a ring?
Published	11/15/2024	What is the charasterictic of a ring?
Published	11/15/2024	What are the units of a ring?
Published	11/15/2024	Divisors of Rings (also greatest common divisor)
Published	11/15/2024	Zerodivisors (Nullteiler) and integral domains (Integritätsbereich)
Published	11/15/2024	Polynomial rings (Definition)
Published	11/15/2024	Addition and multiplication in polynomial rings
Published	11/15/2024	For any commutative ring R, R[x] is a {{c1::commutative ring}}
Published	11/15/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…
Status	Last Update	Fields