The AP Computer Science A 5-hour live stream review is here!Β πŸ’»

Join us on May 5, 2021 for the 🌢️ AP Computer Science A Cram Finale for a last minute review to get all your questions answered!

πŸ“š

All Subjects

Β >Β 

πŸ’»Β 

AP Comp Sci A

Β >Β 

πŸ–₯

Unit 3

3.6 Equivalent Boolean Expressions

4 min readβ€’march 11, 2021

Peter Cao

Caroline Koffke


3.6: Equivalent Boolean Expressions

Sometimes there are multiple ways to represent the same boolean expression. To show that they are the same expression, either prove that they can be simplified to the same expression using boolean properties and identities or prove that they can be the same in all cases.

Proof By Simplification

We can simplify one boolean expression to another in order to show that the two expressions are equivalent. To do so, we will use boolean properties, identities, and theorems. You do NOT need to memorize these, as we will do an easier formulaic way after.
For boolean values a, b, and c, we have the following:

Basic Theorems

  1. a && false == false
  2. a && true == a
  3. a && a == a
  4. a && !a == false
  5. a || false == a
  6. a || true == true
  7. a || a == a
  8. a || !a == true
  9. !(!a) == a (The inverse of an inverse is the original value)

Consensus Theorems (Nice to know, but not required)

  • a || (!a && b) == a || b
  • a || (!a && !b) == a || !b
  • !a || (a && b) == !a || b
  • !a || (a && !b) == !a || !b

Commutative Law (Boolean AND and OR are commutative)

  • a && b == b && a
  • a || b == b || a

Associative Law (Boolean AND and OR are associative)

  • a && (b && c) == (a && b) && c
  • a || (b || c) == (a || b) || c

Distributive Law (Boolean AND distributes over boolean OR)

  • a && (b || c) == (a && b) || (a && c)

DeMorgan's Theorems (Important to know) (Boolean NOT does not distribute over boolean OR or AND)

  • !(a && b) == !a || !b
  • !(a || b) == !a && !b
We can use these properties to simplify boolean expressions. This example is probably more complicated than what you would see on the exam, but it still serves as a good guide:
!a && b && c || a && !b && c || a && b && !c || a && b && c = !a && b && c || a && b && c || a && b && !c || a && !b && c (Commutative Law) = (!a || a) && b && c || a && b && !c || a && !b && c (Distributive Law) = (true) && b && c || a && b && !c || a && !b && c (Basic Theorem 8) = b && c || a && b && !c || a && !b && c (Basic Theorem 2) = b && (c || a && !c) || a && !b && c (Distributive Law) = b && (c || !c && a) || a && !b && c (Commutative Law) = b && (c || a) || a && !b && c (Consensus Theorem) = b && c || b && a || a && !b && c (Distributive Law) = b && c || a && (b || !b && c) (Distributive Law) = b && c || a && (b || c) (Consensus Theorem) = b && c || a && b || a && c. (Distributive Law)
In this simplification, every row is equivalent to the first row due to boolean properties. However, this can get a little messy at times, as seen above, so we have... drumroll please...

Proof By Testing All Cases

Sometimes, the simplification of a boolean expression may not be obvious, so we can test all possible cases of input in a boolean expression to get all possible outputs. If the outputs of two boolean statements are all the same, then these two statements are equivalent. We can do this with truth tables, which are a methodical way to organize these.
Here is a truth table for !a && b || !a && !b:

Truth Table

ab!a!b!a && b!a && !b!a && b || !a && !b
FalseFalseTrueTrueFalseTrueTrue
FalseTrueTrueFalseTrueFalseTrue
TrueFalseFalseTrueFalseFalseFalse
TrueTrueFalseFalseFalseFalseFalse
Note that this expression evaluates to true any time a is false, so an equivalent boolean expression for this is simply !a.
As for the structure of the truth table, the leftmost columns are the inputs with the number of rows dictated by the possible number of inputs. The following columns represent the evaluation of the boolean expression step by step according to the boolean order of operations. Once you become more familiar with these operations, you can skip some of the columns, but it's better to keep all of the columns to be safe.

Was this guide helpful?

πŸ’ͺ🏽 Are you ready for the Comp Sci exam?
Take this quiz for a progress check on what you’ve learned this year and get a personalized study plan to grab that 5!
START QUIZ
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
FREE AP comp sci a Survival Pack + Cram Chart PDF
Sign up now for instant access to 2 amazing downloads to help you get a 5
Browse Study Guides By Unit
πŸ™
Exam Reviews
πŸ–±
Unit 10: Recursion
βž•
Unit 1: Primitive Types
πŸ“±
Unit 2: Using Objects
πŸ•Ή
Unit 4: Iteration
βš™οΈ
Unit 5: Writing Classes
⌚️
Unit 6: Array
πŸ’Ύ
Unit 7: ArrayList
πŸ’»
Unit 8: 2D Array
πŸ–²
Unit 9: Inheritance
Join us on Discord
Thousands of students are studying with us for the AP Computer Science A exam.
join now
πŸ“± Stressed or struggling and need to talk to someone?
Talk to a trained counselor for free. It's 100% anonymous.
Text FIVEABLE to 741741
Β© 2021 Fiveable, Inc.