будемо обчислювати функцію , задану співвідношенням (тут означає побітове додавання за модулем 2). Тоді значення можна отримати так: .
Щоб можна було обчислювати функції, задані булевими схемами в повному базисі, недостатньо взяти базис для оборотних схем з перестановок на двох бітах. Виявляється, що будь-яка перестановка на двох бітах є лінійною функцією (при природному ототожненні безлічі і поля з двох елементів ): , де , , < span align = "justify">, , , . Тому всі функції, обчислювані оборотними схемами в базисі з перестановок на двох бітах, є лінійними.
А от перестановок на трьох бітах вже достатньо, щоб реалізувати будь-яку функцію. При цьому не обов'язково використовувати всі перестановки, досить включити в базис лише дві функції - заперечення і елемент Тоффолі . При цьому мається на увазі реалізованість у розширеному сенсі, тобто можна брати напрокат біти в стані 0 і повертати їх після закінчення обчислень в тому ж стані.
Завдання 6.1. Доведіть для оборотних схем повноту базису, що складається із заперечення і елемента Тоффолі. p align="justify"> Лемма 6.1. Нехай функція реалізується булевої схемою розміру в деякому базисі . Тоді можна реалізувати функцію оборотною схемою розміру в базисі { , що складається з функцій ( ), а також функції .
Зауваження 6.1. Крім "корисного" відповіді схема, зазначена у формулюванні леми, виробляє "сміття" .
Зауваження 6.2. Змістовний сенс операції - оборотне копіювання біта (якщо початкове значення одно ). У літературі ця операція зазвичай називається Controlled NOT з причин, які стануть ясними з подальшого.
Зауваження 6.3. Застосовуючи функцію можна міняти біти місцями в запису. Зверніть увагу, що для перестановок бітів достатньо також мати на базисі , так як
В
Доказ. Візьмемо схему, яка обчислює
