Logic 1 (ch8)

38 flashcards · Mathematics · by J M COOPER

1. What are the pros of propositional logic?

   declarative: pieces of syntax correspond to facts allows partial/disjunctive/negated information (unlike most data structures and databases) compositional: eg meaning of B1,1 ∧ P1,2 is derived from meaning of B1,1 and of P1,2 context-independent (unlike natural language, where meaning depends on context)

2. What is a con of propositional logic?

   limited expressive power (unlike natural language) E.g., cannot say “pits cause breezes in adjacent squares” except by writing one sentence for each square

3. What is the difference between propositional logic and first order logic? What does first order logic contain?

   propositional logic assumes world contains facts, first-order logic (like natural language) assumes the world contains: • Objects: people, houses, numbers, theories, Ronald McDonald, colors, baseball games, wars, centuries . . . • Relations: red, round, bogus, prime, multistoried . . ., brother of, bigger than, inside, part of, has color, occurred after, owns, comes between, . . . • Functions: father of, best friend, third inning of, one more than, end of . . .

4. What does ontological commitment mean?

   The relation between a language and certain objects postulated to exist by that language.

5. What does epistemological commitment mean?

   An obligation to uphold the factual truth of a given proposition, and to provide reasons for one's belief in that proposition. Epistemic means 'of, or relating to knowledge'.

6. What are propositional logic's ontological and epistemological commitments?

   facts true/false/unknown

7. What are first order logic's ontological and epistemological commitments?

   facts, objects, relations true/false/unknown

8. What are probability theory's ontological and epistemological commitments?

   facts degree of belief

9. What are the 7 basic elements of first order logic?

   Constants eg KingJohn, 2, UCB, . . . (names of individual things) Predicates eg Brother, >, . . . (Something that could be true or false) Functions Sqrt, LeftLegOf, . . . (refers to an object, e.g. LeftLegOf(x)) Variables eg x, y, a, b, . . .(constants can be assigned to variables) Connectives: ∧ ∨ ¬ ⇒ ⇔ Equality: = Quantifiers: ∀ ∃

10. What is an atomic sentence and when is one true?

    An atomic sentence is one that consists of a predicate or an assignment. Used to state facts. eg predicate(term1, . . . ,termn) or term1 = term2 An atomic sentence is true if the relation referred to by the predicate symbol holds between the objects referred to by the arguments.

11. What is a predicate?

    something which is affirmed or denied concerning an argument of a proposition. in FOL a predicate is always a single word, beginning with a capital letter. A predicate specifies a relation between objects in the world.

12. What is a term?

    Terms are ways of referring to objects in the world. Eg function(term1, . . . ,termn) or a constant KingJohn or variable x

13. What is a function?

    A function refers to an object. For instance, LeftLegOf(x) might refer to the left of object x. Functions give us a powerful way to refer to objects without using a constant symbol to name them.

14. What is a complex sentence?

    Complex sentences are made from atomic sentences using connectives ¬S, S1 ∧ S2, S1 ∨ S2, S1 ⇒ S2, S1 ⇔ S2 E.g. Sibling(KingJohn, Richard) ⇒ Sibling(Richard, KingJohn) >(1, 2) ∨ ≤(1, 2) >(1, 2) ∧ ¬>(1, 2)

15. When are sentences true?

    Sentences are true with respect to a model and an interpretation. An atomic sentence predicate(term1, . . . ,termn) is true iff the objects referred to by term1, . . . ,termn are in the relation referred to by predicate

16. What does a model contain?

    Model contains ≥ 1 objects (domain elements) and relations among them

17. What does interpretation do?

    Interpretation specifies referents (what each thing stands for) for constant symbols → objects predicate symbols → relations function symbols → functional relations

18. Write an interpretation in which Brother(Richard, John) is true

    Richard → Richard the Lionheart John → the evil King John Brother → the brotherhood relation

19. Can entailment in FOL be computed by enumerating models?

    Yes, but it is not easy: For each number of domain elements n from 1 to ∞ For each k-ary predicate Pk in the vocabulary For each possible k-ary relation on n objects For each constant symbol C in the vocabulary For each choice of referent for C from n objects . .

