miniatura|Grafs com aquests es troben entre els objectes estudiats per les matemàtiques discretes, per les seves interessants propietats matemàtiques, la seva utilitat com a models de problemes del món real i la seva importància en el desenvolupament d'algorismes informàtics La matemàtica discreta és l'estudi d'estructures matemàtiques que es poden considerar «discretes» (d'una manera anàloga a les variables discretes, que tenen una bijecció amb el conjunt dels nombres naturals) més que «continues» (de manera anàloga a les funcions contínues).
Els objectes estudiats en matemàtiques discretes inclouen nombres enters, grafs i enunciats en lògica. Per contra, les matemàtiques discretes exclouen temes de «matemàtiques contínues» com ara els nombres reals, el càlcul o la geometria euclidiana. Els objectes discrets sovint es poden enumerar per nombres enters; més formalment, les matemàtiques discretes s'han caracteritzat com la branca de les matemàtiques que s'ocupa dels conjunts numerables (conjunts finits o conjunts amb la mateixa cardinalitat que els nombres naturals). Tanmateix, no hi ha una definició exacta del terme «matemàtiques discretes».
El conjunt d'objectes estudiats en matemàtiques discretes pot ser finit o infinit. El terme «matemàtica finita» de vegades s'aplica a parts del camp de les matemàtiques discretes que s'ocupen de conjunts finits, particularment aquelles àrees rellevants per als negocis.
La investigació en matemàtiques discretes va augmentar a la segona meitat del , en part a causa del desenvolupament dels ordinadors digitals que funcionen en passos «discrets» i emmagatzemen dades en bits «discrets». Els conceptes i les anotacions de les matemàtiques discretes són útils per estudiar i descriure objectes i problemes en branques de la informàtica, com ara algorismes informàtics, llenguatges de programació, criptografia, demostració automatitzada de teoremes, i desenvolupament de programari. A més, les implementacions per ordinador són importants per aplicar idees de matemàtiques discretes a problemes del món real.
Tot i que els principals objectes d'estudi de les matemàtiques discretes són objectes discrets, sovint també s'utilitzen mètodes analítics de les matemàtiques «continues».
En els plans d'estudis universitaris, les matemàtiques discretes van aparèixer a la dècada del 1980, inicialment com a curs de suport a la informàtica; el seu contingut era una mica casual en aquell moment. Posteriorment, el pla d'estudis s'ha desenvolupat conjuntament amb els esforços de l'Association for Computing Machinery (ACM) i la Mathematical Association of America (MAA) en un curs que pretén bàsicament desenvolupar la maduresa matemàtica en els estudiants de primer any; per tant, avui en dia també és un requisit previ per als estudis de matemàtiques en algunes universitats. També han aparegut alguns llibres de text de matemàtiques discretes d'educació secundària. En aquest nivell, les matemàtiques discretes es veuen de vegades com un curs preparatori, com el precàlcul en aquest sentit.
El Premi Fulkerson s'atorga a treballs destacats de matemàtiques discretes.
Temes de les matemàtiques discretes Informàtica teòrica La informàtica teòrica inclou àrees de matemàtiques discretes rellevants per a la informàtica. Es basa molt en la teoria de grafs i la lògica matemàtica. Dins de la informàtica teòrica s'inclou l'estudi dels algorismes i estructures de dades. La computabilitat estudia el que es pot calcular en principi i té una estreta vinculació amb la lògica, mentre que la complexitat estudia el temps, l'espai i altres recursos que prenen els càlculs. La teoria d'autòmats i la teoria del llenguatge formal estan estretament relacionades amb la computabilitat.
Les xarxes de Petri i l'àlgebra de processos s'utilitzen per modelar sistemes informàtics, i s'utilitzen mètodes de matemàtiques discretes per analitzar circuits electrònics VLSI. La geometria computacional aplica algorismes a problemes geomètrics i representacions d'objectes geomètrics, mentre que l'anàlisi d'imatges per ordinador els aplica a representacions d'imatges. La informàtica teòrica també inclou l'estudi de diversos temes computacionals continus.
Teoria de la informació miniatura|Els codis ASCII de la paraula «Wiquipedia», donats aquí en binari, proporcionen una manera de representar la paraula en teoria de la informació, així com per als algorismes de processament de la informació. La teoria de la informació implica la quantificació de la informació. Molt relacionada hi ha la teoria de codis, que s'utilitza per dissenyar mètodes de transmissió i emmagatzematge de dades eficients i fiables. La teoria de la informació també inclou temes continus com ara: senyals analògics, codificació analògica, encriptació analògica.
Lògica
La lògica és l'estudi dels principis de raonament i inferència vàlids, així com de coherència, consistència i completesa. Per exemple, en la majoria dels sistemes de lògica (però no en la lògica intuïcionista), la llei de Peirce (((P→Q)→P)→P) és un teorema. Per a la lògica clàssica, es pot verificar fàcilment amb una taula de veritat. L'estudi de la demostració matemàtica és particularment important en lògica, i s'ha acumulat a la demostració automatitzada de teoremes i la verificació formal del programari.
Les fórmules lògiques són estructures discretes, com ho són les demostracions, que formen arbres finits o, de manera més general, estructures de grafs acíclics dirigits (amb cada pas d'inferència combinant una o més branques de premissa per donar una única conclusió). Els valors de veritat de les fórmules lògiques solen formar un conjunt finit, generalment restringit a dos valors: «cert» i «fals», però la lògica també pot ser de valor continu, per exemple, la lògica difusa. També s'han estudiat conceptes com ara arbres de prova infinita o arbres de derivació infinita, per exemple, la lògica infinitària.
Teoria de conjunts La teoria de conjunts és la branca de les matemàtiques que estudia els conjunts, que són col·leccions d'objectes, com ara {blau, blanc, vermell} o el conjunt (infinit) de tots els nombres primers. Els conjunts parcialment ordenats i els conjunts amb altres relacions tenen aplicacions en diverses àrees.
En matemàtiques discretes, els conjunts numerables (inclosos els finits) són el focus principal. L'inici de la teoria de conjunts com a branca de les matemàtiques sol estar marcat pel treball de Georg Cantor que distingia entre diferents tipus de conjunts infinits, motivat per l'estudi de les sèries trigonomètriques, i el desenvolupament posterior de la teoria dels conjunts infinits està fora de l'àmbit de les matemàtiques discretes. De fet, el treball contemporani en teoria descriptiva de conjunts fa un ús extensiu de les matemàtiques contínues tradicionals.
Combinatòria La combinatòria estudia la manera com es poden combinar o disposar estructures discretes. La combinatòria enumerativa es concentra a comptar el nombre de certs objectes combinatoris (per exemple, els dotze camins proporciona un marc unificat per comptar permutacions, combinacions i particions). La combinatòria analítica es refereix a l'enumeració (és a dir, la determinació del nombre) d'estructures combinatòries utilitzant eines d'anàlisi complexa i teoria de probabilitats. En contrast amb la combinatòria enumerativa que utilitza fórmules combinatòries explícites i funcions generatrius per descriure els resultats, la combinatòria analítica té com a objectiu l'obtenció de fórmules asimptòtiques. La combinatòria topològica es refereix a l'ús de tècniques de topologia i topologia algebraica/topologia combinatòria en combinatòria. La teoria del disseny és un estudi dels dissenys combinatoris, que són col·leccions de subconjunts amb certes propietats d'intersecció. La teoria de particions estudia diversos problemes d'enumeració i asimptòtics relacionats amb particions d'enters, i està estretament relacionada amb les q-sèries, funcions especials i polinomis ortogonals. Originalment com una part de la teoria de nombres i l'anàlisi, la teoria de les particions es considera ara una part de la combinatòria o un camp independent. La teoria de l'ordre és l'estudi de conjunts parcialment ordenats, tant finits com infinits.
Teoria de grafs miniatura|La teoria de grafs té una estreta relació amb la teoria de grups. Aquest graf d'un tetraedre truncat està relacionat amb el grup alternant A4 La teoria de grafs, l'estudi de grafs i xarxes, sovint es considera part de la combinatòria, però ha crescut prou gran i diferent, amb el seu propi tipus de problemes, per ser considerada com un tema per dret propi. Els grafs són un dels principals objectes d'estudi de les matemàtiques discretes. Es troben entre els models més omnipresents d'estructures naturals i fetes per l'home. Poden modelar molts tipus de relacions i dinàmiques de processos en sistemes físics, biològics i socials. En informàtica, poden representar xarxes de comunicació, organització de dades, dispositius computacionals, el flux de càlcul, etc. En matemàtiques, són útils en geometria i determinades parts de la topologia (per exemple, teoria de nusos).
La teoria de grafs algebraica té vincles estrets amb la teoria de grups, i la teoria de grafs topològica té vincles estrets amb la topologia. També hi ha grafs continus; tanmateix, en la seva major part, la investigació en teoria de grafs entra dins del domini de les matemàtiques discretes.
Teoria dels nombres miniatura|L'espiral d'Ulam de nombres, amb píxels negres que mostren nombres primers. Aquest diagrama indica patrons en la distribució de nombres primers La teoria dels nombres s'ocupa de les propietats dels nombres en general, particularment dels nombres enters. Té aplicacions a la criptografia i la criptoanàlisi, especialment pel que fa a l'aritmètica modular, les equacions diofàntiques, les congruències lineals i quadràtiques, els nombres primers i les proves de primalitat. Altres aspectes discrets de la teoria dels nombres inclouen la geometria dels nombres. En la teoria analítica de nombres també s'utilitzen tècniques de matemàtiques contínues. Els temes que van més enllà dels objectes discrets inclouen els nombres transcendents, l'aproximació diofàntica, l'anàlisi p-àdica i els cossos de funció.
Estructures algebraiques Les estructures algebraiques es presenten tant com a exemples discrets com com a exemples continus. Les àlgebres discretes inclouen: àlgebra booleana, utilitzada en portes lògiques i programació; àlgebra relacional, utilitzada en bases de dades; les versions discretes i finites de grups, anells i cos són importants en la teoria de codis algebraica; els semigrups discrets i els monoides apareixen en la teoria dels llenguatges formals.
Anàlegs discrets de les matemàtiques contínues Hi ha molts conceptes i teories en matemàtiques contínues que tenen versions discretes, com ara càlcul discret, transformades de Fourier discretes, geometria discreta, logaritmes discrets, geometria diferencial discreta, càlcul exterior discret, teoria de Morse discreta, optimització discreta, teoria de la probabilitat discreta, probabilitat discreta de distribució, equacions de diferència, sistemes dinàmics discrets i mesures vectorials discretes.
Càlcul de diferències finites, anàlisi discret i càlcul discret En el càlcul discret i el càlcul de diferència finita, una funció definida en un interval dels nombres enters se sol anomenar «seqüència». Una seqüència podria ser una seqüència finita d'una font de dades o una seqüència infinita d'un sistema dinàmic discret. Aquesta funció discreta es podria definir explícitament per una llista (si el seu domini és finit), o per una fórmula per al seu terme general, o podria estar donada implícitament per una relació de recurrència o equació de diferència.