Should mathematical logic be included in a discrete mathematics course for computer science?

I am going to teach 2nd-year undergraduate students in applied math or computer science a course called "Discrete Mathematics for Computer Science".

Most students who take this course plan to apply for graduate schools. This is a new course, so I will decide the syllabus myself.

I studied computer science for my PhD and my research is mostly in probability and combinatorics. So for most part of the course, I plan to teach these two topics.

However, I have also seen that mathematical logic is included in similar courses in some other university. This means

• Propositional logic: Combining propositions, truth table, axiomatic rule
• Predicate Logic: Negating quantifiers, combining quantifiers, and order of quantifiers

I am not familiar with this topic, so it's hard for me to judge if including it will be beneficial for students when they go to graduate schools. Is mathematical logic still an active domain of research in computer science?

Should I include it in my course?

• Could you clarify a bit with some examples of "mathematical logic"? I'm thinking you mean the kind of reasoning involved with set theory, truth tables, a la De Morgan and along those lines. Apr 30 '21 at 16:12
• California has a syllabus that includes required topics. Finite State Machines is on it. Definitely include sets and logic. Apr 30 '21 at 17:05
• Why would something being a current research topic have bearing on what gets taught at the sophomore level? I really don't get that? May 2 '21 at 2:27
• I find it strange that such a foundational class for CS has never before been taught, perhaps under some other name or scattered among other courses. May 2 '21 at 3:47
• @clay Depending on your university, I guess. I did a quick search for "discrete math syllabus" and I see a lot of classes plan to cover basic propositional/predicate logic. Additionally can confirm at my university that the class where students are formally introduced to these is "Discrete Math", usually in the second year... probably the first week or two would be devoted to those topics, but it would be repeated and expanded on in other courses later on. May 3 '21 at 20:58

Certainly the rudiments of logic are needed in computer science:

• Enough to understand Boolean expressions in if-statements. if (a < pi) and (not finished), etc.
• Enough to understand proofs by contradiction, and induction proofs.
• Enough to understand satisfiability, 3SAT.
• Enough to understand the undecidability of the halting problem for Turing machines.

Not needed: First-order predicate calculus. Resolution. Model theory. The Löwenheim–Skolem theorem. Etc.

• Some pieces of first-order logic may be needed to avoid errors like confusing "if for all x P(x) then for all x Q(x)" with "for all x (if P(x) then Q(x))". Apr 30 '21 at 17:42
• I don't agree that first-order predicate calculus is not needed. You cannot do much logical reasoning without it... I'm kind of surprised by your statement here... May 1 '21 at 3:59
• Also resolution might be interesting to bring up given it's use in logical programming languages like Prolog May 1 '21 at 6:15
• @user21820: One needs to understand $\forall$ and $\exists$, but as AndreasBlass says, these are pieces of FOL. In my experience, actual predicate calculations are rarely needed. May 1 '21 at 14:07
• @user21820: There’s a big difference between teaching students to do rigorous proofs with quantifiers in traditional mathematical language, and formally studying the FOL as an object language. The former is essential for students doing any kind of serious mathematics, including this course — that’s what stops them making unjustified intuitive leaps, etc. But it doesn’t require the latter — both historically and pedagogically, doing careful proofs has comes before formalising them. May 2 '21 at 19:11

The Association for Computing Machinery (which is the professional association for computer scientists) puts out a curriculum guideline for computer science. While the guideline is for what an entire program should include and does not specify how it should be broken into courses, the 41 hours of instruction it recommends under the heading of "Discrete Structures" is frequently taught as one course under a title like "Discrete Mathematics for Computer Science". They recommend:

• 4 hours on sets, relations, and functions
• 9 hours on basic logic
• 11 hours on proof techniques
• 5 hours on basic counting
• 4 hours on graphs and trees
• 8 hours on discrete probability

For more details, see p. 76-81 in ACM 2013 computer science curriculum

This is standard in the Discrete Mathematics course. I teach it, and all of the published textbooks I've looked at start similarly with the unit on logic. A few points on this:

• I mean, you need that stuff.
• Math majors take the course, not just CS majors.
• Frequently the whole raison d'être of the discrete math course is a replacement in lieu of a dedicated introduction to proofs course.
• The CS majors need that platform in order in order to engage with proofs about algorithms, re: halting, correctness, tractability.

My first instinct would just be to pick a good textbook and follow the same sequence; if you're mostly focused on research, then the textbook author has thought about the scaffolding issues much more deeply than you have.

My second suggestion, if that's not compelling, is to look at the rest of the sequence of your program. Has logic already been taught formally in another course? Then you can skip it. Has it not? Then the discrete math course is the intended delivery mechanism.

Finally: Not everything in the undergraduate program needs to link immediately to a trendy current research topic. Your students need the basics first, including (perhaps first and foremost: see the Trivium) classical logical.

