Knill, Laflamme, and Milburn recently showed that non-deterministic quantum logic operations could be performed using linear optical elements, additional photons (ancilla), and post-selection based on the output of single-photon detectors [Nature 409, 46 (2001)]. Here we report the experimental demonstration of two logic devices of this kind, a destructive controlled-NOT (CNOT) gate and a quantum parity check. These two devices can be combined with a pair of entangled photons to implement a conventional (non-destructive) CNOT that succeeds with a probability of 1/4.