(b) V T x
S x
x [ ( )
( )]
∨ ¬
If x is true or it is unsatisfiable.
(c) ℑ
∧ ¬
x T x
P x
[ ( )
( )]
There is some x, for which x is true and it not provable.
(d) ∨ ∨ ∨
∧
⇒
∨
x
y
z
D x y z P z
P x P y
{[ ( , , )
( )] [ ( )
( )]}
If the assertion z = x ∨ y and the assertion p(z) is provable, then
either x is provable or y is provable.
(e) ∨
⇒ ∨ ∨
⇒
x
y
z
T x
D x y z
T z
{ ( )
[ ( , , )
( )]}
If every arithmetic assertion is true, then the assertion z x y
= ∨ is
true.
Ì Exam ple 8.4.3: Write the following using logical notation. Choose
predicates so that each assertion requires at least one quantifier.
(a) There is one and only one even prime
(b) No odd numbers are even.
(c) Every train is fasten than some cars.
(d) Some cars are slower than all trains but at least one train is faster
than every car.
(e) If it trains tomorrow, then somebody will get wet.
Solu tion
(a) P (x): x is prime
E (x): x is even
ℑ
∧
! [ ( )
( )]
x P x E x
(b) P (x): x is odd
E (x): x is even
¬ ℑ
∧
x
x E x
[ ( )
( )]
0
(c) T (x): x is a train
C (y): y is a car
F (x, y): x is faster than y.
∨
⇒ ℑ
∧
x
y
T x
C y F x y
[ ( )
( ( )
( , ))]
(d) ∨ ℑ
∧ ¬
∧ ℑ ℑ
∧
x
y
x y
C y
F x y
T x F x y
[ ( )
( , )]
[ ( )
( , )]
(e) R: It rains tomorrow.
W(x): x will get wet.
R
w x
x
⇒ ℑ [ ( )].
Ì Exam ple 8.4.4: Find an assertion which is logically equivalent to
∨ x P x
( ) but uses only the quantifier ℑ and the logical operator ¬ .
Similarly, express ℑ x P x
( ) in terms of ∨ and ¬. Similarly, express ℑ x P x
( )
in terms of ∨ and ¬.
Prop o si tions and Pred i cates
285