2

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding Boolean algebra. To be specific, I'm stuck on the following practice question:

Let $A = \{a, b\}$ and list the four elements of the power set $\mathcal{P}(A)$. We consider the operation $+$ to be $\cup$, $\cdot$ to be $\cap$, and complement to be set complement. Consider $1$ to be $A$ and $0$ to be $∅$.

  1. Explain why the description above defines a Boolean algebra.
  2. Find two elements $x$, $y$ in $\mathcal{P}(A)$ such that $xy = 0$, $x \neq 0$ and $y \neq 0$.

Starting with the power set: $$\mathcal{P}(A) = \{∅, \{a\},\{b\},\{a,b\}\}.$$

How would I go about finding the elements of $x$ and $y$ to satisfy part two of the question using algebraic axioms? Also, for explaining how the above defines a Boolean algebra, do you think it would suffice to simply mention how there are two binary operations and a set associated with the Boolean algebra?

Community
  • 1
Johnathan Scott
  • 333

2 Answers2

3

Let $x=\{a\}$ and $y=\{b\}$. We have $x\ne\emptyset$ and $y\ne\emptyset$. We also have $xy=x\cap y=\{a\}\cap\{b\}=\emptyset=0$, so that seems to work.

A boolean algebra has variables that can only be true or false (or $1$ or $0$). Normal algebraic operations can continue as usual, unless of course they don't work.

JMP
  • 21,771
  • +1: Excellent! Now you need only prove that/explain why the Boolean algebra axioms hold on the given structure. – Cameron Buie Sep 24 '15 at 03:44
  • As a bonus problem: you should be able to prove that we can replace the given set $A$ with any set, define the operations the same way, and still get a Boolean algebra. This is because Boolean algebras were pretty much invented as generalizations of power sets under intersection and union. – Cameron Buie Sep 24 '15 at 03:47
  • https://en.wikipedia.org/wiki/Boolean_algebra#Concrete_Boolean_algebras – JMP Sep 24 '15 at 03:48
  • /sigh/ Yes, of course you could just look it up, but that won't necessarily help you get a feel for anything. – Cameron Buie Sep 24 '15 at 03:51
  • i should do, but before i got into this question, i was going to look at https://en.wikipedia.org/wiki/Quadratrix – JMP Sep 24 '15 at 03:55
1

A boolean algebra is any set together with two binary operation $\land$ and $\lor$, one unary operation $\lnot$ and two nullary operations $0$ and $1$ (that is, two constants) satisfying a suitable set of axioms - see, for instance, the definition section from the Wikipedia article.

The simplest boolean algebra is the already mentioned two element set $\{0,1\}$ together with the traditional truth table operations, but - as you seem to know already - any set $S$ gives rise to a boolean algebra defined on its power set $\mathcal{P}(S)$: just define $\land, \lor, \lnot, 0$ and $1$ to be $\cap, \cup, S\setminus, \emptyset$ and $S$ respectively ($S\setminus$ means complement with relation to $S$).

As for proving that something is indeed a boolean algebra, there's no free lunch. You must check that the definitions you give for the boolean operations satisfy the axioms. So besides mentioning that there are two binary operations, you must be sure to have them properly defined so that anyone can understand what you take them to be. Also you must define the other operations as well and verify that the axioms hold for them.

For instance, one axiom says that:

$a \land \lnot a = 0$

To show that your particular instance of boolean algebra satisfies this axiom, you must show that:

$a \cap (S\setminus a) = \emptyset$.

Tarc
  • 509