Дискретная математика и семантика программ

Дискретная математика и семантика программ: логика, вычисления, λ-подстановка, типы, редукции и инварианты. Задачи, практика и безопасный один β-шаг.

Пять работ A, B, C, D, E нельзя выполнять в произвольном порядке: C требует A и B, D требует B, а E — C и D. Уже здесь встречаются множество работ, логические условия, ориентированный граф и подсчёт допустимых порядков. Дискретная математика связывает эти языки, чтобы конечную задачу можно было точно поставить и проверить.

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

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

Основные идеи

Множество, подмножество и отношение

Множество определяется элементами; повторная запись элемента не увеличивает его мощность. Отношение на множестве V — набор упорядоченных пар из V×V. Пара (A,C) может обозначать требование выполнить A раньше C, а не арифметическое действие.

Для V={A,B,C,D,E} множество непосредственных зависимостей равно {(A,C),(B,C),(B,D),(C,E),(D,E)}. Из A→C→E следует достижимость A→E, хотя отдельного такого ребра нет.

Логика: условие и его отрицание

Конъюнкция P∧Q истинна, когда истинны обе части. Импликация P→Q ложна лишь при истинном P и ложном Q; она не утверждает причинности. Отрицание «P и Q» имеет вид «не P или не Q», включая случай, когда ложны обе части.

Условие допуска C: «A выполнена и B выполнена». Его отказ: «A не выполнена или B не выполнена». Одного выполненного предшественника недостаточно.

Комбинаторика: что именно считаем

Правило суммы применяют к непересекающимся случаям, правило произведения — к последовательным выборам с известным числом продолжений. Для выбора k разных элементов без порядка из n используют C(n,k)=n!/(k!(n−k)!). Ограничения на порядок требуют дополнительного учёта.

Из пяти работ можно выбрать пару C(5,2)=10 способами. Порядков всех пяти без ограничений 5!=120; допустимых расписаний по нашему графу только пять.

Графы и топологический порядок

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

После выполнения B доступны A и D; работа C всё ещё ждёт A. Если добавить E→B, образуется цикл B→D→E→B, и удовлетворить всем строгим зависимостям уже нельзя.

Сравнения по модулю

Запись a≡b (mod m) при положительном целом m означает, что a−b делится на m. Обратный к a существует ровно при НОД(a,m)=1. Деление в сравнении поэтому требует отдельной проверки и не повторяет деление действительных чисел.

3·5=15≡1 (mod 7), поэтому из 3x≡6 (mod 7) следует x≡30≡2. Для 2x≡1 (mod 6) решений нет: левая часть чётная по любому представителю.

Семантика программ

Подстановка в λ-исчислении: свободная переменная должна остаться свободной

Выполняем один бета-шаг с предварительным переименованием связанного имени и проверяем результат по свободным переменным.

Перед началом: Абстракция и применение функции; Свободное и связанное вхождение; Рекурсивное синтаксическое дерево.

Замена текста может изменить смысл функции

В терме (λf.λz.(f λu.z) z) аргументом внешней функции является свободное z. Если просто вставить это имя вместо f, внешний по отношению к месту вставки λz свяжет его. Свободная ссылка превратится в параметр совсем другой функции. Получившийся текст будет выглядеть грамматически правильно, но обозначать другое выражение. Ошибка называется захватом переменной.

Абстракция λx.M связывает в M соответствующие вхождения x, кроме затенённых внутренними связываниями. Множество свободных переменных вычисляется структурно: у переменной это она сама, у применения — объединение множеств частей, у абстракции — свободные переменные тела без параметра. Перед сокращением полезно вычислить это множество у аргумента: именно такие имена нельзя неожиданно связать при его переносе.

Подстановка останавливается у подходящего связывания

Бета-правило сокращает применение (λx.M) N до M[x:=N]. При обходе M вхождение x заменяется аргументом, а другая переменная остаётся прежней. В применении обходятся обе части. В абстракции с тем же параметром x подстановка останавливается: внутренний x принадлежит новому связыванию. Заменять его было бы уже изменением другой переменной с одинаковым написанием.

