Show that TAUTOLOGY ∈ co-NP

Today I am going to attempt solving the following problem:

Let φ be a boolean formula constructed from:
- the boolean input variables x1, x2, ..., xk
- negations (¬)
-ANDs (∧)
-ORs (∨)
-and Parenthesis
The φ formula is a tautology if it evaluates to 1 for every assignment of 1and 0 to the input variables.
Define TAUTOLOGY as the language of boolean formulas that are tautologies.
Show that TAUTOLOGY ∈ co-NP.
----------------------------

Solution:
Since co-NP is the set of languages L such that L-compliment ∈ NP, then if we show that TAUTOLOGY-compliment ∈ NP, then that constitutes proof that TAUTOLOGY ∈ co-NP.
Let's do that then.

Define notTAUTOLOGY = TAUTOLOGY-compliment.

By definition we have that a language L belongs to NP if and only if there exists a two-input polynomial-time algorithm A and a constant c such that
L = {x ∈{0, 1}* : there exists a certificate y with |y| = O(|x|^c) such that A(x, y) = 1}.

Knowing that, let's observe that for each formula x, to determine if x ∈ notTAUTOLOGY we need to try (in the worst case) all different combinations of 0 and 1 assignments to the input variables until we discover one assignment that evaluates to FALSE. Hence to determine if a give formula x belongs to notTAUTOLOGY, we have to use a certificate y of length |y| of at most O(k*(2^k)) for an algorithm A to check for all possible combinations of 0 and 1 for all k input variables of x.
Hence no certificate y with |y| = O(|x|^c) with c constant can be found for an algorithm A(x, y) to check for acceptance of x. Therefore notTAUTOLOGY ∈ NP and so TAUTOLOGY ∈ co-NP.
QED?