Discrete Mathematics

Sets, relations, and functions

Sets and Operations: Intersection, Union, Complement, etc. Simple graphs defined on the set of vertices and edges. Cartesian product and relations. Relations on the Cartesian plane: well-known polynomial curves. Partial order and equivalence relations.Cartesian product and relations. Relations on the Cartesian plane: well-known polynomial curves. Partial order and equivalence relations. Matrices. Matrices and relations. Equivalence relations and matrices. Functions. Injective, surjective and bijective functions. A connection with matrices and curves. Composition of functions. Permutations. Walk on graphs and adjacency matrix. Proof by induction. Examples: Gauss formula; Cardinality of the power set of a finite set.

Discrete Algebra

Algebraic structures: Groups and Fields. The group of permutation \(S_3\). The set of bits \(F_2\). Operations on \(F_2\). Distributive law. Properties of the field. \(F_2\) is a field. Polynomial on bits: \(F_2[x]\). Operations over polynomials on bits. Powers of \((x+1)\) and the Pascal triangle of 0 and 1. Number of functions from \(F_2\) into \(F_2\). The division algorithm in \(F_2[x]\). Irreducible polynomials. Examples of computations. Vectors of bits. Vectors as polynomials in \(F_2[x]\). A field with 4 elements:\(F_2[a]\) with \(a^2=a+1\). Linear feedback shift registers.

Boolean functions and Logic

Boolean functions and their representation into squarefree polynomial form. Boolean functions in 2 variables and logic. The or operator in a polynomial form. De Morgan laws. Representation of generic Boolean functions in 3 variables. Some examples on different areas.

Modular arithmetic and applications

An introduction to modular arithmetic. The clocks wit 7 and 12 hours. Representations of integers on \(Z_n\) for a fixed n. Operations on \(Z_n\). Sum and product and their tables. A question: When \(Z_n(+,.)\) is a field? Circulant graphs with vertices of degree 2 and their relations with \(Z_n\). Prime numbers and coprimality. The Eratosthenes' sieve. The number of primes are infinite. A proof by contradiction. Coprimality condition for the uniqueness of solution of a linear equation in \(Z_n\). The Chinese Remainder Theorem (CRT). Splitting \(Z_{ab}\) into \(Z_a\times Z_b\) when a and b are coprime and then related circulant graphs. Euler \(\phi\) function. Computation of \(\phi(n)\) knowing the factorization of \(n\). Theorem of Euler. Corollary of Fermat and its application: The computation of big prime numbers. Primitive elements in \(Z_n\) when n is prime. The number of primitive elements. Application to cryptography. A toy stream cypher and Diffie-Hellman key-exchange.

Counting

Inclusion-exclusion principle for two and three sets. An example counting in two ways: By inclusion-exclusion theorem and by Euler phi function. Dispositions with repetition. Permutations and dispositions without repetition. Combinations. Pascal's triangle and binomial theorem. Stifel's formula.

Bibliography

M. Ceria, G. Rinaldo, M. Sala. “Bits, Bytes and Friends". Aracne editrice. 2022.

G. Rinaldo, F. Romeo. "Notes of Discrete Mathematics". A.A. 2022-2023.