Attachment # 00012405 - Exam_2_Review.pptx
Exam_2_Review.pptx (87.58 KB)
Raw Preview of Attachment:
(refer to the detailed question and attachment below)
Exam 2 Review DisclaimerThis is a review, not an in-depth coverage of every topic and concept we have gone over. Please review your notes, the slides, the recitations, and the book to make sure you are not missing anything for the exam.You MUST prepare Lock Down Browser and Webcam for the Exam. Exam FormatMultiple choice questionsTrue/False questionsShort answer questions Notes SheetYou can bring 3 note sheets of paper but it must:Be at most 8.5”x 11”Have all notes written by handHave been created by your own handFailure to follow these rules may result in you receiving an undesirable grade on your exam plus other consequencesYou may write whatever you find helpful on your note sheetCalculator is allowed. You can print the Propositional Logic Rules. It will not be counted as a note sheet. NO MAKEUP EXAMTime：90 min November 9th anytime before the midnight Exam TopicsSlide Sets 05, 06, 07 TreesRooted vs free Node typesRoot, parent, child, sibling, internal, leaf, ancestor, descendantSub-treesHeight and Depth of a Tree/NodePaths: The length of a path is k-16 TreesTraversalsPreorderPostorderIn-orderLevel orderBinary TreesFull: Every node has either 0 or 2 childrenComplete: All levels must have the maximum number of nodes, except the last level. The last level must be filled from left to rightPerfect: All levels must have the maximum number of nodes7 Propositional LogicBasic propositionsCompound propositions∧, ∨, ¬, ⊕→, ↔Truth TablesLogical ReasoningHypotheses & ConclusionPredicates & Quantifiers∀, ∃Bound vs Free variables PracticeCartier does not make cheap watches. Cartier make cheap watches = c ¬cArizona has a national park but Nebraska does not. Arizona has a national park = A Nebraska has a national park = N A ∧ ¬NBoth Harvard and Baylor have medical schools. Harvard has medical school = H Baylor has medical school =B H ∧ BReese Witherspoon wins best actress only if Martin Scorsese wins best director. Martin wins best director = M Reese wins best actress = R M → R PracticeA ∧ (B → C) ∴ (B → (A ∧ C)) A ∧ (B → C) ∧ B ∴ (A ∧ C)A HypoB → C HypoB HypoC Modus Ponens 2,3A ∧ C Conjunction on 1, 4¬A ∧ B ∧ (B → (A ∨ C)) ∴ C¬A HypoB HypoB → (A ∨ C) HypoA ∨ C Modus Ponens 2, 3C Disjunctive Syllogism 1, 4 (¬A → ¬B) ∧ B ∧ (A → C) ∴ C Practice(¬A → ¬B) ∧ B ∧ (A → C) ∴ C¬A → ¬B HypoB HypoA → C HypoB → A Contraposition 1A Modus Ponens 2, 4C Modus Ponens 3, 5 PracticeB(x) x is a ballR(x) x is roundS(x) x is a soccer ballAll balls are round ∀x(B(x) -> R(x))Not all balls are soccer balls ¬∀x(B(x) -> S(x)) : It is not the case that all balls implies soccer balls ∃x(B(x) ∧ ¬S(x)): It must be exist that some balls are not soccer ballsSome balls are not round ∃x (B(x) ∧ ¬R(x)) Some balls are round, but soccer balls are not∃x (B(x) ∧ R(x)) ∧ ¬S(x))Every round ball is a soccer ball∀x((B(x) ∧ R(x)) -> S(x))Only soccer balls are round balls∀x (¬S(x) - > ¬ (B(x) ∧ R(x))) : If it is not a soccer ball, it is not a round ball Practice- Proofs with Quantifiers∃x(P(x) → Q(x)) ∴ (∀xP(x) →∃xQ(x))∃x(P(x) → Q(x)) ∧ ∀xP(x) ∴ ∃xQ(x) 1. ∃x(P(x) → Q(x)) Hypo 2. ∀xP(x) Hypo 3. P(a) → Q(a) ∧a is particular element Existential Instantiation 1 4. P(a) ∧a is particular element Universal Instantiation 2 5. a is particular element Simplification 3 6. P(a) → Q(a) Simplification 3 7. P(a) Simplification 4 8. Q(a) Modus Ponens 6,7 9. ∃xQ(x) Existential Generalization 5, 8 Practice- Proofs with Quantifiers∃xP(x) ∧ ∀x(P(x) → Q(x)) ∴ ∃xQ(x)1. ∀x(P(x) → Q(x)) Hypo 2. ∃xP(x) Hypo 3. P(a) → Q(a) ∧ a is particular element Universal Instantiation 1 4. P(a) ∧ a is particular element Existential Instantiation 2 5. a is particular element Simplification 3 6. P(a) → Q(a) Simplification 3 7. P(a) Simplification 4 8. Q(a) Modus Ponens 6,7 9. ∃xQ(x) Existential Generalization 5, 8 Practice- Proofs with Quantifiers∀xP(x) ∴ ∀x(P(x) ∨ Q(x)) 1. ∀xP(x) Hypo 2. P(a) ∧ a is arbitrary Universal Instantiation 1 3. P(a) Simplification 2 4. a is arbitrary Simplification 2 5. P(a) V Q(a) Addition 3 6. ∀x(P(x) ∨ Q(x)) Universal Generalization 4,5 Boolean LogicOperators•, +, Boolean Functionsf(x,y)Variables, Literals, Terms, Minterms, MaxtermsDNF vs CNF vs CDNF vs CCNFCompletenessBoolean Satisfiability I/O table to AlgebraI/O table to circuit(BA worksheet2, Q3)Truth Table(BA Worksheet 1, Q9)GatesANDORInverter(NOT)(BA worksheet2, Q2)
Whatsapp Lisa