1Вопрос. Формализация

формализация

(от лат. forma - вид, образ)

отображение результатов мышления в точных понятиях и утверждениях. При Ф. изучаемым объектам, их свойствам и отношениям ставятся в соответствие некоторые устойчивые, хорошо обозримые и отождествимые материальные конструкции, дающие возможность выявить и зафиксировать существенные стороны объектов. Ф. уточняет содержание путем выявления его формы и может осуществляться с разной степенью полноты.

Выражение мышления в естественном языке можно считать первым шагом Ф. Дальнейшее ее углубление достигается введением в обычный язык разного рода специальных знаков и созданием частично искусственных и искусственных языков.

Логическая Ф. направлена на выявление и фиксацию логической формы выводов и доказательств. Полная Ф. теории имеет место тогда, когда совершенно отвлекаются от содержательного смысла ее исходных понятий и положений и перечисляют все правила логического вывода, используемые в доказательствах. Такая Ф. включает в себя три момента: 1) обозначение всех исходных, неопределяемых терминов; 2) перечисление принимаемых без доказательства формул (аксиом); 3) введение правил преобразования данных формул для получения из них новых формул (теорем).

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

Ф. играет существенную роль в уточнении научных понятий. Многие проблемы не могут быть не только решены, но даже сформули-

рованы, пока не будут формализованы связанные с ними рассуждения. Так обстоит дело, в частности, с широко используемым понятием алгоритма и вопросом о том, существуют ли алгоритмически неразрешимые проблемы.

Только с Ф. арифметики появилась возможность поставить вопрос, охватывает ли формализованная арифметика всю содержательную арифметику. Как показал К. Гёдель, достаточно богатая содержанием теория (охватывающая арифметику натуральных чисел) не может быть полностью отображена в ее формализованной версии; как бы ни пополнялась дополнительными утверждениями последняя, в теории всегда останется невыявленный, неформализованный остаток (см.: Гёделя теорема).

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

2вопрос. Рекурсивное определение правил.

.В первую очередь необходимо постараться описать процесс решения в виде рекуррентных соотношений (1). В них функция f может быть выражена в словесной форме. Затем разделить это описание на 2 части: собственно рекуррентные соотношения и соотношения, задющие граничные (начальные и конечные) условия процесса. Например, в задаче вычисления факториала соотношения (1) разбиваются на следующие 2 части:  1) Граничные условия 0!=1 - начальные условия; k=N - условия окончания; 2) Рекуррентные соотношения k!=(k-1)!*k; k=1, 2, 3,... Рекурсивное определение в программе также делится на две части. Одна из них соответствует рекуррентным формулам и состоит из правил, в теле которых присутствует целевое утверждение с тем же предикатом, что и заголовок правила, т.е. из правил, рекурсивно вызывающих самих себя. Другая часть содержит утверждения, описывающие терминальную ситуацию, т.е. ситуацию, в которой рекурсивное обращение предиката к самому себе прекращается. В качестве терминальной ситуации выбирается одно из граничных условий. Обычно терминальная ситуация является первым утверждением в определении. В этом случае вот что происходит при выполнении (см. пример 1): • оценивается первое утверждение в рекурсивном определении; • если первое утверждение не выполняется, осуществляется переход к следующему в определении утверждению, и оно оценивается. Обычно это правило, которое содержит условие, начинающее рекурсию; • после прохождения первого уровня рекурсии выполнение возвращается к первому утверждению в определении и опять оценивается его истинность; • если оценивание первого утверждения заканчивается неудачей, выполнение переходит ко второму в определении утверждению и входит во второй уровень рекурсии. Этот процесс продолжается до тех пор, пока первое утверждение (содержащее терминальную ситуацию) не выполнится и, таким образом, сделает определение успешным и остановитрекурсию. В зависимости от того, как осуществляется переход от соотношений (1) к программе, различают два разных стиля рекурсивных определений: нисходящая рекурсия и восходящая рекурсия.

Рекурсия является мощным методом программирования, в котором от­но­ше­ния между объектами можно определить, только пользуясь самими опре­де­ляемыми соотношениями. В Prolog рекурсия приобретает особую важность, так как здесь отсутствуют циклические конструкции. Правила, определяемые этим методом, называются рекурсивными.

В рекурсивном определении выделяют граничное и общее условия. Решить задачу позволяют именно граничные условия, так как в них происходит до­казательство целей и рекурсивный процесс останавливается.

Определим рекурсивно сумму чисел от 0 до N.

 

Математическая запись	Запись на Prolog
Граничное условие
S0=0	sum(0,0).
Общее или рекурсивное условие
Sn=Sn-1 + n	sum(N,S) if N1=N-1, sum(N1, S1), S=S1+N.

Для того чтобы вычислить сумму чисел от 0 до 10, необходимо поставить цель

goal sum(10, F),!.

F=55

 

