Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

12 Суперпозицией функций f 1 ,…,f m называется функция f , полученная с помощью подстановок этих функций друг в друга, а формулой называется выражение, описывающее эту суперпозицию. Пусть дано множество исходных функций S=  f 1 ,…,f m ,…  . Символы переменных x 1 ,…,x n ,… будем считать формулами глубины 0 . Формула F имеет глубину k+1 , если F имеет вид f i (F 1 ,…,F n(i) ) , где f i  S n(i) – число аргументов f i , а F 1 ,…,F n(i) – формулы, максимальная из глубин которых равна k . F 1 ,…,F n(i) называются подформулами F ; все подформулы формул F 1 ,…,F n(i) также называются подформулами F . Например, f 2 (x 1 ,x 2 ) – это формула глубины 1 , а f 3 (f 1 (x 3 ,x 1 ), f 2 (x 1 ,f 3 (x 1 ,x 2 ))) – формула глубины 3 , содержащая одну подформулу глубины 2 и две подформулы глубины 1 . Если f 1 обозначает дизъюнкцию, f 2 – конъюнкцию, а f 3 – сложение по mod2 , то приведенная формула примет более привычный вид: ((x 3  x 1 )  (x 1 &(x 1  x 2 ))) (3.1) Все формулы, построенные описанным способом, т.е. содержащие только символы переменных, скобки и знаки функций из множества S называются формулами над S . Всякая формула, выражающая функцию f , как суперпозицию других функций, задает правило ее вычисления: для вычисления формулы необходимо вычислить значения всех ее подформул. Вычислим, например, формулу (3.1) на наборе x 1 =1, x 2 =1, x 3 =0 . Используя таблицу 2.3 получим x 3  x 1 =1; x 1  x 2 =0, x 1 &(x 1  x 2 )=x 1 &0=0; ((x 3  x 1 )  (x 1 &(x 1  x 2 )))=1  0=1. Таким образом, формула каждому набору значений аргументов ставит в соответствие значение функции и, поэтому, может служить наряду с таблицей способом задания и вычисления функции. По формуле, вычисляя ее на всех 2 n наборах, можно восстановить таблицу функции. О формуле, задающей функцию, говорят, что она реализует или представляет эту функцию.