У абстракции λy.P с отличным параметром нужно дополнительно проверить y относительно свободных переменных N. Если возникает риск захвата при требуемой подстановке, связанный параметр переименовывается в свежее имя. Важно переименовать только связанные с ним вхождения, сохранив внутреннее затенение. Глобальная замена всех букв y в строке не выполняет эту задачу корректно.

Альфа-переименование готовит один бета-шаг

Переименование связанного параметра без захвата называют альфа-преобразованием. Например, λz.P можно записать с новым параметром w, если w не создаёт конфликтов и соответствующие вхождения заменены согласованно. Выбор конкретного свежего написания не является частью результата вычисления: корректные варианты сравнивают с точностью до альфа-эквивалентности. Но свободные имена так переименовывать нельзя.

В нашем примере выбираем w, которого ещё нет в терме, и превращаем внутреннее связывание z в w. Внутри λu бывшее z всё ещё относится к этому внешнему связыванию, поэтому тоже станет w. После этого вставленное свободное z не попадает под λw. Подготовительное альфа-преобразование не является вторым бета-сокращением; это условие корректного выполнения одного заданного шага.

Нормальный поиск редекса и граница демонстрации

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

Для ручной проверки сначала отметьте связывания, затем укажите редекс, свежий параметр и оставшиеся свободные ссылки. У результата нашей задачи свободное z должно сохраниться. Проверка свободных переменных помогает обнаружить захват, но сама по себе не доказывает правильность всего дерева. Поэтому дополнительно сравнивают структуру применения и то, какие вхождения были заменены; совпадение множества имён ещё допускает неправильную перестановку частей.

Аргумент z проходит под другое связывание

Условие. Выполнить один левый внешний бета-шаг: (λf.λz.(f λu.z) z). Применения заключены в скобки; тело λu.z является аргументом внутреннего применения.

  1. Внешний редекс связывает f, аргумент — свободное z. Его множество свободных переменных равно {z}.
  2. В теле есть λz, которое захватило бы вставленное имя. Выбираем свежее w.
  3. Альфа-переименование даёт тело λw.(f λu.w). Параметр u остаётся прежним.
  4. Подставляем z вместо f: получаем λw.(z λu.w). Новое имя w может быть выбрано иначе при сохранении связываний.

Ответ. λw.(z λu.w), с точностью до переименования связанных параметров.

Проверка. Свободные переменные результата — {z}. Наивное λz.(z λu.z) замкнуто и поэтому потеряло свободный аргумент.

Где легко ошибиться. Свежесть имени проверяется по всему нужному контексту, а не только по параметру текущей функции. Красивое новое написание может уже встречаться свободно внутри тела.

Один β-шаг с защитой от захвата переменных

Учебное λ-исчисление: λx.term или \x.term, применение (term term), имена из a–z с цифрами длиной до восьми символов. До 180 токенов и 30 уровней вложенности. Делается один левый внешний β-шаг с α-переименованием при необходимости; это преобразование дерева выражения, не запуск программы.

Данные для расчёта

Проверьте понимание

Что выдаёт ошибку захвата в наивном результате задачи?

Вопросы к этой главе

Должен ли результат буквально использовать букву w?

Нет. Подойдёт другое действительно свежее имя. Сравнение результатов должно учитывать альфа-эквивалентность, сохраняя свободные имена.

Можно заменять переменные обычным replace по строке?

Такой вызов не различает вхождения, области связывания и внутреннее затенение. Подстановка определяется по синтаксическому дереву или равноценному представлению связей.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Cornell CS3110: Capture-Avoiding Substitution

    Проверены подстановка под связыванием, свободные переменные и свежие имена. Терму с вложенной λu и его проверке задано отдельное происхождение.

Малые шаги: как стратегия решает судьбу неиспользованного аргумента

На одном терме сравниваем слабые call-by-value и call-by-name, отделяя отсутствие шага от бесконечного сокращения.

Перед началом: Бета-сокращение; Значение в выбранной семантике; Подстановка без захвата.

Один терм допускает разные пути вычисления

Пусть I обозначает λs.s, а Ω — применение λu.(u u) к такой же абстракции. Рассмотрим (λq.(λr.(r r) I) Ω). Тело внешней функции не использует q. Стратегия, подставляющая аргумент без предварительного вычисления, сможет его отбросить и получить I. Стратегия, требующая сначала значение аргумента, застрянет не на ошибке, а на бесконечном вычислении Ω.

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

