Порядок подстановки задается формулой.

Всякая формула задает способ вычисления функции, если известны значения переменных.

Пример 2.4.

Построим таблицу значений функции

Вычисление функции f(x₁ х₂, х₃)

Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций:

Графы и деревья

При изучении дискретных систем, в частности систем преобразования информации, требуется строить математические модели, описывающие структуру или функционирование таких систем.

Одним из наиболее важных понятий, относящихся к структуре дискретных систем, является понятие графа. Это понятие, описывающее структуру связей между отдельными частями системы, в силу своей общности используется во многих математических моделях.

Блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операторы, а дуги указывают переходы между ними. Другие примеры графов: узлы и соединения в электрической цепи, схема дорог, множество предприятий с указанием двухсторонних связей между ними, группа людей с указанием их психологической совместимости, структура управления с указанием объектов и их подчиненности друг другу и т.д.

Графом G (в широком понимании) называется любая пара (X, А), где Х= {х₁ х₂,...} - множество элементов любой природы, а А = {а₁, а₂,...} - семейство пар элементов из X, причем допускаются пары вида (х_i х,) и одинаковые пары. Если пары в X рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным {орграфом).

Элементы множества X называются вершинами графа, а пары из А - его ребрами; в орграфе они называются ориентированными ребрами или дугами.

Таким образом, граф G задается множеством точек или вершин х₁ х₂,..., х_n (которое обозначается через X) и множеством линий или ребер а₁, а₂,..., а_т (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х.A).

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом. В случае когда G = (X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G = (X, А).

Если дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 4.1(а) обозначение (х₁, х₂) относится к дуге a₁, а (х₂, х₁) - к дуге а₂.

Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = {X, Г).

Для графа на рисунке (а) имеем Г(х₁) = {х₂, x₅}, т. е. вершины x₂и x₅ являются конечными вершинами дуг, у которых начальной вершиной является x₁

Г(х₂)={х₁,х₃},

Г(х₃) ={ х₁ },

Г(х₄) = Ø - пустое множество,

Г(х₅)={х₄}.

А) ориентированный граф;