🎡

Discrete mathematics

TagsMath
Created
Updated

What is discrete mathematics?

It also known as Mathematics for computer science.

Discrete mathematics is the study of numerable sets, it distinct from others. – such as integers, graphs, and statements in logic.
🏫
Discrete \neq Discreet

Collins Dictionary

Wiki

https://www.merriam-webster.com/dictionary/numerable

https://www.dictionary.com/browse/numerable?s=t

https://wikidiff.com/countable/numerable#:~:text=As adjectives the difference between,able to be counted%3B countable.

Discrete. "separate, distinct from others," late 14c., from Old French discret, discre, and directly from Latin discretus "separated;" see discreet. Related: Discretely; discreteness. https://www.etymonline.com/word/discrete

Resources

The Canon

NameWhy?TopicsAuthorsLast edition
Discrete mathematicsMost topics. Several examples. Coding.Richard Johnsonbaugh
Mathematics for Computer Science - TextbookThe clearestAlbert R MeyerEric LehmanF Thomson Leighton
Discrete Mathematics and Its ApplicationsKenneth H. Rosen
Discrete and combinatorial mathematicasRalph P. Grimaldi
Mathematics for Computer Science (6.042J) - CourseAdam ChlipalaAlbert Meyer
Concrete Mathematics (Second edition)AdvanceDiscrete calculusDiscrete probabilityNumber TheoryDonald E. KnuthOren PatashnikRonald L. Graham

Requisites

Unrequisites

Foundations topics

Applications

Sets

Definitions

📌
A collection of objects is a set.

Level 1.

Collection. A group of objects of one type that have been collected by one person or in one place. Oxford dictionary.

Object. The objects are sometimes referred to as elements or members. Elements are unique.

Level 2.

Group. A number of people or things that are located close together or are considered or classed together. Oxford dictionary.

Level 3.

Number - The content of a statement of number is an assertion about a concept. [source: The Foundations of Arithmetic, §55, Engl.transl. page 67].

How to use sets?

TAG is the set of all elements such that element checks properties\text{TAG is the set of all elements such that element checks properties}.

Finite sets. E.g. A={1,2,3,4}A=\{\text{1,2,3,4}\}

Either infinite or large finite sets. E.g. A={xx is positive, even integer}A=\{x|x\text{ is positive, even integer} \}

Number sets

Worked examples

Mathematical logic

Key ideas

Logic is the basis of all reasoning.
A statement or proposition is a declarative sentence that is either true or false, but not both. Remember structure no content.
🏌🏼‍♂️
What are the four types of sentences? Declarative, exclamatory, imperative, and interrogatory. https://typesofsentences.com/

A predicate can be understood as a proposition whose truth depends on the value of one or more variables.

Truth tables

See "truth"

Truth table generator

When you wish to provide a conclusion (or proof in mathematics), you must use chain statements throughout logical consequences (or connectives, methods, and pieces of evidence) from a base set of previous results – such as axioms, theorems, and definitions.

value judgment

You gonna use variables to represent prepositions, thus as you use letters in algebra. e.g.

p:1+2=3p:1+2=3

Logical formulas

Worked examples

1=-1?

Pythagorean theorem

Problem Set

Proofs

What is the proof?

Proof. A finite sequence of statements (called well-formed formulas in the case of a formal language), each of which is a previous result -axiom, an assumption, experiments, or theorems- in the sequence by a rule of inference.

Axiom. Simple postulate or assumption based on a priori knowledge and free contradictions.

Theorems. Important true statements.

Lemma. Preliminary statements.

Corollary. Statements that follows few logical steps from theorem.

Developing mathematical methods to verify programs and systems remains an active research area.

Good proofs

Methods

Proof by perfect induction o Proof by exhaustion

Proof of a Boolean theorem through perfect induction.

Simple induction

We know by Modus Ponens:

P(0)    P(1)P(0).Therefore, P(1).P(0)\implies P(1)\\ P(0).\\ \text{Therefore, }P(1).

The principle of induction says

[P(0)nP(n)    P(n+1)]    nP(n)[P(0) \wedge \forall nP(n)\implies P(n+1)]\implies \forall nP(n)
Base case: P(0)Inductive Hypothesis: Assume that P(n) is trueInductive step: \text{Base case: }P(0)\\ \text{Inductive Hypothesis: Assume that }P(n) \text{ is true}\\ \text{Inductive step: }
(nP(n)    nP(n+1)) iff nP(n+1)(\forall n P(n)\implies \forall n P(n+1)) \text{ iff } \forall nP(n+1)\\

nP(n+1)\forall n P(n+1) use nP(n)\forall n P(n) when nP(n)    nP(n+1)\forall n P(n)\implies \forall n P(n+1) but the same to simple P(n+1)P(n+1)if always is true then P(n)P(n)  is always true.