Call-by-value сначала получает значение аргумента

В выбранной слабой семантике call-by-value абстракция является значением. Для применения вычисляется функция, затем аргумент, и только после получения абстракции и значения разрешается подстановка. Под телом ещё не вызванной абстракции шаги не выполняются. Слово «слабая» указывает на это ограничение поиска, а не на меньшую строгость требований к корректности программы.

Для Ω один бета-шаг воспроизводит то же самое применение. Поэтому возможны шаги, но значение никогда не достигается. Если Ω требуется вычислить как аргумент внешней функции, её тело не начинает работу. Формальное отсутствие завершения отличается от отсутствия допустимого шага: застрявший терм не является значением и не может двигаться по правилам, а Ω постоянно движется к себе.

Call-by-name откладывает работу, но не обязательно разделяет её

В слабом call-by-name после получения функции-абстракции аргумент подставляется как выражение. Если параметр не используется, работа аргумента исчезает. Если параметр встречается несколько раз, его выражение может оказаться в нескольких местах и вычисляться повторно. Поэтому отложенное вычисление и запоминание результата являются разными решениями реализации. Call-by-need добавляет разделение вычисленной работы, которого в простой подстановочной модели нет.

Наш внешний q отсутствует в теле, поэтому call-by-name сразу убирает Ω. После этого два применения идентичности дают конечное значение. Обещать одинаковое число шагов для всех стратегий было бы неверно. При наличии побочных эффектов различия могут касаться не только времени, но и наблюдаемого поведения; здесь выбран чистый λ-язык, чтобы исследовать порядок и завершение без дополнительных эффектов.

Слабая стратегия и полная нормальная форма различаются

Терм λx.Ω является значением обеих выбранных слабых стратегий: тело пока не вычисляется. При поиске полной бета-нормальной формы пришлось бы сокращать и редексы под абстракцией, поэтому такое тело нельзя игнорировать. Вывод «получили функцию» относится к выбранному понятию результата. Его нельзя автоматически переименовать в утверждение, что внутри терма больше вообще нет редексов.

Для проверки трассы на каждом переходе укажите применённое правило и контекст. Если используется сокращённое имя I или Ω, сначала зафиксируйте его определение. Ограничение числа шагов в демонстрации сообщает только, что за этот бюджет значение не найдено. Доказательство бесконечности нашей Ω сильнее: после каждого шага буквально воспроизводится та же структура, поэтому конечное значение не появляется на любой последующей итерации.

Три шага вместо бесконечного аргумента

Условие. I=λs.s, Ω=(λu.(u u) λu.(u u)). Сравнить слабые стратегии для M=(λq.(λr.(r r) I) Ω).

  1. Call-by-name сокращает внешний редекс и получает (λr.(r r) I): параметр q в теле отсутствует.
  2. Следующий шаг подставляет I вместо r, получая (I I).
  3. Третий шаг даёт I, которое является значением слабой семантики.
  4. Call-by-value до внешней подстановки должен вычислить Ω. Каждый шаг Ω даёт Ω, поэтому до тела внешней функции он не доходит.

Ответ. Call-by-name достигает I за три бета-шага; call-by-value расходится на аргументе.

Проверка. В цепочке не вычислялось тело абстракции I до применения. Самовоспроизведение Ω проверяется подстановкой λu.(u u) в оба вхождения u.

Где легко ошибиться. Не путайте бесконечную цепочку допустимых шагов с ошибкой «шаг невозможен». Для анализа безопасности и завершения это разные результаты.

Проверьте понимание

Чем является λx.Ω в выбранной слабой call-by-value семантике?

Вопросы к этой главе

Call-by-name всегда выполняет меньше работы?

Нет. Если параметр используется несколько раз, отложенное выражение может вычисляться повторно. Число шагов зависит от конкретного терма и модели разделения результатов.

Полученная абстракция всегда является полной нормальной формой?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Cornell CS3110: Substitution Model and evaluation strategies

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

Индуктивный тип: конструктор в списке ещё не означает полный разбор

