In this paper, a new class of Boolean networks, called Stochastic Boolean Networks, is presented. These systems combine some features of the classical deterministic Boolean networks (the state variables admit two operation levels, either 0 or 1) and of Probabilistic Boolean Networks (at each time instant the transition map is selected through a random process), enriching the set of admissible dynamical behaviors, thanks to the set-valued nature of the transition map. Necessary and sufficient Lyapunov conditions are given to guarantee global asymptotic stability (resp., global asymptotic stability in probability) of a given set for a deterministic Boolean network with set-valued transition map (resp., for a Stochastic Boolean Network). A constructive procedure to compute a Lyapunov function (resp., stochastic Lyapunov function) relative to a given set for a deterministic Boolean network with set-valued transition map (resp., Stochastic Boolean Network) is reported. (C) 2017 Elsevier Ltd. All rights reserved.