Let be a boolean formula constructed from the boolean input variables x 1 , x 2 , . . . ,x k , negations

Let Φ be a boolean formula constructed from the boolean input variables x₁, x₂, . . . ,x_k, negations (¬), ANDs (∧), ORs (∨), and parentheses. The formula Φ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables. Define TAUTOLOGY as the language of boolean formulas that are tautologies. Show that TAUTOLOGY ∈ co-NP.