The inevitable variability within electronic devices causes strict constraints on operation, reliability and scalability of the circuit design. However, when a compromise arises among the different performance metrics, area, time and energy, variability then loosens the tight requirements and allows for further savings in an alternative design scope. To that end, unconventional computing approaches are revived in the form of approximate computing, particularly tuned for resource-constrained mobile computing. In this paper, a proof-of-concept of the approximate computing paradigm using memristors is demonstrated. Stochastic memristors are used as the main building block of probabilistic logic gates. As will be shown in this paper, the stochasticity of memristors' switching characteristics is tightly bound to the supply voltage and hence to power consumption. By scaling of the supply voltage to appropriate levels stochasticity gets increased. In order to guide the design process of approximate circuits based on memristors a realistic device model needs to be elaborated with explicit emphasis of the probabilistic switching behavior. Theoretical formulation, probabilistic analysis, and simulation of the underlying logic circuits and operations are introduced. Moreover, the expected output behavior is verified with the experimental measurements of valence change memory cells. Hence, it is shown how the precision of the output is varied for the sake of the attainable gains at different levels of available design metrics. This approach represents the first proposition along with physical verification and mapping to real devices that combines stochastic memristors into unconventional computing approaches.