A substitution S is a function from propositional variables to formulas. We apply a substitution to a formula p by simultaneously replacing each variable p in p by the formula S(p). Formally, we define S(p) by induction If is a propositional variable p, then S(g) is the formula S(p), or simply p if S(p) . is undefined If p is ), then S(p) is (S(n)). . If is (*) for a binary connective *, then S(p) is the formula (S() * S()). For example, if S(p)-(an r) and S(q)-(p V q) and S(r) is undefined, then Fix an arbitrary substitution S, and an arbitrary valuation t. Prove that there is a valuation u such that for every formula p, the value of p under u is the same as the value of S(p) under t: in symbols, pu-S(p). Use structural induction on . (Hint: your answer must specify how the valuation u depends on S and t. If you cannot see how to do that at first, try simply starting the proof without specifying u. Then ask yourself: what properties of u do you need in order to make the required arguments?) A substitution S is a function from propositional variables to formulas. We apply a substitution to a formula p by simultaneously replacing each variable p in p by the formula S(p). Formally, we define S(p) by induction If is a propositional variable p, then S(g) is the formula S(p), or simply p if S(p) . is undefined If p is ), then S(p) is (S(n)). . If is (*) for a binary connective *, then S(p) is the formula (S() * S()). For example, if S(p)-(an r) and S(q)-(p V q) and S(r) is undefined, then Fix an arbitrary substitution S, and an arbitrary valuation t. Prove that there is a valuation u such that for every formula p, the value of p under u is the same as the value of S(p) under t: in symbols, pu-S(p). Use structural induction on . (Hint: your answer must specify how the valuation u depends on S and t. If you cannot see how to do that at first, try simply starting the proof without specifying u. Then ask yourself: what properties of u do you need in order to make the required arguments?)