Course Note - Propositional Logic - BN and inference UCLA Adnan Darwiche
by lucainiaoge
Intro
This is a fundamental course for those who wanna have a thorough understanding of Baysian Networks:
When studying the course, I was somehow confused partly because the lecture goes too fast. I have to frequently halt and comprehend the slides. Luckily, the slides are very well arranged.
Through the first several courses, we are lead to discover the mathematical essence of Baysian Networks (BN).
Prerequisites for this note
Knowing what sets are, knowing basic boolean logic, a mathematical mind
Purpose of this note
Set up the foundation of probability calculus.
Link logical calculation with set calculation.
Constructing Propositional Logic
Motivation: There will be a great deal of definitions. My understanding is that they are like fundations of the magnificent building of probibilistic inference for what we interpret as “events” are explained with the Propositional Logic.
Definition (propositional variable and sentence/event): a propositional variable $p$ is defined on a discrete set P;a sentence or an event $\alpha$ is an assignment of propositional variables. $\alpha$ can hold true or false
In other words,$(p=p_0)=\alpha \in \lbrace \pmb{true},\pmb{false} \rbrace$
In the following discussions, we take True as T and False as F.
e.g. propositional variable: B=”Burglery”, E=”Earthquake”, A=”Alarm”; a sentence: $\alpha$=(B=T,A=F)
When we have a lot of propositional variables, the combinitions of possible circumstances are exploding exponentially. To efficiently deal with that is one of our tasks.
First we have to define such possible circumstances with term “world”:
Definition (world): a world $w$ is an assignment for all propositional variables $p_i$.
We can treat worlds as smallest elements of the whole set $\Omega$.
e.g. $p_B$=”Burglery”, $p_E$=”Earthquake”, $p_A$=”Alarm”
$w_1=[(p_B,p_E,p_A)=(T,T,T)]$
$w_2=[(p_B,p_E,p_A)=(T,T,F)]$
$w_3=[(p_B,p_E,p_A)=(T,F,T)]$
$w_4=[(p_B,p_E,p_A)=(T,F,F)]$
$w_5=[(p_B,p_E,p_A)=(F,T,T)]$
$w_6=[(p_B,p_E,p_A)=(F,T,F)]$
$w_7=[(p_B,p_E,p_A)=(F,F,T)]$
$w_8=[(p_B,p_E,p_A)=(F,F,F)]$
$\Omega=\lbrace w_1,w_2,…,w_8 \rbrace$
Definition ($w \models \alpha$): a world $w$ holds true if a sentence $\alpha$ is true.
e.g. given sentences: $B=[p_B=T]$(means Burglery happens), $E=[p_E=T]$, $A=[p_A=T]$, $\neg B=[p_B=F]$ and so forth
Then, $w_1 \models B$, $w_5 \models \neg B$
Definition (model of sentence $\alpha$): $Mods(\alpha)=\lbrace w:w \models \alpha ,w\in \Omega \rbrace$
Model of a sentence is a set. It’s obvious that model of a sentence is unique and given a set of worlds there is a unique sentence whose model is the set.
e.g. $Mods(B)=\lbrace w_1,w_2,w_3,w_4 \rbrace$
Until now, we know that:
- We are studying Propasitional Variables which are discrete
- A sentence/event is a function for Propasitional Variable vectors (i.e. a value assignment). The function value domain is $\lbrace \pmb{true},\pmb{false} \rbrace$
- A world is a sentence considering all Propasitional Variables.
- Model of a sentence is a set whose elements are worlds that hold true when this sentence holds true.
Hope you are getting excited: we are linking the logic world of Ture or False with the world of sets. We can really define logical calculations.
Propositional Logic Calculation
Definition (Basic Propositional Logic Calculation): given sentence $\alpha$ and $\beta$
$\alpha \wedge \beta $ is such a sentence that $Mods(\alpha \wedge \beta)=Mods(\alpha)\cap Mods(\beta)$
$\alpha \vee \beta $ is such a sentence that $Mods(\alpha \wedge \beta)=Mods(\alpha)\cup Mods(\beta)$
$\neg \alpha $ is such a sentence that $Mods(\neg \alpha)=\Omega \setminus Mods(\alpha)$
You see? Your familiar logical calculation “and”,”or” and “not” is actually set calculation “intersection”,”union” and “complement”.
Definition (relationships of sentences): given sentence $\alpha$ and $\beta$
$\alpha$ is consistent or satisfiable $\Leftrightarrow$ $Mods(\alpha)\neq \emptyset$
$\alpha$ is valid $\Leftrightarrow$ $Mods(\alpha)= \Omega$ $\Leftrightarrow$ $\models \alpha$ $\Leftrightarrow$ $\alpha = True$
$\alpha$ and $\beta$ are equivalent $\Leftrightarrow$ $Mod(\alpha)=Mods(\beta)$
$\alpha$ and $\beta$ are mutually exclusive $\Leftrightarrow$ $Mods(\alpha)\cap Mods(\beta)=\emptyset$
$\alpha$ and $\beta$ are exhaustive $\Leftrightarrow$ $Mods(\alpha)\cup Mods(\beta)=\Omega$
$\alpha$ implies $\beta$ $\Leftrightarrow$ $Mods(\alpha)\subset Mods(\beta)$ $\Leftrightarrow$ $\alpha \models \beta$
I think those definitions are to remind people the importance of such relationships. Also helping people to communicate in a more logical manner…
A few more definitions of Propositional Logic calculation:
Definition (More Propositional Logic Calculation): given sentence $\alpha$ and $\beta$
$\alpha \rightarrow \beta $ $\Leftrightarrow$ $\neg \alpha \vee \beta$
$\alpha \leftrightarrow \beta $ $\Leftrightarrow$ $(\alpha \rightarrow \beta)\wedge (\beta \rightarrow \alpha)$
Worth noticing those definitions.
$\alpha \rightarrow \beta $ is in fact telling you that $\alpha$ implies $\beta$, or contraposition. $\alpha \rightarrow \beta = True$ means: whenever $\alpha$ is true, $\beta$ is true. So $Mods(\alpha)\subset Mods(\beta)$. (Think the worlds!)
$\alpha \leftrightarrow \beta $ is actually XNOR. $\alpha \leftrightarrow \beta = True$ means that $\alpha$ and $\beta$ are equivalent.
Several examples:
given sentences: $B=[p_B=T]$, $E=[p_E=T]$, $A=[p_A=T]$, $\neg B=[p_B=F]$ and so forth
$\alpha=(E \vee B)\rightarrow A$
$Mods(\alpha)=\lbrace w_1,w_3,w_5,w_7,w_8 \rbrace$
$\beta=(E \rightarrow B)$
$Mods(\beta)=\lbrace w_1,w_2,w_5,w_6,w_7,w_8 \rbrace$
then, $Mods(\alpha \wedge \beta)=\lbrace w_1,w_5,w_7,w_8 \rbrace$
Calculating intersection is in fact adding information, and we throw away world elements by doing this. This is compactible with information theory!
本文作者： lucainiaoge
本文链接： https://lucainiaoge.github.io.git/2020/03/18/course_note1-propositional_logic-BN_and_inference_UCLA_Adnan/
版权声明： 本作品采用 Creative Commons authorship - noncommercial use - same way sharing 4.0 international license agreement 进行许可。转载请注明出处！
