How do boolean expressions relate to algebra?

[Problem+Solve=Reason]

If anyone knows anything about the basics of Boolean Algebra please tell me what you know. Thanks

----- Life is a problem... SOLVE IT!

 

[gazzo]

(i think) a (finite) Boolean algebra must have $2^n$ elements, for some $n \in \mathbb{N}$ and they form a ring:

$$(\mathbb{Z}/n\mathbb{Z}, +, \cdot)$$

They can be thought of as like, an electric switch, which can either be on (allowing the flow of current) or off (preventing it). Similary in a transistor, or television. That is, they have two-states - and we abstract the 'true and false/on and off' like:

Let $\cal{B} = \{$$0,1$$\}$ and define:

$$0+0=0; 0+1=1+0=1+1=1$$
$$0\cdot0=0=1\cdot0=0\cdot1; 1\cdot1=1$$
$$\overline{0}=1; \overline{1}=0$$

where $\overline{n}$ indicates the complement of n.

so, $x^2 =x \cdot x=xx=x, \forall x \in\cal {B}$

how does it work when n is like 8 or 16 though?

edit: oops sorry! I'm confused and talking about something else? how do you delete posts =/
check out mathworld, the mathematics of boolean algebra (stamford.edu) & wikipedia.

 

[danne89]

Oh, yes. You're only dealing with ones and zeroes, trues and falses, and other arbitrary abstractations one made.

There're three operators: AND, OR, and NOT. You can just write them with letters if you like or use: ^, V respective ~. Where AND and OR are binary operators and NOT -what it the word? -.

Then they're defined as following:
0 AND 0 = 0
1 AND 0 = 0
0 AND 1 = 0
1 AND 1 = 0

0 OR 0 = 0
1 OR 0 = 1
0 OR 1 = 1

NOT 0 = 1
NOT 1 = 0

Then we also have the XOR operator (eXclusive OR).
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0

That's all I can remember for the moment.

 

[Gamish]

I'm a computer programer, so I work with this a lot. Finding the result of 2 boolean expressions is easy, just think of the 0 as a negative number, and the 1 as a positive. Do the math. Exactly how does boolean logic relate to alg?

Im the master at time!

 

[Gokul43201]

Finding the result of 2 boolean expressions is easy, just think of the 0 as a negative number, and the 1 as a positive. Do the math.

Could you please define this approach more rigorously, so that we may actually understand how to "do the math" ?

For instance if 0 -> -x, 1 -> +y, where x,y are positive numbers, what is [0 OR 1] = ?

 

[Gokul43201]

Note the following corrections/additions (in bold) :

...

Then they're defined as following:
0 AND 0 = 0
1 AND 0 = 0
0 AND 1 = 0
1 AND 1 = 1

0 OR 0 = 0
1 OR 0 = 1
0 OR 1 = 1
1 OR 1 = 1

 

[gazzo]

I'm a computer programer, so I work with this a lot. Finding the result of 2 boolean expressions is easy, just think of the 0 as a negative number, and the 1 as a positive. Do the math. Exactly how does boolean logic relate to alg?

It's interesting, the fact that Boolean algebra was first developed as an abstract idea before the application. (1854 Mr Boole thought it up). He probably thought it would serve no real purpose too! :tongue: If only they were all here today, I remember that one dilbert episode where dilbert's garbageman (the genius) brings Benjamin Franklin back to life and he starts talking about the world wide web and TCP/IP.

If $n \in \mathbb{N}$, then ${{\cal B}^{n}} = \{({b_1},{b_2},\ldots,{b_n})\vert{b_i} \in \{$$0,1$[tex]\}, 1 <= i <= n \}[/itex] So a function $f:{{\cal B}^n}\longrightarrow{\cal B}$ is a Boolean/Switching function of $n$ variables.

Let $f:{\cal B}^3\longrightarrow\cal{B}$, where $f(x,y,z) = xy+z$ Then:

$$\begin{tabular}{argument} \hline x & y & z & xy & f(x,y,z)=xy+z \\ \hline 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \hline \end{tabular}$$

They bow down to the usual laws as well as:

Demorgans Law where
$\overline{x+y} = \overline{x}\overline{y}$
$\overline{xy} = \overling{x}+\overline{y}$

Idempotent Law where
$x+y=x$
$xx=x$

Dominance Law:
$x+1=1$
$x\cdot0=0$

Absorption Law:
$x+xy=x$
$x(x+y)=x$

The construction of a logical AND gate would, be a function $\wedge:{\cal B}^2\longrightarrow{\cal B}$ defined by $\wedge(x,y) = xy$ and the logical OR would be $\vee:{\cal B}^2\longrightarrow\cal{B}$ defined by $\vee(x,y) = x+y$, and NOT would just be $\~(x)=\overline{x}$

An XOR would be $\oplus(x,y)=(x+y)(\overline{xy})$ (i think).

Oooh this looks interesting especially when there are huge networks of gates.