Отсечение необходимо поставить, так как  в результате бэктрекинга система будет искать дополнительные решения и исчерпает память.

3вопрос.Логическое программирование

.Логическое программирование (ЛП). Основано на формальной логике. Программа задается как набор логич. утверждений. Путем применения операций унификации (сопоставления) и редукции (преобразования, упрощения) система находит решение задачи. Искомые величины задаются в виде переменных в логических отношениях и запросах. (Переменная здесь не есть "переменная-ячейка памяти" в понимании процедурного программирования. В ЛП, аналогично функциональным языкам, переменная всего лишь символическое обозначение некой сущности. Значение переменной не может изменяться: оно либо найдено, либо нет. Понятие переменной в ФП и ЛП языках более точно соответствует понятию переменной в математике.)

Существуют и другие, более современные подходы в ЛП. Один из них: программирование в ограничениях. Задача формулируется как набор логических ограничений на условия. В таких языках применяется расширенное понятие переменной: недоопределенная переменная. Она имеет конкретное (возможно неизвестное на данном этапе) значение - денотат. И некую область значений, в которую денотат входит.

Пример: Пролог, Меркурий, Моцарт, CHIP.

Языки ФП и ЛП относят к программированию сверхвысокого уровня, декларативному. Т.е. в программе может не задаваться алгоритм решения в явном виде. Исходный текст ближе к естественной математической записи условий.

Сравнение с традиционными языками программирования.

 

Язык программирования характеризуется присущими ему механизмами управления и обработки данных. Пролог как универсальный язык программирования можно рассматривать и с этих точек зрения.

При успешном выполнении вычисления средства управления программ на языке Пролог подобны средствам управления в обычных процедурных языках. Обращение к некоторой цели соответствует вызову процедуры, порядок целей в теле правила соответствует последовательности операторов. Точнее, правило А ß В₁,В₂,…,В_n можно рассматривать как определение процедуры:

Procedure A

      Call B₁

             Call B₂

      .

      .

      .

      Call B_n

End.

Рекурсивный вызов цели в Прологе  в последовательности действий и в реализации подобен тому же вызову в обычных рекурсивных языках. Различие возникает при реализации возврата. В обычных языках, если вычисление не может быть продолжено (например, все ветви в операторе case ложны), возникает ошибка выполнения. В Прологе вычисление просто возвращается к последнему выбору и делается попытка продолжить вычисления по новому пути.

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

Другие особенности использования структур данных в языке Пролог связаны с природой логических переменных. Логические переменные соотносятся с объектами, а не с ячейками  памяти. Если переменной сопоставлен конкретный объект, то эта переменная уже никогда не может ссылаться на другой объект. Иными словами, логическое программирование не поддерживает механизм деструктивного присваивания, позволяющий изменять значение инициализированной переменной.

В логическом программировании обработка данных полностью заключена в алгоритме унификации. В унификации реализованы:

•    однократное присваивание,

•    передача параметров,

•    размещение записей,

• доступ к полям записей для одновременных чтения/записи.

Традиционные языки, как правило, содержат различной степени сложности средства обработки ошибочных и исключительных ситуаций. Чистый Пролог не содержит механизма обработки ошибок и исключительных ситуаций, встроенного в описаниеязыка. В отличие от традиционных языков ситуации, приводящие к ошибке (например, отсутствие нужной ветви в оператореcase, деление на нуль), в чистом Прологе приводят к “отказу”.

4 вопрос Объекты данных-(Факты

Объекты данных-(Факты) в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

Существуют два типа утверждений:

·        факт — это одиночная цель, которая, безусловно, истинна;

·        правило состоит  из  одной  головной  цели  и  одной  или  более хвостовых целей, которые истинны при некоторых условиях.

Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.

Конъюнкцию можно рассматривать как логическую  функцию  И.  Таким образом, правило согласовано, если согласованы все его хвостовые цели.

Примеры фактов:

person (john).

мужчина (виктор).

нравиться (джон, мери).

Примеры правил:

человек (Х) :- мужчина(Х).

твистик(Кто_то) if человечек(Кто_то),

                   любит_танцевать(Кто_то, твист).

Предложения с пустым Телом называются Фактами. Пример факта:

Кот(Иван).

оно эквивалентно правилу:

Кот(Иван) :- ИСТИНА.

5вопрос Структурные объекты

Структурные объекты (или просто структуры) - это объекты, которые состоят из нескольких компонент. Эти компоненты, в свою очередь, могут быть струк­турами. Например, дату можно рассматривать как структуру, состоящую из трех компонент: день, ме­сяц, год. Хотя они и составлены из нескольких ком­понент, структуры в программе ведут себя как еди­ные объекты. Для того, чтобы объединить компоненты в структуру, требуется выбрать функтор.

Для нашего примера подойдет функтор дата. Тогда дату 1-е мая 2004 г. можно записать так: