Статья 2306

У каждого языка - свои грамматика и синтаксис, своя манера выражения понятий.
В принципе большинство вычислительных задач можно решить, пользуясь любым языком, хотя программы при этом выглядели бы совершенно по-разному кроме того, для какой-то конкретной задачи написать программу на одном языке бывает проще, чем на другом. Здесь мы опишем некоторые широко распространенные языки программирования [...]

Читать дальше
Статья 2304

В итоге, получается выражение, которое вновь включает в себя гармонический ряд. Средняя длина пути для дерева, построенного без учета балансировки, логарифмически зависит от количества узлов и отличается от длины оптимального дерева на постоянный коэффициент. Среднее дерево гораздо меньше отличается от оптимального, чем самое плохое, - его путь длиннее оптимального на 38 процентов.
Все рассмотренные мной [...]

Читать дальше
Статья 2302

Изучение подобных вопросов называется анализом сложности.
Методы анализа сложности можно продемонстрировать на примере построения бинарного дерева - структуры данных, часто применяемой в тех случаях, когда важен быстрый поиск информации. Такое дерево обладает двумя характерными свойствами, каждый узел имеет, самое большее, два подузла, а ключи, которые идентифицируют эти узлы, устроены так, чтобы у любого узла меньший [...]

Читать дальше
Статья 255

К их числу относится широко известный метод рассуждения путем разбора случаев для того чтобы построить вывод формулы из посылок, нам достаточно получить выводы этой формулы из множества посылок и множества посылок.
Еще одним интересным способом рассуждения, который может быть оформлен в виде непрямого производного правила, является так называемый метод доказательства от противного. Пусть нам нужно [...]

Читать дальше
Статья 253

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

Читать дальше
Статья 250

Начнем с формулировки прямых производных правил.
Рассмотрим на примерах, на чем основана идея возникновения и применения прямых производных правил. Замечая, что всегда можно построить вывод. Мы оформляем результаты этих выводов в виде правил. Выводу соответствует простое правило введения конъюнкции из посылок выводима их конъюнкция.

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

Выводу соответствует также известное [...]

Читать дальше
Статья 249

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

Читать дальше
Статья 245

Хорошо известно, что сформулированная таким образом система аксиом арифметики Пеано является категорической, все модели данной второпорядковой системы изоморфны между собой. Но семантическое понятие логического следования в этом случае оказывается слишком богатым и не формализуемым ни в каком стандартном языке, в котором все правила вывода финитны и эффективны, и понятие аксиомы тоже является эффективным. Таким образом, [...]

Читать дальше
Статья 243

Можно построить для второпорядкового языка точную семантику и точным образом определить семантические понятия общезначимости и логического следования. Но при этом оказывается, что данные понятия в принципе не могут быть формализованы, нельзя построить такое обладающее свойством полноты непротиворечивое исчисление, в котором все правила вывода были бы финитны, а число логических аксиом конечным и рекурсивным. Строгое [...]

Читать дальше
Статья 241

Свободная переменная варьируется в данном выводе из посылок относительно посылки, если имеются вхождения, и в этом выводе применяется правило обобщение правило Бернайса по переменной формуле, которая зависит от посылки.
Если можно построить вывод формулы из множества посылок, такой, что в нем ни одна переменная не варьируется относительно какой-нибудь посылки, будем писать. Если же в выводе имеет [...]

Читать дальше
Статья 237

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

Читать дальше
Статья 233

Начнем с формулировки аксиоматического исчисления гильбертовского типа.
Аксиолоашческое исчисление предикатов НС, или классическое исчисление гильбертовского типа, включает список формул, принимаемых в качестве аксиом, правила вывода и определение понятия вывода. Логическими аксиомами будут формулы вида.
В формулах не содержит вхождений переменной. Правила вывода. В последних четырех аксиомах и правиле обобщения подстановки везде правильны. Нужно отметить, что выражения, [...]

Читать дальше
Статья 231

Формула следует относительно общезначимости из формулы тогда и только тогда, когда для всякой возможной реализации и любой функции приписывания последняя выполняет, если для всякой возможной реализации и любой функции приписывания она выполняет.
Отметим, что если из логически следует, то формула будет общезначимой. Однако из может следовать, но при этом формула общезначимой не будет. Например, из следует, [...]

Читать дальше
Статья 229

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

Читать дальше
Статья 227

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

Читать дальше
Статья 225