Introduction to Boolean Logic

Logic is an area of mathematics concerned with truth and falsity. Suppose that you have two statements: the statement ''if it rains then the grass outside is wet'' and the statement ''it rains''. If you know that both of these statements are true, can you conclude that the statement ''The grass outside is wet'' must also be true? Intuitively we feel that this should be the case even though we have not even defined what being ''true'' should mean. Logic allows us to make this intuition precise. It gives us a framework to ask meaningful questions about the truth of statements and to answer them.

Logic also lies in the foundation of a bigger part of mathematics, it gives mathematicians rules to prove theorems. It is central to computer science where it is used both in hardware and software. For example, the processor in your computer probably contains billions of logic gates each of which performs some simple logic operation. When you, as a programmer, write a complicated if-statement, you are using logical connectives to combine elementary conditions. Logic also finds use in artificial intelligence, for instance, in automatic planning and scheduling, and plays a key role in computational complexity theory.

In this topic, we will start our exploration of logic by delving into the basics of propositional logic.

Truth values and propositions

There are only two possible truth values in classical logic: true and false, which correspond to 1 and 0, respectively. Either something is true or it is false but there is nothing in between.

A proposition is a statement that can be assigned a truth value. For instance, ''7 is a prime number'' and ''2 is greater than 3'' are propositions. The first one is true and the second one is false. That is, the truth value of the first proposition is 1 and the truth value of the second proposition is 0. In the case above, it was easy to assign truth values to the two propositions. In general, we do not require truth values of propositions to be known, we just require that they can be assigned. To give an example of something that is not a proposition, ''Good morning, Mr. Bond'' is not a proposition because we cannot meaningfully assign a truth value to a greeting.

Propositional logic does not ''see'' inside elementary propositions and treats them as atomic. Therefore we usually denote elementary propositions by letters, e.g. $P$, $Q$, $R$, and call them propositional variables. We can, of course, still imagine that these letters represent some statements in natural language, such as ''it rains'', but we can safely abstract from it.

What this also means is that if we get a logic problem stated in English (or any other language), we will first need to do some work ourselves to represent it using propositional variables, and only then will we be able to use tools from propositional logic.

Conjunction

Logical connectives are similar to connectives that you know from English. They are used to connect logical propositions into more complex ones, much like connectives in English are used to connect clauses into more complex sentences. Here we start with the connective called a conjunction.

The conjunction is a logical connective that corresponds to the English ''and''. It is denoted by the symbol $\land$.

Take two propositional variables, say, $P$ and $Q$. From them, you can construct the proposition $P \land Q$. For instance, if $P$ corresponds to the English sentence ''it rains'' and $Q$ corresponds to ''it is sunny'' then the proposition $P \land Q$ corresponds to ''it rains and it is sunny''.

The truth value of the conjunction $P \land Q$ is determined by the truth values of the propositions $P$ and $Q$. The proposition $P \land Q$ is true only when $P$ and $Q$ are both true. It is false in all the other cases: when $P$ is true and $Q$ is false, when $P$ is false and $Q$ is true and when $P$ and $Q$ are both false. That is, for instance, the proposition ''it rains and it is sunny'' would only be true if both ''it rains'' and ''it is sunny'' were true.

Intermezzo: Truth tables for logical connectives

When we introduced conjunction, we listed all cases when it is true and when it is false, based on the truth values of the propositions in it. There is a more convenient way to do this using what we call a truth table.

One such truth table for the proposition $P \land Q$ is shown below.

This truth table has three columns. The first two are for the truth values of the propositional variables $P$ and $Q$. The third is for the truth value of the conjunction $P \land Q$.

For instance, the first row in our table is 0, 0, 0'' which means that when $P$ (the first ''0'') and $Q$ (the second ''0'') are both false then the proposition $P \land Q$ is also false (the third ''0''). The second row is ''0, 1, 0'' which means that when $P$ is false and $Q$ is true then $P \land Q$ is again false.

