74 - Home - Department of Computer Science



74.419 Artificial Intelligence 2003/2004

Self-assessment Test on Logic (Propositional Calculus, First-Order Predicate Logic)

1. Set up the truth tables for the following formulae

|P |Q |P ( Q |

|F |F |T |

|F |T |T |

|T |F |F |

|T |T |T |

a) P ( Q

|P |Q |( P ( Q |

|F |F |T |

|F |T |T |

|T |F |F |

|T |T |T |

b) ( P ( Q

|P |Q |P ( Q |( (P ( Q) |

|F |F |F |T |

|F |T |T |F |

|T |F |T |F |

|T |T |T |F |

c) ( (P ( Q)

2. Transform the following formulae into equivalent formulae without brackets.

a) P ( (Q ( R) P ( Q ( P ( R

b) P ( (Q ( R) P ( Q ( R

c) ( (( (P)) P

d) ( (P ( Q) (P ( (Q True except if both P and Q true

e) ( (P ( Q) (P ( (Q True only if both P and Q false

3. Transform the following formulae into equivalent formulae without implication symbols.

a) P ( Q (P ( Q

b) P ( Q ((P ( Q) ( ((Q ( P) ( ((P((Q) ( ((P(P) ( (Q((Q) ( (Q(P)

( ((P ( (Q) ( (Q ( P)

4. What can you say about the following formulae regarding their truth values? Which formulae are always true, never true, or they depend (on what?)

a) P ( (P never true

b) P ( (P always true

c) P ( P always true

d) P ( (P depend on the assignment of truth-

e) (P ( Q) depend values to the propositions P, Q

5. What is a Tautology?

A Tautology is a formula which is always true, no matter what interpretation you choose for the propositional variables. Example: P ( (P – Whether the formula evaluates to true or not, does not depend on the truth value of the proposition P.

6. Does the sentence “Either 2+2=4 and it is raining, or 2+2=4 and it is not raining” make any claim about weather, arithmetic, neither, or both? Transform the sentence into a formula in propositional logic and determine its truth status; you can use truth tables for this.

Let P represent “2+2=4” and Q represent “it is raining”. Then the formula would be:

(P ( Q) ( (P ( (Q)

This formula evaluates to true if - and only if - P is true, no matter how the weather is. Thus, we could say that the sentence makes a statement about arithmetic, but not about the weather.

7. What about the sentence “If the moon is made of blue cheese, then I am the Queen of England.” (my personal favorite) - Is it always true, always false or it depends? Why is this sentence so odd? What, if there is a world with a moon made of blue cheese?

Let A represent “The moon is made of blue cheese.” and B represent “I am the Queen of England.” The corresponding formula would be:

A ( B

The formula is true, if the moon is not made of blue cheese, or, in case the moon is made of blue cheese, then I have to be the Queen of England. Otherwise, the sentence would be false, if, for example, the moon was made of blue cheese but I was still not the Queen of England. And there are worlds were the moon is made of cheese, although most of the times, it’s Swiss Cheese, and not Blue Cheese, and these moons are always habitats of a gigantic mouse.

8. Consider a world in which there are only 4 propositions: A, B, C, and D. How many different assignments of truth values to the variables A, B, and C can you find for each formula, which make this formula true?

a) A ( B 1 out of 4

b) A ( B 3 out of 4

c) A ( B ( C 1 out of 8

d) A ( B 3 out of 4

9. What are the main differences between Propositional Logic and First-Order Predicate Logic?

FOPL formulae are more structured than the propositional statements in PropLog through the introduction of predicates, functions, constants and variables. A major difference is the introduction of variables and subsequently the use of quantifiers.

10. Are the following FOPL formulae syntactically correct FOPL formulae (well-formed formula wff), assuming that P, Q, … are predicate symbols; f, g, … function symbols; x, y, … (individual) variables; c, d, … (individual) constants?

Are they always true (T), never true (F) or it depends (D) (on what)?

a) (x. P(x) wff D

b) (x. Q(x) wff D

c) (x. Q(y) not really D

d) (x. Q no

e) (x. Q(c) not really D

f) P(c) ( (x. P(x) wff T

g) (x. P(x) ( P(c) wff T

h) (x. P(f(x)) ( Q(x) wff D

i) (x,y (z. f(x,y)=z wff D

11. Try to find an interpretation of the symbols for formulae h) and i), which make these formulae meaningful sentences. You may choose for h) family relationships (like mother, child, husband, wife, …), and for i) a number model (integers).

(x. P( f(x) ) ( Q(x) Choose f as mother, P as husband, and Q as man.

(x,y (z. f(x,y)=z Choose f as plus, and the domain as integers.

12. There is one very important Inference Rule called Modus Ponens, which is the basis of so-called rational thinking, and used for drawing conclusions in rule-based systems like PROLOG. How does Modus Ponens go?

Modus Ponens (, ( ( (

(

13. Do you remember any other Inference Rules? The following plus Modus Ponens is a complete set of Inference Rules.

a) Introduction of Existential Quantifier ((c)

(Existential Generalization) (x. ( (x)

b) Elimination of All-Quantifier (x. ( (x)

(Universal Instantiation) ((c)

c) Replacement Rules ( ( ( (( ( ( ( ( ( (((( ( (()

(( ( ( ( ( ( (((( ( (() ( ( (

14. If you apply an Inference Rule in reasoning, in general you derive a new formula ( based on a given set of formulae (. Does this mean that ( and ( are always true, or what does it mean?

Inference Rules in general are rules with which you can – in a syntactic manipulation – derive new formulae from given ones, and these new formulae are true, provided the given formulae which were used in the application of the Inference Rule are true. These Inference Rules are schemata, in which specific formulae can substitute the formula-variables, like ( and (.

15. Do you have any idea what an Axiom is?

If you want to specify general rules about a domain o world which you want to model, you can define formulae in a logic, which describe these general rules, rules which are always valid, and thus it is assumed that these formulae are always true (in your world) and thus they are the basic axioms of your logic. An axiom valid in all binary logics (which have only two truth values, True and False), could be, for example, P ( (P, which corresponds to Aristotle’s ‘Law of the Excluded Middle’. Some axioms for FOPL are 1) ( ( ( ( ( 2) ( ( ( ( ( 3) ( ( ( ( ( ( (

16. How about a Theorem?

A Theorem is a formula which you derived from the given Axioms using Inference Rules. If your Axioms are valid, and you applied the Inference Rules properly, then a Theorem is a true formula in your world.

17. Transform the following sentences into FOPL formulae.

a) At least one student fails this class.

(x. student (x, cs419) ( fails (x, cs419)

b) No student fails this class.

(x. student (x, cs419) ( ( (fails (x, cs419))

c) Cs419-students, who do not attend class on a regular basis, will fail the exam.

i. (x. student (x, cs419) ( (attend (x, cs419, regularly) ( fails (x, cs419))

ii. (x. student (x, cs419) ( attend (x, cs419, irregularly) ( fails (x, cs419))

In the first case, ‘regularly’ is a constant referring to, for example, ‘more than 80%’. A student who does not attend 80% or more of the classes (or attends less than 80% of the classes), would fail. In the second formula, we model ‘irregularly’ as a constant referring to, for example, 20% or less (as negation of ‘regularly’). Then, the formula states that a student fails the exam when attending less than 20% of the classes.

In formulae iii and iv, which are describing the ambiguity more exactly, we use a function ‘frequency’, which gives a value for the frequency of class attendance of a student. We apply a predicate ‘regular’ to this value, which yields True or False depending on the frequency. In iii, a student fails if the frequency of class attendance is below 80%; in iv, a student fails if the frequency of not attending is regular, i.e. 80% or higher.

iii. (x. student (x, cs419) ( ( (regular (frequency (attend (x, cs419)))) ( fails (x, cs419))

iv. (x. student (x, cs419) ( regular (frequency (( (attend (x, cs419)))) ( fails (x, cs419))

d) A cs419-student who does not participate in the group project, will score 0 points for this project.

(x. student (x, cs419) ( ( (participate (x, cs419-project)) ( score (x, cs419-project) = 0

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download