Discrete math is typically a requirement in computer science undergraduate programs, and deals with logical arguments, sets, counting and combinatorics and shortest path algorithms (also known as graph theory).
What value does discrete math provide programmers?
Many ideas in discrete math directly relate to programming concepts because the skill of basic logical thinking is of great value. More advanced topics lead into algorithms and problem solving techniques, like the shortest path algorithms covered under tree and graph theory sections.
Proposition
A sentence (or mathematical equation) that is either always true or always false.
Here’s an example proposition, we’ll call p:
p: 2 + 2 = 4
In programming, we’re used to using propositions within the parentheses of a conditional construct that represent a boolean value; i.e:
int occurances = counter.getCount();
if (occurances == 4)
//
where 4 = 4 is our proposition that evaluates to true, for instance.
Negation
The logical not is the opposite of a proposition. Notating a negation is denoted as a single bar over the letter representing a given proposition. Other notations exist, and may vary by source.
In most programming languages the bang (!) notation is used for negating a boolean value, as such:
boolean isFound = parser.locate("needle");
if (!isFound)
//
Conjunction
The logical and combines two (or more) propositions. Given two propositions p and q, a conjunction is represented as “p and q” in plain English, or written in notation as:
p ∧ q
In programming, we might use a conjunction with an &&
operator:
boolean applied = person.applied(job);
boolean qualified = person.isQualified(job);
if (applied && qualified)
company.hire(person);
Disjunction
Combines two (or more) propositions with “or”. This is an inclusive or, meaning that one, or the other or both may be true for the entire statement to be considered true. Spoken as “p or q” or written in notation:
p ∨ q
In programming, we might implement a disjunction with an ||
operator like this:
if (!product.accepts(coupon) || coupon.isExpired())
return new InvalidCouponError();
Other Discrete Math Topics
- Propositions
- Conjunctions and disjuntctions
- Implications
- Truth tables
- Biconditional statements and logical equivalences
- Logical quantifiers
- Proofs
- Direct proofs and divisibilities
- Indirect proofs
- Sequences
- Recursive sequences
- Induction
- Strong inductino
- Set theory
- Basic probability
- Combinatorics
- Addition and multiplication principles
- Permutations and combinations
- Graphs, paths and circuits
- Trees
Continue reading other blog posts and posts within the mathematics category to continue learning.