Difference between propositional logic and predicate logic

As part of computer science studies, students are required to study mathematical logic as a core topic. It's a part of the much richer subject of discrete mathematics — in fact, the very foundations of discrete mathematics.

In this respect, you might've come across two names: propositional logic and predicate logic. This is a standard division that's present in many discrete math books and courses. The question stands: What exactly is the difference between these two? Let's find out.

What is propositional logic?

Propositional logic is reasoning with very simple, declarative statements known as propositions. For example, It is raining outside is a simple statement that proposes a fact. It's either true or false, but not both. This is a proposition.

Propositional logic is all about working with propositions. You can apply logical operators on propositions to obtain new "derived" propositions — often referred to as compound propositions — just like you can obtain new numbers by applying arithmetic operators (e.g. ::+::, ::-::) to numbers.

For example, if It is raining is true, then applying the negation operator gives the proposition It is not raining which, as you can reason by pure intuition, is false. In formal notation, if ::r:: represents the proposition It is raining, which is denoted as:

then the negation that It is not raining. is denoted as:

There are many operators in propositional logic but, in general, the five fundamental ones are: negation (::\neg::), disjunction (::\lor::), conjunction (::\land::), conditional (::\to::), and biconditional (::\leftrightarrow::).

What is predicate logic?

Propositional logic can capture a lot of ideas that occur in the real world. You can use it to formalize reasoning. However, propositional logic hits a wall when you try to capture unknown entities or assert something for multiple things in a set.

For instance, there's no way in propositional logic to capture the statement All male students are in the examination hall, which isn't honestly that complex to comprehend. The insufficiency of propositional logic arises because of the word "all" in this statement.

If you were to really model this statement using propositional logic, you'd have absolutely no other way but to treat it as one single proposition: That is:

Of course, this isn't of any use to anyone. And that's precisely where predicate logic comes in. It allows you to work with statements including unknown entities and words like "all" or "some."

Predicate logic is reasoning with two fundamental constructs: predicates and quantifiers. Predicates are characteristics of unknown entities whereas quantifiers assert these predicates for one or multiple items in a given set, often referred to as the universe or the domain.

For example, here's how predicate logic would model the statement given earlier: First, consider the domain. Let's say it's the set of all students (male and female). Next, define a predicate function called ::M(x):: to assert that a given student from this set is a male, as follows:

Next, define another predicate function to capture the "in the examination hall" part of the original statement; let's call it E(x):

With these building blocks in hand, the original statement becomes this:

The ::\forall:: symbol is the universal quantifier, read as "for all." This logical expression is read as For every student ::x:: in the set of students, if ::x:: is a male, then ::x:: is in the examination hall. Expressed concisely, it's basically just saying that Every male student is in the examination hall.

The differences

So now that you have a general overview of propositional and predicate logic, let's quickly go through the main differences between them.

Positioning as a subject

First things first, if we talk about the positioning of these subjects in the broader category of mathematical logic, propositional logic is hands-down the very foundation that all variants of logic build upon. By that means, predicate logic is also an extension of propositional logic.

Core building blocks

The core building block of propositional logic is propositions — simple, declarative statements. In contrast, the core building blocks of predicate logic are predicates and quantifiers. As a matter of fact, practically most expressions in predicate logic are propositions themselves but internally that's NOT the case.

For example, the statement All male students are in the examination hall. that you saw above is certainly a proposition — it's either true or false. But internally, the components ::x:: is male or ::x:: is in the examination hall aren't propositions — by virtue of the fact that they have an unknown entity ::x::.

Expressiveness

I won't say that propositional logic isn't expressive; you certainly can express a plethora of naturally occurring statements in it. However, it's not as expressive as predicate logic.

The best argument to second this is that most theorems in mathematics assert a property for some or all elements in a domain. For instance, All primes have only two positive factors. asserts a property for all prime numbers — and therefore it can only be modeled using predicate logic.

Proving equivalences

It's a well-established law in propositional logic know as the first De Morgan law that:

In words, the negation of a disjunction is the conjunction of the negations. This is called an equivalence which means that the left side of the ::\equiv:: is identical to the right side. But how do you verify this?

Well, one trivial method is to use a truth table. I won't go into it in this article but using truth tables to verify logical equivalences in propositional logic is a pretty common activity.

However, in predicate logic, there's no way to use a truth table. So, an equivalence like the following in predicate logic:

can only be proven using intuition and previously established laws.

Applications

Propositional logic has directly influenced a branch of mathematics known as Boolean algebra which in turn in used in the construction of digital circuits.

Fundamentally, every single operation that a computer is able to do comes down to primitives electronic circuits which are designed based on ideas that have their roots in propositional logic. (Honestly, I find this a miraculous application of logic.)

Predicate logic isn't used in digital circuit design but that's not to say that it doesn't have practical applications in computer science. Formally verifying programs is an indispensable thing, especially for mission-critical software where a mistake could potentially risk the lives of humans. That's where predicate logic enters.

Automatic theorem provers, like Rocq, are based on concepts in mathematics that have their roots in predicate logic, and are in turn used to formally verify software. Hence, it's not wrong to say that predicate logic is an integral part of modern-day software.