Доказать теорему о том, что отношение => для языка Exp является функцией. | MetodPro.ru

Реклама на сайте

Доказать теорему о том, что отношение => для языка Exp является функцией.


3) Доказать теорему о том что отношение => для языка Exp является функцией
Теорема. Отношение => для языка Exp является функцией
•    Для всех выражений е I Exp справедливо, что если e => v   и   e => v’ , то      v = v’.       Это P(e).
•    Для доказательства применим структурную индукцию. Нужно доказать:
        1) P(n) для всех чисел n.
        2) При условии истинности P(e) и P(e’) доказать P(e op e’) .

Первый случай
•    Если n => v, а для вычисления v  мы могли использовать только правило CR то n = v .
•    Если n => v’, то из тех же соображений
получим n = v ’ .
•    Из n = v  и  n = v ’ следует, что v = v ’ .
Второй случай
•    Если e’ op e” => v, а для вычисления v  мы могли использовать только правило OpR , значит e’=>m’, e”=>m” а v = Ap(opNum, m’, m”) , где m’, m” - некоторые числа.
•    Если e’ op e” => v’, а для вычисления v’  мы могли использовать только правило OpR , значит e’=>k’, e”=>k” а v’ = Ap(opNum, k’, k”) , где k’, k” - некоторые числа.
•    Из P(e’) и P(e”) получим, что m’=k’, m”=k” .
•    А поскольку opNum - функция, получим v=v’ .



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем