Propositional logic derived as a special case of probability calculus

$\def\sa{a} \def\sb{b} \def\sc{c} \def\sd{d} \def\se{e} \def\sf{f} \def\sg{g} \def\sh{h} \def\si{i} \def\sj{j} \def\sk{k} \def\sl{l} \def\sm{m} \def\sn{n} \def\so{o} \def\sp{p} \def\sq{q} \def\sr{r} \def\ss{s} \def\st{t} \def\su{u} \def\sv{v} \def\sw{w} \def\sx{x} \def\sy{y} \def\sz{z} \def\va{\vec{a}} \def\vb{\vec{b}} \def\vc{\vec{c}} \def\vd{\vec{d}} \def\ve{\vec{e}} \def\vf{\vec{f}} \def\vg{\vec{g}} \def\vh{\vec{h}} \def\vi{\vec{i}} \def\vj{\vec{j}} \def\vk{\vec{k}} \def\vl{\vec{l}} \def\vm{\vec{m}} \def\vn{\vec{n}} \def\vo{\vec{o}} \def\vp{\vec{p}} \def\vq{\vec{q}} \def\vr{\vec{r}} \def\vs{\vec{s}} \def\vt{\vec{t}} \def\vu{\vec{u}} \def\vv{\vec{v}} \def\vw{\vec{w}} \def\vx{\vec{x}} \def\vy{\vec{y}} \def\vz{\vec{z}} \def\ga{\mathfrak{A}} \def\gb{\mathfrak{B}} \def\gc{\mathfrak{C}} \def\gd{\mathfrak{D}} \def\ge{\mathfrak{E}} \def\gf{\mathfrak{F}} \def\gg{\mathfrak{G}} \def\gh{\mathfrak{H}} \def\gi{\mathfrak{I}} \def\gj{\mathfrak{J}} \def\gk{\mathfrak{K}} \def\gl{\mathfrak{L}} \def\gm{\mathfrak{M}} \def\gn{\mathfrak{N}} \def\go{\mathfrak{O}} \def\gp{\mathfrak{P}} \def\gq{\mathfrak{Q}} \def\gr{\mathfrak{R}} \def\gs{\mathfrak{S}} \def\gt{\mathfrak{T}} \def\gu{\mathfrak{U}} \def\gv{\mathfrak{V}} \def\gw{\mathfrak{W}} \def\gx{\mathfrak{X}} \def\gy{\mathfrak{Y}} \def\gz{\mathfrak{Z}} \def\ra{A} \def\rb{B} \def\rc{C} \def\rd{D} \def\re{E} \def\rf{F} \def\rg{G} \def\rh{H} \def\ri{I} \def\rj{J} \def\rk{K} \def\rl{L} \def\rm{M} \def\rn{N} \def\ro{O} \def\rp{P} \def\rq{Q} \def\rr{R} \def\rs{S} \def\rt{T} \def\ru{U} \def\rv{V} \def\rw{W} \def\rx{X} \def\ry{Y} \def\rz{Z} \def\rva{\vec{A}} \def\rvb{\vec{B}} \def\rvc{\vec{C}} \def\rvd{\vec{D}} \def\rve{\vec{E}} \def\rvf{\vec{F}} \def\rvg{\vec{G}} \def\rvh{\vec{H}} \def\rvi{\vec{I}} \def\rvj{\vec{J}} \def\rvk{\vec{K}} \def\rvl{\vec{L}} \def\rvm{\vec{M}} \def\rvn{\vec{N}} \def\rvo{\vec{O}} \def\rvp{\vec{P}} \def\rvq{\vec{Q}} \def\rvr{\vec{R}} \def\rvs{\vec{S}} \def\rvt{\vec{T}} \def\rvu{\vec{U}} \def\rvv{\vec{V}} \def\rvw{\vec{W}} \def\rvx{\vec{X}} \def\rvy{\vec{Y}} \def\rvz{\vec{Z}} \def\seta{A} \def\setb{B} \def\setc{C} \def\setd{D} \def\sete{E} \def\setf{F} \def\setg{G} \def\seth{H} \def\seti{I} \def\setj{J} \def\setk{K} \def\setl{L} \def\setm{M} \def\setn{N} \def\seto{O} \def\setp{P} \def\setq{Q} \def\setr{R} \def\sets{S} \def\sett{T} \def\setu{U} \def\setv{V} \def\setw{W} \def\setx{X} \def\sety{Y} \def\setz{Z} \def\fa{a} \def\fb{b} \def\fc{c} \def\fd{d} \def\fe{e} \def\ff{f} \def\fg{g} \def\fh{h} \def\fi{i} \def\fj{j} \def\fk{k} \def\fl{l} \def\fm{m} \def\fn{n} \def\fo{o} \def\fp{p} \def\fq{q} \def\fr{r} \def\fs{s} \def\ft{t} \def\fu{u} \def\fv{v} \def\fw{w} \def\fx{x} \def\fy{y} \def\fz{z} \def\fA{A} \def\fB{B} \def\fC{C} \def\fD{D} \def\fE{E} \def\fF{F} \def\fG{G} \def\fH{H} \def\fI{I} \def\fJ{J} \def\fK{K} \def\fL{L} \def\fM{M} \def\fN{N} \def\fO{O} \def\fP{P} \def\fQ{Q} \def\fR{R} \def\fS{S} \def\fT{T} \def\fU{U} \def\fV{V} \def\fW{W} \def\fX{X} \def\fY{Y} \def\fZ{Z} \def\ma{A} \def\mb{B} \def\mc{C} \def\md{D} \def\me{E} \def\mf{F} \def\mg{G} \def\mh{H} \def\mi{I} \def\mj{J} \def\mk{K} \def\ml{L} \def\mm{M} \def\mn{N} \def\mo{O} \def\mp{P} \def\mq{Q} \def\mr{R} \def\ms{S} \def\mt{T} \def\matu{U} \def\mv{V} \def\mw{W} \def\mx{X} \def\my{Y} \def\mz{Z} \def\loss{\mathcal{L}} \newcommand{\dkl}[2]{D_{\text{KL}}\mathopen{}\paren{#1\,||\,#2}} \newcommand{\dataset}{S} \newcommand{\ndataset}{N} \newcommand{\idataset}{n} \newcommand{\inputRV}{\mathcal{X}} \newcommand{\inputvec}{\vec{x}} \newcommand{\ninputvec}[1]{\vec{x}_{#1}} \newcommand{\iinputvec}[1]{x_{#1}} \newcommand{\niinputvec}[2]{x_{#1, #2}} \newcommand{\icpnt}{i} \newcommand{\inputmatrix}{X} \newcommand{\inputdim}{D} \newcommand{\outputval}{y} \newcommand{\ioutputval}[1]{y_{#1}} \newcommand{\outputvec}{\vec{y}} \newcommand{\trainset}{S_{\text{train}}} \newcommand{\testset}{S_{\text{test}}} \newcommand{\truemodel}{f_{\text{true}}} \newcommand{\trainedmodel}{f_{\trainset}} \newcommand{\linmodel}[1]{f_{#1}} \newcommand{\bestmodel}{f^{*}} \newcommand{\model}{f} \newcommand{\hyperparam}{\lambda} \newcommand{\linparamv}{\vec{w}} \newcommand{\ilinparam}[1]{w_{#1}} \newcommand{\indivloss}{l} \newcommand{\modelclass}{\mathcal{F}} \newcommand{\linclass}{\modelclass_{\text{lin}}} \newcommand{\g}{\mathcal{G}} \newcommand{\gmse}{\g_{\text{MSE}}} \newcommand{\glasso}{\g_{\text{lasso}}} \newcommand{\gridge}{\g_{\text{ridge}}} \newcommand{\glogit}{\g_{\logit}} \newcommand{\l}{\mathcal{L}} \newcommand{\lmse}{\l_{\text{MSE}}} \newcommand{\lmae}{\l_{\text{MAE}}} \newcommand{\llasso}{\l_{\text{lasso}}} \newcommand{\lridge}{\l_{\text{ridge}}} \newcommand{\llogit}{\l_{\logit}} \newcommand{\logit}{\sigma} \newcommand{\reg}{\mathcal{R}} \DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax} \DeclareMathOperator*{\mean}{mean} \DeclareMathOperator*{\avg}{avg} \DeclareMathOperator*{\span}{span} \DeclareMathOperator*{\var}{var} \DeclareMathOperator*{\bias}{bias} \newcommand{\expectation}{\mathbb{E}} \newcommand{\brak}[1]{\left[#1\right]} \newcommand{\paren}[1]{\left(#1\right)} \newcommand{\realset}{\mathbb{R}} \newcommand{\realvset}[1]{\realset^{#1}} \newcommand{\prob}{\mathbb{P}} \newcommand{\gaussian}{\mathcal{N}} \newcommand{\iid}{\stackrel{\text{i.i.d.}}{\sim}} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newcommand{\normtwo}[1]{\norm{#1}_{2}} \newcommand{\normone}[1]{\norm{#1}_{1}} \newcommand{\card}[1]{\left\lvert#1\right\rvert} \newcommand{\grad}{\nabla} \newcommand{\dconv}{\stackrel{d}{\to}} \newcommand{\pconv}{\stackrel{p}{\to}} \newcommand{\rva}[1]{#1} \newcommand{\rve}[1]{\vec{#1}} \newcommand{\obs}[1]{#1} \newcommand{\vobs}[1]{\vec{#1}} \newcommand{\distrib}[1]{#1} \newcommand{\distribof}[2]{#1_{#2}} \newcommand{\density}[1]{#1} \newcommand{\densityof}[2]{#1_{#2}} \newcommand{\distributed}{\sim} \newcommand{\const}[1]{#1} \newcommand{\fun}[1]{#1}$

In this article, I will apply the rules of probability calculus to derive the rules of propositional logic (also called propositional calculus).

This article is very formal and equation oriented. The goal is to show that bayesian thinking through probability calculus is fully compatible with propositional logic. This article contributes to a bigger purpose since I will show in an upcoming article how probability calculus explains inferences that can’t be made using propositional logic. In particular, if we know that $A$ is a cause of $B$ , written $A \Rightarrow B$ , then knowing that $B$ is true in propositional logic doesn’t tell us anything about $A$ . But the next article will show that probability calculus gives us more information about $A$ . Before we explore those extensions, let’s review our basics in the light of the new formalism.

Notations: given two propositions $A$ and $B$ , we use the following notations.

Notation	meaning
$A + B$	$A$ or $B$
$AB$	$A$ and $B$
$\bar{A}$	not $A$
$A \Rightarrow B$	$A$ implies $B$

Since our focus is primarily on inference, let’s use probability calculus to derive the following rules of propositional calculus:

$\begin{align} A \Rightarrow B &\equiv \bar{A} + B \\ A \Rightarrow B &\equiv \bar{B} \Rightarrow \bar{A} \end{align}$

We can take an example to illustrate those rules:

$A \Rightarrow B$ :	If it rain tomorrow then I will go to the cinema;
$\bar{A} + B$ :	Either it doesn’t rain tomorrow or you can be sure I’ll go to the cinema;
$\bar{B} \Rightarrow \bar{A}$ :	If I don’t go to the cinema tomorrow, this means it’s not raining outside.

Before we dive in, let’s recall the rules of probability calculus.

Probability calculus primer

Let $A$ and $B$ be two propositions and $e$ (as in “evidence”) a set of propositions. We note $p(A \mid e)$ our probability estimate for the truth of $A$ given evidence $e$ and we note $p_e(\cdot) = p(\cdot \mid e)$ .

The following rules hold:

negation:	$p_e(\bar{A}) = 1 - p_e(A)$
sum rule:	$p_e(AB) = p_e(A \mid B)\, p_e(B)$
product rule:	$p_e(A + B) = p_e(A) + p_e(B) - p_e(AB)$

If $H_1, ..., H_n$ is a collection of $n$ propositions that are exhaustive (at least one of them is true) and incompatible (no two of them can be true at the same time), then we have for all proposition $A$ :

exhaustivity:	$p_e(H_1 + ... + H_n) = 1$
partition rule:	$p_e(A) = p_e(AH_1) + ... + p_e(AH_n)$

In particular, $A$ and $\bar{A}$ satisfy these properties:

exhaustivity:	$p_e(A + \bar{A}) = p_e(A) + p_e(\bar{A}) = 1$
binary partition rule:	$p_e(A) = p_e(AB) + p_e(A\bar{B})$

If you want to know more about the how these rules were constructed, check out this article: Probability calculus: the logic of uncertainty.

Now that we are all setup, let’s tackle propositional logic.

$A \Rightarrow B \equiv \bar{A} + B$

Let $e$ = “ $A \Rightarrow B$ ”
By definition of $e$ , we have: $p_e(B \mid A) = 1$
We want to show that: $p_e(\bar{A} + B) = 1$

Use the binary partition rule:

$\begin{align} p_e(B) &= p_e(BA) + p_e(B\bar{A}) \\ &= p_e(B \mid A)\,p_e(A) + p_e(B\bar{A}) \\ &= p_e(A) + p_e(B \bar{A}) \end{align}$

Hence:

$\begin{align} p_e(\bar{A} + B) &= p_e(\bar{A}) + \color{blue}{p_e(B)} - p_e(\bar{A}B) \\ &= p_e(\bar{A}) + \color{blue}{p_e(A) + p_e(B\bar{A})} - p_e(\bar{A}B) \\ &= p_e(\bar{A}) + p_e(A) \\ &= 1 \end{align}$

Which achieves the proof that give $A \Rightarrow B$ , we have $\bar{A} + B$ . Let’s prove the other direction.

Let $e$ = “ $\bar{A} + B$ is true”
As shown before, $p_e(B) = p_e(B \mid A)\,p_e(A) + p_e(\bar{B}A)$

So, on the one hand we have:

$\begin{align} p_e(\bar{A} + B) &= p_e(\bar{A}) + \color{blue}{p_e(B)} - p_e(\bar{B}A) \\ &= p_e(\bar{A}) + \color{blue}{p_e(B \mid A)\,p_e(A) + p_e(\bar{B}A)} - p_e(\bar{B}A) \\ &= p_e(\bar{A}) + p_e(B \mid A)\,p_e(A) \\ \end{align}$

And on the other hand we have:

$\begin{align} p_e(\bar{A} + B) &= 1 \\ p_e(A) + p_e(\bar{A}) &= 1 \\ \end{align}$

Therefore:

$\begin{align} p_e(A) + p_e(\bar{A}) &= p_e(\bar{A} + B) \\ &= p_e(\bar{A}) + p_e(B \mid A)\,p_e(A) \\ p_e(A) &= p_e(B \mid A)\,p_e(A) \\ 1 &= p_e(B \mid A) \end{align}$

Which is what had to be proved. Let’s turn to our second proof.

$A \Rightarrow B \equiv \bar{B} \Rightarrow \bar{A}$

Let $e$ = “ $A \Rightarrow B$ ”	so that $p_e(B \mid A) = 1$
We want to prove that:	$p_e(\bar{A} \mid \bar{B}) = 1$
We know from the previous section that:	$p_e(\bar{A}+B) = 1$
This means that:	$\color{blue}{p_e(A\bar{B})} = 1 - 1 = 0$
Since:	$p_e(\bar{B}) = \color{blue}{p_e(A\bar{B})} + p_e(\bar{A}\bar{B})$
We have:	$p_e(\bar{B}) = \color{blue}{0} + p_e(\bar{A}\bar{B})$
Also written:	$p_e(\bar{B}) = p_e(\bar{A} \mid \bar{B})\,p_e(\bar{B})$
And thus:	$p_e(\bar{A} \mid \bar{B}) = 1$

We can obtain the opposite direction by replacing $A$ with $\bar{A}$ and $B$ with $\bar{A}$ .

Did you ever notice that most people think the rule $A \Rightarrow B$ also means $B \Rightarrow A$ ? Probability calculus explains why by showing us that if we know $B,$ then the probability of $A$ increases.

Read my next article to find out: Why bayesian inference is more powerful than logic

Propositional logic derived as a special case of probability calculus

Probability calculus primer

A⇒B≡ˉA+BA \Rightarrow B \equiv \bar{A} + B

A⇒B≡ˉB⇒ˉAA \Rightarrow B \equiv \bar{B} \Rightarrow \bar{A}

$A \Rightarrow B \equiv \bar{A} + B$

$A \Rightarrow B \equiv \bar{B} \Rightarrow \bar{A}$