January 4, 2019
Beyond Calculus
Part III of this series culminated with a rudimentary understanding of truth tables. We walked through two separate examples, mapping both a negation & an implication. You might’ve realized, however, that while we’ve applied truth tables to evaluate compound premises, we’ve yet to prove any sort of equivalency between two or more statements.
This article extends our knowledge of truth tables by focusing on one, rather involved, final example. Instead of mapping out a single compound premise, we’ll directly compare two compound premises in order prove that they’re logically equivalent. Specifically, the following two statements:
Statement #1: (P ^ Q) -> P
Statement #2: P -> (P ⌄ Q)
This time we will not provide our two premises with further context like we did in the previous example — why? in order to drive home the point that it’s not required. The process for creating a truth table does not change; we strictly care about the individual truth & false values stemming from every possible scenario.
So How Do We Prove Equivalency For The Two Above Using Truth Tables?
Easy, by creating a massive truth table that compares the two final columns of both statements. We first calculate the individual truth & false values of both Statement #1 & Statement #2; then, afterwards, compare these final values in order to prove (or disprove) that they’re logically equivalent.
We’ll see this clearly in the final truth table near the end if you’d like to skip ahead. For now though, we’ll start from scratch. Let’s tackle Statement #1.
Instead of deriving the scenarios for all of (P ^ Q) -> P at once, let’s take it apart to two main pieces. Ignore the implication part of the statement (->P) & we’re left with a much more manageable statement. With two premises & a single connective (the conjunction/and), we can deduce that our Partial Statement #1 table requires a total of three columns & four rows:
The truth table above is straight-forward if you’ve been following along. We simply listed out all possible truth & false value for both of our premises (P, Q) in columns one & two, & then calculated the truth/false values for the conjunction in column three. Recall that a conjunction (P^Q) translates to “P and Q are true.” As you can tell above, this happens only in the first row, when both P & Q are indeed true.
Deriving the resultant column of Statement #1, that is, the implication (P ^ Q) -> P, is admittedly more complicated. Below, I did something rather unorthodox by duplicating & re-positioning a column (P) in order to make the calculating the implication a bit more clea
It’s rather easy to get lost by reading far too much into the column titles. Despite the multiple variables, this is still simply an implication much like the one we reviewed in the previous article. Try ignoring the column titles & just push through analyzing an implication reading left-to-right, one row at a time.
The first row states that both the antecedent & consequent hold true, which means that the overall implication is also indeed true. In rows two through four, however, the antecedent is false. From our previous article, we confirmed that in any implication, a false antecedent always leads to a true implication; therefore, the implication values in rows two through four are all also true.
And there we go! With a final column of all trues, Statement #1 is now completely evaluated. Imagine this column of trues as the left-hand side of an equation, now we need to check the right-hand side. Proving that Statement #1 is logically equivalent to Statement #2 is now a clear path forward. We’ll calculate the values for Statement #2 & if they’re all true, then perfect we have a match; if they differ,then we can categorically conclude that they’re not equivalent.
The second time around is much easier. Instead of writing out the table in multiple steps, I fast-forwarded to the finished Statement #2 truth table:
Start by counting the columns, there’s one less than in the Statement #1 table in the previous example — don’t let this confuse you, this time we just opted to not re-write the column (P). Additionally, notice any other columns that we repeated from Statement #1? Both of the premise columns (P) & (Q) appeared in Statement # 1 & Statement #2. Last but not least, glancing at the final column here does indeed confirm another column of all true values, exactly like in Statement #1. This last observation answers the question we set out to answer: since both Statements hold equal resultant true/false values for every scenario, we can incontrovertibly conclude that they are logically equivalent.
Now with both Statements extrapolated to their final truth & false values, constructing the final truth table is strictly a matter of re-arranging the columns we’ve derived along the way. As noted above, we only need to write-in our (P) & (Q) columns once. Next, we fit in the two intermediary connectives that we calculated for both Statements, the conjunction (^) & disjunction (⌄) respectively. And last, we have our two Statement resultants, which are the two columns denoted by blue letters — the only two columns we care about when comparing if the Statements are logically equivalent or not.
By pushing through this third example, we’ve finally applied a truth table to prove logical equivalency; and while we constructed it piece-by-piece, that’ll hopefully become less necessary with repeated exposure. Ideally, when kicking off a future problem, we’ll at least know which columns are necessary as well as how to arrange them — skipping ahead to the structure of the polished truth table above.
If you stuck through this series up till now, then a huge congrats is in your order. While we’ve only scratched the surface of logic proofs by this last example, we at least now equipped with the basic understanding required for a deeper dive in the near future. For now, however, we’ll detour once more with a fascinating branch named Set Theory before continuing on with advanced proofs. As usual, comments, feedback & questions are greatly appreciated.
sources
Logic: The Theory of Formal Inference
The Foundations of Mathematics
