Contest Python: ACSL › Unit 8 — Boolean Algebra
Exercises: Unit 8 — Boolean Algebra
There are two kinds of exercises here, just as on an ACSL contest.
- Short-answer: work it out with pencil and paper and write one exact answer.
- A statement question is answered
TRUEorFALSE. - A value is
1or0; a "how many" question is answered with just the number, such as4. - A truth-table question asks for the result column: its digits from top to bottom as one string, with the rows in counting-up order (
00,01,10,11forA,B), such as1101. - Ordered pairs and triples are written with no spaces inside, in counting-up order, separated by a comma and a space:
(0,1), (1,1). WriteNONEif there are none. - A simplify question asks for a sum of products, with the fewest terms and then the fewest letters: letters in alphabetical order inside each term, and terms in order as Lesson 2 describes (
A * B + ~A * C). Write1or0if it is always TRUE or always FALSE. - An option question is answered with the labels of every correct option, in order, separated by a comma and a space, such as
A, C, orNONE.
- A statement question is answered
- Programming: write a complete program that reads the input with
input()and prints exactly the output described. Save it as a.pyfile and run it from a terminal, typing the sample input or feeding it a file.
Each exercise is marked with the lowest ACSL division it belongs to. Do every exercise at or below your division. Exercises 1 to 6 are an Elementary mock test: six questions in 30 minutes, with no programming, using only what Lesson 1 teaches. Exercises 7 to 9 are extra Elementary practice. Exercises marked Challenge are extra practice for when you want more.
Exercise 1: True or False?
Is the following statement TRUE or FALSE?
(3 + 4 > 6 OR 2 * 5 < 9) AND NOT (8 - 3 = 4)How this is checked: Checked by comparing your answer with the expected answer.
Answer format: `TRUE` or `FALSE`, in capital letters.
Exercise 2: Build the Truth Table
Build the truth table of ~A + A * ~B.
Give its result column, with the rows in the order (0,0), (0,1), (1,0), (1,1).
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 3: Simplify
Simplify ~(A + ~B) + A * B as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 4: Count the Pairs
How many ordered pairs (A,B) make ~(A * ~B) * (A + B) TRUE?
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 5: Which Are Equivalent?
Which of the following expressions are equivalent to ~(A + ~B)?
- (A)
~A * B - (B)
~A + B - (C)
~(A * ~B) - (D)
B * ~(A * B) - (E)
~A * ~B
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: The labels of every correct option, in order, separated by a comma and a space, as in `A, C`; `NONE` if no option is correct.
Exercise 6: Simplify Again
Simplify ~(~A * B) * A + ~B as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 7: Pairs That Fail
Find all ordered pairs (A,B) that make ~A * B + A * ~B FALSE.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Ordered pairs in counting-up order, with no spaces inside a pair, and a comma and a space between pairs, as in `(0,1), (1,0), (1,1)`; `NONE` if there are none.
Exercise 8: Spot the Tautology
Which of the following expressions are tautologies?
- (A)
A * ~A + B - (B)
~(A * B) + A - (C)
A + ~A * B - (D)
~(A * ~A)
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: The labels of every correct option, in order, separated by a comma and a space, as in `A, C`; `NONE` if no option is correct.
Exercise 9: De Morgan at Work
Find all ordered pairs (A,B) that make ~(A * B) * (A + ~B) TRUE.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Ordered pairs in counting-up order, with no spaces inside a pair, and a comma and a space between pairs, as in `(0,1), (1,0), (1,1)`; `NONE` if there are none.
Exercise 10: A Real Paper
An ACSL paper prints this expression:
Find its value when A = 1, B = 0 and C = 0.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 11: Three Variables, One Column
Build the truth table of A ⊕ B * C + ~(A + C).
Give its result column, with the eight rows in counting-up order, from (0,0,0) to (1,1,1).
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 12: Shrink It
Simplify A * B + A * ~B * C + ~A * C as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 13: Two Bars
Simplify ~(~A + B) + ~(A + ~C) as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 14: Every Triple
Find all ordered triples (A,B,C) that make (A + ~B) * (~A + C) * ~(B * C) TRUE.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Ordered triples in counting-up order, with no spaces inside a triple, and a comma and a space between triples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.
Exercise 15: Exclusive or Not
Simplify A ⊕ B + A * B as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 16: Count the Triples
How many ordered triples (A,B,C) make A ⊙ B + ~C TRUE?
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 17: Translate, Then Solve
An ACSL paper prints this expression:
Find all ordered triples (A,B,C) that make it TRUE.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Ordered triples in counting-up order, with no spaces inside a triple, and a comma and a space between triples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.
Exercise 18: From Column to Solutions
The input is one line holding the result column of a truth table: a string of 0s and 1s whose length is 4, 8 or 16.
A length of 4 means two variables (A,B), 8 means three (A,B,C), and 16 means four (A,B,C,D).
The rows are in counting-up order, so the first digit belongs to all 0s and the last to all 1s.
Print every ordered tuple whose digit is 1, in order, in the book's form: no spaces inside a tuple, and a comma and a space between tuples.
If there are none, print NONE.
Constraints
- The column has length 4, 8 or 16, and holds only
0and1.
Sample Input
0111Sample Output
(0,1), (1,0), (1,1)This is the column of A + B.
How this is checked: Checked by running your program on 7 test inputs (1 sample, 6 hidden) and comparing its output line by line.
Exercise 19: The Sum-of-Products Solver
The input is one line holding a sum of products over the variables A, B and C.
Each literal is a capital letter A, B or C, or one of them with a ~ in front and no space (~B).
Literals in a term are joined by * and terms are joined by +, always with one space on each side of the operator.
There are no brackets.
An expression does not have to use all three letters.
Print two lines:
- the number of ordered triples
(A,B,C)that make the expression TRUE; - those triples in counting-up order, in the book's form, or
NONEif there are none.
Constraints
- The expression has between 1 and 8 terms, and each term has between 1 and 3 literals.
- A letter may appear more than once in a term.
Sample Input
A * ~B + ~A * CSample Output
4
(0,0,1), (0,1,1), (1,0,0), (1,0,1)How this is checked: Checked by running your program on 8 test inputs (1 sample, 7 hidden) and comparing its output line by line.
Exercise 20: NOTs Inside NOTs
Simplify ~(~(A * ~B) + ~(B + C)) + ~A * ~~C as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 21: Sixteen Rows
How many ordered quadruples (A,B,C,D) make (A ⊕ B) * (C + ~D) + ~(A + C) * B * D TRUE?
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 22: Unpack the XNOR
Simplify ~(A ⊕ B) * C + A * ~(~B + C) as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 23: Triples That Fail
Find all ordered triples (A,B,C) that make (A ⊙ B) ⊕ C * ~A FALSE.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Ordered triples in counting-up order, with no spaces inside a triple, and a comma and a space between triples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.
Exercise 24: A Flipped XOR
Simplify ~(A ⊕ ~B) + ~(~A * ~C) as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 25: Order of Operations
The input is one line holding a Boolean expression over the variables A, B, C and D, with no brackets.
Each literal is one of the four letters, or a letter with a ~ in front and no space (~D).
The operators are * (AND), + (OR), and XOR and XNOR, which are typed as the words XOR and XNOR because ⊕ and ⊙ are not on the keyboard.
Every literal and operator is separated from the next by one space, and literals and operators alternate.
Use ACSL's order of operations: first ~, then *, then XOR and XNOR (on the same level, left to right), and last +.
Print the number of ordered quadruples (A,B,C,D) that make the expression TRUE.
Constraints
- The expression has between 1 and 40 literals.
- An expression does not have to use all four letters; a letter it leaves out can be 0 or 1 freely.
Sample Input
A * B XOR C + ~DSample Output
12This is (A * B) ⊕ C + ~D.
It is TRUE on the 8 quadruples with D = 0, and on 4 of the 8 with D = 1.
How this is checked: Checked by running your program on 8 test inputs (1 sample, 7 hidden) and comparing its output line by line.
Exercise 26: The Long Simplification
Simplify ~(A * ~(B + ~C)) * ~(~A * B * ~D) * (A + B + C + D) as a sum of products.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.
Exercise 27: Same or Different?
The input is two lines, each holding a Boolean expression in the form of Exercise 25: literals over A, B, C and D, the operators *, +, XOR and XNOR, single spaces, and no brackets.
If the two expressions are equivalent, print EQUIVALENT.
Otherwise, print the first ordered quadruple (A,B,C,D), in counting-up order, on which they have different values, in the book's form.
Constraints
- Each expression has between 1 and 40 literals.
Sample Input
A XOR B
A * ~B + ~A * BSample Output
EQUIVALENTFor an input of A + B and A XOR B, the answer would be (1,1,0,0): the first quadruple with A = 1 and B = 1.
How this is checked: Checked by running your program on 7 test inputs (1 sample, 6 hidden) and comparing its output line by line.