Обсуждавшее выше понятие системы является общим и универсальным, т.е. может использоваться в различных отраслях человеческого знания. Наряду с ним в информатике и ряде других приложений используется понятие «формальная система»; оно отличается от общего понятия системы, подобно тому, как понятие математической модели отличалось от понятия модели вообще.
Формальная система - это математическая модель, задающая множество дискретных компонентов путем описания исходных объектов и правил построения новых компонентов из исходных и уже построенных.
Уточнения к определению:
1. Компонентами формальной системы является информационные представления материальных объектов, состояний, отношений и пр. Представления могут быть знаковыми (символическими) или графическими, но обязательно информационными. Таким образом, формализация (или построение формальной системы) - это замена реального прототипа ее формальным описанием, т.е. ее информационной моделью.
2. Компоненты формальных систем могут представлять комбинацию конечного числа исходных объектов - неделимых (простейших) элементов с определенным набором свойств. Множество видов таких элементов называется алфавитом системы. Число экземпляров элементов каждого вида может быть любым (в том числе бесконечным).
3. Правила построения новых компонентов могут иметь вид «условие - действие» («если имеющиеся объекты или компоненты удовлетворяют некоторым условиям, то для построения нового компонента необходимо выполнить такое-то действие»). Другим видом правил является «посылка - заключение» («если уже построены компоненты вида А1...Аn-1, то компонент Ап также считается построенным»). Новые компоненты называются выводимыми объектами (правильнее было бы их называть «выводимыми компонентами»).
4. Определение формальной системы во многом напоминают общее (интуитивное) определение алгоритма, данное в гл. 6. Это подобие не случайно и будет обсуждаться ниже.
Рассмотрим несколько примеров формальных систем.