January 4, 2019
Beyond Calculus
Now equipped with the principles of logic theory as well as basic notation, it’s time to explore the concept of equivalency in logic. Specifically, what makes two compound premises equal?
Two compound premises X & Y are logically equivalent if, for each assignment of truth values to the primitive premises which make up X & Y, the statements X & Y have identical truth values.
That’s a tricky definition to swallow, but it’s the application of this definition that we care about learning. In order to achieve this, we’ll walk through multiple, increasingly-complicated examples. First though, let’s take a detour to learn a bit more about our Excalibur for this journey — one of the most simple, yet powerful tools for logicians to prove logical equivalence: truth tables.
A truth table is a visual tool, in the form of a diagram with rows & columns, that shows the truth or falsity of a compound premise. It’s a way of organizing information to list out all possible scenarios from the provided premises. Let’s start with the most simple example, a truth table depicting a single premise manipulation: a negation (~) of a primitive premise (P)
Truth tables are always read left to right, with a primitive premise at the first column. In the example above, our primitive premise (P) is in the first column; while the resultant premise (~P), post-negation, makes up column two.
It’s easy to overthink things here — don’t forget that a premise is simply a statement that is either true or false. Since this example only has a single premise, we only need to track for two outcomes; resulting in two rows for when P is true or when it’s false. Row one describes, reading left to right, that if P is true, then the negation of P is false; row two displays that if P is already false, then the negation of P is true.
Let’s move on to a more complicated example of truth tables in the wild by inserting a connective we’ve previously seen: the implication (->). In order to make this a tad more digestible, let’s assign our statements P & Q some context prior to building out our truth table:
P: Thanos snapped his fingers
Q: 50% of all living things disappeared
Before looking below, think through this structure given the details above. First, since we have two primitive premises (P ,Q), we know we’ll need at least two columns; additionally, we should prepare for the resultant premise with the implication connective (P -> Q), which will require another column. A total of three columns.
What about rows? Since we have two premises that can each either be true or false, in order to account for all possible scenarios, we require a total of four rows (P.S — a neat corollary can be derived from this observation: a truth table that accounts for N premises requires N² rows). Let’s now draw this table out & make sure it’s understandable:
Review the truth table above row-by-row. The first row confirms that both Thanos snapped his fingers (P) & 50% of all living things disappeared (Q). Since both premises hold true, then the resultant premise (the implication or conditional) is true as well:
Row two is equally direct in understanding. This time, P is still true, however Q is now false. The interpretation here is “Thanos snapped his fingers, but 50% of all living things did not disappear.” Since we’re setting out to prove the validity of the implication, it makes sense the previous statement renders the overall premise as unequivocally false:
The last two rows are a bit more counter-intuitive. There’s a shortcut here: we only need to look at the first column to register that the implication is true. In both rows three & four, the antecedent premise (P) is false — which is all we need to know, regardless of the value of premise Q, in order to determine the implication as true.
Why is it that a false antecedent always leads to a true implication? Because in the universe of our logical statement, since the antecedent has not happened, it’s impossible to eliminate all possible scenarios that might’ve caused Q. For example, row 3 says that “Thanos did not snap his fingers yet 50% of all living things disappeared” anyways. Well, for all we know a meteor, natural disaster, alien invasion, or myriad of other activities might’ve caused that extinction — in any of those scenarios, regardless of which one, the implication remains true because we still can’t prove what does happen when he snaps his fingers.
Truth tables are slick, handy logic-tracking diagrams that show up not only in mathematics, but also in computer science, electrical engineering & philosophy as well. The notation may vary depending on what industry you’re engaged in, but the basic concepts are the same. They’re a versatile, interdisciplinary tool — yet we’ve only scratched the surface of their utility.
Now equipped with truth tables, it’s time to grow towards proving equivalency between multiple compound premises. In the next article in this series, we’ll leverage our compounding knowledge to prove that two distinct compound premises, such as the implication & contra-positive, are equal.
sources
Logic: The Theory of Formal Inference
The Foundations of Mathematics
