In this challenge we will consider an unconventional 8-segment display which is like a 7-segment display, but has an additional diagonal LED from the top-right to bottom-left of the display. Arrays of such displays are commonly used to display characters in remote controls, blood pressure monitors, dishwashers, and other devices. We label each LED ip, with p being the diagonal segment, as shown here. Each LED can be on or off, but in most applications, only a small number of on/off combinations are of interest (such as the ten combinations that allow the display of a digit in the range 0-9). In that case, the display can be controlled through a small number of input wires with four wires providing 24 input combinations, enough to cover the ten different digits. Here we are interested in using an 8-segment display for some Greek letters. We want it to be able to show eight different letters, namely A, B, ,,E,Z,H, and . For example, to show A, all the display segments, except o and p, should be lit up, giving the pattern 8 . In detail, we want the eight different letters displayed respectively as: Since there are eight letters, we need three input wires, modelled as propositional variables P,Q, and R. We will need to decide on a suitable encoding of the eight letters. One possibility encoding of the eight letters is to let A correspond to input 000 (that is, P=Q=R=f ), B to 001 (that is, P=Q=f and R=t ), etc. If we do that, we can summarise the behaviour of each input combination in the table below: Each of the eight segments ip can be considered a propositional function of the variables P,Q, and R. This kind of display can be physically implemented with logic circuitry, using circuits to implement a Boolean function for each of the outputs. Here we assume that only three types of logic gates are available: An and-gate takes two inputs and produces, as output, the conjunction () of the inputs. Similarly, an or-gate implements disjunction (). Finally, an inverter takes a single input and negates it (). We can specify such a circuit by writing down the Boolean equations for each of the outputs ip. For example, segment i is turned off (is false) when the input is 011, 110, or, 111. So, i can be captured as (PQR)(PQR)(PQR). For efficiency reasons, we often want the circuit to use as few gates as possible. For example, the above equation for i shows that we can implement this output using fifteen gates. But i=(PQR)(PQR)(PQR) is an equivalent implementation, using fewer gates. Moreover, the eight functions might be able to share some circuitry. For example, if we have already implemented a sub-circuit defined by u=QR (introducing u as a name for the sub-circuit), then we can define i=(Pu)(PQR)(Pu), and we may be able to re-use u while implementing the other outputs (rather than duplicating the same gates). In some cases, it may even be feasible to design a circuit that is not minimal for a given function, but provides a minimal solution when all eight functions are designed. Task 3A. Design such a circuit, using as few gates as possible. You can define any number of sub-circuits to help you reduce the gate count (simply give each a name). Submission and Marking: Your answer should be submitted on Grok. Submit a text file circuit.txt consisting of one line per definition. This file will be tested automatically, so it is important that you follow the notational conventions exactly. We write as - and as +. We write as ., or, more simply, we just leave it out, so that concatenation of expressions denotes their conjunction. Here is an example set of equations (for a different problem): # An example of a set of equations in the correct format: i=QR+QR+PQR j=u+P(Q+R) k=P+(QR) 1=u+Pi u=PQ #u is an auxiliary function introduced to simplify j and l Empty lines, and lines that start with '#', are ignored. Input variables are in upper case. Negation binds tighter than conjunction, which in turn binds tighter than disjunction. So the equation for i says that i=(QR)(QR)(PQR). Note the use of a helper function u, allowing j and l to share some circuitry. Also note that we do not allow any feedback loops in the circuit. In the example above, l depends on i, so i is not allowed to depend, directly or indirectly, on l (and indeed it does not). In this challenge we will consider an unconventional 8-segment display which is like a 7-segment display, but has an additional diagonal LED from the top-right to bottom-left of the display. Arrays of such displays are commonly used to display characters in remote controls, blood pressure monitors, dishwashers, and other devices. We label each LED ip, with p being the diagonal segment, as shown here. Each LED can be on or off, but in most applications, only a small number of on/off combinations are of interest (such as the ten combinations that allow the display of a digit in the range 0-9). In that case, the display can be controlled through a small number of input wires with four wires providing 24 input combinations, enough to cover the ten different digits. Here we are interested in using an 8-segment display for some Greek letters. We want it to be able to show eight different letters, namely A, B, ,,E,Z,H, and . For example, to show A, all the display segments, except o and p, should be lit up, giving the pattern 8 . In detail, we want the eight different letters displayed respectively as: Since there are eight letters, we need three input wires, modelled as propositional variables P,Q, and R. We will need to decide on a suitable encoding of the eight letters. One possibility encoding of the eight letters is to let A correspond to input 000 (that is, P=Q=R=f ), B to 001 (that is, P=Q=f and R=t ), etc. If we do that, we can summarise the behaviour of each input combination in the table below: Each of the eight segments ip can be considered a propositional function of the variables P,Q, and R. This kind of display can be physically implemented with logic circuitry, using circuits to implement a Boolean function for each of the outputs. Here we assume that only three types of logic gates are available: An and-gate takes two inputs and produces, as output, the conjunction () of the inputs. Similarly, an or-gate implements disjunction (). Finally, an inverter takes a single input and negates it (). We can specify such a circuit by writing down the Boolean equations for each of the outputs ip. For example, segment i is turned off (is false) when the input is 011, 110, or, 111. So, i can be captured as (PQR)(PQR)(PQR). For efficiency reasons, we often want the circuit to use as few gates as possible. For example, the above equation for i shows that we can implement this output using fifteen gates. But i=(PQR)(PQR)(PQR) is an equivalent implementation, using fewer gates. Moreover, the eight functions might be able to share some circuitry. For example, if we have already implemented a sub-circuit defined by u=QR (introducing u as a name for the sub-circuit), then we can define i=(Pu)(PQR)(Pu), and we may be able to re-use u while implementing the other outputs (rather than duplicating the same gates). In some cases, it may even be feasible to design a circuit that is not minimal for a given function, but provides a minimal solution when all eight functions are designed. Task 3A. Design such a circuit, using as few gates as possible. You can define any number of sub-circuits to help you reduce the gate count (simply give each a name). Submission and Marking: Your answer should be submitted on Grok. Submit a text file circuit.txt consisting of one line per definition. This file will be tested automatically, so it is important that you follow the notational conventions exactly. We write as - and as +. We write as ., or, more simply, we just leave it out, so that concatenation of expressions denotes their conjunction. Here is an example set of equations (for a different problem): # An example of a set of equations in the correct format: i=QR+QR+PQR j=u+P(Q+R) k=P+(QR) 1=u+Pi u=PQ #u is an auxiliary function introduced to simplify j and l Empty lines, and lines that start with '#', are ignored. Input variables are in upper case. Negation binds tighter than conjunction, which in turn binds tighter than disjunction. So the equation for i says that i=(QR)(QR)(PQR). Note the use of a helper function u, allowing j and l to share some circuitry. Also note that we do not allow any feedback loops in the circuit. In the example above, l depends on i, so i is not allowed to depend, directly or indirectly, on l (and indeed it does not)
