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

Как решать задачи на ЭВМ. Математик разрабатывает алгоритм решения задачи, а программист, используя один из языков программирования, реализует предложенный алгоритм в виде программы.

Или иной подход: задачу надо представить в виде высказывания, доказательство которого следует предоставить ЭВМ.

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

Логическая программа представляет собой конечный набор формул логики предикатов одного из следующих выводов:

P (t1,t2…..tn).

Q(s1,…, sk): - Q1(s1,…, sk),…, Qm(s1,…..sk).

Где Q1,Q2,…Qm – предикаты, а t1,…,tn, s1,…, sk – термы. Формулы первого вида называются фактами, второго – правилами. Факт - один единственный экземпляр, свойство или отношение между объектами.

Правило читается как «Q(s1,…, sk) истинно, если истины Q1(s1,…, sk),…, Qm(s1,…..sk) ». Формула Q(s1,…, sk) называется ЗАГОЛОВКОМ правила. Правило позволяет выводить новые факты из уже имеющихся.

Таким образом, логическая программа состоит из конечного числа фактов и правил. В фактах и правилах описывается логическая модель предметной области.

Логическая программа задает множество следствий, которые являются результатом программы. Выполнение логической программы – это вывод следствия из него.

Логическое программирование предполагает наличие логической машины, называемой интерпретатором, который осуществляет процесс логического вывода.

Для реализации идей логического программирования разработаны различные языки логического программирования, такие как PROLOG, TURBO PROLOG и т. д.

26. Теорема Геделя о неполноте и суть ее доказательства.

Во всякой теореме 1-го порядка, включающей формальную арифметику:

1.Существует истинная формула А, истинность которой нельзя ни доказать, ни опровергнуть.

2. Утверждение о непротиворечивости данной теории - это формула данной теории, которую нельзя доказать.

Попытка доказательства Геделя.

1.0-0

0‘-1

0‖-2 z

2.П↑ подстановка x на z X

Применятся, подстановка может только к свободным переменным, а не к связанным.

Если взять любую ф-лу состоящую из символов данного алфавита, например:

То для этой ф-лы можно вычислить универсальный Геделев номер.

Существует единственное разложение натурального числа в виде произведения простых чисел с различными степенями.

В любой правильно построенной ф-ле сопоставлено уникальное число, обратное неверно.

Как восстановить ф-лу?

Надо гигантское число разложить на простые множители, затем определить показатели этих сомножителей.

Г(F1,F2…Fm)-это ф-я определяет Г.Н док-во, являющиеся в виде последовательности ф-л F1,F2…

Г(F1,F2…Fm)=

4.Вводится в рассмотрение импликант

1)Д(у,х):=(у=Г(док (х)) – утверждает что «у» - Г.Н док-во ф-л, чей Г.Н – «х».

2)

3)

4) Пусть n0-Г.Н ф-лы G(x)

n0- [G(x)] (4)

G(n0)

Лемма: (G(n0))=S(n0)

Теперь докажем, что G(n0) имеет док-во, то у этого док-ва есть свой Г.Н. Обозначим за m0 Г.Н док-ва.

M0=Г(докG(n0)),получится D(m0, (G(n0))=D(m0,S(n0))= yD(y,S(n0))= ┐ y┐D(y,S(n0))

По ф-ле (3), G(n0)= y┐D(y,S(n0)) (6), ф-ла (5) противоречит ф-ле (6), следовательно нам не удалось док-ть истинности G(n0),

Рассмотрим теперь док-во ложности ф-лы G(n0),

┐G(n0)= ┐ y┐D(y,S(n0))= yD(y,S(n0)) (7)

Попытка найти отрицание ф-лы G(n0) привело к тому, что мы получили док-во S(n0).Если мы проведем это док-во, то получим:

(G(n0))- существование номера Геделевской ф-лы,что противоречит

отрицанию.

Теорема Геделя, доказанная в 1931 г. Послужила толчком в области исследования формальной системы. В дальнейшем были сформулированы еще боле сильные ф- лы с простыми док-ми. Было доказано, что множество номеров истинных формул не исчислимо, это нельзя док-ть ни сейчас, ни в каком другом будущем. Все это привело к принципу несовершенства Геделя:

Всякая фундаментальная теория несовершенна - она либо противоречива либо недостаточна для решения всех возникающих проблем.

27. Понятие алгоритма. Свойства алгоритмов. Способы записи алгоритмов.

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

Основные свойства алгоритма:

1.Дискретность. Процесс решения протекает в виде последовательности отдельных действий, следующих друг за другом.

2.Элементарность действий. Каждое действие является настолько простым, что оно не допускает возможности неоднозначного толкования.

3.Определенность. Каждое действие определено и после выполнения каждого действия однозначно определяется, какое действие будет выполнено следующим.

4.Конечность. Алгоритм заканчивает работу после конечного числа шагов.

5.Результативность. В момент прекращения работы алгоритма известно, что является результатом.

6.Массовость. Алгоритм описывает некоторое множество процессов, применимых при различных входных данных.

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

Схема определения алгоритма в практическом смысле выглядит так:

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

2. Данные для своего размещения требуют памяти. В ЭВМ память состоит из ячеек. Единицы объема данных и памяти согласованы, и в прикладных алгоритмических моделях объем данных можно измерять числом ячеек, в которых данные размещены.

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