PRINT LINKED RELATED

Truth Tables

    In this topic we take a careful look at making mathematical statements and determining their validity. Our main tool will be the use of truth tables. But first we will consider what a mathematical statement is and how to write clear and precise mathematical statements. Then we learn how to do computations with statements so that we can determine tautologies, contradictions, and contingencies.
    A mathematical statement refers to any assertion that can be classified as either true or false (but not both). For example: This piece of metal is hot. Of course this statement must be preceded by an earlier definition of what is meant by hot. For example, an iron worker might consider a certain metal to be hot at a certain temperature whereas an archaeologist might consider hot to mean something else. The point is that once you have a definition of hot, then one can check whether or not this piece of metal satisfies the conditions in the definition.
    Using operations, statements are often glued together to make compound statements, called propositions, such as: This piece of  metal is hot and this liquid is cold. In this case, the two statements: "This piece of metal is hot." and "This liquid is cold." are combined to make a new statement. A statement is often denoted by a lowercase single letter such as For example, "This piece of metal is hot." could be denoted by and "This liquid is cold." could be denoted by Then we can form the compound statement, say and Here are the definitions for the four main operations:

Definition (And) The And operation is a connective in logic which yields true if all conditions are true, and false if any condition is false and is denoted by The And operation has the following truth table:

Definition (Or) The Or operation is a connective in logic which yields true if any one of a sequence of conditions is true, and false if all conditions are false and is denoted by The Or operation has the following truth table:

Definition (Not) The Not operation is a connective in logic which converts true to false and false to true and is denoted by   The Not operation has the following truth table:

Definition (Implication) The Implication operation is a connective in logic which yields true if the assumption is false or the assumption and conclusion are both true, and false otherwise; and is denoted by The Implication operation has the following truth table:

    In terms of a truth table, statements and are called the variables. By definition, a proposition whose value is true for all cases of all variables is called a tautology; a proposition whose value is false for all cases of all variables is called a contradiction; and a proposition whose value depends on a value of a variable is called a contingency. Note that all four operations, And, Or, Not, and Implication are all contingencies. It is interesting to also note that we can take a combination of contingency statements and build a contradiction or a tautology.

Definition (Tautology) A proposition whose value is true for all cases of all variables is called a tautology.

Definition (Contradiction)  A proposition whose value is false for all cases of all variables is called a contradiction.

Definition (Contingency)  A proposition whose value depends on a value of a variable is called a contingency.  

Example (Truth Table)  Construct a truth table for and state which kind of proposition this is, a tautology, contradiction, or a contingency.
    
    Solution. Breaking the given compound statement into the pieces and to construct a truth table we have,


This truth table show that the proposition is a tautology because every entry in the last column is true.

Example (Truth Table) Construct a truth table for and state which kind of proposition this is, a tautology, contradiction, or a contingency.
    
    Solution. Breaking the given compound statement into the pieces and to construct a truth table we have,



This truth table show that the proposition is a tautology because every entry in the last column is true.

    Given two statements and there are two very important propositions associated with

Definition (Contrapositive)  The contrapositive of is the statement

Definition (Converse)  The converse of is the statement

     By constructing a truth table you can check that the contrapositive statement is equivalent to the original statement (check this!). The same is not true for the converse statement; that is, the converse of a statement is not equivalent to the original statement (check this!). The contrapositive can be very useful when trying to prove a difficult statement.
    Why are truth tables important? Well, this stems from the fact that all mathematical statements are actually conditional statements:
    
        "some hypothesis statement"   implies    "some conclusion statement".

As shown above, statements built up from other statements using the above operations can be constructed. But in the finality of it all, a proposition can be dissected into a truth table. In some case this may not seem obvious. For example, a well known statement in calculus states that: If is a differentiable function, then is a continuous function. This is obviously a conditional statement. Sometimes it can be more difficult to determine the hypothesis; for example, there is a famous theorem that states, is irrational. Can you write this as a conditional statement? Also, don't forget that not all conditional statements are actually propositions.
    Finally, we state that building statements into propositions using the four basic logic connectives stated above is very important for anyone wishing to do rigorous mathematics; (and just as important, rearranging statements into equivalent statements). Proving difficult mathematical statements can be extremely challenging and proving an equivalent statement is often a remedy for a thorny proposition. This topic is meant to introduce these concepts and give a couple of examples of truth tables.

Math Logic Books

The Big Book of Brain Games: 1,000 PlayThinks of Art, Mathematics & Science List Price: $22.95 Buy New: $13.89 You Save: $9.06 (39%) New (29) Used (16) from $8.29About the original 1000 PlayThinks,Will Shortz of The New York Times said it best: ?The most wide-ranging, visually appealing, entertaining, gigantic collection of brainteasers since Sam Loyd?s Cyclopedia (more)

My Best Mathematical and Logic Puzzles (Math & Logic Puzzles) List Price: $4.95 Buy New: $1.72 You Save: $3.23 (65%) New (29) Used (17) from $1.72 (more)

Discrete Mathematics and Its Applications Buy New: $120.00 New (32) Used (61) from $109.96Discrete Mathematics and its Applications, Sixth Edition, is intended for one- or two-term introductory discrete mathematics courses taken by students from a wide variety of majors, including computer (more)

Mensa Exercise Your Mind Math & Logic Puzzles List Price: $7.95 Buy New: $4.05 You Save: $3.90 (49%) New (26) Used (11) from $4.05An old favorite--Mensa Math & Logic Puzzles--gets a brand-new look: it's now in color!And the puzzles are fantastic: they're the kind of challenge found at the World Puzzle Championships, and they require (more)

Perplexing Puzzles and Tantalizing Teasers (Math & Logic Puzzles) List Price: $7.95 Buy Used: $2.41 You Save: $5.54 (70%) New (21) Used (30) from $2.41 (more)

Mensa Challenge Your Brain Math & Logic Puzzles List Price: $7.95 Buy New: $4.04 You Save: $3.91 (49%) New (29) Used (9) from $4.04Give your brain a workout on the type of brainteasers that challenge the best solvers at the World Puzzle Championships. They're tough, but fun, and the feeling of satisfaction you get when you succeed (more)

The Moscow Puzzles: 359 Mathematical Recreations (Math & Logic Puzzles) List Price: $12.95 Buy New: $6.00 You Save: $6.95 (54%) New (21) Used (14) from $5.45Most popular Russian puzzle book ever published. Marvelously varied puzzles ranging from simple "catch" riddles to difficult problems. Lavishly illustrated with clear diagrams and amusing sketches. Edited (more)

Entertaining Mathematical Puzzles List Price: $5.95 Buy New: $3.24 You Save: $2.71 (46%) New (23) Used (19) from $1.57Only an elementary knowledge of math is needed to enjoy this entertaining compilation of brain-teasers. It includes a mixture of old and new riddles covering a variety of mathematical topics: money, speed, (more)

Calculus II For Dummies (For Dummies (Math & Science)) List Price: $19.99 Buy New: $9.74 You Save: $10.25 (51%) New (40) Used (16) from $9.00An easy-to-understand primer on advanced calculus topics Calculus II is a prerequisite for many popular college majors, including pre-med, engineering, and physics. Calculus II For Dummies offers (more)

Will Shortz Presents I Can KenKen! Volume 1: 75 Puzzles for Having Fun with M... List Price: $5.95 Buy New: $2.80 You Save: $3.15 (53%) New (25) Used (5) from $2.64Not only are these puzzles fun but KenKen helps children improve concentration, logic and arithmetic skills. Children ages 9-12 have excelled in math and gained real-life problem solving skills all from (more)