/* MINDFIRE BLOG */

Now we pull all those threads together and formally show that probability theory is an extension of propositional logic.

As a reminder, in earlier posts we built a sequence of ideas:

• Aristotle: The First AGI Researcher - We covered the long road from Aristotle to today to try to simulate human thinking that led to the creation of deductive logics. In that post we also included a primer on propositional logic, the basis for computation.

• The Atomization of Thought — We showed any boolean function can be built out of nothing more than AND and NOT operators by using 'minterms'. That is to say, AND + NOT are universal operators that can represent any other boolean operations or function of any complexity.

• One Logical Operator to Rule Them All — We showed that a single operator, NAND (or the pair NOT+AND together), is functionally complete: every propositional function can be built from them. It is a single universal boolean operator.

• From Certainty to Belief: How Probability Extends Logic - Part 1 and Part 2 — We introduced variables, marginals, conditional probability and Bayes’ Rule, and showed how probabilistic reasoning generalizes syllogistic logic as created by Aristotle.

Now we pull all those threads together and formally show that probability theory is an extension to propositional logic.

Because NOT and AND (or NAND) are enough to express any propositional formula, it is sufficient to show how to express NOT and AND in probability theory. Once we can do that, probability theory can represent every propositional logical function — with logical entailment appearing as probability = 1.

How to encode NOT and AND with probability

Encoding NOT and AND boolean operators into probability theory is remarkably easy. We treat logical statements as random variables taking values tr (true) or fa (false). Then we use probability constraints to encode logical facts.

NOT
Logical ¬A (not A) is encoded by the probabilistic constraint: p(A = tr) = 0.

But recall that for two mutually exclusive values for a random variable they must marginalise (sum) to 1. So if p(A = tr) = 0 then p(A = fa) = 1 - p(A = tr). Since p(A = tr) = 0, this means:

p(A = fa) = 1 - p(A = tr) = 1 - 0 = 1.

So p(A = fa) = 1. This forces A to be false in every model/distribution that satisfies the KB. This allows us to represent the NOT operator using the notation of probability theory.

AND
Logical A ∧ B (A and B) can be expressed in probability in a couple of very simple, equivalent ways — pick whichever feels more natural.

• Joint form (one statement): say the probability that both A and B are true is 1:
  p(A = tr, B = tr) = 1
  This literally means: in every scenario allowed by our assumptions, A and B are both true.

• Separate form (two statements): say A is true with certainty and B is true with certainty:
  p(A = tr) = 1 and p(B = tr) = 1
  Together these mean the same thing as the joint form — the only possible worlds left are those where A and B are both true.

Either way, you have encoded the logical AND using probabilities.

NAND (single-operator route)
NAND(A,B) is just NOT (A ∧ B). To say “A NAND B is true” you can rule out the assignment where both A and B are true:

• p(A = tr, B = tr) = 0

That says: the situation where both A and B are true has zero probability — it cannot happen. Since NAND is universal, you can use this single kind of constraint to build any Boolean function if you want to work from one operator only.

Tiny worked example — A ∧ ¬B

We want to encode the formula “A and not B”.

Two equivalent, simple encodings:

• Joint constraint: require the single assignment where A is true and B is false to be the only possibility:
  p(A = tr, B = fa) = 1
  Read plainly: the only allowed scenario is A true and B false — so the formula is true in every allowed scenario.

• Atom constraints: say A is certain and B is impossible:
  p(A = tr) = 1 and p(B = tr) = 0
  That also leaves only worlds where A is true and B is false, so again the formula is true in every allowed scenario.

Either approach works.

Logical connectives — Boolean version and probabilistic version

• NOT (¬)
  Boolean: If P is true, then ¬P is false; if P is false, then ¬P is true.
  Probability: encode ¬P by forcing P to be false:
  p(P = tr) = 0 (equivalently p(P = fa) = 1).

• AND (∧)
  Boolean: P ∧ Q is true only if both P and Q are true.
  Probability (joint form): require both to be true with certainty:
  p(P = tr, Q = tr) = 1.
  Probability (separate form): require each true with certainty:
  p(P = tr) = 1 and p(Q = tr) = 1 (together these imply the joint form).

• OR (∨)
  Boolean: P ∨ Q is true if at least one of P or Q is true.
  Probability (direct): require that at least one is true with certainty:
  p(P = tr or Q = tr) = 1 (read literally: the probability that P or Q is true equals 1).
  Probability (algebraic): using inclusion–exclusion:
  p(P = tr) + p(Q = tr) - p(P = tr, Q = tr) = 1.

• IMPLIES (→)
  Boolean: P → Q is false exactly when P is true and Q is false; otherwise it’s true.
  Probability (for implication-as-certainty): either of these equivalent encodings works:

  • Forbid the counterexample: p(P = tr, Q = fa) = 0.
  • Or express as a conditional: p(Q = tr | P = tr) = 1.
    (Both say: whenever P is true, Q must also be true. However, when using conditional form p(Q = tr | P = tr) = 1, this implicitly assumes p(P = tr) > 0; if p(P = tr) = 0 prefer the joint form p(P = tr, Q = fa) = 0.)

• EQUIVALENT (↔)
  Boolean: P ↔ Q is true only when P and Q share the same truth value (both true or both false).
  Probability (joint form): require that only the matching pairs are true:
  p(P = tr, Q = tr) + p(P = fa, Q = fa) = 1.
  Probability (conditional form): equivalently, require both directions as certain:
  p(P = tr | Q = tr) = 1 and p(P = tr | Q = fa) = 0.

Note that: - Saying p(...)=1 is the probabilistic way to say “this is certainly true” (the logical 1).
- Saying p(...)=0 is the probabilistic way to say “this cannot happen” (the logical 0).
- You can mix joint probabilities (e.g., p(P,Q)) and conditionals (e.g., p(Q | P)) — they are equivalent ways to express the same logical constraint.
- Once you can express NOT and AND this way, you can build OR, IMPLIES, EQUIV, and therefore any propositional formula, by combining the probabilistic encodings above.

Conclusion

As this post shows, probability theory can represent any boolean or propositional logical statement. Thus probability theory extends boolean and propositional logic. That is to say, it generalizes boolean and propositional logic — the 0/1 case of probability theory recovers ordinary logic.

But what about First Order logic? Also, is there a way to formally prove this?