# 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.