A statement in sentential logic is built from simple statements using the logical connectives
Here's the table for negation:
"If you get an A, then I'll give you a dollar."
The statement will be true if I keep my promise and false if I don't.
Suppose it's true that you get an A and it'strue that I give you a dollar. Since I kept my promise, the implication is {\it true}. This corresponds to the first line in the table.
Suppose it's true that you get an A but it'sfalse that I give you a dollar. Since I didn'tkeep my promise, the implication is false. This corresponds to the second line in the table.
What if it's false that you get an A? Whether or not I give you a dollar, I haven't broken my promise. Thus, the implication can't be false, so (since this is a two-valued logic) it must be true. This explains the last two lines of the table.
Remarks. 1. When you're constructing a truth table, you have to consider all possible assignments of True (T) and False (F) to the component statements. For example, suppose the component statements are P, Q, and R. Each of these statements can be either true or false, so there are
When you're listing the possibilities, you should assign truth values to the component statements in a systematic way to avoid duplication or omission. The easiest approach is to use lexicographic ordering. Thus, for a compound statement with three components P, Q, and R, I would list the possibilities this way:
I'll write things out the long way, by constructing columns for each "piece" of the compound statement and gradually building up to the compound statement.
Example. Construct a truth table for the formula
A tautology is a formula which is "always true" --- that is, it is true for every assignment of truth values to its simple components. You can think of a tautology as a rule of logic.
The opposite of a tautology is acontradiction, a formula which is "always false". In other words, a contradiction is false for every assignment of truth values to its simple components.
Example. Show that
I construct the truth table for
Example. Construct a truth table for
Example. Suppose
"
"
"Calvin Butterball has purple socks" is true.
Determine the truth value of the statement
P = "
Q = "
R = "Calvin Butterball has purple socks".
I want to determine the truth value of
Two statements X and Y are logically equivalent if
From a practical point of view, you can replace a statement in a proof by any logically equivalent statement.
To test whether X and Y are logically equivalent, you could set up a truth table to test whether
Example. Show that
There are an infinite number of tautologies and logical equivalences; I've listed a few below; a more extensive list is given at the end of this section.
Example. Write down the negation of the following statements, simplifying so that only simple statements are negated.
(a)
Example. Use DeMorgan's Law to write thenegation of the following statement, simplifying so that only simple statements are negated:
"Calvin is not home or Bonzo is at the movies."
Let C be the statement "Calvin is home" and let B be the statement "Bonzo is at the moves". The given statement is
Example. Use DeMorgan's Law to write thenegation of the following statement, simplifying so that only simple statements are negated:
"If Phoebe buys a pizza, then Calvin buys popcorn."
Let P be the statement "Phoebe buys a pizza" and let C be the statement "Calvin buys popcorn". The given statement is
Here, then, is the negation and simplification:
Example. Replace the following statement with its contrapositive:
"If x and y are rational, then
By the contrapositive equivalence, this statement is the same as "If
Example. Show that the inverse and the converse of a conditional are logically equivalent.
Let
I could show that the inverse and converse are equivalent by constructing a truth table for
Start with
Example. Suppose x is a real number. Consider the statement
"If
Construct the converse, the inverse, and the contrapositive. Determine the truth or falsity of the four statements --- the original statement, the converse, the inverse, and the contrapositive --- using your knowledge of algebra.
The converse is "If
The inverse is "If
The contrapositive is "If
The original statement is false:
The converse is true. The inverse is logically equivalent to the converse, so the inverse is true as well.