A Probabilistic Boolean Logic and its Meaning

We introduce a novel probabilistic Boolean logic (pbl) in which the probabilistic disjunction, conjunction and negation operators, provide the “output ” expected of their deterministic counterparts, with a probability p. By design, this output can be incorrect with a probability (1 − p). In order to distinguish our approach to injecting probabilities into Boolean logic from past approaches, we introduce a semantic model based on the novel notion of event sets. To the best of our knowledge, event sets provide a novel meaning to truth when Boolean logic and probability are combined. Building on this, we continue to show that while several of the standard properties (or laws) of Boolean logic are preserved in pbl, we unearth some surprises by showing that the analogs of distributivity and associativity, are not preserved. In fact, the amount by which associativity is not preserved in pbl can be quantified as the degree of non-associativity ∆n which grows as Ω(n), where n is the length of the formula, and p = (1 − 1 nc). An obvious question is to ask whether pbl is essentially equivalent to a logic whose formulae are formed from deterministic operators, but where (some of) the inputs are random variables. We show that the latter approach to injecting probabilistic behavior is distinguishable semantically, and separable—since it is provably more expensive if energy consumption is the complexity measure—from an equivalent approach based on pbl. We show this difference to be true both in the combinational context of logic as well as in that of models of computation with state based on probabilistic automata. Our interest in pbl is motivated in large part, by an increasing need to model transistors, gates and circuits—the building blocks of very large scale integration (VLSI)—probabilistically as they approach nanometer sizes, creating a need to shift away from deterministic models and logics that have been successfully used in the past. 1