# How to represent multiple-output logic circuits in tree-based genetic programming

Consider the following digital logic circuit, which has multiple inputs and one output:

The logic circuit above can be represented in tree form:

This tree representation could then be used in a tree-based genetic programming framework to evolve the circuit. For example, this tree could be represented as a Lisp list (or (and A B) (not C)), which could then be used with the Little LISP genetic programming framework from John R. Koza's Genetic Programming textbook.

However, I now want to deal with digital logic circuits that have more than one output. For example, in the half-adder circuit below, there are two outputs $$S$$ and $$C$$, each of which is affected by both inputs $$A$$ and $$B$$.

(Image source: SICP by Abelson et al. Section 3.3.4 A Simulator for Digital Circuits. CC BY-SA 4.0)

How do I represent and evolve such a circuit in tree-based genetic programming? How do I represent the circuit above as a tree that could then be used to evolve the circuit using a tree-based genetic programming framework?

• Maybe you can do this with a custom function that gets $s$ and $c$ as input and that would produce the final return type, i.e. a binary vector.
– nbro
Feb 16, 2022 at 18:56
• @nbro Thank you for the suggestion, but how would such a tree look like exactly? With the binary vector return type, $S$ and $C$ can each be influenced by either $A$ or $B$ but not both. That is the consequence of a tree representation. Perhaps I am not fully understanding your suggestion because I don't see how it could represent things like half-adders (shown in the question) and flip-flops.
– Flux
Feb 17, 2022 at 5:39
• I didn't realise that you didn't want both A and B to affect both S or C, because you didn't explain this in the post. In any case, my suggestion was more about how you could possibly deal with 2 outputs. You can could create a function like id(s, a) = [s, a], and the output of the circuit/tree is of type list. Here, id is the custom function that you need to add to you function set, in addition to and, or and not. If I have some time, later, I will try to create a simple proof-of-concept that illustrates my idea.
– nbro
Feb 17, 2022 at 9:41
• @nbro Sorry for not making that clear. In the half-adder circuit shown in the question, The output at $S$ is affected by both inputs $A$ and $B$. Similarly for the output at $C$.
– Flux
Feb 17, 2022 at 9:46
• Ok, that's fine. My suggestion above still applies.
– nbro
Feb 17, 2022 at 9:49