20. Write "Everyone at Berkeley is smart" in FOL

    ∀ x At(x, Berkeley) ⇒ Smart(x)

21. When would ∀x P be true?

    ∀x P is true in a model m iff P is true with x being each possible object in the model Roughly speaking, equivalent to the conjunction of instantiations of P (At(KingJohn, Berkeley) ⇒ Smart(KingJohn)) ∧ (At(Richard, Berkeley) ⇒ Smart(Richard)) ∧ (At(Berkeley, Berkeley) ⇒ Smart(Berkeley)) ∧ . . .

22. What is wrong with: ∀ x At(x, Berkeley) ∧ Smart(x)?

    A common mistake: using ∧ as the main connective with ∀ Typically, ⇒ is the main connective with ∀ ∀ x At(x, Berkeley) ∧ Smart(x) means “Everyone is at Berkeley and everyone is smart” should be ∀ x At(x, Berkeley) ⇒ Smart(x)

23. What is ∀?

    Universal quantification/ for all eg ∀ x At(x, Berkeley) ⇒ Smart(x) "Everyone at Berkeley is smart" "For all x that are at berkeley implies those x are smart"

24. What is ∃?

    Existential quantification/ there exists eg ∃ x At(x, Stanford) ∧ Smart(x) "Someone at Stanford is smart" "there is an x at stanford and that x is smart"

25. When would ∃x P be true?

    ∃x P is true in a model m iff P is true with x being some possible object in the model Roughly speaking, equivalent to the disjunction of instantiations of P (At(KingJohn, Stanford) ∧ Smart(KingJohn)) ∨ (At(Richard, Stanford) ∧ Smart(Richard)) ∨ (At(Stanford, Stanford) ∧ Smart(Stanford)) ∨ . . .

26. What is wrong with: ∃ x At(x, Stanford) ⇒ Smart(x)

    Common mistake: using ⇒ as the main connective with ∃ Typically, ∧ is the main connective with ∃ ∃ x At(x, Stanford) ⇒ Smart(x) Means that if there exists an x at stanford it implies that x is smart - is true if there is anyone who is not at Stanford! (Remember P⇒Q is the same as ¬P∨Q) should be ∃ x At(x, Stanford) ∧ Smart(x)

27. is ∃x ∀y the same as ∀y ∃x?

    Not the same: ∃x ∀y Loves(x, y) “There is a person who loves everyone in the world” ∀y ∃x Loves(x, y) “Everyone in the world is loved by at least one person”

28. Is ∀ x ∀ y the same as ∀ y ∀ x?

    yes

29. Is ∃ x ∃ y the same as ∃ y ∃ x?

    yes

30. What is quantifier duality?

    Each can be expressed using the other, for example: ∀ x Likes(x, IceCream) all x like icecream ¬∃ x ¬Likes(x, IceCream) there does not exist an x that does not like icecream ∃ x Likes(x, Broccoli) there exists an x that likes broccoli ¬∀ x ¬Likes(x, Broccoli) not all x do not like broccoli

31. Express in first order logic: all people like icecream there does not exist a person that does not like icecream

    ∀ x Likes(x, IceCream) ¬∃ x ¬Likes(x, IceCream)

32. Express in first order logic: Brothers are siblings

    ∀ x, y Brother(x, y) ⇒ Sibling(x, y).

33. Express in first order logic: “Sibling” is symmetric

    ∀ x, y Sibling(x, y) ⇔ Sibling(y, x).

34. Express in first order logic: One’s mother is one’s female parent

    ∀ x, y Mother(x, y) ⇔ (Female(x) ∧ Parent(x, y)).

35. Express in first order logic: A first cousin is a child of a parent’s sibling

    ∀ x, y FirstCousin(x, y) ⇔ ∃ p, ps Parent(p, x) ∧ Sibling(ps, p) ∧ Parent(ps, y)

36. What are semantic primitives in FOL?

    objects and relations are semantic primitives

37. What is the syntax of FOL?

    constants, functions, predicates, equality, quantifiers

38. Express in first order logic: there exists a person that likes broccoli not all people do not like broccoli

    ∃ x Likes(x, Broccoli) ¬∀ x ¬Likes(x, Broccoli)