{math.logic} A short note

It is worth noting that in the Electrical Engineering (EE) curriculum, there is little space left for important topics such as Mathematical Logic. They either assume that EE students are naturally logical or they will never use mathematical logic in their studies.

I remember that we had to take propositional and predicate logic in high school (although at that time, I did not know the English terminology). Well, I am using Temporal Logic in one of my grad courses and I thought, I should refresh my mind on the subject matter. In fact, I was reading a PhD thesis and the author compared temporal logic to propositional and predicate logic. On the second thought, I figured that I do not remember the exact boundary between different branches of mathematical logic. Wikipeida is a nice resource and won't let you down if you are searching for a comp sci related topic.

Simply put, when you deal with propositions (such as p, q, etc.) you call it propositional logic. Predicate logic (also called First-Order Logic) extends propositional logic and includes quantifications such as ∀ and ∃ (for all, for some). For example, ∃x P(x) means that for some x, P(x) is true (first-order).

There is also Second-Order Logic, where the predicates are in the variable position. For example, ∃P P(x) is second-order. Second-order logic extends the first-order, which in turn, extends the propositional logic. These branches of logic are also called binary logic, because they use only two truth values (TRUE and FALSE).

Temporal logic is completely different in nature, as it includes time and considers it as a sequence of states. Temporal logic can describe evolution of a system over time. A sentence can be true at certain instants and false in others. In fact, temporal logic is quite useful to study Finite State Machines, where the behaviour evolves over time. There are branches to it, such as CTL (Computation Tree Logic) and LTL (Linear Temporal Logic). Temporal Logic is somewhat new in computer science (though it existed since 1960's). The scientist who introduced temporal logic in computer science and specifically in system verification won a Turing Award (Noble prize of computing) in 1996.

BTW, There is an introductory course at the Department of Computing Science at the University of Alberta that covers an introduction to logic with a focus on its use in computer science (does not cover temporal logic). I think for a first or second year undergraduate student, it is not completely clear why they should learn mathematical, but as they are promised in that course, they will find tons of applications, sooner or later.