CS264A: Automated Reasoning
Fall 2023 Homework 3
Due Date: Monday, Nov 27
(a) (b) (c) Figure 1: Vtrees over variables A, B, C.
1. [12pts]Considerthefunctionf=(¬A∨¬B∨C)∧(B∨¬C).
(6pt) What is the compressed (X, Y)-partition of function f, where X = {A, B} and Y = {C}?
(3pt) To construct an SDD using the (X, Y)-partition that you derived in the previous ques- tion, which of the vtrees in Figure 1 should be used?
(3pt) Which vtrees in Figure 1 will lead to an SDD that corresponds to an OBDD? 2. [16pts]Considerthefollowingfunctionf=(A∧B)∨(B∧C)∨(C∧D).
(8pt) Construct the compressed (X,Y)-partitions for f and ¬f, where X = {A,C} and Y = {B,D}.
(8pt) Derive a general rule for finding an (X, Y)–partition for any function ¬f from an (X, Y)- partition of function f.
Figure 2: A vtree over variables A, B, C, D.
3. [14pts]ConstructanSDDforthefunctionf =(A∧¬B)∨(¬B∧C)∨(C∧D)basedonthe
vtree in Figure 2.
4. [12 pts] Consider a structured space which corresponds to selecting k or more items from a set of n items, where n ≥ 1 and 0 ≤ k ≤ n. A Boolean formula ∆ captures this space iff there is a one-to-one correspondence between the possible selections and the satisfying assignments of ∆. Suppose we use the Boolean variable Ai to indicate whether item i is selected.
Programming Help
(4pt) Describe a CNF that captures this structured space. How many clauses does the CNF have in terms of n and k.
(4pt) Describe a DNF that captures this structured space. How many terms does the DNF have in terms of n and k.
(4pt) Can you capture this structured space more efficiently using an OBDD? If so, describe the OBDD and its size in terms of n and k.
5. [12 pts] Consider the CNF:
∆ = (¬A ∨ B ∨ ¬C) ∧ (¬A ∨ B ∨ C) ∧ (A ∨ ¬B ∨ ¬C) ∧ (A ∨ ¬B ∨ C) ∧ (A ∨ B ∨ C).
(8pt) List the prime implicates of ∆. (4pt) List the prime implicants of ¬∆.
Figure 3: An OBDD representing a classifier.
6. [14 pts] Consider a model that predicts a movie’s box success based on four binary features, S (Original Screenplay), G (Great Cinematography), F (Famous Cast), and M (Marketing). The OBDD in Figure 3 describes the classification function, i.e. a feature configuration is evaluated to 1 iff the corresponding movie is predicted to be a success. Please answer the following explanation queries on the OBDD.
(4pt) Prime Implicant Explanation: Consider a movie that is an original screenplay and has poor cinematography, a famous cast, and good marketing {S = 1, G = 0, F = 1, M = 1}. Identify a smallest set of features α that renders the remaining features β irrelevant to the decision on this instance. That is, if we fix features α to their current values, we can change the values of features β arbitrarily without changing the current decision.
(4pt) Complete Reason: The class formula for the positive class is [G∧(¬S ∨F)]∨(F ∧M)∨[(¬S ∨G)∧(F ∨M)].
Compute the complete reason for the decision on instance I = {S = 0,G = 1,F = 0, M = 1}.
(6pt) Sufficient and Necessary Reasons: Compute the sufficient reasons and necessary reasons for this decision. That is, compute the prime implicants and prime implicates of the complete reason.
Programming Help, Add QQ: 749389476
Figure 4: A system.
7. [20 pts] Consider the system in Figure 4 and suppose the health of gates X, Y and Z are
represented by variables okX, okY and okZ. (5pt) Write the system description as a CNF.
Suppose the system input is A = 1, B = 0 and the system output is E = 0. Answer the following questions under this system observation.
(8pt) Construct the health condition for the system using directed resolution. (4pt) List the kernel diagnoses.
(3pt) List the minimal-cardinality diagnoses.
CS Help, Email: tutorcs@163.com