значень вихідних змінних результатом обчислення є .
Схема називається формулою, якщо кожна допоміжна змінна використовується в правій частині присвоювань тільки один раз. (Звичайні математичні формули саме так задають послідовність присвоювань: "всередині" формул не прийнято використовувати посилання на їх частини або інші формули.) p align="justify"> Схему можна також представляти у вигляді орієнтованого ациклического графа, у якого вершини вхідний ступеня 0 (входи) позначені вихідними змінними; інші вершини (функціональні елементи) позначені функціями з базису (при цьому вхідні ступінь вершини повинна збігатися з кількістю аргументів її позначки); ребра помічені числами, що вказують номери аргументів; вершини вихідний ступеня 0 (виходи) позначені змінними, що описують результат роботи схеми. Обчислення на графі визначається індуктивно: як тільки відомі значення всіх вершин , з яких ведуть ребра в дану вершину , вершина отримує значення , де - базисна функція, якою позначена вершина. При переході до графа схеми ми опускаємо несуттєві присвоювання, які жодного разу не використовуються на шляху до вихідних вершин, так що вони ніяк не впливають на результат обчислення.
Базис називається повним, якщо для будь-якої булевої функції є схема в цьому базисі, що обчислює . Ясно, що в повному базисі можна обчислити довільну функцію (таку функцію можна представити як упорядкований набір з булевих функцій).
Булева функція може бути задана таблицею значень. Наведемо таблиці значень для трьох функцій
В
(заперечення, диз'юнкція, кон'юнкція), що утворюють повний базис, який будемо вважати стандартним. Надалі маються на увазі схеми саме в цьому базисі, якщо явно не вказано небудь інше. br/>В
Кон'юнкція і диз'юнкція визначаються для довільного числа булевих змінних аналогічним чином: кон'юнкція дорівнює 1 тільки тоді, коли всі аргументи рівні 1, а диз'юнкція дорівнює 0 тільки тоді, коли всі аргументи рівні 0. У стандартному базисі вони очевидним чином обчислюються схемами (і навіть формулами) розміру .
Теорема 1.1. Базис - повний.
Доказ. Літералом будемо називати змінну або її заперечення. Кон'юнкція літералів (це схема і навіть формула) легко уявити функцію , яка приймає значення 1 рівно один раз: при . Якщо , включаємо в кон'юнкцію змінну
