Спирина, М.С. Дискретная математика

f i x ) = gix). Проверить эквивалентность двух функций можно с помощью таблиц истинности. Преобразование булевой функции F\ с применением заданных эквивалентностей (формул) дает н о ­ вую функцию F2, эквивалентную исходной. Формулы. Как известно, композицией функций f , f 2, н а ­ зывается функция f полученная с помощью подстановок этих функций друг в друга и переименования переменных. Тогда форму­ лой называется выражение, соответствующее этой композиции, описывающее ее. Всякая формула, выражающая некоторую функ­ цию / как суперпозицию других функций (подфункций), задает способ ее вычисления в том случае, если известны способы вычис­ лений этих подфункций. Каждому набору значений аргументов формула ставит в соответствие значение функции, т.е. может слу­ жить способом задания и вычисления логической функции. Гово­ рят, что формула представляет или реализует соответствующую логическую функцию. Практически композицией двух булевых функ­ ций / (от п переменных) и g (от т переменных) будет функция И(х), такая, что Vx € Вп И(х) = ( g i f , f m)(x) = g ( f ( x ) , ..., f m(x)). В процессе формализации учтем следующие правила. • Простому высказыванию соответствует элементарная формула. • Для построения формулы, соответствующей составному вы ­ сказыванию, надо: выделить все элементарные высказывания и логические связ­ ки, соответствующие структуре высказывания; заменить их соответствующими символами; расставить скобки в соответствии с логической структурой высказывания. Для упрощения операций в логике высказываний принято не заключать в скобки формулы, стоящие под знаком отрицания и не являющиеся частями других формул. Пусть дано множество (конечное или бесконечное) некоторых аргументов (хь ..., х„, ...) и исходных функций { f , / 2, ..., / т }, зависящих от них. Формулы могут состоять из самих аргументов хь ..., х„, ... или включать в себя другие функции (или подфор­ мулы). Тогда, например, f ( x b х2, х3) — булева функция или ф о р ­ мула, непосредственно зависящая от аргументов х, (/ = 1 , 2 , 3), а f \ ( f i i x u хзУ, / ( х 2); f ( x \)) — сложная функция, образованная су ­ перпозицией функций / (одного переменного), f (трех перемен­ ных) и / 2 (двух переменных). Всякая формула, выражающая функцию / как суперпозицию других (исходных) функций, одновременно задает и способ ее вычисления. Сначала вычисляются значения подформул, а затем сама формула, согласно установленному порядку действий. Булевы функции одной переменной. При п = 1, согласно общей формуле, существуют четыре различные булевы функции. Поскольку при упорядоченных (по принципу целого двоичного числа) аргу- 135