Truth Tables - Florida Institute of Technology

Truth Tables

Truth tables are useful for showing the complete behavior of a Boolean function.

However, hand construction of a truth table is tedious once there are more than a few propositions in the expression.

The number of truth assignments is exponential in the number of propositions.

Truth Tables

You know that there are 2n truth assignments on n Boolean variables. A (complete) truth table shows the input/output behavior for all possible truth assignments. The rate of growth in a truth table rows as a functions of the number of propositions is shown in the table below.

Number of Number of Propositions Rows

0

1

1

2

2

4

3

8

4

16

...

...

n

2n

Truth Tables There is no one way to construct a truth table. However, basis rules exist. The rules are similar to those for

performing arithmetic operations.

1. Expressions in parenthesis are evaluated first from innermost to outermost.

2. NOT is evaluated before AND

3. AND is evaluated before OR

4. OR is evaluated before IMPLIES

5. IMPLIES is evaluated before EQUIV

1

Tautologies and Valid Statements

When a Boolean function is True for every one of its truth assignments, the expression is said to be a "tautology." Or the statement is valid.

A valid statement is always True.

There are several important valid statements.

? p ?p Exclusive Middle ? (p (p q)) q Modus Ponens ? p (?q ?p) q Modus Tollens ? ((?p q) (?p ?q)) p Reductio ad Absurdum ? ((p q) (?p r)) (q r) Resolution Reductio Ad Absurdum Truth Table

Let's construct a truth table for Reductio ad absurdum. ((?p q) (?p ?q)) p

Input

Reductio Ad Absurdum

p q ((?p q) (?p ?q)) p

00

0

0

1

10

01

1

0

0

10

10

1

1

1

11

11

1

1

1

11

7

3

11

15 3

1st

3rd

2nd

5th 4th

2

Resolution Truth Table Let's construct a truth table for resolution.

((p q) (?p r)) (q r)

Input

Resolution

p q r ((p q) (?p r)) (q r)

000

0

0

1

1

0

001

0

0

1

1

1

010

1

1

1

1

1

011

1

1

1

1

1

100

1

0

0

1

0

101

1

1

1

1

1

110

1

0

0

1

1

111

1

1

1

1

1

15 51 85 63 53 245 255 119

1st

3rd

2nd

5th

4th

Contradiction and Invalid Statements When a Boolean function is False for every one of its truth

assignments, the expression is said to be a contradiction.

Of course, you can construct a contradiction by negating a tautology.

A computational hurdle occurs when every truth assignment must be investigated to determine if a statement is a tautology or a contradiction.

Contingency Statements When a Boolean function sometimes True and sometimes False,

dependent on the values in a truth assignment, the expression is said to be a contingency.

Satisfiability is a fundamental problem in computer science. Problem 1 (SAT). Give a Boolean function in n variables is it satisfiable?

That is, is there a truth assignment for its propositions that makes the expression True?

3

Tautology, Contradictions or Contingency? Consider the Boolean function B(p, q, r) = ((p q) r) p

Is it a tautology? (always True). Is it a contradiction? (always False). Or, is it a contingency? (sometimes True and sometimes False). Let's construct a truth table to find out.

Truth Table for a Boolean Expression

A truth table for ((p q) r) p is:

Input

Expression

p q r ((p q) r p

000 0 001 0 010 1 011 1 100 1 101 1 110 1 111 1

00 1 0 01 1 0 00 1 0 11 0 0 00 1 1 11 1 1 00 1 1 11 1 1

1st

3rd 2nd 5th 4th

The expression (function) is a contingency.

4

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download