A variety of technologies are being considered as possible replacements for CMOS. Many of the candidates, including nanoscale crossbar arrays, are characterized by high defect rates and inherently random interconnect and switching behavior. We present a novel logic synthesis technique for such nanoscale systems, using probability as the state variable. We encode signal values as the probability of obtaining a one versus a zero in a bundle of wires. This representation is much less compact than binary radix. However, complex operations can be performed with remarkably simple logic.  For instance, multiplication can be performed with a single AND gate. Also, because the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips).