Truth Tables -
Also for:
Symbols
(◙♦●×) indicate applicability to courses.
Truth Tables
A truth table shows the truth value for a statement for all the possible combinations of truth values for all the statement variables in the statement.
In these truth tables, p, q, and r are statement variables.
Examples of statements (which could be true or false) are:
“I fed the dog”
“I cleaned off the dining room table”
“I raked the leaves”
[JOH2001:3, 4, 9, 11]
Negation (◙♦●×)
|
p |
Øp |
|
T |
F |
|
F |
T |
“true” can be represented by T or 1;
”false” can be represented by F or 0 [zero];
|
p |
Øp |
|
1 |
0 |
|
0 |
1 |
Conjunction:“and,”
“Both” (◙♦●×)
|
p |
q |
p Ù q |
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
F |
Disjunction: “or,”
“At least one,” also sometimes called “inclusive or” (◙♦×)
INFS3450 see or (x Ú
y) implemented using AND and NOT gates, Fig. 9.5.1 [JOH2001:440]
|
p |
q |
p Ú q |
|
T |
T |
T |
|
T |
F |
T |
|
F |
T |
T |
|
F |
F |
F |
Exclusive Or: “xor,”
“One or the other, but not both”: p Ú q Ù Ø (p Ù q) (◙♦)
INFS3450 see xor (x Å y) implemented as combinatorial circuit
using AND, OR, and NOT gates, Fig. 9.5.6 [JOH2001: 442]; see also definition
9.4.1 [JOH2001:434]
|
p |
q |
p Å q |
|
T |
T |
F |
|
T |
F |
T |
|
F |
T |
T |
|
F |
F |
F |
NAND: Ø (p Ù q) (◙♦)
INFS2210/6210 see
switches and gates [BUR2003:139-140] and flip-flop circuits, Fig. 5-4
[BUR2003:167]
INFS3450 see NAND
gate [JOH2001:440-443]
|
p |
q |
p ↑
q |
|
T |
T |
F |
|
T |
F |
T |
|
F |
T |
T |
|
F |
F |
T |
NOR: Ø (p Ú q) (◙)
INFS3450 see NOR gate
exercises [JOH2001:446]
|
p |
q |
p ¯ q |
|
T |
T |
F |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
T |
Conditional:
“if…then…” or “implies”; the conditional p
Þ
q is equivalent to the disjunctionØ p Ú q (◙)
|
p |
q |
p Þ q |
|
antecedent |
consequent |
ant.Þcons. |
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
T |
|
F |
F |
T |
Biconditional: “…if
and only if…” “equivalent” – p and q have same truth value – (p Þ q) Ù (q Þ p) (◙)
|
p |
q |
p Û q |
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
T |
Tautology (example):
a statement that is always true (◙)
|
p |
Øp |
p Ú Øp |
|
T |
F |
T |
|
F |
T |
T |
Contradictory
statement (example): a statement that is always
false (◙)
|
p |
Øp |
p Ù Øp |
|
T |
F |
F |
|
F |
T |
F |
A statement which is neither tautologous nor contradictory is contingent. [COP1967:28] (◙)
Truth tables with only one (1) statement variable (like p) require two (2) lines; example negation: (◙)
|
p |
Øp |
|
T |
F |
|
F |
T |
Truth tables with two (2) statement variables (like p, q) require four (4) lines; example conditional: (◙)
|
p |
q |
p Þ q |
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
T |
|
F |
F |
T |
Truth tables with three (3) statement variables (like p, q, r) require eight (8) lines; example statement (p Ú q) Ù r: (◙)
|
p |
q |
r |
p Ú q |
(p Ú q)
Ù
r |
|
T |
T |
T |
T |
T |
|
T |
T |
F |
T |
F |
|
T |
F |
T |
T |
T |
|
T |
F |
F |
T |
F |
|
F |
T |
T |
T |
T |
|
F |
T |
F |
T |
F |
|
F |
F |
T |
F |
F |
|
F |
F |
F |
F |
F |
All of the above tables are based on two-valued logic (2VL): the only truth values which may be assigned are T and F (1 and 0). In logic theory, three (or more) values may be assigned. Copi gives examples with three-valued logic, using the values 0, 1, and 2. [COP1967:section 3.3] In database theory, Date describes a three-valued logic (3VL) approach to dealing with null values or “missing information” in relational databases where the third value is unknown, which could be represented by U. [DAT1995:570-571] Wagner proposes two kinds of negation for the Semantic Web. [WAG2001](◙)
References
[BUR2003] Stephen D. Burd, Systems Architecture, 4th ed. (Thomson, 2003).
[COP1967] Irving F. Copi, Symbolic Logic, 3rd ed. (MacMillan, 1967)
[DAT1995] C. J. Date, An Introduction to Database Systems, 6th ed. (Addison-Wesley, 1995)
[FIT2002] Jerry FitzGerald and Alan Dennis, Business Data Communications and Networking, 7th ed. (Wiley, 2002)
[JOH2001] Richard
Johnsonbaugh, Discrete Mathematics, Special Supplemented Edition for
INFS3450 (Pearson, 2003)
[KIR2003] Wolfgang Kirsten, Michael Ihringer, Mathias Kühn, and Bernhard Röhrig, Object-Oriented Application Development Using the Caché Postrelational Database, 2nd ed (Springer, 2003)
[
Contacts:
Valerie
J. Harvey, RT(R), PhD, C&IS, RMU
E.
Gregory Holdan, PhD, Mathematics, RMU