Propositional Logic

All mathematical arguments boil down to "if p, then q" statements, such as if x is even, then x is divisible by two. It is therefore imperative that one understands propositional logic (the branch of mathematics that studies statements like "if p, then q") in order to fully comprehend mathematical arguments and proofs. Before we begin to study the elementary operations, such as ∧ (logical conjunction - also known as "and"), ∨ (logical disjunction - also known as "or"), and ¬ (negation), we must first describe propositions.


PROPOSITIONS


Definition: A proposition is a declarative statement that is either true or false, but not both.


An example of a proposition is: "Propositional logic is fundamental to mathematics." An example of a statement that is not a proposition is: "It may rain in New York City tomorrow." Why? The answer lies in the fact that it is not declarative; it is merely stated that it might rain in New York City tomorrow, but does not state definitively one way or the other.


Why must we include "but not both" in the definition of a proposition? The inclusion of this sentence fragment would lead one to think that there are statements that can be both true and false. An incredibly popular example of a statement that is both true and false is the statement "This statement is false."


Let's try to assign a truth value to this statement. If it is to be a proposition, then it is either true or false. Let's start by assigning a truth value of true to the statement. If the statement is true, then it must be false (because it said so!). So on one hand, the statement is true and yet it is false. Strange, but let's check if it is false. If it is false, it agrees with what we said, but if it agrees with it then it must be true!


It seems like there is no way to win with this statement! What we have invented is a self-contradicting statement. If it is true, then it must be false and if it is false, it must be true. We cannot assign a truth value to the statement; it can neither be true nor false. In order to perform meaningful logical arguments, we must avoid statements like these at all costs, else we will get nowhere. Hence the inclusion of "but not both" in the definition of a proposition.


Paradoxes are very interesting in and of themselves, but for now I will continue with propositions and logic. Another example of a proposition is: "The sum of the first n nonnegative integers is n(n+2)/2" (this statement is actually false). Again, this is a definitive statement and can only be true or false - either the formula holds or it does not. It is conceivable that the statement does hold true for some value of n, but if this statement is not true for all values of n, then it is false. So, in mathematics, we take the stance that a statement is only true if it is always true.


Now that we have an understanding of propositions, we can begin to formulate logical combinations of propositions using the elementary logical operations mentioned earlier.


LOGICAL OPERATIONS


We can combine propositions in different ways, such as: "It is Sunday and it is sunny outside", or "It is Saturday or Sunday", or "It is Saturday or Sunday but not Monday." Each of these three statements can be written using logical operations. Take, for example, "It is Sunday and it is sunny outside." We will represent the proposition "it is Sunday" by the symbol p and we will represent the proposition "it is sunny outside" by q. We would then write the compound proposition as p ∧ q.

NEGATION

The negation of a proposition means to take the truth value and reverse it. To be more clear, if your proposition is true, then the negation of the proposition is false; if the proposition is false, then the negation is true.

Take for example the proposition 1 = 2. 1 = 2 is false. The negation reads 1 ≠ 2 (the equality symbol with a slash through it represents not equal to). We know for a fact that 1 ≠ 2, so it is true. And this agrees with our statement that the negation swaps the truth value of the statement.

LOGICAL CONJUNCTION


The statement p ∧ q (read p and q) is defined to be true if and only if both p and q are true, otherwise it is false. This can be summarized in what is called a truth table, as seen below:

The first line reads, if p is true (T) and q is true (T), then p and q is true (T). Similarly, the second line reads if p is true and q is false, then the compound proposition p and q is false.


An example will help to illustrate the idea: Let p be the proposition that 1 = 1 and q be the proposition that 1 = 2. p and q says 1 = 1 and 1 = 2. Obviously this compound proposition is false. While 1 does indeed equal 1, 1 does not equal 2; by definition, the conjunction of two proposition is only true if both statements are true.


Another example is: Today is Friday and today is Sunday. Obviously, it cannot both be Friday and Sunday so we conclude that the proposition is false.


Another fundamental logical operation is disjunction, as we shall see in the next section.


LOGICAL DISJUNCTION


The proposition p ∨ q (read p or q) is defined to be true if at least one of the proposition is true. Alternatively, the proposition is only false if both are false. The truth table representing the logical disjunction is shown below:

As you can see, if either p or q is true, the truth value of p or q is true. The utility of truth tables becomes very apparent as they graphically represent the truth values of compound propositions. For simple compound propositions like p and q or p or q the utility isn't so apparent, however for complicated expressions, they are very useful (as we shall see later).

An example will help illustrate the idea behind the logical disjunction of two statements. Take our proposition to be 1 = 1 or 1 = 2. 1 = 1 is true, whereas 1 = 2 is not, yet because at least one is true, we say that the compound proposition is true.

With these three tools under our belt, we can finally discuss the most important logical operation: implication.

IMPLICATION

The statement p→q is a little odd at first and trips many students up the first time they encounter it and for good reason. While I defined the previous three logical operations before giving examples, I will present this with an example and then give the general statement. Take as our example the proposition: "If it is Sunday, I will go to the park." 

This is obviously a proposition, so it must (based upon the truth values of the propositional variables - the p and q) either be true or false. We will determine when the proposition is false and otherwise it must be true.

The only time this statement is false is if it is Sunday but I am not going to go to the park. The question to ask is: When can you call me a liar? (Meaning, when does the output not match the input?) You can only call me a liar if I do not go to the park on Sunday. In this case, the overall statement is false, but any other combination cannot be said to be false. Therefore all other cases must be true.

The truth table for implication then looks as follows:

TAUTOLOGIES

With this in mind, we will explore an important logical construct called a tautology.

Definition: A proposition is said to be a tautology if it is always true regardless of the truth values of its propositional variables. An important example is the statement p ∨ ¬p is a tautology. Unlike before, we only have two possible scenarios to check since ¬p is a function of p.

p has only two possible truth values, true or false. We will check both cases. If p is true, then ¬p is false. The disjunction of T and F is T. If p is false, then ¬p is true and the disjunction of these two again yields a truth value of T. So we conclude that regardless of the truth value of p, this statement is always true and is therefore a tautology.

There are many other tautologies to observe, but I do not wish to spend too much time on them, as there are many other topics left to cover.

LOGICAL EQUIVALENCE AND DE MORGAN'S LAWS

Two compound propositions are said to be logically equivalent if they have the same truth values for the same truth values of their propositional variables. Logical equivalence is denoted by p ≡ q.

An example are the compound propositions ¬(p ∨ q) and ¬p ∧ ¬q, as can be seen in the following truth tables:

This is actually an example of what is known as one of De Morgan's Laws. The other is of very similar form:  ¬(p ∧ q) and ¬p ∨ ¬q.  These are widely used in introductory electronics classes when breadboarding and are very helpful for reducing what could be considered messy Boolean algebra statements into very clean and concise ones.

For those interested, Boolean algebra is very interesting and can be used to implement basic circuitry. You can use logic to make cool programs!

This is the conclusion of propositional logic. The next blog post will be an introduction to set theory and proof. There are three main kinds of proof: direct, inductive and contradiction. Each has their own merits and drawbacks. Often times only one can be used to prove a statement and determining which to use can be tricky, but I will attempt to make recognizing which proof to start with easier. Many similarities between sets and propositional logic will arise, namely a similar formulation for De Morgan's Laws will be realized. This is part of a much deeper theorem concerning propositional logic and set theory and will be discussed later.