Worked example.

https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf

https://math.stackexchange.com/questions/2926239/when-we-can-use-mathematical-induction-and-when-we-cant

https://www.purplemath.com/modules/inductn2.htm

Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction

Zermelo-Fraenkel Axioms

Our Axioms

Mathematical data types

Counting

Sums and Asymptotics

Cardinality Rules

The Bijection Rule

Bijection := one-to-one correspondence

Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

What does it mean to write |A| = n?

It means that there is a bijection f : A → {1, . . . , n}

MIT OpenCourseWare. 2016. 3.3.3 Counting with Bijections: Video. YouTube. Retrieved May 25, 2021 from https://www.youtube.com/watch?v=n0lce1dMAh8‌

The Bijection Rule or Equinumerosity

Let S and T be two finite sets. If there exists one-to-one correspondence (or bijection) between them, from S to T, if and only if S=T|S|=|T| i.e. S and T have the same number of elements. This is taken as the definition.

https://www.cs.colostate.edu/~cs220/summer19/slides/16_bijection_rule.pdf

Counting Sequences

Multiplication Principle or Product Rule

P1×P2×...×Pn={(p1,p2,...pn)p1P1,p2P2,...,pnPn}=all sequencesP_1\times P_2\times ... \times P_n=\{(p_1,p_2,...p_n)|p_1\in P_1,p_2 \in P_2,...,p_n\in P_n\}=\text{all sequences} called Cartesian product.

Thus, if P1,P2,,PnP_1,P_2,\cdots ,P_n are finite sets, then

P1×P2××Pn=P1P2Pn|P_1\times P_2 \times \cdots \times P_n|=|P_1|\cdot|P_2|\cdots|P_n|

For example, if A={x,y,z}A=\{x,y,z\} and B={1,2,3}B=\{1,2,3\}

A×B={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)}A\times B=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)\}

A×B=AB=33=9|A\times B|=|A|\cdot|B|=3 \cdot 3=9

Key ideas

Product Rule Worked examples

Exercises 10–12 ask about strings of length 5 formed using the letters ABCDEFG without repetitions.

Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points.

Addition Principle or Sum Rule

If A1,A2,...,AnA_1,A_2,...,A_n are disjoint sets, then:

A1A1...An=A1+A2+...+An|A_1\cup A_1\cup ...\cup A_n|=|A_1|+|A_2|+...+|A_n|

Inclusion–exclusion principle

If XX and YY are finite sets, then

XY=X+YXY|X\cup Y|=|X|+|Y|-|X\cap Y|

The k-to-1 rule or division rule

If B is a finite set and f : A → B maps precisely k items of A to every item of B, then A has k times as many items as B.

https://dspace.mit.edu/bitstream/handle/1721.1/70477/6-042j-fall-2002/contents/readings/ln9.pdf

The division rule is a common way to ignore “unimportant” differences when you are counting things. You can count distinct objects, and then use the division rule to “merge” the ones that are not significantly different.

Permutations

A permutation of n things taken r at a time, written P(n,r), is an arrangement in a row of r things, taken from a set of n distinct things. Order matters.

In your problem, (a0,a1,a2)(a1,a2,a0)?(a_0,a_1,a_2)\ne(a_1,a_2,a_0)?

Example: How many permutations of the letters ABCDEF contain the letters DEF together in anyorder?

Counting Subsets or combinations

A combination of n things taken r at a time, written C(n,r) or n r (“n choose r”) is any subset of r things from n things. Order makes no difference.

In your problem, (a0,a1,a2)=(a1,a2,a0)?(a_0,a_1,a_2)=(a_1,a_2,a_0)?

The key points to remember in this section are that a permutation takes order into account and a combination does not take order into account. Thus, a key to solving counting problems is to determine whether we are counting ordered or unordered items.

Counting subsets=CoutingGroup by repetitions\text{Counting subsets}=\frac{Couting}{\text{Group by repetitions}}

Combinatorial Proofs

n(n1k1)=k(nk)n{n-1 \choose k-1}=k{n \choose k}

Vandermonde's identity

(m+nk)=j=0k(mj)(nkj){m+n \choose k} = \sum^k_{j=0} {m \choose j}{n\choose k-j}

The Binomial Theorem

Pascal’s Triangle Identity

Worked examples

The Pigeonhole Principle

Generating Functions

Finite calculus

Recurrences relations, sequences, and subsequences, or difference equations

Worked examples

Note

https://web.math.utk.edu/~cplaut/docs/analysis.pdf

https://wp.kntu.ac.ir/hrahmanei/Adv-Control-Books/Difference-Equations-Axler.pdf

