Дискретна математика

Дискретна математика је област математике која проучава структуре које су у својој основи дискретне у смислу да не подржавају или не захтевају појам континуалности. Већина ако не сви објекти који се проучавају у дискретној математици су пребројиви скупови, попут целих бројева, коначних графова, и формалних језика. Дискретна математика је добила на значају у протеклих неколико деценија услед својих примена у рачунарству. Концепти и нотације из дискретне математике су корисни за изучавање и описивање објеката или проблема у области рачунарских алгоритама и програмских језика. Неке од области чијим изучавањем се бави дискретна математика су: релације, функције, Булова алгебра, групе и групоиди, прстени и поља, полиноми, комплексни бројеви, конструкција поља, системи линеарних једначина, матрице и детерминанте.

Дискретна математика изучава и графове као на слици због занимљивих математичких својстава као и због практичне примене на реалне проблеме и развој рачунарских алгоритама.

У универзитетским наставним плановима и програмима, „Дискретна математика“ се појавила током 1980-их, у почетку као курс за подршку рачунарству; њен садржај је у то време био донекле насумичан. Наставни план и програм се након тога развио у сарадњи са напорима ACM и MAA у курс који је у основи намењен развоју математичке зрелости код студената прве године; стога је то данас предуслов за математичке смерове и на неким универзитетима. Појавили су се и неки уџбеници дискретне математике за средњошколски узраст. На овом нивоу, дискретна математика се понекад посматра као припремни курс, слично предкалкулусу у овом погледу.

Велики изазови, прошли и садашњи

Многа истраживања у теорији графова била су мотивисана покушајима да се докаже да се све карте, попут ове, могу обојити коришћењем само четири боје, тако да ниједна област исте боје не дели ивицу. Кенет Апел и Волфганг Хакен су то доказали 1976. године.

Историја дискретне математике укључивала је низ изазовних проблема који су усмерили пажњу у области овог поља. У теорији графова, многа истраживања била су мотивисана покушајима да се докаже теорема о четири боје, која је први пут изречена 1852. године, али није била доказана све до 1976. (од стране Кенета Апела и Волфганга Хакена, уз значајну помоћ рачунара).

У логици, други проблем на листи отворених проблема Дејвида Хилберта представљеној 1900. године био је да се докаже да су аксиоми аритметике конзистентни. Друга Геделова теорема о непотпуности, доказана 1931. године, показала је да то није могуће – барем не унутар саме аритметике. Хилбертов десети проблем је био да утврди да ли дата полиномска Диофантова једначина са целобројним коефицијентима има целобројно решење. Јуриј Матијасевич је 1970. године доказао да се то не може учинити.

Потреба за разоткривањем немачких кодова у Другом светском рату довела је до напретка у криптографији и теоријској компјутерској науци, са првим програмабилним дигиталним електронским рачунаром који је развијен у енглеском Блечли парку под вођством Алана Тјуринга и његовог семиналног дела, О израчунљивим бројевима. Истовремено, војни захтеви су мотивисали напредак у истраживању операција. Хладни рат је значио да је криптографија остала важна, са фундаменталним напретком као што је криптографија са јавним кључем који се развијао у наредним деценијама. Операциона истраживања су остала важна као алат у пословању и управљању пројектима, а метод критичног пута развијен је 1950-их. Телекомуникациона индустрија је такође мотивисала напредак у дискретној математици, посебно у теорији графова и теорији информација. Формална верификација исказа у логици била је неопходна за развој софтвера система критичних за безбедност, и напредак у аутоматизованом доказивању теорема је био вођен овом потребом.

Неколико области дискретне математике, посебно теоријске рачунарске науке, теорија графова и комбинаторика, су важне у решавању изазовних проблема биоинформатике повезаних са разумевањем стабла живота.

