Составляющие формальной системы. Язык формальной теории. Синтаксис формального языка, отношение между формулой и подформулой, сложные и атомарные формулы (стр. 7 )

В качестве правил вывода используются все правила исчисления предикатов.

28.  Исчисление строгого и нестрогого порядка Язык, аксиоматика, правила, теоремы.

Предикат – высказывательная функция, определенная на некотором множестве М, т. е. такая n-местная функция Р, которая каждому упорядоченному набору <a1,a2, …, an> элементов множества М сопоставляет некоторое высказывание, обозначаемое P(a1,a2, …, an).

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

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

Исчисление нестрогого порядка:

Включение в аксиоматику исчисления порядка (для отношения Ђ) следующей аксиомы приводит к исчислению нестрогого порядка.

В качестве правил вывода используются все правила исчисления предикатов.

Исчисление строгого порядка:

Включение в аксиоматику исчисления порядка (для отношения Ђ) следующей аксиомы приводит к исчислению строгого порядка.

В качестве правил вывода используются все правила исчисления предикатов.

29.  Исчисление с выводом по аналогии. Отношение подобия.

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

Ещё одним примером неклассического логического вывода является вывод по аналогии.

Правило прямого вывода (заключения) по аналогии формально может выглядеть так:

где σ – бинарное отношение подобия на множестве термов и формул.

Вывод по аналогии реализуется в рамках базы знаний. База знаний состоит из набора фактов и правил, записанных на линейном языке. Факты представлены предикатными формулами с указанными значениями аргументов; факты утверждают истинность заданной интерпретации предиката. Значением аргументов являются константы. Например: P(a, b).

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

Например: P(A, B) <- P(A, C); P(C, B).

Последнее равносильно:P(A, B) Ú Ø P(A, C) Ú Ø P(C, B)

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

Здесь формула α , имеющая свободное вхождение переменной χ , обозначена как α (χ) . Формула α (χ) не имеет свободных вхождений τ . Формула α (τ) получена заменой всех свободных вхождений переменной χ на τ .

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

Подобие - В метрических пространствах так же, как в n-мерных римановых, псевдоримановых и финслеровых пространствах подобие определяется как преобразование, переводящее метрику пространства в себя с точностью до постоянного множителя. Отношение подобия – отношение выполняющие данное преобразования.

30.  Исчисление арифметики. Язык, аксиоматика, правила, теоремы.

Предикат – высказывательная функция, определенная на некотором множестве М, т. е. такая n-местная функция Р, которая каждому упорядоченному набору <a1,a2, …, an> элементов множества М сопоставляет некоторое высказывание, обозначаемое P(a1,a2, …, an).

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

Исчисление арифметики описывает натуральные числа и закономерности операций над натуральными числами. В алфавит языка исчисления арифметики дополнительно вводятся классы следующих символов,',0+,∗. Аксиоматика кроме аксиомных схем исчисления предикатов содержит шесть аксиом и одну аксиомную схему, формализующую метод математической индукции.

Теоремы: Примерами теорем исчисления арифметики являются следующие формулы.

31.  Теория алгоритмов. Понятие примитивно-рекурсивной функции.

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

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n = 0,1). Вот пример рекурсивной функции, дающей n-ое число Фибоначчи:

Примитивно рекурсивная функция — вычислимая функция нескольких натуральных переменных, частный случай рекурсивной функции.

Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса исходных примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся. К числу исходных примитивно рекурсивных функций относятся функции следующих трёх видов: 1) Нулевая функция O одного переменного, сопоставляющая любому натуральному числу значение 0. 2) Функция следования S одного переменного, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x + 1. 3) Функции , где , от n переменных, сопоставляющие любому упорядоченному набору x1,...xn натуральных чисел число xm из этого набора.

32.  Теория алгоритмов. Понятие рекурсивной функции.

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

Рекурси́вная фу́нкция — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n = 0,1). Вот пример рекурсивной функции, дающей n-ое число Фибоначчи:

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

Например, рекурсивния функция:

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

Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру.

33.  Теория алгоритмов. Понятие задачи. Классы задач. Понятие кодировки задачи. Понятие неизбыточной кодировки задачи.