I started computer science in university. And we started learning about Discrete and it's mathematics which is completely based on logic, which I understand. however, how is predicates, sets, proofs are related to computers ? I want to know the reason for learning these stuff?

  • 2
    $\begingroup$ "Discrete" is not a person. It is the quality of being "discrete": that deals with things that are discontinuous, made of distinct elements. $\endgroup$ Dec 5 '15 at 16:06
  • 1
    $\begingroup$ For the time being, accept that your teachers think it's important. That should be enough for you. (If you have a look around the site, I think you'll see enough examples.) $\endgroup$
    – Raphael
    Dec 5 '15 at 20:51
  • $\begingroup$ Nothing's closer to computer programming than logics and discrete maths. Programming is theorem proving. You shouldn't even be raising the question. $\endgroup$ Dec 5 '15 at 22:18
  • $\begingroup$ Logicians invented computer science. $\endgroup$ Dec 5 '15 at 22:26
  • $\begingroup$ Regardless of the motivations behind this question, I think it's a potentially interesting one to answer on this forum, in the spirit of this question: cs.stackexchange.com/questions/3028/…. $\endgroup$
    – cody
    Dec 7 '15 at 23:08

Very roughly speaking, Discrete Mathematics is the body of material that a computer scientist needs to know. You can look at it as that part of mathematics which doesn't involve limits, continuity, differentiation, or integration. In set notation, we have Discrete = Mathematics \ Calculus.

The usual topics in a Discrete course and their applications to CS are

  • Propositional and predicate logic: used to establish the correctness of a program.
  • Proofs: used throughout CS, for things like establishing the closure properties of, say, regular languages.
  • Functions: obvious uses, since functions are ubiquitous in CS.
  • Sets: you can't do much in the theory of databases without them
  • Relations: again, fundamental for databases and also the basis for algorithms such as topological sorting
  • Recurrences: lists and trees can be viewed as recursively defined. Also, you can't do much to establish the time or space complexity of algorithms without being conversant with recurrence relations
  • Graphs and trees: when establishing the properties of networks
  • Counting: again, fundamental for the design and analysis of algorithms
  • Probability: for example, finding the average time complexity of an algorithm

Obviously, I've left out many more uses, but you get the idea. One could make the point that essentially all of CS beyond Programming I uses the concepts of Discrete in one way or another.

  • 1
    $\begingroup$ FWIW, the wary reader may note that the first paragraph simplifies. There are many opinions on what kind of mathematics CS needs; google e.g. "Concrete Mathematics". $\endgroup$
    – Raphael
    Dec 5 '15 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.