Senior computer science student here (graduating in December). I took a similar course titled "Discrete Math for Computing" in my freshman year. It's been a few years so my memory is hazy (and having just this morning finished the most stressful semester I've ever had doesn't help with that), but going through my homework files, it seems the topics were roughly:

• propositional and predicate logic, including identities, inference, and proving arguments
• mathematical induction
• recursive sequences (e.g. Fibonacci)
• set theory
• combinatorics (counting, combinations, permutations, but not probability)
• graph theory and trees, including tree traversal (preorder, inorder, postorder) and how those traversal methods relate to arithmetic expressions (e.g. reverse Polish notation)
• Boolean algebra, linking back to the logic and set theory sections, and including Karnaugh maps
• base-n arithmetic (including a variety of n from 2 to 16, but with a focus on binary and hexadecimal)

As I mentioned, this was a course designed for an incoming freshman's first semester (requiring only a math placement test result qualifying them for pre-calc or calculus), so it was more of a broad survey, without many deep dives into a single topic. It was also a mandatory course for all computer science students, not one intended only for students going to graduate school.

Some future courses in the major expanded on some of the topics from this course; e.g. our statistics course expanded on combinatorics and really dived into probability, and we have a separate "Logic for Computer Science" course (also required) typically taken as a junior or senior that takes the propositional and predicate logic section from the discrete math course and expands on that topic over a full semester. Things like finite state machines and the halting problem are covered in various other mandatory courses in the major.

Since your course is for sophomores and apparently an elective, this obviously wouldn't perfectly apply to you, but hopefully it's helpful to see what an existing similar course elsewhere teaches.

One very important point to realize is that using FOL is completely different from studying FOL. The first is necessary for all logical reasoning, and hence you should include it in your course, if not how will those students ever learn to use FOL? The second is not; it is a mathematical investigation of FOL itself, and is carried out in a suitable meta-system MS, and is what the field of "mathematical logic" is all about. While mathematical logic is very interesting, it is not a good idea to attempt to teach it to beginners who do not yet know how to use FOL, not the least because working in MS requires using FOL already!

So yes the topics you mentioned (PL and then FOL including basic stuff like quantifier order) ought to be taught to students as early as possible. In fact, almost all courses with the title "mathematical logic" will not teach those stuff since it is already assumed, and they instead cover theorems of MS including semantic completeness of FOL and syntactic incompleteness of certain formal systems.

I speak from the perspective of a someone who got a bachelors in CS who is currently teaching a coworker programming. I have no formal training in education. I believe Propositional Logic is essential to a CS education and programming in general, so if your students aren't getting this knowledge elsewhere (which Discrete Math for a CS student atleast in my case was the only oppurtunity I had to learn this stuff in depth) make sure they are getting it in your class. Predicate Logic feels essential as well. There is a great amount of simplicity that can come into a program by not overcomplicating your propositional logic. Also if you don't know the equivalence of different propositional statements when you get in the work force it would be hard to read others code if they do it differently then you might generally.

As a very simple and overly trivial example !(a == b) can be written as a != b. And !(a && b) can sometimes be written as !a || !b by De Morgan's law. Not knowing these logical equivalences can continue to confuse a CS student.

Predicate Logic: Negating Quantifiers, Combining Quantifiers, Order of Quantifiers I am not familiar with this topic, so it's hard for me to judge if including it will be beneficial for students when they go to graduate schools. Is mathematical logic still an active domain of research in computer science? Should I include it in my course?

Predicate logic is important to young students, because it provides a building block to help them reason about correctness of Computer Programs and how to refactor (and possibly simplify or even improve efficiency of) them and keep the same outcome just as it was with propositional logic. For example one such example I gave to my coworker recently was about negating quantifiers. The two basic quantifiers are the existential quantifier (usually stated as a there exists statement. Such as "there exists a P such that it is Q"), and the universal quantifier (usually stated as an all statement, such as "all Ps are Qs"). We thought through a simple exercise with my coworker that said something to the effect of: "If not all of the numbers are greater than 3 return true otherwise false". Now it might be obvious to some, but the secret that predicate logic teaches you in the "NOT ALL Ps are Qs" part of the statement is that it's true "if and only if" (a.k.a. IFF, and in other less formal words only as long as) "THERE EXISTS atleast one P such that it is NOT Q". If and only if is another way to state the two statements are either true or false together.

So, given the above problem statement "If not all of the numbers are greater than 3 return true otherwise false", do you need to always check ALL of the n numbers? The answer is no not always, because as soon as you find THERE EXISTS one counterexample such that the statement is NOT the case you can break the loop. Yes this is a very trivial and simple example in this case only gave minor efficiency gains, but reasoning and creating logical proofs by induction and knowing things like loop invariants (such as ALL $$i - 1$$ elements up to the point of iteration are sorted) which both almost always use some form of quantifier will help your CS students so much in their Graduate level CS classes.

