Реализация функций формулами
Эквивалентность функций
По таблицам 2 и 3 легко заметить, что некоторые функции никак не зависят от значений некоторых своих аргументов. Так, например, функции g1, g4, f1, f16 не зависят от значений любого из аргументов, это константы ноль и единица. Функции f4 и f13 не зависят от значений аргумента у, а функции f6 и f11 – не зависят от аргумента х. Это позволяет выразить их как функции меньшего числа аргументов путем удаления аргумента, не влияющего на значения функции. Такой аргумент называют несущественной переменной для функции.
В противовес несущественным переменным, аргументы, от значений которых существенно зависят значения функции, называются существенными переменными. Таким образом, если переменная xi является существенной для функции f(x1,x2,…,xn), то обязательно существует такой набор значений остальных переменных a1, a2,…, ai-1, ai+1, ai+2,…, an, что значение функции при xi=1 не равно значению функции при xi=0, т.е. 
. Для несущественной переменной такого набора не существует.
Две функции f1 и f2 называются эквивалентными или равными (обозначается это традиционно f1 = f2), если одна может быть получена из другой путем удаления или введения несущественной переменной.
Процедура удаления несущественной переменной xi на практике заключается в удалении всех строк вида: a1, a2,…, ai-1, 1, ai+1,…, an (т.е. таких строк, где переменная xi равна 1) и столбца xi из таблицы истинности функции. Введение несущественной переменной – обратный процесс.
Пример: пусть функция f(x,y,z) задана следующей таблицей истинности:
Таблица 1
| x | y | z | f(x,y,z) | |
| ¨ | ||||
| ¨ | ||||
| ¨ | ||||
| ¨ |
Из таблицы 4 видно, что значения функции не зависят от значений переменной у, поскольку на всех фиксированных наборах значений для x и z: (0,0), (0,1), (1,0) и (1,1), – значения функции при у=0 и у=1 одинаковы. Тем самым, у – несущественная переменная, и её можно удалить. Для этого вычеркнем из таблицы 4 все помеченные строки, где у=1, и столбец у. Оставшиеся строки и столбцы таблицы будут определять функцию от двух переменных: х и z. Оформим результат в виде новой таблицы 5. Эта таблица является таблицей истинности элементарной функции. Это импликация. Итак, исходная функция эквивалентна импликации.
Таблица 2
| x | z | f(x,z) |
Рассмотрим теперь процедуру включения несущественной переменной. Для этого в таблицу 5 добавим новый столбец у, расположив его между столбцами х и z, и 4 новых строки: две в середине и две в конце таблицы. Скопируем значения переменных х и z, а также значения функции из двух верхних строк в добавленные ниже них, и из двух следующих строк в последние две. Заполним значения в столбце у так, чтобы в старых строках оно было равно 0, а в добавленных – 1. Получим таблицу истинности эквивалентной функции от большего числа переменных, совпадающую с таблицей 4.
Реализация функций формулами
Классическое определение формулы алгебры логики вводится по шагам:
любая пропозициональная переменная является формулой;
если А формула, то выражение 
или 
тоже формула;
если А и В – формулы, то выражения вида (А&В), (АÚВ), (А®В), (АºВ) и прочие, где между А и В стоит пропозициональная связка, отличная от отрицания, – тоже формулы;
ничто иное не является формулой.
Формулы из пункта 1 называют элементарными. Формулы А и В из пунктов 2 и 3, если они не элементарны, называют подформулами составных формул.
При записи формул используются скобки для выделения подформул и указания порядка логических операций. В некоторых случаях скобки могут опускаться, это упрощает запись, делает её компактней. О соглашениях о бесскобочной записи формул будет сказано ниже.
Примеры формул:
1) 
2) 
3) 
4) выражение вида 
формулой не является.
Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n+s, а число строк – 2n. При этом последний столбец этой таблицы будет представлять значения формулы.
Для примера рассмотрим построение полной таблицы истинности формулы . Разделим её на подформулы: f1=Øx, f2=f1Úy, f3=f2®z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 6.
Таблица 3
| x | y | z | f1 | f2 | f3 |
В последнем столбце таблицы 6 находятся значения исходной формулы.
Сокращенная таблица истинности строится непосредственно под формулой. Для этого выписывают саму формулу, затем под именами переменных записывают столбцы их значений, а под каждой логической связкой – столбец результатов соответствующей логической операции.
Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 7.
Таблица 4
| ((Ø | x | Ú | y) | ® | z) |
 0
|
Внизу таблицы стрелками указаны участвующие в операции столбцы, номером в кружочке отмечен порядок выполняемых действий. Столбец результатов отмечен номером 3. Нетрудно заметить, что он совпадает с последним столбцом таблицы 6, но этого и следовало ожидать, поскольку способ оформления вычислений не должен оказывать влияния на результаты.
Из рассмотренных примеров видно также, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Эта функция соответствует формуле или, как говорят, реализуется формулой, про формулу в этом случае говорят, что она реализует функцию.
Пусть функция f(х1,х2,…,хn) реализуется формулой U(х1,х2,…,хn). Т.к. функция f может иметь несущественные переменные, то справедливо считать, что формула U реализует любую функцию, эквивалентную f. Если xi – несущественная переменная для функции f, то функцию f можно заменить функцией g путем удаления несущественной переменной. Тогда формула U1, полученная из формулы U отождествлением xi с любой из оставшихся переменных, будет реализовывать функцию g.
Для подтверждения этого факта рассмотрим формулу: 
. Вычислим значения этой формулы. См. таблицу 8.
Таблица 5
| ((z | & | (x | ® | y) | Ú | (Øy | ® | Øx)) |
 1
|
Результат находится в столбце, отмеченном номером 4. Реализуемая формулой функция приведена в таблице 9. Эта функция имеет несущественную переменную z. Удалив эту переменную, получим функцию g(x,y), см. таблицу 10.
Таблица 6
| x | y | z | f(x,y,z) |
Таблица 7
| x | y | g(x,y) |
Далее отождествим в исходной формуле переменную z с переменной у. При этом будет получена новая формула: 
. Построим таблицу истинности этой формулы. См. таблицу 11.
Таблица 8
| ((у | & | (x | ® | y) | Ú | (Øy | ® | Øx)) |
| 1
|
И, как видно из таблицы 11, новая формула реализует функцию g(x,y).
Если функция fÎP2 реализуется формулой U[f1,f2,…,fs], сконструированной из функций f1,f2,…,fsÎP2, то функция f называется суперпозицией функций f1,f2,…,fs или говорят, что функция f получена с помощью операции суперпозиции из функций f1,f2,…,fs.