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?
$\begingroup$
$\endgroup$
5
-
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$– André Souza LemosCommented Dec 5, 2015 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$– RaphaelCommented Dec 5, 2015 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$– user16034Commented Dec 5, 2015 at 22:18
-
$\begingroup$ Logicians invented computer science. $\endgroup$– Andrej BauerCommented Dec 5, 2015 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$– codyCommented Dec 7, 2015 at 23:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 5, 2015 at 17:27
-
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$– RaphaelCommented Dec 5, 2015 at 20:50