CIS 115

Bits and Boolean Algebra

The Laws of Thought

Image Source: Project Gutenberg

De Morgan's Law

Negation (inverse) of a logic statement

¬ ( A ∧ B ) = ( ¬ A ) ∨ ( ¬ B)

¬ ( A ∨ B ) = ( ¬ A ) ∧ ( ¬ B)

Distribute the negative (¬) then swap ands (∧) and ors (∨)

Boolean Algebra

• ∨ works like addition ( + )
• ¬ works like negation ( − )
• ∧ works like multiplication ( × )
• Associative: (A ∧ B) ∧ C = A ∧ (B ∧ C)
• Commutative: (A ∧ B) = (B ∧ A)
• Distributive:
  A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)

Logic via Electrical Switches?
Charles Sanders Peirce

Image Source: Wikipedia

A Symbolic Analysis of Relay and Switching Circuits

Image Source: MIT

"...possibly the most important, and also the most famous, master's thesis of the century."
- Psychologist Howard Gardner (via Wikipedia)

Logic Gates

AND	OR	XOR	NOT
NAND	NOR	XNOR

Note: The little circle at the end of the NOT gate is the only part that matters.

Boolean Values

Note: These values are traditionally used in theory. In many electronic systems and programming languages these values may be reversed for various reasons. Check the manual!

Example 1

(A ∧ C) ∨ (B ∧ C)

C ∧ (A ∨ B) works as well

Example 2

¬A ∧ ( B ∨ C )

( ¬A ∧ B) ∨ ( ¬A ∧ C) works as well

Example 3

( A ⊕ B ) ∧ C

(A ∧ C) ⊕ (B ∧ C) works

(A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) works

Example 4

¬ ( A ∧ B ∧ ¬C )

By De Morgan's Law
( ¬A ∨ ¬B ∨ C ) works as well

Universal Logic Gates

Image Source: Wikipedia

Universal Logic Gates - Adder

Image Source: Wikipedia

Image Source: schoolphysics.co.uk

Next Steps

• Programming
• Finite State Machines


Image Source: Wikipedia

Assignments

• Read and be prepared to discuss:
  • Pattern on the Stone
    Chapter 3: Programming
• Blog 1: Personal Biography - Due Tuesday 1/30 10PM
• ATM Project - Due 2/7 10PM

Blog 1: Personal Biography

Tell us a little about yourself. This is your chance to let us know who you are and what interests you. Some questions you can answer to get you started are below, but feel free to be as creative and expressive as possible introducing yourself.

• Where are you from?
• Why did you choose to come to Kansas State?
• What interests you about Computing Science?
• Do you have any hobbies?
• What is your family like?
• Have you had any interesting jobs or experiences?
• What do you want to do after you graduate?

Booleans in Scratch

And

Or

Not

Getting Boolean Values

Less Than

Greater Than

Equals

Mouse Down

Key Pressed

Using Boolean Values

If block

If Else block

Scratch Variables

Variable

Set Variable

Change Variable

Show Variable

Hide Variable