На конечном дереве находим пропущенный случай с отрицательной меткой и строим полный структурный обход.

Перед началом: Вариантный тип и конструктор; Рекурсивное определение; Условие в ветви сопоставления.

Допустимые значения задаёт тип

Зададим конечные деревья T=Tip|Fork(int,T,T). Ветка Fork может иметь любую целую метку и два дерева, включая пустые. Значение Fork(−2,Tip,Fork(3,Tip,Tip)) допустимо: отрицательная метка не запрещена объявлением типа. Если функция обрабатывает только внутренние узлы с положительными метками, она пропускает часть совершенно законных входов. Ошибка находится в охвате случаев, а не в построении этого дерева.

Индуктивное определение создаёт значения конечным применением конструкторов. Tip даёт базовый случай, Fork строит более сложное значение из уже построенных частей. Для нашей математической модели не предполагаются скрытые циклические ссылки или ленивые бесконечные деревья. Такие возможности потребовали бы другого рассуждения о значениях и завершении обхода. Слово «рекурсивный» само по себе не разрешает молча смешивать эти модели.

Проверяйте покрытие значений, а не только имена конструкторов

Пусть первая ветвь возвращает ноль для Tip, вторая обрабатывает Fork(n,Tip,Tip), а третья — Fork(n,l,r) только при условии n>0. Оба имени конструкторов присутствуют, но отрицательный внутренний узел не попал никуда. Guard сужает множество значений своей ветви. Отдельная обработка листового узла также не покрывает все формы Fork: дети могут быть непустыми.

Шаблоны проверяются в установленном порядке. Более общий шаблон раньше специального может сделать последний недостижимым. Ветка «всё остальное» способна скрыть проблему при добавлении нового конструктора. Для понимания исчерпываемости полезно разбить пространство значений по конструкторам, затем по вложенным формам и условиям. Результат должен покрывать каждое допустимое значение, а не только каждую строку небольшого теста.

Полный структурный обход имеет простое основание

Для суммы меток достаточно двух ветвей: score(Tip)=0 и score(Fork(n,l,r))=n+score(l)+score(r). Специальная ветвь листа не нужна: общее правило само даёт n+0+0. Знак метки не влияет на допустимость рекурсии. Отрицательные значения меняют сумму, но не структуру, по которой определяется следующий вызов.

Корректность доказывается структурной индукцией. Базовое пустое дерево содержит ноль меток. Для Fork предполагаем правильность сумм обоих поддеревьев и добавляем метку корня; это перечисляет все узлы ровно один раз. Каждый рекурсивный вызов получает строгое поддерево, поэтому на конечных значениях обход заканчивается. Здесь одна и та же структура даёт и смысл результата, и меру продвижения.

Исчерпываемость не доказывает любое поведение функции

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

Практический контрпример выбирают именно из непокрытого множества: отрицательный узел, который не является листом. После исправления сравните результат с независимым перечислением меток. Затем рассмотрите пустое дерево и одиночный узел. Такие проверки направлены на логические границы определения, а не на случайный размер входа. Если появится новый конструктор, доказательство и шаблоны должны быть пересмотрены вместе с типом.

Законный вход без подходящей ветви

Условие. Для T=Tip|Fork(int,T,T) есть ветви Tip→0; Fork(n,Tip,Tip)→n; Fork(n,l,r) when n>0→n+score(l)+score(r). Вход Fork(−2,Tip,Fork(3,Tip,Tip)).

  1. Вход является Fork, поэтому первая ветвь Tip не подходит.
  2. Правый ребёнок не Tip, поэтому шаблон одиночного листового узла тоже не подходит.
  3. Условие третьей ветви −2>0 ложно. Значение допустимо, но разбор не исчерпывающий.
  4. Заменяем специальные ветви общим правилом Fork без guard. Получаем −2+0+(3+0+0)=1.

Ответ. Изначальный разбор пропускает вход; полный структурный score возвращает 1.

Проверка. Независимый список меток дерева — [−2,3], его сумма 1. Базовый Tip не добавляет меток.

Где легко ошибиться. Наличие имени Fork в нескольких шаблонах не означает покрытия всех Fork. Вложенный шаблон и guard ограничивают охватываемые значения.

