Build logic gates out of dominoes.
Start off by showing this video from Numberphile in whole or in part. In it is a demonstration of how to use dominoes to model logical operations of a computer. It begins with a simulation of an
AND gate and writes out its corresponding truth table. This is followed by the same process with
XOR, which then allows for the construction of a half adder and in conclusion a full adder. (You may also share this video with students, which contains an elaborate, 10000-domino construction. Per the YouTube description, "The result was a Domino Computer capable of automatically adding numbers. It can take any two four-digit binary numbers and return the five-digit binary sum.")
Then challenge students to build elementary logic gates themselves (you might need a lot of dominoes, but I bet it would be worth it in the long run). You could start by having them come up with designs for
XOR, etc. on their own. Depending on how this goes, consider using this resource to help guide the design of gates in dominoes.
After students create these gates, consider giving them longer Boolean expressions to model and solve using dominoes. This would also be a clever way of showing how DeMorgan's Law works.
The level of complexity knows almost no bounds with this approach. I could see some students, especially those with a love for computer science, who would thrive doing a hands-on, constructive activity like this.