Discrete Structures
섹션 개요
-
Diskretne strukture VSŠ 63705
-
Predavanja: Matematična indukcija. Izjave, izjavni vezniki.
Lectures: Mathematical induction (pages 5-7); Introduction into propositional logic: atoms, logical connectives, logical formulas, truth tables, equivalence of formulas (pages 95-99).
-
-
Predavanja: Izjavni izrazi, resničnostna tabela, enakovredni izjavni izrazi. Zakoni izjavnega računa. DNO in KNO. Polni nabori izjavnih veznikov.
Lectures: Laws of propositional logic (pages 11-15); Disjunctive and conjuctive normal form (pages 4-6); Functionally complete sets of connectives
-
Predavanja: Sklepanje v izjavnem računu. Formalizacija sklepov, definicija pravilnega sklepa, pravila sklepanja, dokaz pravilnosti sklepa. Pomožni sklepi - pogojni sklep, sklep s protislovjem, analiza primerov.
Lectures: Logical inference - formalization, rules of inferece, derivation of rules (pages 100-104). Proof by contradiction (section 8 - on this link you can freely download the book), proof by conditional derivation (section 6.2), proof by cases (explained at the bottom of section 3.2).
-
Predikatni račun - jezik predikatnega računa, izjavne formule. Doseg kvantifikatorjev, proste in vezane spremenljivke. Interpretacija izjavne formule, enakovrednost izjavnih formul, preimenovanje spremenljivk, zakoni predikatnega računa,
Predicate logic: predicates; universe of discourse, universal and existential quantifier. (link) Scope of quantifiers. Free and bound variables. Well-formed formulas. Interpretation of formulas, equivalence of formulas. Laws of predicate calculus.
-
-
-
Družine množic. Kartezični produkt.
Moč končnih množic.
Definicija relacije, lastnosti relacij.
Families of sets. Cartesian product.
Cardinality of finite sets.
Relations, definition and examples, properties of relations (link),
-
-
Predavanja: Grafična predstavitev relacije, operacije z relacijami, potence relacij, tranzitivna in tranzitivno-refleksivna ovojnica relacije.
Preslikave, njihove lastnosti.
Lectures: Graphical representation of relations, operations with relations (link), transitive closure and reflexive-transitive closure (pages 28-30)
-
-
Preslikave, kompozitum preslikav, inverzna preslikava. Lastnosti kompozituma preslikav. Ekvivalenčna relacija, ekvivalenčni razredi, faktorska množica.
Lectures: Mappings, inverse mapping (link), composition of functions (link). Properties of a composition of functions (link). Equivalence relation (link), equivalence classes, factor set. (link)
-
Teorija grafov - lema o rokovanju, grafična zaporedja, družine grafov (polni in prazni grafi, polni dvodelni grafi, cikli, poti). Izomorfizem grafov. Podgrafi. Sprehod, pot, obhod, cikel.
Graph theory - definition of a graph (link), degree of a vertex, handshaking lemma (Theorem 5.1.1), graphical sequences (link), families of graphs (complete and empty graphs, complete bipartite graphs, cycles, paths) (link). Graph isomorphism (link). Subgraphs (link). Walk, path , closed walk, cycle. (link)
-
-
Teorija grafov - Povezanost in komponente za povezanost. Razdalja v grafu. Karakterizacija dvodelnih grafov. Eulerjev problem. Drevesa in gozdovi.
Graph theory - Connected graphs and components. Distance in graphs. (link) Characterization of bipartite graphs. (link) Euler's problem (link). Trees and forests.
-
Predavanja: Hamiltonovi grafi. Barvanja grafov.
Teorija števil - deljivost.
Lectures: Hamiltonian graphs (link ). Coloring of graphs.Number theory - divisibility.
-
-
Predavanja: Teorija števil - deljivost, razširjeni Evklidov algoritem, linearne diofantske enačbe.
Permutacije. Zapis s tabelicami in zapis z disjunktnimi cikli.
Lectures: Number theory - divisibility, extended Euclidean algorithm (link), linear diophantine equations (link).
Permutations (link). Tables and disjoint cycles representations.