Любая логическая функция может быть записана с помощью трех элементарных функций: инверсии (НЕ), дизъюнкции (ИЛИ), конъюнкции (И). Проведя преобразования записанной таким образом формулы, можно ее упростить, т.е. уменьшить число выполняемых при расчете операций. Однако такие преобразования с целью упрощения сами по себе не так уж просты, для их выполнения требуется опыт, надо ими часто заниматься. Поэтому порой при расчете вручную можно просто последовательно подставлять все возможные наборы переменных и определять для них значение функции. Это не очень сильно удлинит расчет. Но в вычислительной технике значения логической функции определяет не человек, а комбинационное устройство. Чтобы это устройство состояло из меньшего числа элементов, а сами элементы были в максимальной степени однотипными, необходимо преобразовать реализуемую логическую функцию в определенную форму. В алгебре логики различают несколько форм, которым соответствуют наиболее рациональные построения схем комбинационных устройств.
Логические функции, представляющие собой дизъюнкции отдельных членов, каждый из которых, в свою очередь, есть некоторая функция, содержащая только конъюнкции и инверсии, называются логическими функциями дизъюнктивной формы. Форма представления дизъюнктивной функции, в которой инверсия применяется лишь непосредственно к аргументам, но не к более сложным функциям этих аргументов, называется дизъюнктивной нормальной формой (ДНФ) представления функций. Если же каждый член ДНФ от п аргументов содержит все эти п аргументов (с инверсией или без нее), то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ).
Логические функции, представляющие собой конъюнкцию отдельных членов, каждый из которых есть функция, содержащая только дизъюнкции и инверсии, называются логическими функциями конъюнктивной формы. По аналогии с дизъюнктивными формами возможны конъюнктивные нормальные формы (КНФ) и совершенные конъюнктивные нормальные формы (СКНФ)
Возможность записи функций в дизъюнктивных и конъюнктивных формах определяется исходя из следующего. Рассмотрим произвольную логическую функцию от п аргументов типа конституенты единицы. Как указывалось ранее, конституента единицы полностью определяется заданием набора, обращающего ее в 1. В этом наборе некоторые аргументы могут быть равны 1, а остальные равны 0. Составим конъюнкцию от всех п аргументов, причем те из аргументов, которые в указанном наборе равны 0, возьмем с инверсией, а аргументы, равные 1, — без инверсии. Если все аргументы будут соответствовать заданному набору, то при нем функция обратится в конъюнкцию п единиц и будет равна 1. Для всех остальных наборов хотя бы один член конъюнкции, а значит, и вся конъюнкция обратится в 0. Таким образом, произвольная функция от п аргументов типа конституенты единицы может быть выражена через конъюнкцию и инверсию.
Переход от табличного задания функции к записи в виде СДНФ выполняется в такой последовательности:
в таблице задания функции выбираются все наборы аргументов, при которых функция обращается в 1;
выписываются конъюнкции, соответствующие этим наборам аргументов. Если аргумент х,- входит в данный набор как 1, то он вписывается без изменения в конъюнкцию, соответствующую данному набору; если же х,- входит в данный набор как 0, то в соответствующую конъюнкцию вписывается его отрицание;
все полученные конъюнкции соединяются между собой знаками дизъюнкции.
Аналогично выполняется переход от табличного задания функции к записи в виде СКНФ:
в таблице задания функции выбираются все наборы аргументов, при которых функция обращается в 0;
выписываются дизъюнкции, соответствующие этим наборам аргументов. Если аргумент х,- входит в данный набор как 0; он вписывается без изменения в дизъюнкцию, соответствующую данному набору; если же х, входит в данный набор как 1, то в соответствующую дизъюнкцию вписывается его отрицание;
все полученные дизъюнкции соединяются между собой знаками конъюнкции.
Выбор той или иной формы аналитической записи определяется видом таблицы заданной функции. Если большинство значений данной функции 0, то выгодно записывать ее в СДНФ, в противном случае более экономную запись дает СКНФ.
Таким образом, любую функцию алгебры логики можно записать в виде СДНФ или СКНФ, т.е. представить с помощью системы из трех элементарных функций: инверсии, дизъюнкции и конъюнкции. Существуют и другие системы функций, с помощью которых может быть выражена произвольная функция. Полная система функций, с помощью которой можно представить любую функцию от произвольного числа аргументов, называется базисом. Базис называют полным, если любая функция представима суперпозицией функций, составляющих рассматриваемый базис. Под суперпозицией функций понимают любую последовательность функциональных отношений из перечня функций, составляющих базис. Иными словами, из функций, составляющих базис, можно записать любую сложную функцию.
Базис из дизъюнкции, конъюнкции и инверсии не является минимальным. Поскольку конъюнкцию можно представить через инверсию и дизъюнкцию, то можно получить минимальный базис из дизъюнкции и инверсии. С другой стороны, дизъюнкцию можно представить через инверсию и конъюнкцию, т.е. получить минимальный базис из конъюнкции и инверсии.
Возможны и другие минимальные базисы, например из конъюнкции и инверсии. Каждая из функций Пирса и Шеффера также составляет полную систему и представляет собой минимальный базис. Благодаря тому, что любую, сколь угодно сложную логическую функцию можно реализовать с помощью малого числа типов логических операций (например, только дизъюнкции и инверсии), самые сложные электросхемы могут быть построены из однотипных элементов. Таких элементов потребуется очень много, но при массовом производстве они будут очень дешевы. К тому же наладить массовое производство всего одного или двух типов элементов значительно дешевле, чем большого числа типов. Особенно это важно при производстве больших интегральных схем.