What is Propositional Logic

Today we’re exploring the question: what is propositional logic. Propositional logic is one of my favorite topics in discrete mathematics. It happens to also be the first topic I discuss in when I teach the subject. So, what is it? Let’s find out!

A definition

First, I think of discrete math as the study of discrete values. For example, the value 10 is discrete while the value 10.10 is continuous. Based on that thinking, I suggest that propositional logic is the study of discrete values that happen to only ever be True or False. Now, I don’t know of any textbook that will connect discrete math and propositional logic in such a manner, but I do because I like that way such a simple statement couples the two topics.

More formally, we can say that propositional logic is the set of rules by which we construct mathematical statements. Fortunately for us, the rules are not long and are all encoded in a standard notation (symbols). We’re going to naturally pick up the notation we repeatedly use. Other notation is rarely used and we should know where to look it up. Furthermore, in propositional logic, we develop the means to evaluate these mathematical statements as being True or False. We also develop the means to prove why or how such statements are True.

Of course, none of that means anything unless we know what propositions look like, right?

Our definition in action

Remember, propositions are statements that are demonstrably True or False. Take for example the following statements:

The sun will rise tomorrow.

x = 1

2 > 5

Both are statements. The first is true although it could be false. On the other hand, in the second statement, we have no idea what value x holds. Because we don’t know what value x holds, we cannot determine x’s truth state. Further, the third is false and I cannot imagine a reality in which it could be true. Thus, the first and third are propositional statements while the second is not.

Don’t let the variable x mislead us though. We can use variables in propositional statements too. The operational importance is that we (a) know what value the variable holds and (b) the statement is either true or false.

Pretty simple, right? Well, just like in normal language, propositions can grow large and complex.

A little more complex now

The sun will rise and the cranes will return once more to the pond.

We can summarize that using variables:

p /\ q

where p = The sun will rise, q = the cranes will return once more to the pond

That leaves us with the notation for and which is the  character. That’s called a connective by the way and is important to our truth state evaluation because it (the connective) encapsulates the rule. Remember when we said that propositional logic supports the rules to construct and evaluate mathematical statements?

Thus, given our connective here, the rule would be something like the entire statement (p and q) is True when p is True and q is also True. If either p or q are False, then the entire statement would also be False.

Going forward

That’s the heart and spirit of propositional logic. However, not only are there more connectives, but there are also some techniques to visualize the possible truth states of a given propositional statement as well as mechanisms to prove Truth.