Тренутно, један од најпознатијих отворених проблема у теоријској информатици је проблем P = NP, који укључује однос између класа сложености P и NP. Клејов математички институт понудио је награду од милион долара за први тачан доказ, заједно са наградама за шест других математичких проблема.

Види још

• Теорија графова
• Теорија коначних аутомата
• Граматике и формални језици

Литература

• Norman L. Biggs (2002-12-19). Discrete Mathematics. Oxford University Press. ISBN 978-0-19-850717-8. 
• Dwyer, John (2010). An Introduction to Discrete Mathematics for Business & Computing. ISBN 978-1-907934-00-1. 
• Susanna S. Epp (2010-08-04). Discrete Mathematics With Applications. Thomson Brooks/Cole. ISBN 978-0-495-39132-6. 
• Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics.
• Grimaldi, Ralph P. (2004). Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. ISBN 978-0-201-72634-3. 
• Donald E. Knuth (2011-03-03). The Art of Computer Programming, Volumes 1-4a Boxed Set. Addison-Wesley Professional. ISBN 978-0-321-75104-1. 
• Matoušek, Jiří; Nešetřil, Jaroslav (1998). Discrete Mathematics. Oxford University Press. ISBN 978-0-19-850208-1. 
• Obrenic, Bojana (2003-01-29). Practice Problems in Discrete Mathematics. Prentice Hall. ISBN 978-0-13-045803-2. 
• Rosen, Kenneth H.; John G. Michaels (2000). Hand Book of Discrete and Combinatorial Mathematics. CRC PressI Llc. ISBN 978-0-8493-0149-0. 
• Kenneth H. Rosen (2007). Discrete Mathematics: And Its Applications. McGraw-Hill College. ISBN 978-0-07-288008-3. 
• Simpson, Andrew (2002). Discrete Mathematics by Example. McGraw-Hill Incorporated. ISBN 978-0-07-709840-7. 
• Walicki, Michał (2011). Introduction to Mathematical Logic. Singapore: World Scientific Publishing. ISBN 9789814343879. 
• Boolos, George; Burgess, John; Jeffrey, Richard (2002). Computability and Logic (4th изд.). Cambridge University Press. ISBN 9780521007580. 
• Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972). What is mathematical logic?. London, Oxford, New York City: Oxford University Press. ISBN 9780198880875. Zbl 0251.02001. 
• Enderton, Herbert (2001). A mathematical introduction to logic (2nd изд.). Boston MA: Academic Press. ISBN 978-0-12-238452-3. 
• Fisher, Alec (1982). Formal Number Theory and Computability: A Workbook. (suitable as a first course for independent study) (1st изд.). Oxford University Press. ISBN 978-0-19-853188-3. 
• Hamilton, A.G. (1988). Logic for Mathematicians (2nd изд.). Cambridge University Press. ISBN 978-0-521-36865-0. 
• Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (2nd изд.). New York City: Springer. ISBN 9780387942582. 
• Katz, Robert (1964). Axiomatic Analysis. Boston MA: D. C. Heath and Company. 
• Mendelson, Elliott (1997). Introduction to Mathematical Logic (4th изд.). London: Chapman & Hall. ISBN 978-0-412-80830-2. 
• Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd изд.). New York City: Springer. ISBN 9781441912206. doi:10.1007/978-1-4419-1221-3. 
• Schwichtenberg, Helmut (2003—2004). Mathematical Logic (PDF). Munich: Mathematisches Institut der Universität München. Приступљено 2016-02-24. 
• Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, (2004) ISBN 0-19-852981-3. Covers logics in close relation with computability theory and complexity theory
• van Dalen, Dirk (2013). Logic and Structure. Universitext. Berlin: Springer. ISBN 978-1-4471-4557-8. doi:10.1007/978-1-4471-4558-5. 
• Andrews, Peter B. (2002). An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd изд.). Boston: Kluwer Academic Publishers. ISBN 978-1-4020-0763-7. 
• Barwise, Jon, ур. (1989). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Amsterdam: Elsevier. ISBN 9780444863881. 
• Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 9780521587136. 
• Jech, Thomas (2003). Set Theory: Millennium Edition. Springer Monographs in Mathematics. Berlin, New York: Springer. ISBN 9783540440857. 
• Kleene, Stephen Cole.(1952), Introduction to Metamathematics. New York: Van Nostrand. (Ishi Press: 2009 reprint).
• Kleene, Stephen Cole (1967). Mathematical Logic. John Wiley. ISBN 0-486-42533-9. OCLC 523472. 
• Shoenfield, Joseph R. (2001). Mathematical Logic (2nd изд.). A K Peters. ISBN 9781568811352. 
• Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2000). Basic Proof Theory. Cambridge Tracts in Theoretical Computer Science (2nd изд.). Cambridge University Press. ISBN 978-0-521-77911-1. 
• Augusto, Luis M. (2017). Logical consequences. Theory and applications: An introduction. London: College Publications. ISBN 978-1-84890-236-7. 
• Boehner, Philotheus (1950). Medieval Logic. Manchester. 
• Cohen, Paul J. (1966). Set Theory and the Continuum Hypothesis. Menlo Park CA: W. A. Benjamin. 
• Cohen, Paul J. (2008). Set theory and the continuum hypothesis. Mineola NY: Dover Publications. ISBN 9780486469218. 
• J.D. Sneed, The Logical Structure of Mathematical Physics. Reidel, Dordrecht, 1971 (revised edition 1979).
• Davis, Martin (1973). „Hilbert's tenth problem is unsolvable”. The American Mathematical Monthly. 80 (3): 233—269. JSTOR 2318447. doi:10.2307/2318447. 
  Reprinted as an appendix in Davis, Martin (1985). Computability and Unsolvability. Dover. ISBN 9780486614717. 
