Контрольные вопросы

1) Расскажите своими словами, что представляет собой алгебра.

2) Что является носителем алгебры?

3) Чем отличается одноосновная алгебра от многоосновной?

4) Сформулируйте формальное определение алгебры.

5) Что такое редукт, расширение, приращение алгебры?

4.3. Алгебры слов

Для любой сигнатуры  существует особая алгебра W_ , называемая алгеброй слов, или алгеброй термов. Ее элементы принято называть базисными термами. В соответствии с количеством основ сигнатуры алгебры все множество базисных термов разбивается на подмножества термов каждой из этих основ. Множества базисных термов основы s S определяется следующим образом:

• все нуль-арные знаки операций (константы) основы s называются базисными термами основы s;

• для всех знаков операции  _us и всех базисных термов t₁, t₂, … , t_n, принадлежащих основам s₁ S, s₂ S, … , s_n S,  (t₁, t₂, … , t_n) является базисным термом основы s.

Термы алгебры слов часто называют выражениями, а входящие в них знаки операций – конструкторами выражений. Для сигнатуры алгебры множеств базисными термами основы setofnat будут empty, insert(empty, zero), insert(insert(empty, zero), succ(zero)), … . В той же сигнатуре базисными термами основы nat будут zero, succ(zero), succ(succ(zero)), … . Для сигнатуры алгебры чисел множество «чисел» алгебры слов будет состоять из zero, one, plus(zero, zero), plus(zero, one), … . Каждое применение операции образует выражение «большей длины» из выражения «меньшей длины». Например, применение операции times к аргументам zero и plus(zero, one) приводит к терму times(zero, plus(zero, one)). Такие выражения можно рассматривать как строки символов, а их конструкторы – как операции над строками, использующими операцию конкатенации строк.

Пусть Х является S – индексированным множеством, элементы которого называются переменными. Тогда можно ввести расширение алгебры слов, с которым постоянно имеют дело программисты, а именно алгебру слов на множестве переменных Х_s основы s. Множество элементов этой алгебры составляют термы, использующие данные переменные. Например, если х – переменная из множества X_number, то наряду с plus(zero, zero) термом алгебры будет и plus(x, zero). И в этой алгебре все термы по-прежнему связываются с определенными основами, а знаками операций по-прежнему являются конструкторы выражений. Однако в алгебре слов на множестве переменных Х множество базисных термов сигнатуры расширено множеством термов с переменными. Определение терма с переменными основы s, или просто терма, получается расширением определения базисного терма:

• все базисные термы основы s являются термами основы s;

• все переменные x X_s являются термами основы s;

• для всех знаков операции   _us и всех термов t₁, t₂, … , t_n, основы s  (t₁, t₂, … , t_n) является термом основы s.

Пусть А есть некоторая  - алгебра, а V = (V_s : X_s  A_s)_sS – семейство функций оценки, сопоставляющих элемент V_s(х) A_s каждой переменной основы s. Тогда каждый терм алгебры слов может быть «проинтерпретирован», или «вычислен» в этой алгебре. Это означает, что посредством последовательного исполнения функций V_s , осуществляющих привязку переменных к конкретным значениям, и функций _us, сопоставленным знакам операций _us, входящим в данный терм, вырабатывается некоторый объект соответствующей основы. Порождение элемента носителя А_s для терма t основы s в алгебре А будем называть интерпретацией, или вычислением терма t в алгебре А и обозначать t^A. Например, пусть имеется алгебра: number = {0, 1, 2, 3}, succ : функция (n : number) number = n + 1 и функции оценки {V(x)=0, V(x)=1, V(x)=2}. Пусть имеется терм t=succ(x). Тогда применение пар операций приведет к следующим интерпретациям

V : x=0 V : x=1 V : x=2

succ(0)=1 succ(0)=2 succ(2)=3.