Дискретно-непрерывная математика (стр. 47 )

b) Индуктивный переход. Пусть— функция из F и - выражения, являющиеся либо формулами над F, либо символами переменных (аргументов). Тогда выражение называется формулой над F.

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

Так как мы можем определить значение формулы А (опираясь на индуктивное определение формул) на любом наборе перемен­ных, то тем самым мы сопоставим этой формуле некоторую функ­цию т. е. по формуле, вычисляя ее на всех пm наборах, можно восстановить таблицу функции. Про функцию, сопостав­ленную формуле, говорят, что она реализуется этой формулой.

В отличие от табличного задания, реализация (представление) данной функции формулой не единственно. Например, в двузнач­ной логике штрих Шеффера можно представить формулами

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

Опираясь на понятие эквивалентности, можно описать основ­ные свойства элементарных функций. Как и в классической логике, функции обладают свойствами ассоциативности, ком-

мутативности, идемпотентности и дистрибутивны относительно друг друга. Ниже мы покажем, что посредством функций

и констант любую функциюиз Рп можно

представить в так называемой первой форме, являющейся аналогом совершенной д. н.ф. для функций алгебры логики (см. 1.3).

Если функция f реализуется формулой, которая составлена только из символов функций (а также символов переменных), то говорят, что функция f является суперпозицией функций а процесс получения функции f из называют операцией суперпозиции [Яблонский 1958].

Например, из элементарных функций посредством их

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

В итоге задание конкретной модели многозначной логики со­стоит в указании множества истинностных значений Vn, множества элементарных функций F и множества функций, полученных по­средством суперпозиции над F и реализуемых формулами. Эта мо­дель называется формульной моделью, а также п-значной логикой (см. [Кудрявцев 1982]). В кибернетике такие модели рассматрива­ются как управляющие системы. Элементарные функции при этом являются элементами, производящими определенные операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными задачами для формульной модели являются: задача об указании всех формул, реализующих заданную константу; зада­ча об эквивалентных преобразованиях; задача о сложности реали­зации; задача о минимизации и т. д.

7.2. Алгебра функций

Однако в зависимости от того, какие цели преследуются при изу­чении многозначной логики, по-разиому понимается, что собой представляет ее модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы. В отличие от универсальной алгебры, где носителем может служить множест­во произвольной природы, в теории функциональных систем носи­тель должен быть множеством функций, в то время как операции над этими функциями могут быть неалгебраического характера. Основные проблемы, стоящие перед теорией функциональных сис­тем были сформулированы в докладе СВ. Яблонского [Яблонский 1978]. Некоторые итоги подведены в работе [Куд­рявцев 1981], а также в [Марченков 2004].

Нас будут интересовать те функциональные системы, которые базируются на функциях многозначной логики с операцией супер­позиции, т. е. под функциональной системой мы будем понимать пару (Рп , С), где Рп есть множество всех функций п-значной логи­ки с заданной на нем операцией суперпозиции С. Наиболее яркие достижения в этой области относятся к двум взаимосвязанным те­мам: построение и анализ порождающих множеств и проблема полноты. Классические работы здесь принадлежат Э. Посту, , СВ. Яблонскому, , И. Розенбергу. Тщательное изложение всех основных результатов, начиная со ста­тьи Э. Поста [Post 1920], содержится в фундаментальной моногра­фии [Lau 2006], которая значится как базовый курс по конечнозначной логике.

7.2.1. Оператор замыкания, замкнутые классы и базисы

Операция суперпозиции порождает на Рп оператор замыкания. ПустьТогда, следуя (см. [Кузнецов 1959)],

множество всех функций, которые можно получить с помощью операции суперпозиции из F, называется замыканием F и обозна­чается посредством [F]. Таким образом, оператор замыкания опре­деляется на множестве всех подмножеств n-значных функций и ставит в соответствие каждому множеству F замыкание множества F, состоящее из всех функций, которые выразимы формулами, со­ставленными из функций множества F,

Операторобладает следующими свойствами—

произвольные множества n-значных функций):

(i) (рефлексивность),

(ii) (идемпотентность), .

(iii) влечет (монотонность),

(iv) Если система F1 является полной и то и

система F2 является полной. ;

Все эти утверждения следуют из определения оператора замыкания. Утверждение (iv) позволяет устанавливать полноту некото­рой системы, выражая с её помощью все функции другой системы, полнота которой уже установлена.

Множество F п-значных функций называется (функционально) замкнутым множеством (классом), если оно совпадает со своим замыканием, т. е. если F= [F].

Примеры.

1. Класс F = Рп, очевидно, является замкнутым классом.

2. Класс функций от одной переменной, очевидно, является замкнутым классом.

3. Класс функций от двух переменных не является замкнутым классом, поскольку функция от трех переменных, является

суперпозицией дизъюнкции. •

Говорят, что множество функций замкнуто относительно опе­рации суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это множество. Таким образом, замкнутость класса функций F означает собой сохранение при суперпозиции «наследственных» свойств этих функций. Пример (3) рак раз показывает, что свойство быть функцией от двух переменных не сохраняется при суперпозиции.

Пусть F — замкнутый класс и Говорят, что множество функций F1 порождает замкнутый класс F (или что F порождается множеством функций F1), еслиЕсли F1 порождает класс F,

то говорят также, что F1 полно в классе F. В случае, когда замкнутый класс F порождается конечным множеством функций, класс F называют конечно порожденным. Множество функций F1 называ­ется базисом, замкнутого класса F, если F1 порождает F и для любого подмножества F2 множества F1, отличного от F1, т. е. базисом является минимальная полная независимая система функций, удаление из которой любой функции делает систему неполной.

Хорошо известным примером полных в Р2 систем функций (использующихся при построении СДНФ и полинома Жегалкина) являются . Первая не является базисом Р2, а

вторая является таковым. В свою очередь, системаявляется

базисом класса линейных функций (см. ниже). Число функций, входящих в базис, называется рангом базиса.