Question 1. The rank of a formula is defined by recursion on formulas: • rk(A) = 0 for every basic formula. • rk(¬A) = rk(A) + 1. • rk(A o B) = max(rk(A), rk(B)) + 1 for o € {A, V}. %3D rk(A → B) =...

please send handwritten solution for Q 1

Extracted text: Question 1. The rank of a formula is defined by recursion on formulas: • rk(A) = 0 for every basic formula. • rk(¬A) = rk(A) + 1. • rk(A o B) = max(rk(A), rk(B)) + 1 for o € {A, V}. %3D rk(A → B) = max(rk(A) +1, rk(B)) Prove by induction on formulas that rk(A) < depth(a)="" for="" all="" formulas="">


Extracted text: Example of a function defined by recursion on formulas We define the depth of a formula as follows • depth(A) = 0 for every basic formula. depth(¬A) = depth(A) +1. depth(A o B) = max(depth(A), depth(B)) + 1 for ● E {A, V, →}. We also let con(A) be the number of occurrences of logical connectives (A, V, →, -) in the formula A. Lemma 2. con(A) < 2depth(4).="" proof.="" by="" induction="" on="" formulas.="" induction="" base:="" if="" a="" is="" a="" basic="" formula,="" then="" con(a)="0">< 1="2º" =="" 2depth(a).="" induction="" step:="" we="" have="" to="" consider="" composite="" formulas.="" ¬a:="" by="" induction="" hypothesis="" (i.h.)="" we="" have="" con(a)="">< 2depth(4).="" therefore="" con(¬a)="" con(a)="" +="" 1="" i.h.="">< 2depth(a)="" +="" 1="">< 2="" *="" 2depth(a)="" 2depth(4)+1="" 2depth(¬a)="" ao="" b="" where="" o="" €="" {a,="" v,→}:="" by="" induction="" hypothesis="" we="" have="" con(a)="">< 2depth(a)="" and="" con(b)="">< 2depth(b).="" con(a="" o="" b)="" con(a)="" +="" con(b)="" +="" 1="">< con(a)="" +1+="" con(b)="" +1="" i.h.="">< 2depth(a)="" +="" 2depth(b)="">< 2*="" 2max(depth(a),depth(b))="" 2depth(aob)="" this="" completes="" the="" proof.="">