Given current data, only few binary Boolean operators are expressed in lexically simple fashion in the world’s languages: and, or, nor. These do not occur in every combination, for example, nor is not observed by itself. To explain these cross-linguistic patterns, we propose an encoding of Boolean operators as update procedures to accept or reject information in a context. We define a measure of conceptual simplicity for such updates, on which attested operators are conceptually simpler than the remaining Booleans. Moreover, we show that language evolution selects for the attested lexical inventories by minimizing the complexity of using a lexical inventory compositionally to convey precise information