Основные математические понятия

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abc может служить схема

Процесс применения нормального алгоритма к произвольному слову V в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' -- слово, полученное на предыдущем шаге работы алгоритма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгоритма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая верхняя. Если эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R -- самое короткое, после чего работа алгоритма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид , то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R -- самое короткое, после чего слово RDSсчитается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге. Например, в ходе процесса применения алгоритма с указанной выше схемой к слову | * | | последовательно возникают слова | b * | ,ba | * | , a | * | , a | b * , aba | * , baa | * , aa | * , aa | c, aac, ac | и c | | , после чего алгоритм завершает работу с результатом | | . Другие примеры смотрите ниже. Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот -- любая машина Тьюринга эквивалентна некоторому нормальному алгоритму. Вариант тезиса Чёрча -- Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть «принципом нормализации». Нормальные алгоритмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгоритма идеи используются в ряде ориентированных на обработку символьной информации языков программирования -- например, в языке Рефал.

Вывод (лат. conclusio) -- процесс рассуждения, в ходе которого осуществляется переход от некоторых исходных суждений(предпосылок) к новым суждениям -- заключениям. Правила преобразования исходной системы предпосылок в систему заключений называются правилами вывода или правилами проведения умозаключений. Если вид посылок и заключений указан явно, то вывод называется прямым. Если в посылках и заключении указаны лишь виды выводов, от одного из которых разрешается переходить к другому, то вывод называют косвенным. Понятие вывода используется во многих формальных системах: в логике, математике, информатике, логическом программировании и др. В математической логике правила логического вывода задаются в исчислении высказываний либо исчислении предикатов. В информатике вывод умозаключений проводится с использованием правил, принципов и законов логического вывода на основе заданных фактов и правил с использованием методов и средств логического программирования. В информатике для описания фактов и правил логического вывода, а также баз знаний и моделей экспертных систем широко используется язык логического программировании Пролог. Умозаключения (отдельные шаги вывода) разделяют:1По направлению логического следования.

1. Дедуктивные (от общего к частному).

2. Индуктивные (от частного к общему).

3. Традуктивные (от одной степени общности к такой же степени общности).

2. По достоверности вывода.

1. Достоверные.

2. Правдоподобные.

3. По числу посылок.

1. Непосредственные.

2. Опосредственные.

Размещено на Allbest.ru