(d) 3x = 6 if and only if x = 2
∨
⇔
x P x
E x
[ ( , , )
( , )]
3 6
2
(e) There is no solution to x
2 = y unless y ≥ 0.
∨ ¬
⇔ ¬
∨
x
x x y
G y
E y
[ ( , , )
[ ( , )
( , )]]
0
0
(f) x < z is a necessary condition for x < y and y < z.
∨ ∨ ∨ ¬
∧ ¬
⇒ ¬
x
y
z
G x y
G y z
G x z
[[
( , )
( , )]
( , )]
(g) x y
≤ and y x
≤ is a sufficient condition for y = x.
∨ ∨
¬
∧ ¬
⇒
x
y
G x y
G y x
E y x
[[
( , )
( , )]
( , )]
(h) If x < y and z > 0, then xz > yz.
∨ ∨ ∨
∧
⇒ ∨ ∨
∧
⇒
x
y
z
u
v
G y x G z
P x z u P y z v
G
[( ( , )
( , )
[[ ( , , )
( , , )]]
(
0
u v
, )
(i) It cannot happen that x = y and x < y.
¬ ∨ ∨
∧
x
y E x y G y x
[ ( , )
( , )]
(j) If x < y then for some z such that z < 0, xz > yz.
∨ ∨
∧ ℑ
⇒ ∨ ∨
∧
⇒
x
y
y
u
v
G y x
G z
P x z u P y z v
G
[( ( , )
( , )]
[[ ( , , )
( , , )]]
0
( , ).
u v
(k) Do it yourself.
Ì Exam ple 8.4.2: Let the universe of discourse be the set of arithmetic
assertions with predicates defined as follows:
P (x) denotes “x is provable”.
T (x) denotes “x is true”.
S (x) denotes “x is satisfiable”.
D (x, y, z) denotes “z is the disjunction x y
∨ ”
Translate the following assertions into English statements.
(a) ∨
⇒
x P x
T x
[ ( )
( )]
(b) ∨
∨ ¬
x T x
S x
[ ( )
( )]
(c) ℑ
∧ ¬
x T x
P x
[ ( )
( )]
(d) ∨ ∨ ∨
∧
⇒
∨
x
y
z
D x y z P z
P x P y
{[ ( , , )
( )] [ ( )
( )]}
(e) ∨
⇒ ∨ ∨
⇒
x
y
z
T x
D x y z
T z
{ ( )
[ ( , , )
( )]}
Solu tion
(a) ∨
⇒
x P x
T x
[ ( )
( )]
If x is provable, then x is true.
284
Theory of Automata, Formal Languages and Computation