Define a set of boolean formulas by: For each i N, the variable x; F. If...

  

Transcribed Image Text:

Define a set of boolean formulas by: For each i N, the "variable" x; F. If pe F then (-p) EF. If p, q E F then (p^q) EF and (pv q) EF. Nothing else is in F. Define T,N: F F by: . For each i EN, T(x;) = x; and N(x) = x;. If p E F then T((-p)) = N(p) and N((-p)) = T(p). If p, q E F then - T((p ^q)) = (T(p) ^ T(q)) - N((p ^q)) = (N(p) v N(q)) - T((pv q)) = (T(p) V T(q)) - N((p V q)) = (N(p) ^ N(q)) (a) Prove that for each p = F, T(p) is logically equivalent to p and has negation only on variables. Do that by Structural Induction on the definition of F, after first strengthening the claim to include a claim about function N. (b) Write a recursive Python function to compute T, but without writing any helper functions (in particular, don't define N). Use the following representation for boolean formulas: If x; is a variable the string "x_i" represents it, e.g., 'x_236' represents X236. If p and q represent boolean formulas then so does the 2-tuple ('', p) and so do the 3-tuples (p. 'A', q) and (p, 'V', q). State a natural-number measure of size for formulas, so that your recursive calls are always on formulas of smaller size, and put a comment before each recursive call explaining why it is on a formula of smaller size. Define a set of boolean formulas by: For each i N, the "variable" x; F. If pe F then (-p) EF. If p, q E F then (p^q) EF and (pv q) EF. Nothing else is in F. Define T,N: F F by: . For each i EN, T(x;) = x; and N(x) = x;. If p E F then T((-p)) = N(p) and N((-p)) = T(p). If p, q E F then - T((p ^q)) = (T(p) ^ T(q)) - N((p ^q)) = (N(p) v N(q)) - T((pv q)) = (T(p) V T(q)) - N((p V q)) = (N(p) ^ N(q)) (a) Prove that for each p = F, T(p) is logically equivalent to p and has negation only on variables. Do that by Structural Induction on the definition of F, after first strengthening the claim to include a claim about function N. (b) Write a recursive Python function to compute T, but without writing any helper functions (in particular, don't define N). Use the following representation for boolean formulas: If x; is a variable the string "x_i" represents it, e.g., 'x_236' represents X236. If p and q represent boolean formulas then so does the 2-tuple ('', p) and so do the 3-tuples (p. 'A', q) and (p, 'V', q). State a natural-number measure of size for formulas, so that your recursive calls are always on formulas of smaller size, and put a comment before each recursive call explaining why it is on a formula of smaller size.

Answer rating: 100% (QA)

a To prove that for each p F Tp is logically equivalent to p and has negation only on variables we will use structural induction on the definition of ... View the full answer