ОПРЕДЕЛЕНИЕ. Слово n+1 в алфавите (A È V) выводится из слов 1,

Слово _n+1 в алфавите (A È V) выводится из слов
₁, . . . , _n в этом же алфавите применением продукции
p = , если существует такая подстановка Q, содержащая все различные символы переменных, входящих в образцы t₁, ... , t_n+1, что " i = 1, ... , n+1(t_iQ = _i).

В пределах одной продукции одинаковые символы переменных понимаются одинаково и при всяком применении продукции заменяются одинаково. Процесс получения слова _n+1­ из слов ₁, . . . , _n с помощью продукции p называется шагом вывода, а слово _n+1­ называется применением продукции p.

Если продукция является аксиомой, то любое применение её заключения безусловно выводимо и может применяться в дальнейших рассуждениях или вычислениях.

Одинаковые символы переменных в различных продукциях не связаны между собой.

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

Упражнение. Пусть основной и вспомогательный алфавиты состоят из символов 0 и 1, а алфавит переменных состоит из символов x, y. Привести пример продукции p = , где t_n+1 содержит только такие символы переменных, которые входят в t₁, . . . , t_n, и последовательности слов ₁, . . . , _n, из которых с помощью подстановок Q₁ и Q₂ выводятся разные слова.