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.
