21 Introduction to Computers and Programming Prof. I. K. Lundqvist Recitation 5 May 13 2004 Logic in proofs Rule of Inference Tautology Name p ∴ p ∨ q p → (p ∨ q) Addition p ∧ q (p ∧ q) → p Simplification ∴ p p, q (p ∧ q) → p ∧ q Conjunction ∴ p ∧ q p, p → q ∴ q (p ∧ (p → q)) → q Modus Ponens ¬q, p → q ∴ ¬p (¬q ∧ (p → q)) → ¬p Modus Tollens p → q, q → r ∴ p → r ((p → q) ∧ (q → r)) → (p → r) Hypothetical Syllogism p ∨ q, ¬p ∴ q ((p ∨ q) ∧ ¬p) → q Disjunctive Syllogism p ∨ q, ¬p ∨ r ∴ q ∨ r (p ∨ q) ∧ (¬p ∨ r) → q ∨ r Resolution3 Rules of Inference p p ∨ q p ∧ q p p ∴ p ∨ q p ∧ q ∴ p 4 Rules of Inference p q will loose p ∧ q p q ∴ p ∧ q •Addition – RedSox will win – RedSox or the Mets will win • Simplification – RedSox will win and The Yankees will not – RedSox will win • Conjunction – RedSox will win – The Yankees will loose – The RedSox will win and the Yankees5 Rules of Inference (R v S) Æ W (R v S) W p Æ q p ∴ q 6 Rules of Inference (R v S) Æ W ¬ W ¬ (R v S) p Æ q ¬ q ∴¬p • Modus Ponens – If it is raining or snowing, the ground is wet – It is raining or snowing – The ground is wet •Modus Tollens – If it is raining or snowing, the ground is wet – The ground is not wet – It is not raining nor snowing7 Rules of Inference p Æ q q Æ r p Æ q q Æ r ∴ p Æ r 8 Rules of Inference p ∨ q ¬p q p ∨ q ¬ p ∴ q • Hypothetical syllogism – If it is raining, the ground is wet – If the ground is wet, use an umbrella – If it is raining, use an umbrella • Disjunctive syllogism – It is either snowing or raining – It is not snowing – It is raining9 Rules of Inference P v Q ¬Q v R) p ∨ q ¬ p ∨ r ∴ q ∨ r 10 Rules of Inference P Æ R Q Æ S R v S p ∨ q p Æ r q Æ s ∴ r ∨ s •Resolution – It is snowing or raining – It is not snowing or hale Pv R – It is raining or hale • Constructive dilemma – Either RedSox or Yankees will win P v Q – If RedSox wins, then Boston goes wild – If Yankees wins, then NYC goes wild – Boston or NYC goes wild11 Example ∨ Q) Æ R] ∧ [R Æ (S Æ T)] ∧ [P ∧ S] Æ T ∧ B) ∨¬C] ∧ [(A ∧ B) Æ D] ∧ [E ∨¬D] ∧¬E Æ ¬C ¬I ∧ J) Æ K] ∧ [¬L Æ J] ∧ [¬L ∧¬I] Æ K ∨ M 12 Simple Exception Handling function Tan (X : Float )return Float is beginreturn Sin(X) / Cos(X);exceptionwhen Numeric_Error => if (Sin(X)>=0.0 and Cos(X)>= 0.0) or (Sin(X)< 0.0 and Cos(X)<= 0.0) then return Float'Last;else return -Float'Last; ;end Tan; •Prove that – [(P –[(A –[(end if13 Exception Handling procedure Safe_Get_Float(Out_Float : out Float;Min, Max : in Float ) is Local_Float : Float;Good_One : Boolean := False; beginwhile not Good_One loopbeginPut("Enter a float in range ");Put( Min, Exp => 0 );Put( " to ");Put( Max, Exp => 0 );Put( " ");Get( Local_Float ); Good_One:=((Local_Float>=Min) and (Local_Float<=Max)); if not Good_One then raise Data_Error; end if; exceptionwhen Data_Error => Put_Line("DATA ERROR. Invalid );new_line;Skip_Line;end; end loop; Skip_Line; Out_Float := Local_Float; end Safe_Get_Float; Conventional Execution Exception 14 Exception Handling procedure Safe_Get_Float(Out_Float : out Float;Min, Max : in Float ) is Local_Float : Float;Good_One : Boolean := False; beginwhile not Good_One loopbeginPut("Enter a float in range ");Put( Min, Exp => 0 );Put( " to ");Put( Max, Exp => 0 );Put( " ");Get( Local_Float ); Good_One:=((Local_Float>=Min) and (Local_Float<=Max)); if not Good_One then raise My_Error; end if; exceptionwhen Data_Error => Put_Line("DATA ERROR. Invalid );new_line;Skip_Line;when My_Error =>Put_Line("MY ERROR. Invalid input,);new_line;skip_Line;raise My_Error; end; end loop; Skip_Line; Out_Float := Local_Float; end Safe_Get_Float; Conventional Execution Exception -- Safe_Get_Float -- this point can only be -- reached if the get -- did not raise the exception -- now tested against limits -- specified -- Loal_Float < Min OR -- Local_Float > Max input, pls try again "-- protected block of code -- this point can only be reached -- when valid value input -- export input value -- Safe_Get_Float -- this point can only be -- reached if the get -- did not raise the exception -- now tested against limits -- specified -- Loal_Float < Min OR -- Local_Float > Max input, pls try again "pls try again"-- protected block of code -- this point can only be -- reached when valid value input -- export input value15 Infix Evaluation operand stack operator stack operator stack top of operand stack 16 Binary Tree A binary tree is a tree that is 1. Empty 2. Has two children left, right which are themselves binary trees Prove that the height of a non-empty binary tree is at least ⎣lg(n)⎦, where n is the number of nodes in the tree. • Check if the parentheses are balanced • Parse the input string from left to right – If Input(I) is an operand, push it on – If Input(I) is an operator, push it on – If Input(I) = ‘)’ • Pop two elements from the operand stack • Pop the operator from the operator stack • Perform computation and Push result back onto • The value of the expression is now on17 Proof – ⎣lg(n)⎦ = ⎣lg(n)-1⎦ if n>2 and n odd height(Tree) >= ⎣lg(num_nodes)⎦ 18 Base Case (n=1), the theorem holds lg(1) = 0 •Given: – height = 1 + max (height of subtrees) •To prove: • For a tree with just the root node19 Inductive Step ≤ j < n • Prove that theorem holds for j = n Given that n>=2, the tree T can be split into L and TR Assume that both TL and TR have equal number of nodes. 20 Inductive Step ⎡(n-1)/2 ⎤ ≤ TL ≤ ⎣n-1⎦ Given that theorem holds for subtrees, Height (TL) ≥ lg ⎡(n-1)/2 ⎤ Æ Height(T) ≥⎣lg ⎡(n-1)/2 ⎤⎦+ 1 ≥⎣1+ lg ⎡(n-1)/2 ⎤⎦ ≥⎣ ⎡(n-1)/2 ⎤ )⎦ ≥⎣ ⎦ • Assume n >= 2, theorem holds for 1two subtrees Tlg (2lg
View Full Document
Unlocking...