Проверьте понимание

Какое правило полностью обрабатывает оставшиеся Fork для суммы меток?

Вопросы к этой главе

Если все конструкторы обработаны, рекурсия завершится?

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

Почему отрицательная метка не является ошибкой типа?

Тип содержит int без дополнительного ограничения. Положительность пришлось бы выразить отдельным инвариантом или более точным представлением допустимых значений.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Cornell CS3110: Algebraic Data Types

    Проверены вариантные и рекурсивные типы и сопоставление по конструкторам. Тип дерева, guard-контрпример и сумма меток составлены отдельно.

Type soundness: что именно обещают прогресс и сохранение типа

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

Перед началом: Суждение о типе; Малый шаг вычисления; Значение и замкнутый терм.

Тип результата должен переживать шаги вычисления

Выражение if ((λb:Bool.b) true) then ((λn:Int.n+3) 4) else 0 имеет тип Int в нашей мини-системе. Условие типизировано как Bool, обе ветви — как Int. После сокращения условия и выбора ветви выражение должно сохранить тот же итоговый тип. Такая трасса показывает смысл сохранения типа на конкретном примере, хотя не является доказательством для всех термов языка.

В учебной системе есть функции, Bool, математические целые Int и тотальное сложение целых. При добавлении операций к формальному ядру нужно проверить новые правила, а не автоматически перенести готовую теорему. Например, операция, которая может вызвать исключение, требует описания этого результата в семантике. Типизированность и поведение операции связаны через конкретные определения языка.

Два утверждения работают вместе

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

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

Не застрять и обязательно закончить — разные свойства

Бесконечная цепочка корректных шагов не противоречит прогрессу. Язык с общей рекурсией может допускать типизированную функцию, которая вызывает себя без завершения. Для чистого просто типизированного ядра существуют дополнительные результаты о нормализации, но они не выводятся из одного определения слов «прогресс» и «сохранение». Нужно указать точный язык и отдельное обоснование завершения.

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

Проверяйте ошибочные расширения на малом контрпримере

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

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

Один итоговый тип на всей трассе

Условие. Учебные Bool, Int и тотальное сложение. Терм: if ((λb:Bool.b) true) then ((λn:Int.n+3) 4) else 0.

  1. Условие имеет тип Bool; применение в then имеет тип Int; else также Int. Весь терм получает Int.
  2. Сокращение условия даёт if true then ((λn:Int.n+3) 4) else 0; итоговый тип остаётся Int.
  3. Выбирается then: ((λn:Int.n+3) 4), по-прежнему Int.
  4. Бета-шаг даёт 4+3, арифметический шаг — 7. Оба выражения имеют тип Int, последнее является значением.

Ответ. Трасса заканчивается значением 7 типа Int; каждый промежуточный терм также имеет итоговый тип Int.

Проверка. Замена else на false нарушила бы правило одинакового типа ветвей ещё до вычисления, хотя условие в данном запуске истинно.

Где легко ошибиться. Успешная проверка типов относится к определённым правилам языка. Она не является универсальным обещанием завершения, прикладной правильности и отсутствия любых реальных сбоев.

Проверьте понимание

Что непосредственно утверждает прогресс для замкнутого корректно типизированного терма?

Вопросы к этой главе

Зачем в прогрессе требовать замкнутый терм?

Свободная переменная может иметь объявленный тип, но не иметь значения для выполнения. Теорема должна явно учитывать окружение или ограничить термы замкнутыми.

Можно доказать type soundness тестированием?

Тесты обнаруживают контрпримеры и проверяют реализацию на выбранных данных. Общее утверждение обо всех допустимых термах требует доказательства по правилам системы.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Software Foundations: Properties of STLC

    Проверены роли прогресса, сохранения и подстановки. Учебное расширение с Int и его конкретная трасса заявлены отдельно от полного формального доказательства.

Инвариант цикла: сумма растёт, утверждение сохраняется

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

Перед началом: Предусловие и постусловие; Индукция; Математические целые без переполнения.

Семь итераций ещё не доказывают общее правило

