  We establish a lower bound of $2^n$ conditional branches for deciding the
satisfiability of the conjunction of any two Boolean formulas from a set called
a full representation of Boolean functions of $n$ variables - a set containing
a Boolean formula to represent each Boolean function of $n$ variables. The
contradiction proof first assumes that there exists a Post machine (Post's
Formulation 1) that correctly decides the satisfiability of the conjunction of
any two Boolean formulas from such a set by following an execution path that
includes fewer than $2^n$ conditional branches. By using multiple runs of this
Post machine, with one run for each Boolean function of $n$ variables, the
proof derives a contradiction by showing that this Post machine is unable to
correctly decide the satisfiability of the conjunction of at least one pair of
Boolean formulas from a full representation of $n$-variable Boolean functions
if the machine executes fewer than $2^n$ conditional branches. This lower bound
of $2^n$ conditional branches holds for any full representation of Boolean
functions of $n$ variables, even if a full representation consists solely of
minimized Boolean formulas derived by a Boolean minimization method. We discuss
why the lower bound fails to hold for satisfiability of certain restricted
formulas, such as 2CNF satisfiability, XOR-SAT, and HORN-SAT. We also relate
the lower bound to 3CNF satisfiability. The lower bound does not depend on
sequentiality of access to the boxes in the symbol space and will hold even if
a machine is capable of non-sequential access.