• Felscher, Walter (2000). „Bolzano, Cauchy, Epsilon, Delta”. The American Mathematical Monthly. 107 (9): 844—862. JSTOR 2695743. doi:10.2307/2695743. 
• Ferreirós, José (2001). „The Road to Modern Logic-An Interpretation” (PDF). Bulletin of Symbolic Logic. 7 (4): 441—484. JSTOR 2687794. S2CID 43258676. doi:10.2307/2687794. hdl:11441/38373. Архивирано из оригинала (PDF) 02. 02. 2023. г. Приступљено 20. 12. 2021. 
• Hamkins, Joel David; Löwe, Benedikt (2007). „The modal logic of forcing”. Transactions of the American Mathematical Society. 360 (4): 1793—1818. S2CID 14724471. arXiv:math/0509616 . doi:10.1090/s0002-9947-07-04297-3. 
• Katz, Victor J. (1998). A History of Mathematics. Addison–Wesley. ISBN 9780321016188. 
• Morley, Michael (1965). „Categoricity in Power”. Transactions of the American Mathematical Society. 114 (2): 514—538. JSTOR 1994188. doi:10.2307/1994188 . 
• Soare, Robert I. (1996). „Computability and recursion”. Bulletin of Symbolic Logic. 2 (3): 284—321. CiteSeerX 10.1.1.35.5803 . JSTOR 420992. doi:10.2307/420992. 
• Solovay, Robert M. (1976). „Provability Interpretations of Modal Logic”. Israel Journal of Mathematics. 25 (3–4): 287—304. S2CID 121226261. doi:10.1007/BF02757006 . 
• Woodin, W. Hugh (2001). „The Continuum Hypothesis, Part I” (PDF). Notices of the American Mathematical Society. 48 (6). 
• Banach, Stefan; Tarski, Alfred (1924). „Sur la décomposition des ensembles de points en parties respectivement congruentes” (PDF). Fundamenta Mathematicae (на језику: француски). 6: 244—277. doi:10.4064/fm-6-1-244-277 . 
• Bochenski, Jozef Maria, ур. (1959). A Precis of Mathematical Logic. Synthese Library, Vol. 1. Превод: Otto Bird. Dordrecht: Springer. ISBN 9789048183296. doi:10.1007/978-94-017-0592-9. 
• Burali-Forti, Cesare (1897). A question on transfinite numbers.  Reprinted in van Heijenoort 1976, стр. 104–111
• Cantor, Georg (1874). „Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen” (PDF). Journal für die Reine und Angewandte Mathematik. 1874 (77): 258—262. S2CID 199545885. doi:10.1515/crll.1874.77.258. 
• Carroll, Lewis (1896). Symbolic Logic. Kessinger Legacy Reprints. ISBN 9781163444955. 
• Dedekind, Richard (1872). Stetigkeit und irrationale Zahlen (на језику: немачки).  English translation as: "Consistency and irrational numbers".
• Dedekind, Richard (1888). Was sind und was sollen die Zahlen?.  Two English translations:
  • 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
  • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787–832.
