4
Jaka jest minimalna wielkość obwodu, który oblicza PARYSTOŚĆ?
Jest to klasyczny wynik, że każdy obwód wachlarza 2 AND-OR-NOT, który oblicza PARITY ze zmiennych wejściowych, ma rozmiar co najmniej i jest ostry. (Definiujemy rozmiar jako liczbę bramek AND i OR). Dowodem jest eliminacja bramki i wydaje się, że zawodzi, jeśli pozwolimy na dowolne wbicie. Co jest znane w tej …