Concept

How do truth tables represent logical connectives?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"Several times in this book, we’ve drawn the distinction between intension — the inner, conceptual meaning — and extension — the exhaustive list of examples. A set can have both an intension like “the prime numbers less than ten” and an extension like {2,3,5,7}. A relation can have an intension like “isDaughterOf” and an extension like “{(Lisa,Homer), (Lisa,Marge), (Maggie,Homer), (Maggie,Marge)}.” So, too, with the logical connectives. When we say that the “∧” operator means “both propositions must be true,” we’re specifying the conceptual meaning of the “and” operator. Another way to describe it, however, would be to just list its value for all the possible inputs. Such an exhaustive list is called a truth table. We specify every possible combination of inputs, and list the output for each one of them. Here’s the truth table for “∧”:\n\nX Y X ∧ Y\n\n0 0 0\n\n0 1 0\n\n1 0 0\n\n1 1 1\n\nWe use “1” to represent true and “0” for false, just to make the table more compact. The “∧” operator works on two propositions, either of which can have a truth value of 0 or 1. There are therefore, by the Fundamental Theorem of Counting, four different combinations of inputs, and so our truth table has four rows. The right-most column shows the output for each of these sets of inputs. It indicates that X ∧ Y is 1 only when both inputs are 1, and 0 otherwise. Even if we didn’t grasp the simple concept that “∧” is supposed to represent the concept of “and,” we could just look up the value of X ∧ Y if we knew the truth values of X and Y.\n\nSometimes we show more than one output in a truth table. For instance, this truth table shows the values for the other five operators:\n\nX Y X ∨ Y X ⊕ Y ¬ X X ⇒ Y X ⇔ Y\n\n0 0 0 0 1 1 1\n\n0 1 1 1 1 1 0\n\n1 0 1 1 0 0 0\n\n1 1 1 0 0 1 1\n\nTake a moment and look carefully through the entries in that table, and make sure you agree that this correctly represents the outputs for the five operators. (Note that “¬”, being a unary operator, only has X as an input, which means that the value of Y is effectively ignored for that column.) Now sometimes we have a more complex expression (like the (C ⊕ (A ∧¬ B)) ⇒ ¬ A example from above) and we want to know the truth value of the entire expression. Under what circumstances — i.e., for what truth values of A, B, and C — is that expression true? We can use truth tables to calculate this piece by piece."

Related Ideas

How do truth tables represent logical connectives? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm