Verified for the 2025 AP Computer Science A exam•5 min read•Last Updated on June 18, 2024
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.
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:
!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...
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.
Remember that there is an order of operations to these operators if there are multiple boolean logical operators in one expression. The NOT operator has the highest precedence, followed by the AND operator and finally the OR operator.
Here is a truth table for !a && b || !a && !b:
| a | b | !a | !b | !a && b | !a && !b | !a && b || !a && !b | | --- | --- | --- | --- | --- | --- | --- | | False | False | True | True | False | True | True | | False | True | True | False | True | False | True | | True | False | False | True | False | False | False | | True | True | False | False | False | False | False |
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.
Here is a truth table for (!a || b) && (!a || !b):
| a | b | !a | !b | !a || b | !a || !b | (!a || b) && (!a || !b) | | --- | --- | --- | --- | --- | --- | --- | | False | False | True | True | True | True | True | | False | True | True | False | True | True | True | | True | False | False | True | False | True | False | | True | True | False | False | True | False | False |
Note that this expression also evaluates to true any time a is false, so an equivalent boolean expression for this is also !a.
This term refers to an expression that checks if one condition is true while the other is false using the logical AND operator.
Term 1 of 14
This term refers to an expression that checks if one condition is true while the other is false using the logical AND operator.
Term 1 of 14
Theorems are statements that have been proven to be true using logical reasoning and previously established facts.
Axioms: Fundamental statements or principles that serve as the foundation for proving theorems.
Corollaries: Statements that can be easily derived from a theorem, often providing additional insights or consequences.
Proofs: Logical arguments or demonstrations that establish the truth of a theorem or statement.
This term refers to the logical AND operator in programming, which checks if both conditions on either side of the operator are true.
Logical Operator: A symbol or word used to connect multiple conditions in programming.
Boolean Expression: An expression that evaluates to either true or false.
Short-circuit Evaluation: The process where the second condition is not evaluated if the first condition already determines the outcome.
This term refers to an expression that checks if one condition is true while the other is false using the logical AND operator.
Logical NOT Operator (!): A unary operator that negates (flips) the value of a boolean expression.
Equality Operator (==): An operator used to compare two values for equality.
De Morgan's Laws: Mathematical rules that describe how logical operators can be applied when negating expressions.
This term refers to the logical OR operator in programming, which checks if at least one of the conditions on either side of the operator is true.
Conditional Statement (if statement): A control structure that executes certain code blocks based on specified conditions.
Truth Table: A table used in logic and computer science to determine the outputs of logical expressions.
Short-circuit Evaluation: The process where the second condition is not evaluated if the first condition already determines the outcome.
The logical OR operator (||) is used to combine two boolean values. If either of the values is true, the result will be true.
Logical OR operator (||): Combines two boolean values and returns true if at least one of them is true.
Boolean value: A data type that can have one of two possible values - true or false.
Logical AND operator (&&): Combines two boolean values and returns true only if both of them are true.
The logical OR operator (||) can also be used to combine the same boolean value twice. If the value is true, the result will be true; otherwise, it will be false.
Logical OR operator (||): Combines two boolean values and returns true if at least one of them is true.
Boolean value: A data type that can have one of two possible values - true or false.
Logical NOT operator (!): Reverses the boolean value. If it was originally false, applying NOT makes it true; if it was originally true, applying NOT makes it false.
The logical OR operator (||) can also be used in combination with the logical NOT operator (!). It checks whether at least one of the original value or its negation is true.
Logical OR operator (||): Combines two boolean values and returns true if at least one of them is true.
Logical NOT operator (!): Reverses the boolean value. If it was originally false, applying NOT makes it true; if it was originally true, applying NOT makes it false.
Boolean value: A data type that can have one of two possible values - true or false.
The distributive law allows us to distribute (or break apart) an expression into smaller parts and then combine them back together. It helps simplify calculations by breaking down complex expressions.
Expression: A combination of variables, constants, and operators used to represent a value or perform calculations.
Coefficient: A number multiplied by a variable in an algebraic expression.
Like Terms: Terms in an algebraic expression that have identical variables raised to identical powers.
The NOT operator is a logical operator that reverses the truth value of a given expression. It returns true if the expression is false, and false if the expression is true.
AND operator: The AND operator combines two or more conditions and returns true only if all conditions are true.
OR operator: The OR operator combines two or more conditions and returns true if at least one condition is true.
XOR (exclusive OR) operator: The XOR operator combines two conditions and returns true only if exactly one condition is true.
The AND operator is a logical operator that combines two or more conditions and returns true only if all conditions are true.
OR Operator: The OR operator combines two or more conditions and returns true if at least one condition is true.
NOT Operator: The NOT operator reverses the truth value of an expression.
Short-circuit evaluation: A technique used by programming languages where they stop evaluating an expression as soon as its outcome can be determined based on previous evaluations.
The OR operator is a logical operator that combines two or more conditions and returns true if at least one condition is true.
AND Operator: The AND operator combines two or more conditions and returns true only if all conditions are true.
NOT Operator: The NOT operator reverses the truth value of an expression.
Short-circuit evaluation: A technique used by programming languages where they stop evaluating an expression as soon as its outcome can be determined based on previous evaluations.