Algorithm for idempotent algebra
Let us consider the following decision version of your first problem:


  Given a SAT instance, does its multilinear representation have a term of degree at most $d$?


I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones.

Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear representation of the instance. Substituting 1 for the variables in $m$ and 0 for the variables outside of $m$, we get 1, that is, that the instance is satisfied. This shows that if the multilinear representation has a term of degree at most $d$, then the instance has a satisfying assignment with at most $d$ ones.

Now suppose that all terms in the multilinear representation have degree more than $d$. If we substitute any assignment with at most $d$ ones, then all monomials equal 0, and so the assignment falsifies the instance.

Therefore the decision version is equivalent to MIN-ONES-SAT, which is the following problem:


  Given a SAT instance, does it have a satisfying assignment with at most $d$ ones?


The problem is in NP (it is easy to count the number of ones in a satisfying assignment), and it is clearly NP-hard (take $d = n$). Hence the problem is NP-complete.



Using an NP oracle, we can easily find a monomial with minimal degree, equivalently, a satisfying assignment with the least ones. Just substitute a 0 in one of the variables, and see if it increases the minimum weight of a solution. If so, set this variable to 1, otherwise set it to zero, and continue to the next variable. This answers your first question.