As you may probably agree, using truth tables is quite convenient. They are easy to read once you get used to them. Next, we will use truth tables to introduce other logical connectives.

Disjunction

Disjunction is the logical connective that corresponds to the English ''or''. It is denoted by the symbol $\lor$.

Below is the truth table for disjunction.

Consider the following English sentence: ''I will eat a cake or I will eat an ice cream.'' We can denote ''I will eat a cake'' by $P$ and ''I will eat an ice cream'' by $Q$. We can now take a look at the proposition $P \lor Q$ and some concrete cases from the truth table for this proposition.

First, we will look at the case when $P$ is false and $Q$ is false. Then $P \lor Q$ is also false according to the truth table for disjunction. That can be interpreted in our example as: if I do not eat a cake and if I do not eat ice cream then the statement ''I will eat a cake or I will eat an ice cream'' is not true. Intuitively, this also corresponds to the meaning of ''or'' from everyday English. When we normally use ''or'', we mean that at least one of the statements should hold.

Second, we will consider the case from the last row of the truth table. Here, both $P$ and $Q$ are true. The disjunction $P \lor Q$ is again true. In our example with cake and ice cream, this corresponds to the situation when I will eat both a cake and an ice cream. In everyday language, in situations like this we might oftentimes mean by ''or'' something closer to ''either… or...'' but in propositional logic, this is not the case. Disjunction $P \lor Q$ is true when either one of $P$ and $Q$ is true or if both $P$ and $Q$ are true. So maybe if you happen to host a party for logicians in your future life, if they say that they want ice cream or a cake, you can give them both.

Negation

Negation is another logical connective. It is denoted by $\lnot$. Unlike the two other connectives, conjunction and disjunction, negation does not connect two propositions, it applies to only one, e.g. we can have $\lnot P$. As its name suggests, negation ''flips the truth value of the proposition it is applied to. When $P$ is true, $\lnot P$ is false and when $P$ is false then $\lnot P$ is true.

The truth table of negation is rather simple and is shown below.

For instance, when $P$ corresponds to the English statement ''the grass is green'', its negation $\lnot P$ corresponds to the statement ''the grass is not green''.

Building more complex propositions

Now that we have learned about conjunction, disjunction, and negation, we can use them to construct more complex propositions. For that, we can also use brackets and the constants 1 and 0.

The following are examples of propositions: $P$, $P \lor Q$, $(P \lor Q) \land R$, $\lnot (R \land S)$.

We can also construct truth tables for the more complex propositions. The truth value of a proposition is determined by the truth tables of the connectives involved and the truth values of the propositional variables. For instance, to compute the truth value of the proposition $(P \lor Q) \land R$ when $P$ is true, $Q$ is false and $R$ is false, we first determine the truth value of the proposition $P \lor Q$, which is 1. Now what is left is to evaluate the expression $1 \land R$, which is what we got after we replaced $P \lor Q$ in $(P \lor Q) \land R$ by 1. Since the truth value of $R$ is 0, the conjunction $1 \land R$ evaluates to 0.

Now we know how to compute truth values of more complex propositions. That means that we can also construct truth tables for them!

Here is an example. Consider again the proposition $(P \lor Q) \land R$. Here is its truth table.

Conclusion

In this topic, we got acquainted with the basics of propositional logic. The main take-away points from this topic are:

• A proposition is a statement which can be assigned a truth value 0 (false) or 1 (true).
• Propositional variables, e.g. $P$, $Q$, represent atomic propositions.
• Conjunction, denoted $\land$, is the logical connective that corresponds to the English ''and''. The proposition $P \land Q$ is true when both $P$ and $Q$ are true and false otherwise.
• Disjunction, denoted $\lor$, is the logical connective that corresponds to the English ''or''. The proposition $P\lor Q$ is true when at least one of $P$ and $Q$ is true and it is false when both of them are false.
• Negation, denoted $\lnot$, is the logical connective that corresponds to the English ''not''. The proposition $\lnot P$ is true when $P$ is false and false when $P$ is true.
• Propositions can be combined using logical connectives into more complex propositions.