At some point they will probably have to prove correctness of algorithms in their graduate and hopefully their undergraduate studies. I only took one graduate level class in CS (during my bachelor's degree) and that was Computational Geometry which my teacher described as very similar to his Advanced Algorithms class he gave to undergraduate students. This computational geometry class I had to use both propositional logic as well as predicate logic on basically every single question and for sure for every assignment. That graduate class was basically pure theory with no code, but it was absolutely enlightening and logical proofs were absolutely a corner stone of that class.

Unless you are absolutely certain the CS students are learning these logical proof methods as a prereq to your class and to their other theory heavy CS classes, I would highly encourage you to teach them it. If you want help with learning the basics of Propositional and Predicate Logic I would check out the first and second chapters of the great course notes from the Mathematics for Computer Science course taught at MIT (basically that course is their version of Discrete Math, so feel free to borrow ideas from them on what should be taught to CS students). I learned all I know about propositional and predicate logic from those notes and my Discrete Math course in college, and it was never repeated to that same extent anywhere else in my CS education.

• A lot of CS departments at major US universities align their core curriculum to what is being taught at MIT. So that is a good suggestion. May 3 '21 at 23:57

Practical suggestion: I would doublecheck the rest of the standard curriculum and see if this stuff is covered elsewhere (or a good portion of it). For instance, would be surprised if they are not seeing Boolean algebra somewhere. (Heck, I wasn't even CS and got that in a survey EE course.)

• Just because the material might be covered elsewhere should not preclude it from being covered again in the discrete math course, especially if the course in question isn't a prerequisite. May 1 '21 at 1:52

The prerequisites of the course are important in recognizing your students' degree of exposure and penetration into these topics. If they've already completed curricula on formal logic and fundamental proofs, then repeating these in depth across too many lectures might be suboptimal and too easy/boring; on the other hand, providing a review at the beginning of the semester might be helpful. Summarily, it depends on the coursework that ALL students need to take during freshman year.

If they haven't taken any course in formal logic or math proofs, then I'd recommend:

• Week 1: intro formal logic, truth tables, propositional logic, common logical fallacies
• Week 2: algebraic proofs, contrapositives, proof by contradiction
• Week 3: (strong) induction
• Week 4: minterm/maxterm, logic statement simplification, kmaps, finite state machines / automata ("digital electronics week")
• Week 5: set theory basics and notation; countable and uncountable infinite sets (cardinality); subsets / partitioning
• Week 6: the definition of functions; relations; bijectivity
• Week 7: conditional probability, Bayes, Bernoulli processes
• Week 8: intro for combinatorics and permutations; counting two ways; binomial theorem; bijection counting
• Week 9: combinatorial proofs with inclusion/exclusion; counting subsets
• Week 10: trees and traversal
• Week 11: basic graphs, isomorphism; coloring; min paths and optimization techniques
• Week 12: GCDs; Euclidean algorithm; modular arithmetic, Fermat's, Diophantine equations
• Week 13+: applications in efficient algorithm design; algorithmic complexity; ensuring code correctness and making assertions; identifying and dealing with edge cases; statistical computing; recursion; network optimization; cryptography.

"Discrete Math" is a pretty broad way of categorizing topics in modern mathematics. It was required in my second year of undergrad CS, and mathematical logic was the central theme. We used "Discrete Mathematics and Its Applications" by Kenneth Rosen, and the syllabus followed the same progression as the chapters in the text. We covered every chapter except the last one ("Modeling Computation" which was covered extensively in an upper division course dedicated to that topic). It more or less went like this:

• propositional logic, predicates, quantifiers, and proof techniques
• sets, functions, sequences, series, cardinality, countable sets
• algorithms and complexity
• basic number theory (divisibility and congruence, modular arithmetic, residue classes, primality)
• induction, recursive relations, solving linear recurrence relations, inclusion/exclusion
• counting, generalized permutations and combinations
• basic probability, Bayes, expected value
• brief introduction to graphs/trees, their properties and common operations
• boolean algebra and functions (covered in greater detail in another required course)

We took several detours to topics outside of the text that our instructor thought would be beneficial, if not interesting (we proved Euler's identity and that Q is dense in R). It was challenging, but I liked that class. I still use the book as a reference occasionally. This was ~15 years ago at one of the larger midwestern universities.

TL;DR: FOL is the Foundation of almost all Information Representation

I'd recommend to include FOL for one more reason:

It's the foundation of nearly all information representation we do in software engineering, e.g. the direct basis of relational database systems.

Knowing about FOL makes clear what the limitations of such representations are, e.g. the virtually non-existent support for negating statements.

And personally, I find the interpretation of predicates as natural-language sentences with placeholders very useful, as a documentation what the bits and bytes in our data storages mean.