Программа начинает с i=0, s=0 и, пока i<n, выполняет s=s+3i+2, затем i=i+1. При n=7 она складывает 2,5,8,11,14,17,20 и получает 77. Но успешный запуск не объясняет результат для произвольного n. Нужно утверждение, которое связывает текущий счётчик с уже накопленной частью суммы и остаётся верным после каждой итерации.

Работаем с математическими целыми и постоянным n≥0. Это исключает скрытое переполнение машинного типа и изменение границы цикла извне. Цель — после завершения получить s=n(3n+1)/2. Если эти предпосылки поменять, доказательство придётся проверить заново. Например, отрицательное n меняет связь между отсутствием итераций и ожидаемой формулой; параллельное изменение n разрушает выбранную меру продвижения.

Инвариант описывает уже обработанный префикс

Возьмём I: 0≤i≤n и s=i(3i+1)/2. Перед первой проверкой условия i=s=0, поэтому I выполнен. Выражение справа равно сумме первых i членов последовательности 3k+2 при k от нуля до i−1. Инвариант говорит именно об обработанных членах, а не о будущей полной сумме, которую ещё предстоит получить.

На входе в тело известно I вместе с i<n. После первого присваивания s становится i(3i+1)/2+3i+2=(i+1)(3i+4)/2. Затем счётчик увеличивается, и та же формула принимает вид s=i_new(3i_new+1)/2. Условие i<n гарантирует верхнюю границу нового i. Таким образом, тело сохраняет все части I, а не только арифметическое равенство.

Выход использует и инвариант, и отрицание условия

Когда цикл заканчивается, известно i≥n. Инвариант одновременно даёт i≤n, поэтому i=n. Подстановка в равенство накопителя даёт требуемое постусловие. Одного инварианта без информации о выходе было бы недостаточно: при i=0 он верен и до вычисления всей суммы. Одного ложного условия также недостаточно, потому что оно ничего не говорит о s.

В логике Хоара такая схема обосновывает частичную корректность: если программа завершилась при выполненных предпосылках, постусловие верно. Чтобы не подменить это обещанием обязательного завершения, отдельно зададим вариант V=n−i. При истинном условии он положителен, после тела уменьшается ровно на единицу и остаётся неотрицательным. Бесконечно убывать в натуральных значениях он не может.

Порядок присваиваний входит в доказательство

Первое присваивание использует старое i. Если увеличить счётчик раньше, вместо последовательности 2,5,… начнётся 5,8,… . Текст почти тот же, но выбранный инвариант больше не сохраняется. В рассуждении по присваиванию значение правой части вычисляется в предыдущем состоянии; обозначения i_old и i_new помогают не заменить его незаметно уже обновлённой переменной.

Для собственной проверки выпишите предусловие, инициализацию, сохранение, выход и вариант завершения как разные обязанности. Слабое утверждение вроде s≥0 может сохраняться, но не вывести нужную точную сумму. Слишком сильное s=n(3n+1)/2 не выполнено вначале. Удачный инвариант достаточно точен для постусловия и одновременно верен для каждого промежуточного префикса работы, а не только для финального числа.

Накопитель для n=7

Условие. n=7; i=0; s=0. Пока i<n: сначала s=s+3i+2, затем i=i+1. Все числа математические целые.

  1. Инициализация даёт s=0=0·(3·0+1)/2 и 0≤i≤7.
  2. Общий переход переводит i(3i+1)/2 в (i+1)(3i+4)/2, затем обновляет i.
  3. При выходе i=7, поэтому s=7·22/2=77. Вариант 7−i убывал от 7 до 0.
  4. Независимо складываем 2+5+8+11+14+17+20=77. Если переставить присваивания, получится 5+8+11+14+17+20+23=98.

Ответ. Исходный цикл возвращает 77; выбранный инвариант и вариант обосновывают правильность и завершение для любого n≥0.

Проверка. Разница при перестановке равна 3n=21 для n=7. Она возникает из-за другого набора членов, а не из-за ошибки округления.

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

Проверьте понимание

Что вместе с I позволяет вывести i=n при выходе?

Вопросы к этой главе

Любое сохраняющееся утверждение годится как инвариант?

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

Почему нужен запрет переполнения?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Software Foundations: Hoare Logic

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

