Wir brauchen nur nicht, und und oder, da die Implikation und die Äquivalenz aus diesen resultiert. Außerdem können wir zeigen, dass die Negation unseren Ausdruck nicht in der AV-Anzahl größer machen kann, da nur eine Variable durch eine Variable mit einem nicht ausgedrückt wird.

Wichtig sind also nur und und oder, die beide vom Aufbau her gleich sind und zwar wird eine Variable (damit meine ich nicht eine AV sondern nur eine Stelle im Ausdruck, welcher eine AV oder eine weiteren Teilausdruck beinhalten kann, mir fällt grade das richtige Wort nicht ein) durch einen Ausdruck mit zwei Variablen, die mit einem und/oder verbunden sind ersetzt.

Die Induktion aufbauend auf i = 1 mit (p1 und p2) bzw (p1 oder p2) zeigt dann, das pro Induktionstiefe (i steht für die Teilausdrücke aus denen der Ausdruck aufgebaut ist) der Ausdruck um Maximal 1 AV erweitert werden kann.

Die Tiefe i des Ausdrucks ist endlich und die Anzahl der AV damit auch, denn diese ist dann i+1.