py4kidsSearch

Contest Python: ACSL › Unit 13 — Digital Electronics

Exercises: Unit 13 — Digital Electronics

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.
    • An output is 1 or 0; a "how many" question is answered with just the number, such as 5.
    • A result column is the output's digits from top to bottom, with the rows in counting-up order, such as 1101.
    • Tuples list the inputs in the order of the INPUTS line, with no spaces inside, in counting-up order, separated by a comma and a space: (0,1,0), (1,1,1). Write NONE if there are none.
    • A simplify question asks for a sum of products, with the fewest terms and then the fewest letters, written as in Unit 8 (A * B + ~A * C), or 1 or 0 if the circuit 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, or NONE. The labels are just names for the options; they have nothing to do with the inputs A, B, C and D.
  • Programming: write a complete program that reads the input with input() and prints exactly the output described. Save it as a .py file and run it from a terminal, typing the sample input or feeding it a file.

Every circuit is a netlist, as in Lesson 1: the INPUTS line, then one gate per line, and the last gate is the output. Every input on the INPUTS line counts, even one that no gate uses.

Each exercise is marked with the lowest ACSL division it belongs to. Do every exercise at or below your division. Exercises marked Challenge are extra practice for when you want more.

Exercise 1: Follow the Signal

  • Division: Junior

What is the output of this circuit when A = 1, B = 0 and C = 1?

INPUTS A B C
p = NOR(A, C)
q = XNOR(B, p)
out = NAND(q, C)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Exercise 2: Four Rows

  • Division: Junior

Build the truth table of this circuit. Give its result column, with the rows in the order (0,0), (0,1), (1,0), (1,1).

INPUTS A B
p = NOT(A)
q = NAND(p, B)
out = XOR(q, A)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For parents and teachers: report a problem

Exercise 3: When the Lamp Stays Off

  • Division: Junior

Find all ordered triples (A,B,C) that make this circuit FALSE.

INPUTS A B C
p = OR(A, B)
q = NAND(B, C)
out = AND(p, q)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: Tuples with the inputs in the order of the `INPUTS` line and no spaces inside, listed in counting-up order with a comma and a space between tuples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.

For parents and teachers: report a problem

Exercise 4: Count the Lit Rows

  • Division: Junior

How many ordered triples (A,B,C) make this circuit TRUE?

INPUTS A B C
p = XOR(A, C)
q = NOR(A, B)
out = OR(p, q)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Exercise 5: Which Expressions?

  • Division: Junior

Which of the following expressions give the same output as this circuit for every triple (A,B,C)?

INPUTS A B C
p = NOR(A, B)
q = NAND(B, C)
out = OR(p, q)
  • (A) ~(A + B) + ~(B * C)
  • (B) ~A * ~B + ~B + ~C
  • (C) ~(A + B + B * C)
  • (D) ~A + ~B + ~C
  • (E) ~B + ~C

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.

For parents and teachers: report a problem

Exercise 6: Read the Sketch

  • Division: Junior

An ACSL paper draws this circuit:

A ---+---------------------------------\
     |                                  [XOR]--- out
     |                           r +---/
     +----\                        |
           [AND]--- p ---\         |
B --------/               [NOR]----+
C ---[NOT]--- q ---------/

Which of the following netlists describe this same circuit: the same gates, wired the same way? (A two-input gate may list its inputs in either order.)

(A)

INPUTS A B C
p = AND(A, B)
q = NOT(C)
r = OR(p, q)
out = XOR(r, A)

(B)

INPUTS A B C
p = AND(B, A)
q = NOT(C)
r = NOR(q, p)
out = XOR(A, r)

(C)

INPUTS A B C
p = AND(A, C)
q = NOT(B)
r = NOR(p, q)
out = XOR(r, A)

(D)

INPUTS A B C
p = AND(A, B)
q = NOT(C)
r = NOR(p, q)
out = XNOR(r, A)

(E)

