Lecture 4. Boolean algebra
Slides∀I
Logical methods for AI
Lecture 4
Boolean algebra
This work is licensed under CC BY 4.0
-
Truth values
Ideas
- Binary logic: true vs false
- True = 1 and False = 0 $$\mathbf{2}=\Set{0,1}$$
- Truth is relative:
- it's raining in $s$ $\Rightarrow$ $RAIN$ is true
- it's not raining in $s$ $\Rightarrow$ $RAIN$ is false
Functions
- Function = assignment $f:X\to Y$
- $f(a,b,c,\dots)=x$
Non-Functions
- Function = assignment $f:X\to Y$
-
Boolean algebra
Boolean algebra
- Truth-functions: $f:\Set{0,1}^n\to\Set{0,1}$
- Idea: Truth-functions = logical operators
Boolean NOT
Boolean AND
Boolean OR
Boolean XOR
| Negation laws | ||
|---|---|---|
| Complementation 1 | $x\times -x=0$ | |
| Complementation 2 | $x+ -x=1$ | |
| Involution | $--x=x$ | |
| De Morgan 1 | $-(x+y)=-x\times -y$ | |
| De Morgan 2 | $-(x\times y)=-x+-y$ |
| Conjunction laws | ||
|---|---|---|
| Idempotence $\times$ | $x\times x=x$ | |
| Commutativity $\times$ | $x\times y=y\times x$ | |
| Associativity $\times$ | $x\times(y\times z)=(x\times y)\times z$ | |
| Identity $\times$ | $x\times 1=x$ | |
| Annihilation $\times$ | $x\times 0=0$ |
| Disjunction laws | ||
|---|---|---|
| Idempotence $+$ | $x+x=x$ | |
| Commutativity $+$ | $x+y=y+x$ | |
| Associativity $+$ | $x+(y+z)=(x+y)+z$ | |
| Identity $+$ | $x+0=x$ | |
| Annihilation $+$ | $x+ 1=1$ |
| Interaction laws | ||
|---|---|---|
| Distributivity 1 | $x\times(y+ z)=(x\times y)+(x\times z)$ | |
| Distributivity 2 | $x+(y\times z)=(x+ y)\times(x+ z)$ | |
| Absorption 1 | $x+(x\times y)=x$ | |
| Absorption 2 | $x\times(x+ y)=x$ |
-
Boolean models
Idea
- Boolean algebra = model of situations
- Bivalence = modelling assumption
Language
$$A::=p_i\mid \neg A\mid (A\land A)\mid(A\lor A)$$Valuations
$$\nu:\Set{p_i}\to\Set{0,1}$$Recursion
$$\nu(\neg A):=-\nu(A)$$ $$\nu((A\land B)):=\nu(A)\times \nu(B)$$ $$\nu((A\lor B)):=\nu(A)+ \nu(B)$$-
Applicat10ns
Boolean inference
- Valuations = situations
- $[A]=\Set{\nu:\nu(A)=1}$
- Valid inference: $$P_1,P_2,\dots\vDash C\Leftrightarrow [P_1]\cap [P_2]\cap \dots\subseteq [C]$$
Logical laws
$$x+(x\times y)=x\Rightarrow [A\lor(A\land B)]=[A]$$ $$\Rightarrow A\lor (A\land B)\vDash A\qquad A\vDash A\lor (A\land B)$$Logical laws
$$x\leq x+y \Rightarrow [A]\subseteq [A\lor B]$$ $$\Rightarrow A\vDash A\lor B$$Binary arithmetic
- Binary numbers: $$101=1\times 2^2+0\times 2^1+1\times 2^0=5$$
- Binary addition: $$\phantom{+\ }010$$ $$\underline{+\ 011}$$ $$=\ 101$$
Boolean arithmetic
- $z=x+y$ $$x=\dots x_3x_2x_1$$ $$y=\dots y_3y_2y_1$$ $$z=\dots z_3z_2z_1$$
- Binary addition: $$z_i=(x_i\oplus y_i)\oplus (x_{i-1}\times y_{i-1})$$
Thanks!
Highlights
Powered by
