Общая характеристика логики первого порядка
Логика первого порядка – это формальное исчисление (расширение логики высказываний), которое допускает высказывания относительно:
- переменных,
- фиксированных функций,
- предикатов.
Алгебра и исчисление высказываний могут решить вопрос, является ли анализируемая формула тавтологией (тождественно истинной формулой), с помощью таблиц истинности. Для логики предикатов не разработано универсального эффективного способа, позволяющего ответить, является ли формула общезначимой (существуют методы только для частных случаев). Поэтому математические теории, использующие понятие предиката (и связанное с ним понятие квантора), нуждаются в аксиоматическом методе. Этот метод построен на простых отношениях, связывающих символы и выражения точных формальных языков. Он использует сравнительно простые методы арифметики.
Статья: Логика первого порядка
Аксиоматическая теория, построенная на основе заданной системы аксиом, - это совокупность всех теорем, которые доказываются на основе этой системы.
Аксиоматические теории подразделяются на:
- формальные,
- неформальные – наполненные теоретико-множественным содержанием. В них понятие выводимости носит расплывчатый характер и в значительной степени базируется на здравом смысле.
Формальную аксиоматическую теорию считают определенной при выполнении следующих условий:
- задан язык теории – алфавит и множество всех слов над этим алфавитом,
- определено понятие формулы,
- выделен набор формул, названных аксиомами,
- определены правила, по которым в этой теории осуществляется вывод.
Математические теории весьма многочисленны и разнообразны. Особое место среди них занимают теории первого порядка, отличающиеся от теорий высших порядков запретом на предикаты, имеющие в качестве возможных значений аргументов иные предикаты. Кроме того, теории первого порядка не разрешают проводить квантификацию предикатов.
В принципе, теорий первого порядка хватает, чтобы описать большую часть математических теорий. Многие теории высших порядков сводятся к теориям первого порядка.
Теории первого порядка относятся и к прикладным исчислениям, в которых логические аксиомы дополняются собственными аксиомами. Как правило, в собственных аксиомах используются:
- индивидуальные (конкретные) предикатные буквы (=, больше, меньше);
- функциональные буквы (+, –, *);
- предметные константы (пустое множество, натуральные числа и т.д.).
В конечном счете, ценность любой формальной теории зависит от ее способности описать объекты и существующие между ними связи. Поэтому для любой теории одним из первых возникает вопрос: для описания каких объектов она может использоваться? Если трактовать этот вопрос как общую проблему соответствия между научными знаниями о мире и самим миром, его нельзя обсуждать сугубо математическими средствами, т.к. математика работает не непосредственно с миром (как естественные науки), а с формальными описаниями его частей. В такой постановке проблема обретает фундаментальность и должна рассматриваться в философии и методологии науки, выходя далеко за пределы логики. Задача является математической в более простом случае – когда множество объектов, для которых выполняется построение формальной теории, само по себе достаточно строго описано. Тогда проблема адекватности формальной теории трактуется как математическая задача о соответствии содержательно построенной теории и множества высказываний об этой теории (формального значения исчисления).
Итак, логика первого порядка - это набор правил, которые используются для сравнения и анализа высказываний, которые могут быть истинными или ложными. Эта логика используется для формулирования сложных связей между отдельными фактами, утверждениями, предложениями и т.д. Она также используется для составления сложных связей между аргументами, чтобы доказать, что утверждение является истинным.
Свойства логики первого порядка
Логика первого порядка – привлекательный инструмент формализации математики благодаря ее свойствам:
- полноте,
- непротиворечивости.
Теория называется полной, если в ней доказуема любая синтаксически корректная замкнутая формула или ее отрицание.
Существует широкое и узкое понимание полноты теории:
- теория называется абсолютно полной, если для любого высказывания или его отрицания имеется теорема, причем высказывание интерпретируется в некоторой модели;
- теория называется полной в узком смысле, если при добавлении к ее аксиомам любого недоказуемого утверждения делает теорию противоречивой.
Теория называется противоречивой, если она содержит такое высказывание, что и оно само, и его отрицание являются теоремами.
Во многих случаях вопрос непротиворечивости аксиоматической теории решается с помощью моделей. Действительно, для противоречивых теорий в каждой модели будет содержаться противоречие, поскольку пара теорем, противоречащих друг другу в теории, переходит в пару противоречащих высказываний о модели. Значит, теория будет непротиворечивой, если для нее удается построить модель, свободную от противоречий. Именно таким способом доказаны непротиворечивость исчисления предикатов и исчисления высказываний.
Кроме перечисленных свойств, логика первого порядка обладает свойством компактности.
При аксиоматическом построении теорий первого порядка крайне важными представляются теоремы Геделя о неполноте.
Первая теорема Геделя утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.
Иными словами, какую бы систему аксиом ни выбрали для арифметики, в этой формальной теории всегда найдется высказывание о натуральных числах, которое будет невозможно ни опровергнуть, ни доказать.
Вторая теорема Геделя утверждает, что если формальная арифметика непротиворечива, то в ней невыводима некоторая формула, содержательно утверждающая непротиворечивость этой арифметики.