INPUTS A B C
p = AND(A, B)
q = NOT(C)
r = NOR(p, q)
out = XOR(r, 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.

For parents and teachers: report a problem

Exercise 7: Simplify the Circuit

  • Division: Junior

Write the expression of this circuit, and simplify it as a sum of products.

INPUTS A B C
p = NAND(A, C)
q = OR(B, C)
out = AND(p, q)

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.

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

For parents and teachers: report a problem

Exercise 8: The Missing Gate

  • Division: Junior

In this circuit the last gate has lost its label, shown as GATE:

INPUTS A B
p = AND(A, B)
q = NOR(A, B)
out = GATE(p, q)

The circuit's result column, with the rows in the order (0,0), (0,1), (1,0), (1,1), is 1001. Which of the following gates could GATE be?

  • (A) AND
  • (B) NAND
  • (C) OR
  • (D) NOR
  • (E) XOR
  • (F) XNOR

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.

For parents and teachers: report a problem

Exercise 9: The Unused Input

  • Division: Junior

How many ordered triples (A,B,C) make this circuit TRUE?

INPUTS A B C
p = XNOR(A, B)
out = NOR(p, B)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Exercise 10: Gate by Gate

  • Division: Junior

The first line of input is a whole number n. Each of the next n lines is the name of a gate followed by its input values, separated by single spaces: one value for BUFFER and NOT, and two values for AND, NAND, OR, NOR, XOR and XNOR.

For each line, print the gate's output, 0 or 1, on its own line.

Constraints

  • 1 ≤ n ≤ 100.
  • Every value is 0 or 1, and every gate name is one of the eight above, in capital letters.

Sample Input

5
AND 1 1
NAND 1 1
NOT 0
XOR 1 0
NOR 0 0

Sample Output

1
0
1
1
1

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output line by line.

For parents and teachers: report a problem

Exercise 11: Trace the Circuit

  • Division: Junior

The first line of input is g, the number of gates. The next g + 1 lines are a netlist, written exactly as in this unit: the INPUTS line, and then the g gate lines, each name = GATE(x, y) or name = GATE(x), with a comma and a space between two inputs. The last line holds the value of each input, 0 or 1, in the order of the INPUTS line, separated by single spaces.

Work out every gate, from the top of the netlist down. For each gate, print its name, a space, and its output, on its own line.

Constraints

  • The circuit has between 1 and 4 inputs, capital letters in alphabetical order.
  • 1 ≤ g ≤ 20. Gate names are words of small letters, and every gate's inputs are circuit inputs or gates on earlier lines.
  • The gate on the last line is the output. An input may be used by no gate at all.

Sample Input

3
INPUTS A B C D
p = XOR(A, B)
q = NOR(p, C)
out = AND(q, D)
1 1 0 1

Sample Output

p 0
q 1
out 1

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.

For parents and teachers: report a problem

Exercise 12: The Result Column

  • Division: Junior

The first line of input is g, the number of gates. The next g + 1 lines are a netlist, written exactly as in this unit: the INPUTS line, and then the g gate lines, each name = GATE(x, y) or name = GATE(x), with a comma and a space between two inputs.

Print the circuit's result column: its output for every tuple, in counting-up order, as one string of 0s and 1s. A circuit with k inputs has 2 × 2 × … × 2 (k times) rows.

Constraints

  • The circuit has between 1 and 4 inputs, capital letters in alphabetical order.
  • 1 ≤ g ≤ 20. Gate names are words of small letters, and every gate's inputs are circuit inputs or gates on earlier lines.
  • The gate on the last line is the output. An input may be used by no gate at all.

Sample Input

2
INPUTS A B C
p = NAND(A, B)
out = OR(p, C)

Sample Output

11111101

This is ACSL's first sample: (1,1,0) is the only triple that makes it FALSE.

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.

For parents and teachers: report a problem

Exercise 13: Sixteen Rows

  • Division: Intermediate

How many ordered 4-tuples (A,B,C,D) make this circuit TRUE?

INPUTS A B C D
p = NAND(A, B)
q = XOR(C, D)
r = NOR(p, D)
s = XOR(q, A)
out = OR(r, s)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Exercise 14: The XNOR Chain

  • Division: Intermediate

Find all ordered 4-tuples (A,B,C,D) that make this circuit TRUE.

INPUTS A B C D
p = XNOR(A, B)
q = XNOR(p, C)
r = XNOR(q, D)
out = AND(r, A)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: Tuples with the inputs in the order of the `INPUTS` line and no spaces inside, listed in counting-up order with a comma and a space between tuples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.

For parents and teachers: report a problem

Exercise 15: Four Inputs, Fewer Letters

  • Division: Intermediate

Simplify the expression of this circuit as a sum of products.

INPUTS A B C D
p = NAND(A, B)
q = NOR(C, D)
r = OR(p, q)
s = XNOR(A, C)
out = AND(r, s)

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.

For parents and teachers: report a problem

Exercise 16: Only NOR Gates

  • Division: Intermediate

This circuit is built from NOR gates only. Simplify its expression as a sum of products.

INPUTS A B C
p = NOR(A, A)
q = NOR(B, C)
r = NOR(p, q)
out = NOR(r, r)

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.

For parents and teachers: report a problem

Exercise 17: The FALSE Side

  • Division: Intermediate

Find all ordered 4-tuples (A,B,C,D) that make this circuit FALSE.

INPUTS A B C D
p = OR(A, B)
q = XNOR(B, D)
r = NAND(C, q)
out = AND(p, r)

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: Tuples with the inputs in the order of the `INPUTS` line and no spaces inside, listed in counting-up order with a comma and a space between tuples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.

For parents and teachers: report a problem

Exercise 18: Every Solution

  • Division: Intermediate

The first line of input is g, the number of gates. The next g + 1 lines are a netlist, written exactly as in this unit: the INPUTS line, and then the g gate lines, each name = GATE(x, y) or name = GATE(x), with a comma and a space between two inputs. The last line is 1 or 0, the output wanted.

Print two lines:

  1. the number of tuples that give the wanted output;
  2. those tuples, in counting-up order, in the book's form (no spaces inside a tuple, and a comma and a space between tuples), or NONE if there are none.

A circuit with one input has tuples of one value, such as (1).

Constraints

  • The circuit has between 1 and 4 inputs, capital letters in alphabetical order.
  • 1 ≤ g ≤ 20. Gate names are words of small letters, and every gate's inputs are circuit inputs or gates on earlier lines.
  • The gate on the last line is the output. An input may be used by no gate at all.

Sample Input

2
INPUTS A B C
p = NAND(A, B)
out = OR(p, C)
0

Sample Output

1
(1,1,0)

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.

For parents and teachers: report a problem

Exercise 19: An XNOR From NANDs

  • Division: Senior

Which of the following circuits, built from NAND gates only, are equivalent to A ⊙ B?

(A)

INPUTS A B
p = NAND(A, B)
q = NAND(A, p)
r = NAND(B, p)
out = NAND(q, r)

(B)

INPUTS A B
p = NAND(A, B)
q = NAND(A, p)
r = NAND(B, p)
s = NAND(q, r)
out = NAND(s, s)

(C)

INPUTS A B
p = NAND(A, A)
q = NAND(B, B)
r = NAND(p, q)
out = NAND(r, r)

(D)

INPUTS A B
p = NAND(A, A)
q = NAND(B, B)
r = NAND(A, B)
s = NAND(p, q)
out = NAND(r, s)

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.

For parents and teachers: report a problem

Exercise 20: Two Layers of NAND

  • Division: Senior

Which of the following circuits, built from NAND gates only, are equivalent to A * B + ~C?

(A)

INPUTS A B C
p = NAND(A, B)
q = NAND(C, C)
r = NAND(q, q)
out = NAND(p, r)

(B)

INPUTS A B C
p = NAND(A, B)
q = NAND(C, C)
out = NAND(p, q)

(C)

INPUTS A B C
p = NAND(A, B)
out = NAND(p, C)

(D)

INPUTS A B C
p = NAND(A, B)
q = NAND(p, p)
r = NAND(C, C)
out = NAND(q, r)

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 `B, D`; `NONE` if no option is correct.

For parents and teachers: report a problem

Exercise 21: Six Gates Deep

  • Challenge
  • Division: Senior

Simplify the expression of this circuit as a sum of products.

INPUTS A B C D
p = XOR(A, B)
q = NAND(p, C)
r = NOR(B, D)
s = XNOR(q, r)
t = OR(s, A)
out = NAND(t, D)

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.

For parents and teachers: report a problem

Exercise 22: Same Circuit?

  • Challenge
  • Division: Senior

The input holds two netlists with the same INPUTS line. Each one is given as in Exercise 11: a line with its number of gates, then the netlist itself.

If the two circuits are equivalent (the same output for every tuple), print EQUIVALENT. Otherwise, print the first tuple, in counting-up order, on which their outputs differ, in the book's form.

Constraints

  • Each netlist follows the rules of Exercise 11, and the two INPUTS lines are identical.
  • The two netlists may use the same gate names.

Sample Input

4
INPUTS A B
p = NOR(A, B)
q = NOR(A, p)
r = NOR(B, p)
out = NOR(q, r)
1
INPUTS A B
out = XNOR(A, B)

Sample Output

EQUIVALENT

For the second netlist out = OR(A, B) instead, the answer would be (0,0): the first netlist gives 1 there and OR gives 0.

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.

For parents and teachers: report a problem

Back to Unit 13 — Digital Electronics