Доказательство. Пусть R и Q - символы, которые не встречаются среди символов алфавитов систем P1 и P2.

Пусть R и Q - символы, которые не встречаются среди символов алфавитов систем P ₁ и P ₂.

1. Определим систему P_U. Основной алфавит и алфавит переменных этой системы получаются объединениями основных алфавитов и алфавитов переменных систем P ₁ и P ₂.

Вспомогательный алфавит системы P_U состоит из символов вспомогательных алфавитов для P ₁ и P ₂, а также символов R и Q.

Множество продукций системы P_U состоит из продукций, получаемых из продукций P ₁ приписыванием всем образцам слева символа R, а также продукций, получаемых из продукций системы P ₂ с помощью аналогичного приписывания символа Q.

Кроме того, в P_U добавлены продукции:

и .

Покажем, что в системе P_U выводятся те и только те слова, которые принадлежат W ₁ W _2.

Это следует из того, что некоторое слово x выводится в системе P_U тогда и только тогда, когда в этой системе выводится либо слово Rx, либо слово Qx.

Последнее равносильно тому, что x выводится либо в P ₁, либо в P ₂. Поэтому в P_U выводится множество слов W ₁ W ₂.

 

2. Определим систему Поста P_I.

Алфавиты этой системы определяются так же, как это было определено для системы P_U.

Продукции системы P_I получаются из продукций P ₁ и P ₂ приписыванием ко всем образцам в них слева символов R и Q соответственно.

К этим продукциям добавляется еще одна

.

Видно, что в системе P_I выводятся такие и только такие слова x, которые могут быть выведены как в P _1, так и в P ₂.

Поэтому множество слов, выводимых в системе P_I, равно
W ₁ W ₂.