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. Walk on graphs and adjacency matrix.

Groups, fields, polynomials, and logic

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]\). Linear feedback shift registers. A field with 4 elements:\(F_2[a]\) with \(a^2=a+1\). Nibbles and bytes. Boolean functions in 2 and 3 variables. De Morgan laws. Representation of generic Boolean functions in 3 variables.

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. Primitive elements in Zn when n is prime. The number of primitive elements. Application to cryptography. A toy stream cypher and Diffie-Hellman key-exchange. Self-evaluation test.

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.