- Please DO NOT use any AI tools like Chat-GPT to generate codes/answers as that'd a violation.

1. (SAT-solving) a. In the DPLL strategy, certain variables are assigned values before others are assigned values. What are the two conditions corresponding to these strategic choices? b. In what sense and why are these choices "safe"? c. In clause learning (enabling non-chronological backtracking), what literals (i.e., negated or unnegated variables) are made part of a learned clause? Why?

2. (Frames) a. Try to write down a definitional frame for A HAMMER consisting of A METALLIC HEAD ATTACHED TO A WOODEN HANDLE, using the exact syntax covered in class (with appropriate keywords, brackets, and appropriate use of upper and lower case). If you're doing this correctly, you should have trouble capturing all of the capitalized information above; what's the problem? What new device(s) would you suggest allowing in frame contents, to overcome this problem? What would the specific add-on(s) be in the hammer example?

b. Much of our understanding of what physical objects look like and how they are structured seems to be in the form of 3-D "imagistic" knowledge. Suppose we augment frames for specific kinds of physical objects with 3-D graphics representations (e.g., we would do this for "HAMMER" but not for something more generic like "TOOL"). But then we need some way of linking the image parts to the symbolic parts. E.g., a robot using frames and asked by a person to grasp the handle of a hammer lying nearby would first of all need to match the physical hammer to its hammer-image, and it would then have to figure out which part of the matched object is the handle. How could the symbolic and 3-D graphics information about parts be annotated to enable the robot to do the right thing? 3. (CWA) Consider knowledge base KB = {Penguin(A) Flies(A), (x (Walks-upright(x) => Flies(x))), Walks-upright(A), Flies(B), Flies(C)}. a. Is this a Horn KB? Why or why not? b. Does this KB satisfy the condition for the consistency of CWA[KB]? Explain. c. List the (negative) facts that are directly added by the CWA. Consider only those facts that can be formed from the predicates and constants occurring in KB. d. Suppose C is a chicken and we're not actually sure whether it flies or not, so we try to express this by replacing Flies(C) with Flies(C) Flightless(C), (x (Flightless(x) => Flies(x))); Call the altered knowledge base KB'. Indicate why this leads to an inconsistent CWA[KB'] (saying enough about the combined consequences of the two formulas to convince the grader you understand why). If we change the '=>' to '<=>' in the added universal formula, the inconsistency disappears. Indicate why. 4. (Nonmonotonic inheritance networks) In the NIN about mushrooms in the slides (slides18.pdf reachable from the course page), what are all the conclusions can we draw (nonmonotonically) about a bolete (if this is all we know about it)? Indicate what edges are preempted by the Triangle Rule in drawing the inferences, Similarly, what conclusions can be drawn about an amanita, and what edges are preempted in making the inferences?

5. (Default logic) People in general -- if we have no reason to believe otherwise -- are not sociopaths. Despots in general -- if we have no reason to believe otherwise -- are sociopaths. Friends of sociopaths in general -- if we have no reason to believe otherwise -- are themselves sociopaths. A certain person A is a friend of B, who is a despot. a. Express these premises using FOL and normal default rules as appropriate. b. Give a default proof that person A is a sociopath, and another default proof that A is not a sociopath. c. Why (intuitively) don't your rules allow derivation of a contradiction? d. Which proof should we prefer, and why (in terms of your own intuitions)?

6. a. Consider a hypothesis H, for which we have separate evidence items E1 and E2. What conditional independence assumption is needed in order for the odds-likelihood-ratio update formula O(H|E1,E2) = O(H)L(E1)L(E2) to be precisely correct?

b. In part (a), once we've computed O(H|E1,E2), how do we obtain Pr(H|E1,E2)?

c. For the Bayesian network shown, write down the formula for the joint probability distribution Pr(X=x,Y=y,Z=z) for the three boolean variables X, Y, Z: X Note: edges are directed downward / | Y | \ | Z

7. Neural network-based inference.

a. (This is related to a simple example discussed in class Nov. 16) Consider a simple perceptron with two boolean (0/1) inputs x, y, whose output "fires" (= 1) if and only if the linear combination of its two inputs is greater than 0, i.e., a.x + b.y + c > 0, where a, b, c are the weights and bias applied to the inputs. It turns out that no choice of a, b, c will cause this perceptron to fire if and only if x and y are the same, i.e., if & only if x <=> y (i.e., x, y are both 0 or both 1). This is a basic limitation of combining inputs linearly. Suppose that we allow a quadratic function f(x,y) instead of a.x + b.y + c, i.e., one allowing products of x and y (and also their squares, but squaring 0 or 1 doesn't change them!). Construct such a quadratic f(x,y) so that f(x,y) > 0 just in case x <=> y.

b. What technical method (show the relevant product explicitly) did Socher and Manning use in their "tensor"-based method of inferring relations such as (Pablo Picasso, nationality, Spain), to allow for quadratic interactions between input components (here, the encoded version of "Pablo Picasso" and the encoded version of "Spain")? How does this product allow for quadratic interactions? c. In the REFLEX system of Kassner et al., we might find any of the foll- owing configurations of statements S1, S2, S3 in a constraint network:

[S1:F] [S1:F] [S1:T] [S2:T] xor r1 r2 [S2:T] [S2:F] [S3:F] The T/F values indicated are the truth value judgements of the LLM; r1, r2 are rule names. Which of these configurations would be judged inconsistent, when the algorithm for resolving inconsistencies is applied? Why or why not?

And which statement, in each configuration, might have its truth value "flipped" because of the inconsistency (if there is one)?

- Please answer all the questions/parts as all are part of one single assignment and I cannot ask them in parts.