Editing Monotonic function (section)

== In Boolean functions ==
{| style="float:right;"
| [[File:Hasse3 x impl y and z.svg|thumb|With the nonmonotonic function "if {{mvar|a}} then both {{mvar|b}} and {{mvar|c}}", {{color|#c00000|false}} nodes appear above {{color|#00c000|true}} nodes.]]
|}
{| style="float:right;"
| [[File:Hasse3 ge2.svg|thumb|Hasse diagram of the monotonic function "at least two of {{mvar|a}}, {{mvar|b}}, {{mvar|c}} hold". Colors indicate function output values.]]
|}
In [[Boolean algebra]], a monotonic function is one such that for all {{mvar|a<sub>''i''</sub>}} and {{mvar|b<sub>''i''</sub>}} in {{math|{0,1}<nowiki />}}, if {{math|''a''<sub>1</sub> ≤ ''b''<sub>1</sub>}}, {{math|''a''<sub>2</sub> ≤ ''b''<sub>2</sub>}}, ..., {{math|''a''<sub>''n''</sub> ≤ ''b''<sub>''n''</sub>}} (i.e. the Cartesian product {{math|{0, 1}<sup>n</sup>}} is ordered [[coordinatewise order|coordinatewise]]), then {{math|f(''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>) ≤ f(''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>)}}. In other words, a Boolean function is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. Graphically, this means that an {{mvar|n}}-ary Boolean function is monotonic when its representation as an [[hypercube|{{mvar|n}}-cube]] labelled with truth values has no upward edge from ''true'' to ''false''.  (This labelled [[Hasse diagram]] is the [[Duality (mathematics)#Dimension-reversing dualities|dual]] of the function's labelled [[Venn diagram]], which is the more common representation for {{math|''n'' ≤ 3}}.)

The monotonic Boolean functions are precisely those that can be defined by an expression combining the inputs (which may appear more than once) using only the operators ''[[logical conjunction|and]]'' and ''[[logical disjunction|or]]'' (in particular ''[[negation|not]]'' is forbidden). For instance "at least two of {{mvar|a}}, {{mvar|b}}, {{mvar|c}} hold" is a monotonic function of {{mvar|a}}, {{mvar|b}}, {{mvar|c}}, since it can be written for instance as (({{mvar|a}} and {{mvar|b}}) or ({{mvar|a}} and {{mvar|c}}) or ({{mvar|b}} and {{mvar|c}})).

The number of such functions on {{mvar|n}} variables is known as the [[Dedekind number]] of {{mvar|n}}.

[[SAT solving]], generally an [[NP-hard]] task, can be achieved efficiently when all involved functions and predicates are monotonic and Boolean.<ref>{{cite conference | doi=10.1609/aaai.v29i1.9755 | url=https://ojs.aaai.org/index.php/AAAI/article/view/9755 |first1=Sam |last1=Bayless |first2=Noah |last2=Bayless |first3=Holger H. |last3=Hoos |first4=Alan J. |last4=Hu | title=SAT Modulo Monotonic Theories | editor= | conference=Proc. 29th AAAI Conf. on Artificial Intelligence | publisher=AAAI Press | series= | volume= | pages=3702&ndash;3709 | year=2015 | doi-access=free | arxiv=1406.0043 |url-status=live |archive-url=https://web.archive.org/web/20231211023402/https://ojs.aaai.org/index.php/AAAI/article/view/9755 |archive-date= Dec 11, 2023 }} 
</ref>