DNA strand displacement has been widely used for the design of molecular circuits, motors, and sensors in cell-free settings. Recently, it has been shown that this technology can also operate in biological environments, but capabilities remain limited. Here, we look to adapt strand displacement and exchange reactions to mammalian cells and report DNA circuitry that can directly interact with a native mRNA. We began by optimizing the cellular performance of fluorescent reporters based on four-way strand exchange reactions and identified robust design principles by systematically varying the molecular structure, chemistry and delivery method. Next, we developed and tested AND and OR logic gates based on four-way strand exchange, demonstrating the feasibility of multi-input logic. Finally, we established that functional siRNA could be activated through strand exchange, and used native mRNA as programmable scaffolds for co-localizing gates and visualizing their operation with subcellular resolution.