CS161 Theorems Questions and Answers | New One | Grade A+

Refutation Theorem Ans: ∆╞ α iff ∆^¬α is inconsistent. Modus Ponens Ans: If the knowledge base contains α and α⇒β, then add β to the knowledge base. Modus Tollens Ans: If knowledge base contains α⇒β and ¬β, then add ¬α to knowledge base. ∆╞ α Ans: ∆ entails α, M(∆) is a subset of M(α), therefore α logically follows from ∆. Decomposable Ans: If α ^ β appears in NNF, then vars(α)∩vars(β)=∅. Basically, α and β shouldn't share variables. DNNF means "Decomposable NNF". Deterministic Ans: If α v β appears in NNF, then α ^ β is inconsistent. (ex. NNF (AvB)^C is not deterministic.) Smooth Ans: A circuit is smooth if and only if its disjuncts mention the same set of variables for every disjunction. Mutually Exclusive Ans: α,β are "mutually exclusive" iff Mods(α)∩Mods(β) = ∅. Universal Ans: Any sentence can be converted to that form. CNF, DNF, NNF are universal. Horn CNF is not. SAT