AI Ch07-Ch09 Flashcards _ Quizlet

pdf

School

University of Southern California *

*We aren’t endorsed by this school

Course

561

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by MegaRam3541

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 1/12 AI Ch07-Ch09 Terms in this set (79) ∀ x (dog(x) => animal(x)) What is the predicate form of the following statement? "All dogs are animals." Eliminate Implications The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [ ∀ y Animal( y ) Loves( x, y )] [ y Loves( y, x )] [2] ∀ x [ ¬ ∀ y ¬ Animal( y ) ∨ Loves( x, y )] ∨ [ ∃ y Loves( y, x )] ∀ x [d_pusher(x) ⇒ ¬ VIP(x)] What is the predicate form of the following statement? "No drug pusher was a VIP" Drop Universal Quantifier The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [Animal( F(x) ) ∧ ¬ Loves( x, F(x) )] ∨ Loves( G(x), x ) [2] [Animal( F(x) ) ∧ ¬ Loves( x, F(x) )] ∨ Loves( G(x), x ) Standardize the variable The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [ ∃ y Animal( y ) ∧ ¬ Loves( x, y )] ∨ [ ∃ y Loves( y, x )] [2] ∀ x [ ∃ y Animal( y ) ∧ ¬ Loves( x, y )] ∨ [ ∃ z Loves( z, x )] John McCarthy [AI07] _____ was primarily responsible for the introduction of first-order logic as a tool for building AI systems.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 2/12 satisfiable [AI07-09] Decide whether the following sentence is valid, unsatisfiable, or satisfiable.Smoke Fire Resolution [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic. Select the best choice as discussed in the class. Horn [AI07-09] The ___ clause is a disjunction of literals of which at most one is positive. Sound [AI07-09] An inference algorithm that derives "only" entailed sentences is called ____. complete [AI07-09] Forward chaining with Horn clauses is ____ as every entailed atomic sentence will be derived. John McCarthy [AI07] Logical state estimation, of course, requires a logical representation of the effects of actions — a key problem in AI since the late 1950s. The dominant proposal has been the situation calculus formalism by _____ (1963), which is couched within first- order logic. backward chaining [AI07-09] _____ is a form of goal-directed reasoning. Select the best answer.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 3/12 sound [AI07-09] (Note: i-th literal l or j-th literal m is denoted as l[i] or m[j].)The resolution rule is ____. This can be seen easily by considering the literal l[i] that is complementary to literal m[j] in the other clause. If l[i] is true, then m[j] is false, and hence m[1] ∨ · · · ∨ m[j − 1] ∨ m[j+1] ∨ · · · ∨ m[n] must be true, because m[1] ∨ · · · ∨ m[n] is given. If l[i] is false, then l[1] ∨ ··· ∨ l[i − 1] ∨ l[i+1] ∨ ··· ∨ l[k] must be true because l[1] ∨ ··· ∨ l[k] is given. Now l[i] is either true or false, so one or other of these conclusions holds — exactly as the resolution rule states. Cordell Green [AI07] _____ (1969a, 1969b) developed a first-order reasoning system, QA3, leading to the first attempts to build a logical robot at SRI (Fikes and Nilsson, 1971). valid [AI07-09] What good are valid sentences? From our definition of entailment, we can derive the deduction theorem, which was known to the ancient Greeks: For any sentences and , |= if and only if the sentence ( ) is ____. forward [AI07-09] With ____ chaining, the inferred table could be viewed as a logical model where every definite clause in the original KB is true in this model. Or-Introduction [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 4/12 And-Elimination [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic. definite [AI07-09] Every ____ clause can be written as an implication whose premise is a conjunction of positive literals and whose conclusion is a single positive literal. factoring [AI07-09] If we resolve (A ∨ B) with (A ∨ ¬ B), we obtain (A ∨ A), which is reduced to just A. The removal of multiple copies of literals is called ____. Horn [AI07-09] The restricted form of ____ is the basis of logic programming (e.g., Prolog). Select the best choice. unification [AI09] Lifted inference rules require finding substitutions that make different logical expressions look identical. This process is called _____ and is a key component of all first-order inference algorithms. valid [AI07-09] Decide whether the following sentence is valid, unsatisfiable, or satisfiable.Smoke ∨ Fire ∨ ¬ Fire J. A. Robinson [AI07] The prospects for logic-based AI were advanced significantly by ______ (1965) development of resolution, a complete procedure for first-order inference

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 5/12 Thoralf Skolem [AI07] This process by ____ is the process of removing existential quantifiers by elimination. Emil Post and Ludwig Wittgenstein [AI07] Truth tables as a methodof testing validityor unsatisfiability in propositional logicwere introduced independently by_______. backward chaining [AI07-09] The first complete algorithm of _____ is often called the Davis-Putnam algorithm, after the seminal paper by Martin Davis and Hilary Putnam (1960). The algorithm is in fact the version described by Davis, Logemann, and Loveland (1962), so it is called DPLL after the initials of all four authors. Alfred Horn [AI07] This form of clause (a disjunction of literals of which at most one is positive) and logic by ___ is the theoretical basis of logic programming language (e.g., Prolog). KB ∧ |= [AI07-09] Consider logical systems which are monotonic. For any sentences and , if KB |= then ____. Every sentence of propositional logic then forms a set of disjunctive normal form of clauses [AI07-09] Which one of the following statements is NOT correct? M ( ) ⊆ M ( ). [AI07-09] M( ) to mean the set of all models of . The formal definition of entailment is this: |= if and only if, ____. proof by modus ponens [AI07-09] Proving from by checking the unsatisfiability of ( ∧ ¬ ) corresponds exactly to the standard mathematical proof technique of ______. Which one of the following choices is NOT correct?

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 6/12 Skolemize The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [ ∃ y Animal( y ) ∧ ¬ Loves( x, y )] ∨ [ ∃ z Loves( z, x )] [2] ∀ x [Animal( F(x) ) ∧ ¬ Loves( x, F(x) )] ∨ Loves( G(x), x ) A2 & C In the process of proving: "Kills(Curiosity, Tuna)" with KB given below: [A1] Animal(F( x )) ∨ Loves(G( x ), x ) [A2] ¬ Loves( x , F( x )) ∨ Loves(G( x ), x ) [B] ¬ Animal( y ) ∨ ¬ Kills( x,y ) ∨ ¬ Loves( z,x )] [C] ¬ Animal( x ) ∨ Loves(Jack, x ) [D] Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna) [E] Cat(Tuna) [F] ¬ Cat( x ) ∨ Animal( x )Which clause(s) is/are used to get the following resolvent: Loves(G(Jack), Jack) ∨ ¬ Animal(F(Jack)) Move negation inward The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [ ¬ ∀ y ¬ Animal( y ) ∨ Loves( x, y )] ∨ [ ∃ y Loves( y, x )][2] ∀ x [ ∃ y Animal( y ) ∧ ¬ Loves( x, y )] ∨ [ ∃ y Loves( y, x )] (Animal(F( x )) ∨ Loves(G( x ), x )) ∧ ( ¬ Loves( x , F( x )) ∨ Loves(G( x ), x )) What is the clausal form of the following FOL clause [1]?[1] ∀ x [ ∀ y Animal( y ) Loves( x, y )] [ y Loves( y, x )] Distribute ∨ over ∧ The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] [Animal( F(x) ) ∧ ¬ Loves( x, F(x) )] ∨ Loves( G(x), x ) [2] [Animal( F(x) ) ∨ Loves( G(x), x )] ∧ [ ¬ Loves( x, F(x) )] ∨ Loves( G(x), x )] Eliminate Implications The following step in conversion from (1) FOL to (2) Clausal form is to ___. [1] ∀ x [ ∀ y Animal( y ) Loves( x, y )] [ y Loves( y, x )] [2] ∀ x [ ¬ ∀ y ¬ Animal( y ) ∨ Loves( x, y )] ∨ [ ∃ y Loves( y, x )]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 7/12 linear [AI07-09] The cost of backward chaining is much less than ____ in the size of the knowledge base, because the process touches only relevant facts. Select the best answer. standarizing apart [AI09] The UNIFY algorithm takes two sentences and returns a unifier for them if one exists: UNIFY(p, q) = where SUBST( , p) = SUBST( , q). The problem arises only because the two sentences happen to use the same variable name, x. The problem can be avoided by ____ one of the two sentences being unified, which means renaming its variables to avoid name clashes. Early termination [AI07-09] DPLL algorithm uses the fact that the sentence (A ∨ B) ∧ (A ∨ C) is true if A is true, regardless of the values of B and C. Similarly, a sentence is false if any clause is false, which occurs when each of its literals is false. Again, this can occur long before the model is complete. This strategy is an example of ____. Unit clause heuristic [AI07-09] Consider DPLL. If the model contains B = true, then ( ¬ B ∨ ¬ C) simplifies to ¬ C, which is a unit clause. Obviously, for this clause to be true, C must be set to false. This strategy assigns all such symbols before branching on the remainder. One important consequence is that any attempt to prove (by refutation) a literal that is already in the knowledge base will succeed immediately. This is an example of ________. entails [AI07-09] An alternative definition of equivalence is as follows: any two sentences and are equivalent only if each of them ___ the other Horn [AI07-09] Deciding entailment with ____ clauses can be done in time that is linear in the size of the knowledge base.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 8/12 True [AI07-09] This is ____ that the sentence x = 0 entails the sentence xy = 0. The set of atomic sentences at the final state defines a refuted model of the original KB. [AI07-09] Which one of the following statements is NOT correct? Consider forward chaining. satisfiable [AI07-09] Decide whether the following sentence is valid, unsatisfiable, or satisfiable.Smoke Fire definite [AI07-09] One restricted form of FOL in clausal form is the ____ clause, which is a disjunction of literals of which exactly one is positive. Gottlob Frege [AI07] ____, who developed full first-order logic in 1879, based his system of inference on a collection of valid schemas plus a single inference rule, Modus Ponens. Alain Colmerauer [AI07] In Europe, logic programming (Prolog, a restricted form of first-order reasoning) was developed for linguistic analysis by ______ and for general declarative systems (Kowalski, 1974). Computational logic was also well entrenched at Edinburgh through the LCF (Logic for Computable Functions) project (Gordon et al., 1979). CNF [AI07-09] The algorithm described by Davis, Logemann, and Loveland (1962), so it is called DPLL takes as input a sentence in ____ - a set of clauses. Select the best answer. Complete [AI07-09] An inference algorithm that can derive "any" sentence that is entailed sentences is called ____.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 9/12 complete [AI09] First-order inference via propositionalization is ____. That is, any entailed sentence can be proved. And-Introduction [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic. ∃ x ∀ y [entered_country(x) ∧ d_pusher(x)] ∧ [searched(y,x) ⇒ d_pusher(y)] What is the predicate form of the following statement? "Some of the drug pushers entered this country and they were only searched by drug pushers" ¬ official(x) ∨ ¬ d_pusher(x) The goal to prove (by refutation) is: "At least one of the custom officials was a drug pusher." What should be the goal in Clausal Form? semidecidable [AI09] The question of entailment for first-order logic is _____. That is, algorithms exist that say yes to every entailed sentence, but no algorithm exists that also says no to every nonentailed sentence. Early termination [AI07-09] The DPLL algorithm detects whether the sentence must be true or false, even with a partially completed model. A clause is true if any literal is true, even if the other literals do not yet have truth values; hence, the sentence as a whole could be judged true even before the model is complete. This is an example of _____. |= if and only if is satisfiable when is satisfiable. [AI07-09] Which one of the following statements is NOT correct?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 10/12 fixed point [AI07-09] With forward chaining, the final state of the inferred table reaches a(an) _____ where no new inferences are possible. The table contains true for each symbol inferred during the process, and false for all other symbols. RC(S) could be countable in size. [AI07-09] Which one of the following statements is NOT correct?Consider the resolution closure RC(S) of a finite set of clauses S, which is the set of all clauses derivable by repeated application of the resolution rule to clauses in S or their derivatives. Kurt G ö del [AI07] ___ showed that a complete procedure for inference in first-order logic could be obtained via a reduction to propositional logic,using Herbrand's theorem (Herbrand, 1930). Modus Ponens [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic. Select the best choice as discussed in the class. monotonic [AI07-09] One property of logical systems is _____. That is, the set of entailed sentences can only increase as information is added to the knowledge base.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 11/12 Unit Resolution [AI07-09] The following ____ rule is one of the seven inference rules for propositional logic. Select the best choice as discussed in the class. John McCarthy [AI07] The frame problem was first recognized by ____ and Hayes. Many researchers considered the problem unsolvable within first-order logic, and it spurred a great deal of research into nonmonotonic logics. The solution of the frame problem with successor-state axioms is due to Ray Reiter (1991). Thielscher (1999) identifies the inferential frame problem as a separate idea and provides a solution. depth-first [AI07-09] The DPLL algorithm generates essentially a ____ enumeration of possible models. Existential Instantiation [AI09] _____ is a special case of a more general process called skolemization. valid [AI07-09] Decide whether the following sentence is valid, unsatisfiable, or satisfiable.Smoke Smoke forward chaining [AI09] ____ algorithm for propositional definite clauses is done as follows: start with the atomic sentences in the knowledge base and apply Modus Ponens in the forward direction, adding new atomic sentences, until no further inferences can be made. satisfiable [AI07-09] A sentence is ____ if it is true in, or satisfied by, some model.

23/10/2023, 13:14 AI Ch07-Ch09 Flashcards | Quizlet https://quizlet.com/713070702/ai-ch07-ch09-ﬂash-cards/ 12/12 is true, is also true. [AI07-09] In mathematical notation, we write " |= " to mean that the sentence entails the sentence . The formal definition of entailment is this: |= if and only if, in every model in which _____. The resolvent of (4 & 5) & 6 In the process of proving the goal [G] with KB given below: [1] ¬ food(x) ∨ likes(John, x) [2] food(Apple) [3] food(Chicken) [4] ¬ eats(x,y) ∨ killed(x,y)) ∨ food(y) [5] eats(Bill, Peanuts) [6] ¬ killed(Bill, Peanuts) [7] ¬ eats(Bill,x) ∨ eats(Sue,x) Which clause(s) is/are used to get the following resolvent: food(Peanuts). An empty clause may indicate that the inference is terminated and KB does not entail . [AI07-09] Consider Resolution algorithm Inference procedure. Which one of the following statements is NOT correct? sound [AI07-09] Forward chaining with Horn clauses is ____ as every inference is essentially an application of Modus Ponens. NP-complete [AI07-09] The problem of determining the satisfiability of sentences in propositional logic — the SAT problem — was the first problem proved to be ____. The sentence P ^ ¬ P is valid. [AI07-09] Which one of the following statements is NOT correct? [AI07-09] ___ is a form of data-driven reasoning, started with the known data. Select the best choice.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

AI Ch07-Ch09 Flashcards _ Quizlet

Related Documents