Темы направления

Целочисленная арифметика: сравнения и алгоритмы

Обзор модуля

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

Булева логика: отрицание, импликация и эквивалентность схем

Обзор модуля

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

Алгоритмы на графах: представление, пути и зависимости

Обзор модуля

Выбор представления графа, условия алгоритма Дейкстры, топологический порядок и длиннейший путь в DAG: сравнение задач и гарантий алгоритмов.

Графовые задачи: существование, построение и точный подсчёт

Обзор модуля

Реализация степеней, маршруты, зависимости, раскраски, назначения и остовы с независимыми проверками результата.

Двоичные представления: коды, рекурсии и эскизы

Обзор модуля

Как компактная запись хранит информацию: интервалы арифметического кода, GF(2), линейная рекурсия и слияние регистров.

Автоматы и границы алгоритмического доказательства

Обзор модуля

Детерминизация, различимость префиксов, накачка и неразрешимость семантических свойств программ.

Разобранный пример

Сколько порядков удовлетворяет зависимостям?

Работы A–E выполняются по одной, каждая ровно один раз. Даны рёбра A→C, B→C, B→D, C→E, D→E. Найдите число допустимых полных порядков; длительности работ не учитываются.

  1. Сначала доступны только A и B: у остальных есть невыполненный предшественник. E всегда последняя, поскольку от каждой другой вершины к ней идёт путь.
  2. Если первой выбрана A, второй обязана быть B. После AB можно переставлять C и D: получаем ABCDE и ABDCE — два случая.
  3. Если первой выбрана B, второй может быть A или D. После BA остаются два порядка: BACDE и BADCE. После BD сначала требуется A, затем C и E: BDACE — ещё один.
  4. Ветви «первая A» и «первая B» не пересекаются и исчерпывают все начала. Поэтому число равно 2+(2+1)=5; это обоснование полноты, а не только найденный список.
  5. Проверьте каждую из пяти записей по пяти исходным рёбрам: позиция начала должна быть меньше позиции конца. Это проверяет допустимость перечисленного, а разбор ветвей доказывает отсутствие пропусков.

Ответ: Пять порядков: ABCDE, ABDCE, BACDE, BADCE, BDACE.

Проверка: Независимая конечная проверка — перебрать 120 перестановок и отобрать те, где pos(A)<pos(C), pos(B)<pos(C), pos(B)<pos(D), pos(C)<pos(E), pos(D)<pos(E). Отбор даёт те же пять; доказательство через ветви объясняет этот результат без полного перебора.

Проверьте понимание

К исходному графу добавили A→E. Что произойдёт с числом допустимых порядков?

Вопросы по направлению

Чем граф отличается от рисунка функции?

Граф зависимостей — это вершины и рёбра между ними; координаты нарисованных точек не входят в задачу. График функции показывает соответствие аргумента и значения. Положение вершины на листе не делает её более ранней работой.

Почему один найденный порядок ещё не решает задачу подсчёта?

Один порядок доказывает существование расписания. Для подсчёта требуется описать все варианты без повторов и показать полноту. В примере эту работу выполняет разбиение по первым доступным вершинам.

Можно ли считать кратчайший путь и порядок работ одним алгоритмом?

У этих задач разные ответы. Кратчайший путь минимизирует сумму весов, а топологический порядок согласует зависимости. Дейкстра требует неотрицательных весов; для конечного DAG порядок существует независимо от численных весов.

Зачем после вычисления нужен сертификат?

Сертификат позволяет проверить конкретное утверждение независимо от способа поиска. Для порядка это сравнение позиций концов каждого ребра. Для оптимальности или точного количества такой проверки допустимости мало: нужно ещё обоснование границы или полноты.

Почему таблица истинности доказывает эквивалентность?

Для формул с фиксированным конечным набором n булевых переменных есть ровно 2ⁿ наборов значений. Совпадение результатов на всех строках исчерпывает эту область. Несколько случайных строк дают только частичную проверку.

Основа объяснения

  • MIT OpenCourseWare: Mathematics for Computer Science

    Официальный учебный каталог: логика, теория чисел, ориентированные графы и правила подсчёта. Задача пяти работ и её разбор составлены для этого введения.