Molecular circuits capable of processing temporal information are essential for complex decision making in response to both the presence and history of a molecular environment. A particular type of temporal information that has been recognized to be important is the relative timing of signals. Here we demonstrate the strategy of temporal memory combined with logic computation in DNA strand-displacement circuits capable of making decisions based on specific combinations of inputs as well as their relative timing. The circuit encodes the timing information on inputs in a set of memory strands, which allows for the construction of logic gates that act on current and historical signals. We show that mismatches can be employed to reduce the complexity of circuit design and that shortening specific toeholds can be useful for improving the robustness of circuit behavior. We also show that a detailed model can provide critical insights for guiding certain aspects of experimental investigations that an abstract model cannot. We envision that the design principles explored in this study can be generalized to more complex temporal logic circuits and incorporated into other types of circuit architectures, including DNA-based neural networks, enabling the implementation of timing-dependent learning rules and opening up new opportunities for embedding intelligent behaviors into artificial molecular machines.