Boolean Algebra

Boolean Algebra

I strongly recommend you get paper out.

Open Ended

We all remember AND, XOR, OR, and NOT... don't we?

So what is...

XNOR?

Starting with OR

Represented with a plus sign <-- This is important

A refresher on Binary Operations

AND

Represented with a multiplication sign

A refresher on Binary Operations

NOT

Represented with a bar above the variable

A refresher on Binary Operations

XOR

Represented with a circle with a plus in it

A refresher on Binary Operations

XNOR

Represented with a circle with a dot in it

A refresher on Binary Operations

Order of Precedence

It is important to do the operations in correct order.

The order of operations is:

NOT, AND, XOR, XNOR (xor and xnor are interchangeable), OR

What are Boolean Variables?

A boolean variable (such as x) is a variable which can only represent 1 (True) or 0 (False)

Note that we can use our boolean operators on boolean variables.

The Goal of Boolean Algebra

A boolean expression might look like: A(A + B) + BA

Which is equal to just A.

This simplification is ideally what most boolean algebra problems ask.

Commutative Property

Remember the following 11 laws. You'll need them for the contest. You probably know more of these than you think you do.

x + y = y + x

x * y = y * x

For fun, see if you can prove all of these laws.

Associative Property

(x + y) + z = x + (y + z)

(x * y) * z = x * (y * z)

Idempotent Law

x + x = x

x * x = x

Annihilator Law

x + 1 = 1

x * 0 = 0

Identity Law

x + 0 = x

x * 1 = x

Complement Law

x + x̅ = 1 (a bar over anything means NOT)

x * x̅ = 0

Absorptive Law

x + xy = x

x + x̅y = x + y

x(x + y) = x

Distributive Law

x * (y + z) = xy + xz

(x + y) * (p * q) = xp + xq + yp + yq

(x + y)(x + z) = x + yz

DeMorgan's Law A very useful law honestly

x͞ ͞+͞ ͞y͞ = x̅ * y̅

x͞ ͞* ͞y͞ = x̅ + y̅

Double Negation

This basically means if you have the not symbol (looks like this x̅) above a variable like x twice, it simplifies to x (I couldn't find a way to put two lines over a character so I had to do this).

For example: NOT(NOT(1)) = NOT(0) = 1 and 1 = 1

XOR and XNOR

x ⊙ y = x͞ ͞⊕͞ ͞y͞ = x ⊕ y̅ = x̅ ⊕ y

x ⊕ y = x̅y + xy̅

x ⊙ y = xy + x̅y̅

Using these 11 Laws

Let's look at this problem and see how to do it with our laws.

The goal of this problem is to simplify this boolean expression as far as we can.

Using these 11 Laws

Here's the answer and how to

simplify the below boolean

expression.

Multiple Choice

Simplify this boolean expression.

I assure you, this will become easier after you do more of these problems

• A̅

• A + B

• AB

• A

• C 👀

Multiple Choice

How many ordered pairs make this expression TRUE? In other words, of the 4 possible values for A and B, how many of them when put in this expression make it true?

Hint: simplify first rather than trying all possible combinations.

• 0

• 1

• 2

• 3

• 4

Multiple Choice

Simplify this boolean expression.

• 0

• 1

• A

• A̅

• AB̅

Multiple Choice

Taking all the ordered triples which make this expression FALSE, count the total number of ones in all those triples, and the answer is the sum of these numbers.

• 1

• 2

• 3

• 4

• 5