2. Predicate Logic
Solutions
Exercises A.
1. Define DERIVE functions FIRST and TAIL that take a vector as input. The function FIRST returns the first component of the input vector, and the function TAIL returns the vector obtained by deleting the first component of the input vector. For example,
FIRST([15, 2, 8, 19]) = 15, and
TAIL( [15, 2, 9, 19]) = [2, 9, 19].
Test your functions on the following vectors: [], [3], [4, 0, 1], and [true, false, false, false, false]. Write detailed descriptions of your definitions.
Solution
Author the following DERIVE expressions. The first and third expressions define the functions. The second and fourth expressions can be simplified to verify that the functions FIRST and TAIL return the desired results in these cases.
FIRST(v ) := v SUB 1
[FIRST([]), FIRST([3]), FIRST([4, 0, 1]), FIRST([true, false, false, false, false])]
TAIL(v) := VECTOR(v SUB i, i, 2, DIMENSION(v))
[TAIL([]), TAIL([3]), TAIL([4, 0, 1]), TAIL([true, false, false, false, false])]
The arguments of the functions FIRST and TAIL are vectors. The function FIRST returns the first element of the input vector v, and the function TAIL returns the vector obtained by construction of a vector starting with the second element of v.
2. Define a function CHECK of two variables: the first variable is a vector v of two components and the second variable is a value n. The function checks to see if the first component of the vector v equals n. For example,
CHECK( [1, false], 2 ) = false, and
CHECK ( [1, false], 1 ) = true.
Test your function CHECK, and write a complete description of your definition.
Solution
Author the following DERIVE expressions to define and test the function.
CHECK(v, n) := v SUB 1 = n
CHECK([1, false], 2)
CHECK([1, false], 1)
The function CHECK returns true if the first component of the vector v equals n, and CHECK returns false otherwise.
3. The function VAL defined below is a function of two variables: a predicate p expressed as a vector and a value n. This function evaluates the predicate p on n. For example, if we consider:
p := [ [0, true], [3, false], [2, true] ],
then we want the following:
VAL(p, 0 ) = true, VAL(p, 3) = false, and VAL(p, 2) = true.
The definition of VAL is recursive because its definition refers to itself.
VAL(p, n) := IF (DIMENSION(p) = 0, false,
CHECK (FIRST(p), n) AND (FIRST(p)) SUB 2 OR (VAL (TAIL(p),n)))
Test the function VAL, and write a complete description of how VAL computes the desired result. Try to think of a different definition for the function VAL.
Solution
Author the DERIVE expressions below and simplify the last two expressions to define and test the function VAL. Note that VAL returns false when n is not in the domain of the predicate p.
VAL(p, n) := IF(DIMENSION(p) = 0, false, CHECK(FIRST(p), n) AND (FIRST(p)) SUB 2 OR VAL(TAIL(p), n))
p := [[3, false], [0, true], [1, false], [2, true], [4, true]]
VECTOR([i, VAL(p, i)], i, 0, 4)
VAL(p, 5)
The function VAL recursively examines each element of the input predicate p. For each element c, VAL computes the conjunction of ‘the first component of c = n’ and the second component of c. The final result is the disjunction of the results computed for the components and false, the value of VAL on the empty predicate
A different definition of VAL correctly handles the case when n is not in the domain of the predicate p. Author the following DERIVE expressions and simplify the second expression.
VAL2(p, n) := IF(CHECK(FIRST(p), n), (FIRST(p)) SUB 2, VAL2(TAIL(p), n), "undefined")
VECTOR([i, VAL2(p, i)], i, -1, 6)
4. Define functions ALL and EXISTS of two variables: a set s (represented as a vector) and a predicate P. The functions check to see if all or at least one member of the set s has the property P, respectively. For example, if we use P of question #3, we want the following to hold:
ALL( [0, 2], P ) = true,
ALL( [0, 2, 3], P ) = false,
EXISTS( [2, 3], P ) = true, and
EXISTS( [ 3 ], P ) = false.
Test your functions, and write complete descriptions of their definitions.
Solution
Author the following DERIVE expressions to define and test the functions. The predicate p is that used in the previous problem.
ALL(s, p) := IF(DIMENSION(s) = 0, true, VAL(p, FIRST(s)) AND ALL(TAIL(s), p))
[ALL([], p), ALL([0, 2], p), ALL([0, 1, 2, 3], p)]
EXSTS(s, p) := IF(DIMENSION(s) = 0, false, VAL(p, FIRST(s)) OR EXISTS(TAIL(s), p))
[EXISTS([], p), EXISTS([0, 2], p), EXISTS([0, 1, 2, 3], p)]
The functions ALL and EXISTS recursively determine the value of p on each element of the set s. The function ALL returns the conjunction of these values, and the function EXISTS returns their disjunction.
Exercises B.
Now we will identify the logic constants true and false with the integers 1 and 0, respectively. Since we will need case-sensitive names, use the DERIVE command:
Declare Algebra State Input
and choose Sensitive Case.
1. Describe how the following vectors can be interpreted as predicates. What is the domain of each predicate?
IS_ODD1 := VECTOR( [i, MOD(i, 2)], i, 1, 10)
IS_EVEN1 := VECTOR( [i, 1 - MOD(i, 2)], i, 1, 10 )
IS_ODD2 := VECTOR( [i, MOD(i, 2)], i, -100, 100)
IS_EVEN2 := VECTOR( [i, 1 - MOD(i, 2)], i, -100, 100 )
Solution
Author the following DERIVE expressions, and simplify the definitions.
CaseMode := Sensitive
IS_ODD1 := VECTOR([i, MOD(i, 2)], i, 1, 10)
IS_EVEN1 := VECTOR([i, 1 - MOD(i, 2)], i, 1, 10)
IS_ODD2 := VECTOR([i, MOD(i, 2)],i, -100, 100)
IS_EVEN2 := VECTOR([i, 1 - MOD(i, 2)], i, -100, 100)
The vectors can be interpreted as predicates with 0 and 1 in the second columns associated with false and true, respectively.
The first two predicates have domain the set {1, 2, …, 10}; the last two predicates have domain the set {1, 2, …, 100}.
2. Define a function val that corresponds to the function VAL. Use your DERIVE functions and and or in the definition of the function val. Test your function val.
Solution
Author the following DERIVE expressions to define and test the function.
not(p) := 1 - p
and(p, q) := p * q
or(p, q) := not(and(not(p), not(q)))
check(v, n) := IF(v SUB 1 = n)
dim(p) := DIMENSION(p)
val(p, n) := IF(dim(p) = 0, 0, or(and(check(FIRST(p), n), (FIRST(p)) SUB 2),
val(TAIL(p), n)))
p := [[1, 1], [3, 0], [4, 0], [2, 1]]
val(p, 3)
VECTOR(val(p, i), i, 1, 4)
[val(IS_ODD1, 3), val(IS_ODD1, 8), val(IS_EVEN1, 3), val(IS_EVEN1, 8)]
[val(IS_ODD2, 25), val(IS_ODD2, -36), val(IS_EVEN2, 25), val(IS_EVEN2, -36)]
3. Test the following function and describe how it computes the desired value:
exists(S, P) :=
STEP (SUM (val(P, S SUB i), i, 1, DIMENSION(S)) -0.5)
The function STEP is the predefined function such that:
STEP(x) = 1 if x > 0, and
STEP(x) = 0 if x < 0.
For example,
exists( [1, 3, 2], IS_ODD1 ) = 1, and
exists( [8, 4, 0, 6], IS_ODD1 ) = 0.
Try to think of a different definition for the function exists.
Solution
The following DERIVE expressions define and test the function. The predicate p is defined in the solution of the preceding problem.
exists(S, P) := STEP(SUM(val(P, S SUB i), i, 1, dim(S)) - 0.5)
[exists([], p), exists([3, 4], p), exists([4, 3, 2], p), exists([1, 2], p)]
[exists([], IS_ODD1), exists([2, 3, 4], IS_ODD1), exists([2, 4], IS_EVEN1),
exists([7, 9, 3], IS_EVEN1)]
The function exists first computes the sum of all the values of the predicate P on members of S. If there is at least one 1, this sum minus 0.5 is positive, and STEP returns 1. On the other hand, if there is no value 1 of the predicate P on S, this sum equals 0, the sum minus 0.5 is negative, and STEP returns 0.
The correct results are obtained with a different definition.
exists2(s, p) := IF(dim(s) = 0, 0, or(val(p, FIRST(s)), exists2(TAIL(s), p)))
[exists2([], p), exists2([3, 4], p), exists2([4, 3, 2], p), exists2([1, 2], p)]
[exists2([], IS_ODD1), exists2([2, 3, 4], IS_ODD1), exists2([2, 4], IS_EVEN1),
exists2([7, 9, 3], IS_EVEN1)]
4. Define an analogous function all. Test the function all and describe how the desired result is computed.
Solution
The following DERIVE expressions define and test the function all.
all(S, P) := PRODUCT(val(P, S SUB i), i, 1, dim(S))
[all([], IS_ODD1), all([2, 3, 4], IS_ODD1), all([2, 4], IS_EVEN1), all([7, 9, 3],
IS_EVEN1)]
The function all computes the product of the values of the predicate P on the set S. This product is 1 if and only if there are no 0’s found.
5. Use the functions all and exists with particular sets s and particular predicates p and q to show that the three argument forms below are invalid. Explain how your examples show that the argument forms are invalid.
There exists x in the set S such that P(x). Therefore, for all x in S, P(x).
For all x in the set S, either P(x) or Q(x). Therefore, either for all x in S, P(x) or for all x in S, Q(x).
For all x in the set S, P(x) implies that for all x in S, Q(x). Therefore, for all x in S, P(x) implies Q(x).
Solution
The three argument forms can be written with DERIVE expressions as shown below. Each form is shown to be invalid by finding its value to be 0, which means false, in a particular case.
not(x) := 1 - x
and(x, y) := x * y
imp(x, y) := not(and(x, not(y)))
P := [[3, 0], [4, 1]]
S := [3, 4]
imp(exists(S, P), all(S, P))
Thus the first argument form is invalid.
Q := [[3, 1], [4, 0]]
PorQ := VECTOR([P SUB i SUB 1, or(P SUB i SUB 2, val(Q, P SUB i SUB 1))], i, 1,
DIMENSION(P))
S := [3, 4]
imp(all(S, PorQ), or (all(S, P), all(S, Q)))
Thus the second argument form is invalid.
imp(imp(all(S, P), all(S, Q)), all(S, imp(P, Q)))
Thus the third argument form is invalid.
1