http://mitran-lab.amath.unc.edu/courses/MATH564/biblio/text/02.pdf

https://oeis.org/

http://math.colga

https://people.math.aau.dk/~matarne/11-imat/notes2011a.pdfte.edu/math312/Spring1999/iterate.html

An Introduction to Difference Equations (Undergraduate Texts in Mathematics)

Introduction to Difference Equations 978-0486650845

https://www.cimt.org.uk/projects/mepres/alevel/discrete_ch14.pdf

https://www.rand.org/content/dam/rand/pubs/reports/2006/R374.pdf

https://people.math.umass.edu/~lr7q/ps_files/teaching/math456/Chapter3.pdf

Graph theory

💡
A graph G is a par if sets (V,E) where V is called vertices (or nodes) and a set E of edges (or arcs) such that each edge eEe\in E is associated with a pair of vertices.

Definiciones

Grafo o red -Graph-

G=(V,E)G = (V, E), donde V son los vértices y E las aristas.

Loop

Una arista conectada a un vértice a sí misma.

Directed

Walk

Cycle

Circuit

Open walk

Closed walk

Definiciones

ConceptoDef.EjemploRepresentaciónObservaciones
Graph, NetworkG = (V, E), donde V son los vertices y E las aristas.
LoopUna arista conectada a un vertice a si mismo.
DirectedCada arista tiene una direccion.
WalkUna sequencia v0v1v2...v_0v_1v_2...
Cycle
Circuit
Open walkWalk donde el primer y el ultimo vertice son distintos.
Closed walkWalk donde el primer y el ultimo vertice son iguales.
TrailUn walk abierto con distintas aristas.
PathUn walk abierto con distintos vertices y aristas. Todos los path son trials.
Euler TrailUn trial que incluye todas las aristas del grafo, esto es, en el trial cada arista aparece exactamente una sola vez.
ConnectedUn grafo donde existe un path entre cualquier par de de vertices.
TourClosed Walk que incluye todos las aristas al menos una vez.
Euler Tour o Eulerian CircuitTour donde cada arista es incluida una unica vez. Asi, es un Euler Trial cerrado. Otra def: Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión.
EulerianEulerian es un grafo que tiene un Euler Tour
ComponentUn maximo conectado subgrafo.
TreeUn conectado subgrafo.
Free treeUn arbol con ninguna raiz.
DAGGrafo aciclico dirigido.
Eulerian -Tour de Euler, ciclo euleriano, camino de Euler- Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión.
HamiltonianGrafo con un ciclo visitando cada vertice una vez.
Cut -corte-Conjunto de vertices donde cada remoción incrementa el numero de componentes.
Cut-setEl minimo corte.
Cut-edgeEl tamano de un corte.
k-ConnectedUn grafo conectado con la remoción de k-1 vertices.
k-ToughSV,S\forall S\subseteq V,S\neq\emptyset we have kc(GS)Skc(G-S)\le|S|
k-RegularUn grafo donde todos los vertices tienen grado k.
k-FactorUn k-regular esparza un subgrafo.
MatchingUn conjunto de aristas, no pares que no tienen adjuntos.
CliqueUn conjunto de vertices que son todos adjuntos.
Ind. setUn conjunto de vertices donde ninguno es adjunto.
Vertex coverUn conjunto de vertices el cual cubre todos las aristas.
Planar graphUn grafo el cual esta embebido en un plano.
Plane graphEl embemiento de un planar graph.
OrderNumero de vertices en el grafo.
SizeNumero de aristas en el grafo.

Notación

EspañolRep. matemáticaEjemplo
Grafo o redGG
Nodo o vértice -vertex-v,uv,u
Conjunto de aristas, arcos o enlace -edge-E(G)E(G), G.EG.E
Conjunto de vérticesV(G)V(G), G.VG.V
Cantidad de componentesc(G)c(G)
Subgrafo inducidoG[S]G[S]
Grado de un vérticedeg(v)deg(v)
Máximo grado del grafoΔ(G)\Delta(G)
Menor grado del grafoδ(G)\delta(G)
Número cromático X(G)X(G)
Número cromático de aristas XE(G)X_E(G)
Complemento del grafoGCG^C
Grafo completoKnK_n
Grafo completo bipartitoKn,n2K_{n,n_2}
Número de Ramseyr(k,l)r(k,l)
Grado de entradaindegree(v)in-degree(v)
Grado de salidaoutdegree(v)out-degree(v)

Notas

http://www.uop.edu.pk/ocontents/Euler Tours.pdf

https://d3gt.com/unit.html

If you want to represent a graph use Graphviz and its dot language.

Para representar grafos usa Graphviz y su dot languaje, una version online esta disponible o https://edotor.net/

Frank Harary. Graph Theory. Addison-Wesley, 1969.