• Fraenkel, Abraham A. (1922). „Der Begriff 'definit' und die Unabhängigkeit des Auswahlsaxioms”. Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse (на језику: немачки). стр. 253—257.  Reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice" in van Heijenoort 1976, стр. 284–289.
• Frege, Gottlob (1879), Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle a. S.: Louis Nebert. Translation: Concept Script, a formal language of pure thought modelled upon that of arithmetic, by S. Bauer-Mengelberg in van Heijenoort 1976.
• Frege, Gottlob (1884), Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: W. Koebner. Translation: J. L. Austin, 1974. The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.
• Gentzen, Gerhard (1936). „Die Widerspruchsfreiheit der reinen Zahlentheorie”. Mathematische Annalen. 112: 132—213. S2CID 122719892. doi:10.1007/BF01565428.  Reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.
• Gödel, Kurt (1929). Über die Vollständigkeit des Logikkalküls [Completeness of the logical calculus]. doctoral dissertation. University Of Vienna. 
• Gödel, Kurt (1930). „Die Vollständigkeit der Axiome des logischen Funktionen-kalküls” [The completeness of the axioms of the calculus of logical functions]. Monatshefte für Mathematik und Physik (на језику: немачки). 37: 349—360. S2CID 123343522. doi:10.1007/BF01696781. 
• Gödel, Kurt (1931). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” [On Formally Undecidable Propositions of Principia Mathematica and Related Systems]. Monatshefte für Mathematik und Physik (на језику: немачки). 38 (1): 173—198. S2CID 197663120. doi:10.1007/BF01700692. 
• Gödel, Kurt (1958). „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”. Dialectica (на језику: немачки). 12 (3–4): 280—287. doi:10.1111/j.1746-8361.1958.tb01464.x .  Reprinted in English translation in Gödel's Collected Works, vol II, Solomon Feferman et al., eds. Oxford University Press, 1993.
• van Heijenoort, Jean, ур. (1976). From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (3rd изд.). Cambridge MA: Harvard University Press. ISBN 9780674324497. (pbk.). 
• Hilbert, David (1899). Grundlagen der Geometrie (на језику: немачки). Leipzig: Teubner.  English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.
• Hilbert, David (1929). „Probleme der Grundlegung der Mathematik”. Mathematische Annalen. 102: 1—9. S2CID 122870563. doi:10.1007/BF01782335. Архивирано из оригинала 08. 09. 2017. г. Приступљено 20. 12. 2021. 
• Hilbert, David; Bernays, Paul (1934). Grundlagen der Mathematik. I. Die Grundlehren der mathematischen Wissenschaften. 40. Berlin, New York City: Springer. ISBN 9783540041344. JFM 60.0017.02. MR 0237246. 
• Kleene, Stephen Cole (1943). „Recursive Predicates and Quantifiers”. Transactions of the American Mathematical Society. 53 (1): 41—73. JSTOR 1990131. doi:10.2307/1990131 . 
• Lobachevsky, Nikolai (1840). Geometrishe Untersuchungen zur Theorie der Parellellinien (на језику: немачки).  Reprinted in English translation as Robert Bonola, ур. (1955). „Geometric Investigations on the Theory of Parallel Lines”. Non-Euclidean Geometry. Dover. ISBN 0-486-60027-0. 
• Löwenheim, Leopold (1915). „Über Möglichkeiten im Relativkalkül”. Mathematische Annalen (на језику: немачки). 76 (4): 447—470. ISSN 0025-5831. S2CID 116581304. doi:10.1007/BF01458217. Архивирано из оригинала 08. 09. 2017. г. Приступљено 20. 12. 2021.  Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort (1967). A Source Book in Mathematical Logic, 1879–1931. Harvard Univ. Press. стр. 228—251. 
• Mancosu, Paolo, ур. (1998). From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s. Oxford University Press. 
• Pasch, Moritz (1882). Vorlesungen über neuere Geometrie. 
• Peano, Giuseppe (1889). Arithmetices principia, nova methodo exposita (на језику: литвански). 
• Richard, Jules (1905). „Les principes des mathématiques et le problème des ensembles”. Revue Générale des Sciences Pures et Appliquées (на језику: француски). 16: 541.  Reprinted in English translation as "The principles of mathematics and the problems of sets" in van Heijenoort 1976, стр. 142–144.
• Skolem, Thoralf (1920). „Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen”. Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse (на језику: немачки). 6: 1—36. 
• Soare, Robert Irving (22. 12. 2011). „Computability Theory and Applications: The Art of Classical Computability” (PDF). Department of Mathematics. University of Chicago. Приступљено 23. 8. 2017. CS1 одржавање: Формат датума (веза)
• Swineshead, Richard (1498). Calculationes Suiseth Anglici (на језику: литвански). Papie: Per Franciscum Gyrardengum. 
• Tarski, Alfred (1948). A decision method for elementary algebra and geometry. Santa Monica CA: RAND Corporation. 
• Turing, Alan M. (1939). „Systems of Logic Based on Ordinals”. Proceedings of the London Mathematical Society. 45 (2): 161—228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3 . 
• Weyl, Hermann (1918). Das Kontinuum. Kritische Untersuchungen über die Grund lagen der Analysis (на језику: немачки). Leipzig. 
• Zermelo, Ernst (1904). „Beweis, daß jede Menge wohlgeordnet werden kann”. Mathematische Annalen (на језику: немачки). 59 (4): 514—516. S2CID 124189935. doi:10.1007/BF01445300. Архивирано из оригинала 05. 03. 2016. г. Приступљено 20. 12. 2021.  Reprinted in English translation as "Proof that every set can be well-ordered" in van Heijenoort 1976, стр. 139–141.
• Zermelo, Ernst (1908a). „Neuer Beweis für die Möglichkeit einer Wohlordnung”. Mathematische Annalen (на језику: немачки). 65: 107—128. ISSN 0025-5831. S2CID 119924143. doi:10.1007/BF01450054. Архивирано из оригинала 08. 09. 2017. г. Приступљено 20. 12. 2021.  Reprinted in English translation as "A new proof of the possibility of a well-ordering" in van Heijenoort 1976, стр. 183–198.
• Zermelo, Ernst (1908b). „Untersuchungen über die Grundlagen der Mengenlehre”. Mathematische Annalen. 65 (2): 261—281. S2CID 120085563. doi:10.1007/BF01449999. Архивирано из оригинала 08. 09. 2017. г. Приступљено 20. 12. 2021. 

Спољашње везе

• Discrete mathematics Архивирано на сајту Wayback Machine (29. август 2011) at the utk.edu Mathematics Archives, providing links to syllabi, tutorials, programs, etc.
• Iowa Central: Electrical Technologies Program Discrete mathematics for Electrical engineering.