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