Solu tion
P
Q
P Q
⇒
T
T
T
T
F
F
F
T
T
F
F
T
Suppose P is false.
Then P Q
⇒ is true for any proposition Q. If we know P Q
⇒ as true, and
accept P as true, then we can infer the truth of Q.
Q may or may not be true (as seen in truth table).
Ì Exam ple 8.1.20: The Sheffer stroke, or nand operator, is defined by the
following truth table:
P
Q
P Q
|
0
0
1
0
1
1
1
0
1
1
1
0
Nand is an acronym for not and, P Q
| is logically equivalent to ¬ ∧
(
).
P Q
Show that
(a) P P
P
| ⇔ ¬
(b) ( | )| ( | )
P P Q Q
P Q
⇔ ∨
(c) ( | )| ( | )
.
P Q P Q
P Q
⇔ ∧
Solu tion
P
Q
P Q
∧
¬ ∧
(
)
P Q
T
T
T
F
T
F
F
T
F
T
F
T
F
F
F
T
P Q
P Q
|
(
).
⇔ ¬ ∧
(NAND).
262
Theory of Automata, Formal Languages and Computation