What are Propositions, Compound Propositions, and Boolean Logic?
“It is not of the essence of Mathematics to be conversant with the ideas of number and quantity.” — George Boole, 1854
A Brief History of Boolean Logic
George Boole was best known for his work on Boolean algebra — a branch of the subject that defines variables with true or false values, denoted usually with 1 or 0.
His work was pre-dated primarily by Gottfried Willhelm Leibniz’s algebra of concepts, where Leibniz enunciated the concepts we now call conjunction, disjunction, negation, identity, set inclusion, and the empty set.
Much of Leibniz's concepts were not published in his lifetime, however, it is argued that his work may have had an influence on Boole and modern logicians.
For a more thorough account of the influence of Leibniz on Boole, please see this article published on the Stanford University website.
Boole was one of the first to point out an analogy between algebraic symbols and those that can represent logical forms and syllogisms (logical inferences drawn from two propositions presumed to be true).
“Boole’s original and remarkable general symbolic method of logical inference, fully stated in Laws of Thought (1854), enables one, given any propositions involving any number of terms, to draw conclusions that are logically contained in the premises.”(1) — Britannica
What is a proposition?
A proposition is simply a statement, whereas propositional logic studies these statements and how they can interact with each other.
Propositional logic does not care about the content of the statements, only if they be inferred to have some true or false value.
In computing, we are dealing with systems that process data in binary states. Either the processor has a charge or it does not have a charge, denoted with binary values.
We could simplistically compare computer processing to the state of a cup being full or empty. It is one or the other, but never anything in between. Likewise, with propositional logic — we can denote a statement as being true or false. It is one or the other, and nothing in-between.
There is no gray area.
This is how we must first perceive propositions before interpreting them for any form of true or false logic. It is not adequate or helpful for you to consider propositional logic from the standpoint that there can be multiple answers to a ‘true’ or ‘false’ statement.
Examples of Propositions
The following are several examples of propositions, each on their own line, with an explanation:
The temperature is above 22 Celsius.
This is a proposition because the statement is either true or false. It is either above 22 celsius (true) or it is below (false). This is not a question asking for more information or instruction, it is a statement of validity — true or false.
Paris is the capital of France.
Again this is a proposition because Paris is either the capital of France or it is not. It holds either a true or false value. In this case, the proposition evaluates to be true. However, if it said “Berlin is the capital of France” it would evaluate as false.
New York City is the Capital of New York State.
This is another proposition in which it can evaluate as either true or false, but nothing in-between. Albany is the capital of New York State, so in this case — this proposition evaluates to false.
My name is Adam.
This is another proposition and of course, depends on who wrote or said the proposition. It is either true or false — the person’s name is either Adam or it isn’t.
1 + 1 = 2
This is a proposition that 1 + 1 = 2. It either holds the value true or false based on the statement itself. We know the answer is 2, so it evaluates to true.
2 + 2 = 5
This is another proposition that has either a true or false value. 2 + 2 does not equal 5, so it evaluates to false.
What is not a proposition?
These could be summarised as statements that are either questions or commands/orders/instructions.
Questions
Is it raining?
This is a question rather than a proposition and does not hold a true or false value, it is asking for more information. If the statement was “It is raining” rather than “Is it raining?” — it would be a proposition with a true or false value. In this case, it is not.
Is x = 5?
Again, this is a question rather than a proposition — it does not hold a true or false value. If the statement was “x = 5” we could then evaluate it as either true or false, but in this case, it is phrased as a question and therefore does not have a true or false value.
Commands/orders/instructions
Get back
This is a command, order, or instruction which holds no true or false value.
Get me a glass of water
Another command, order, or instruction with no true or false value.
If the temperature is above 22 celsius, then turn off the heating
This is an instruction that cannot be evaluated as either true or false, however, if you extracted “the temperature is above 22 celsius” from it — that could be interpreted as a proposition holding a true or false value.
Forms of propositions
Propositions can appear as sentences, ideally, we want them to be as succinct as possible. Recall that computers only care about binary values — true or false, one or the other — but nothing in between, therefore the verbosity of the sentence has no value, only whether we can deduce truthfulness from it.
We can write a proposition and denote it as a letter in the alphabet, these are known as Boolean variables.
Convention has it that we pair propositions starting with the letter ‘P’ followed by ‘=’ and then the proposition itself.
We can define propositions as p,q,r,s, and so on.
We can say: P = ‘I am in my room’
We can also say that ‘Q’ is another proposition and use boolean operators to determine if the statements evaluate to true or false.
We can say: Q = ‘The light is on’
What is a Compound Proposition?
Propositions that are represented by single boolean values on their own are called atomic propositions.
E.G
p = ‘I am in my room’
q = ‘I am awake’
We can use these atomic propositions to create more sophisticated propositions. For example, we can create a proposition that is true only if p = true and q = true.
In shorthand, as above, we can write p = t (for true) and q = t (for true). Likewise, for false values, we can use the letter f.
A compound proposition is one where there is more than one proposition and we use boolean operators to determine the true or false value of the entire statement.
Boolean Operators
These are symbols that denote how the propositions should be interpreted to evaluate the entire statement to a true or false value. AND, OR and NOT are the most basic and common of these operators.
AND ^ (Conjunction)
In an AND statement, both propositions must evaluate to be true for the statement to evaluate to true. We replace the word and with ^.
Take the following example, noting that T = True, and F = False:
The third column p ^ q evaluates the statement in its entirety. Only in the case that “I am in my room” AND “I am awake” is true, does the statement evaluate to true.
In all other cases, the statements evaluate as false.
Why is this? Think of the two propositions using the English language, replacing ^ with AND, considering that the full statement can only be true if you are both in your room and awake.
“I am in my room AND I am awake” can only be true if both statements are true.
OR ∨ (Disjunction)
In an OR statement, one or more of the conditions has to be true for the whole statement to evaluate to be true.
Consider that if we were to use the same statement but with p or q, as above, we would write out our truth table as follows:
Note that if both conditions are true, the whole statements evaluate to be true.
It only matters in this case that one or more of the propositions is true for the whole statement to evaluate to be true.
NEGATION / NOT ¬
Where we state that a proposition is NOT or ¬ we are simply stating that it is the reverse value to the one it already holds.
If we said that ‘p = I am in my room’ is NOT true, we flip the value to its alternative which is that the value is now false.
Exclusive OR ⊕
When we compare two propositions with an exclusive or ⊕ operator we are stating that either statement has to be true for it to evaluate to true, but not both.
We are simply stating that either statement has to be true but not both of them. It is exclusively p OR q is true, but not both of them can hold a true value, for the whole statement to evaluate to true.
Memorize the above simply by recalling that either statement has to be true, but both of them cannot be.
Conditional →
This is perhaps one of the more tricky boolean operators, given that it doesn’t translate as simply into the English language as the above operators we have already discussed.
It translates as closely into English as “if P (is true) → (then) Q (is true)”.
Consider that it does not matter what the contents of these propositions are, only that they either hold a true or false value and we do the correct evaluation using the boolean operator in question.
If I am in my room, then I am awake can be evaluated as follows:
To memorize this truth table, simply recall that all statements evaluate to true except in the case that P = T, and Q = F.
If the first statement is true (P = T) then the second statement must also be true (Q = T) for it to evaluate to be true.
However, this condition is true by implication.
P being true implies Q is true — this is a one-way relationship. Q does not imply P is true.
You should focus on the second condition and work backward. If Q is true, then it does not matter what P is, as the statement is one way and can be evaluated as true in this manner.
Where both P = F, and Q = F there is not enough evidence to deduce if P → Q so we simply evaluate to true in this instance, as there is a possibility it could be true.
Watch the above video for a thorough explanation of the P → Q conditional.
Biconditional ↔
The biconditional can be interpreted as “if and only if”.
It is understood as meaning that both p and q must be true or both p and q must be false for the statement to evaluate to be true.
All other conditions evaluate as false.
Again, as with the conditional operator — in the biconditional, where both statements are false, we don’t have enough evidence to evaluate as false, so that circumstance evaluates to true.
Tautology
In tautology, all statements evaluate to true — it is the equivalent of writing the following:
P ∨ ~P
For example, where P is true or P is not true, the statement will always evaluate as true.
Contradiction
This is the opposite of tautology, where all statements evaluate as false as opposed to true.
Summary Truth Tables for All the Boolean Operators
You should memorize the truth tables for all the Boolean operators, however, it is just as important to understand why they evaluate their given values
I hope you have found this article useful in understanding propositions, compound propositions, and boolean logic in general. It is important you understand these concepts for a variety of domains, not exclusively Computing or programming.
In the next article, I will be writing on the topic of complex compound propositions, the boolean operators order of precedence, and how to evaluate such statements by writing truth tables yourself.
