Homework 2 - Predicate Logic

Problem 1 Identify the following as constants, variables, ground atomic formulas, or non-ground atomic formulas, using the conventions of this section.

a) CMPT333

b) cmpt333

c) 333

d) cmpt333

e) p(X,x)

f) p(3,4,5)

g) p(3,4,5)

Problem 2

(csg(CMP T333, S, G) AND snap(S, C.Brown, A, P)) answer(G) (1)

Write an expression similar to (1)

for the question What grade did L. Van Pelt get in CMPT220? What substitution for variables did you make to demonstrate the truth of this answer? (See Example 3)

Logical Expressions Example 3 Suppose that we have predicates csg and snap, which we interpret as the relations Course-Student-Grade and Student-Name-Address Phone. Suppose also that we want to find the grade of the student named "C. Brown" in course CS101. We could assert the logical expression csg("CS101", S, G) AND snap(S, "C.Brown, A, P) + answer(G) (1) Here, answer is another predicate, intended to be true of a grade Gif G is the grade of some student named "C. Brown" in CS101. When we "assert" an expression, we mean that its value is TRUE no matter what values we substitute for its variables. Informally, an expression such as (1) can be interpreted as follows. If we substitute a constant for each of the variables, then each of the atomic formulas becomes a ground atomic formula. We can decide whether a ground atomic formula is true or false by referring either to the "real world," or by looking it up in a relation that lists the true ground atomic formulas with a given predicate. When we substitute 0 or 1 for each of the ground atomic formulas, we can evaluate the expression itself, just as we did for propositional logic expressions. In the case of expression (1), we can take the tuples to be true. In particular, 1 csg("CS101",12345, A) and snap(12345, "C. Brown, 12 Apple St.", 4555-1234") are true. Then we can let S=12345 G= "A" A= "12 AppleSt." P= "555 1234" That makes the left side of (1) become 1 AND 1, which has the value 1, of course. In principle, we don't know anything about the predicate answer. However, we asserted the expression, which means that what- ever values we substitute for its variables, its value is TRUE. Since its left side is made TRUE by the above substitution, the right side cannot be FALSE. Thus we deduce that answer("A") is true. Logical Expressions Example 3 Suppose that we have predicates csg and snap, which we interpret as the relations Course-Student-Grade and Student-Name-Address Phone. Suppose also that we want to find the grade of the student named "C. Brown" in course CS101. We could assert the logical expression csg("CS101", S, G) AND snap(S, "C.Brown, A, P) + answer(G) (1) Here, answer is another predicate, intended to be true of a grade Gif G is the grade of some student named "C. Brown" in CS101. When we "assert" an expression, we mean that its value is TRUE no matter what values we substitute for its variables. Informally, an expression such as (1) can be interpreted as follows. If we substitute a constant for each of the variables, then each of the atomic formulas becomes a ground atomic formula. We can decide whether a ground atomic formula is true or false by referring either to the "real world," or by looking it up in a relation that lists the true ground atomic formulas with a given predicate. When we substitute 0 or 1 for each of the ground atomic formulas, we can evaluate the expression itself, just as we did for propositional logic expressions. In the case of expression (1), we can take the tuples to be true. In particular, 1 csg("CS101",12345, A) and snap(12345, "C. Brown, 12 Apple St.", 4555-1234") are true. Then we can let S=12345 G= "A" A= "12 AppleSt." P= "555 1234" That makes the left side of (1) become 1 AND 1, which has the value 1, of course. In principle, we don't know anything about the predicate answer. However, we asserted the expression, which means that what- ever values we substitute for its variables, its value is TRUE. Since its left side is made TRUE by the above substitution, the right side cannot be FALSE. Thus we deduce that answer("A") is true