Информатика · объяснение и практика

Почему ложное условие не опровергает импликацию

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Логика и логические схемы · Учебная карта

Главная мысль

Чтобы проверить правило P → Q на конечной таблице, найдите строки, где P истинно, а Q ложно. Только они нарушают импликацию. Отсутствие таких строк подтверждает правило для проверенной таблицы; оно не доказывает закон для всех будущих данных.

Проверка начинается с набора строк

В каталоге четыре записи: у А стоят признаки P=1, Q=1; у Б — P=1, Q=0; у В — P=0, Q=1; у Г — P=0, Q=0. Здесь единица означает «истинно», ноль — «ложно», а оба признака заранее известны. Нужно проверить требование: у каждой записи с признаком P должен быть признак Q. Нарушитель — Б. Запись В показывает другое свойство: Q встречается и без P. Это разрешено исходным требованием.

Такую проверку удобно представить двумя действиями. Сначала отберите все строки с P=1. Затем среди отобранных найдите Q=0. В таблице остались А и Б, из них не прошла Б. Формула нарушения имеет вид P и не Q; допустимость одной строки задаётся как не P или Q. Остальные строки не скрывают нарушение, потому что требование к ним не предъявлялось.

Если проверяется высказывание «для всех записей P → Q», одного нарушителя достаточно для отрицательного ответа. Три подходящие записи из четырёх не делают это всеобщее утверждение истинным. Доля прошедших строк может понадобиться для отдельного отчёта, но она отвечает на другой вопрос. Укажите, проверяете ли вы всеобщее правило, отдельную строку или статистическую долю.

Пример

Удалили запись Б. Какие строки нарушают P → Q, а какие нарушают Q → P?

В оставшихся А, В, Г первое правило не нарушено. Обратное правило нарушает В: у неё Q=1 и P=0. Значит, проверка исходного направления не подтверждает обратное.

Пустой отбор не означает полноту данных

Пусть в новой таблице только В и Г. Отбор P=1 пуст. Контрпримеров к P → Q в этой таблице нет, поэтому всеобщее требование для неё выполнено. Но таблица ничего не показала о записях с P=1: таких наблюдений не было. Логическое выполнение ограничения и наличие подходящих наблюдений следует выводить отдельно. При необходимости добавляют вторую проверку: существует ли хотя бы одна запись с P=1.

Теперь заменим известное Q у записи с P=1 на «не измерено». Это уже не один из четырёх случаев классической таблицы истинности. Неизвестность нельзя без договорённости кодировать нулём, иначе отсутствие измерения превратится в ложность признака. Для такой записи сообщите, что данных для проверки не хватает, либо заранее выберите отдельную модель работы с пропусками. Значения NULL в базе данных тоже требуют собственных правил.

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

Меняем направление и проверяем смысл результата

В терминах множеств правило требует, чтобы множество строк с P=1 входило во множество строк с Q=1. Удаление нарушителя Б обеспечило это включение. Обратная импликация потребовала бы противоположного включения; запись В ему мешает. Для равносильности нужны оба включения, то есть одинаковые множества подходящих строк. Это позволяет проверить направление по данным без подмены стрелок.

Равносильная исходному правилу контрапозиция имеет вид не Q → не P. У неё тот же запрещённый набор P=1, Q=0. Можно перепроверить результат по тем же строкам, не меняя фактов. Простая перестановка P и Q или только отрицание обеих частей даёт другие требования. Сначала выпишите, какая именно строка опровергает новую запись.

Совпадение признаков не объясняет их причину. Таблица может удовлетворять правилу из-за фильтра отбора, устройства каталога или случайного состава наблюдений. Материальная импликация описывает допустимые сочетания значений, а не устанавливает физический механизм. Оператор if, в свою очередь, выбирает ветвь выполнения; сам по себе он не проверяет все строки и не доказывает всеобщее ограничение.

В ответе полезно назвать область проверки, найденных нарушителей и ограничения вывода. Для нашей исходной таблицы это звучит так: «Правило не выполнено: запись Б имеет P=1 и Q=0». После её удаления: «В оставшихся трёх записях контрпримеров нет; обратное правило не выполнено из-за В». Такой ответ можно проверить по исходным данным.

От чтения к действию

А теперь — вы

В таблице только две полностью известные строки: P=0,Q=1 и P=0,Q=0. Какой вывод о правиле «для всех этих строк P → Q» корректен?

Частые вопросы

Если строк с P=1 нет, правило нарушено?

Нет: в полностью известной конечной таблице нет строки с P=1 и Q=0. Но существование записей с P=1 этой проверкой не подтверждено; его проверяют отдельно.

Успешная проверка таблицы доказывает правило навсегда?

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

Как найти контрпример к обратной импликации?

Для Q → P найдите строку с Q=1 и P=0. У исходного P → Q нарушитель имеет противоположное сочетание: P=1 и Q=0.

Углублённый разбор

Интуиционистская импликация и необратимость контрапозиции

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

Перед началом: Классическая импликация; Доказательство от предположения.

Один вывод не использует исключённого третьего

Из P→Q можно получить ¬Q→¬P без классического снятия двойного отрицания. Допустим ¬Q и затем P. По исходной импликации получаем Q, что противоречит ¬Q. Значит из предположения P выводится противоречие, то есть доказано ¬P. Этот ход остаётся допустимым в интуиционистской логике.

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

Миры обозначают расширение подтверждённых сведений

В модели Крипке миры упорядочены отношением доступности, которое рефлексивно и транзитивно. Атом, подтверждённый в мире, остаётся подтверждённым во всех следующих. Мир w подтверждает A→B, если в каждом доступном v из подтверждения A следует подтверждение B. Проверяется и сам w, поскольку доступность рефлексивна.

Отрицание A означает A→⊥. Значит ¬A подтверждается тогда, когда A не подтверждается ни в одном доступном мире. Отсутствие подтверждения A сейчас не равносильно подтверждению ¬A: позднее A может стать известным. Это ключевое отличие от присваивания каждому атому готового классического значения в текущей строке таблицы.

Контрмодель проверяет конкретное недопустимое обращение

Чтобы опровергнуть обратную контрапозицию, достаточно мира, где ¬Q→¬P подтверждено, а P→Q нет. Нужно проверить все доступные миры в определении стрелки, а не только выписать значения атомов в начале. Иначе модель незаметно превратится в классическую оценку и потеряет требуемое различие.

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

Два этапа знания

Условие. Есть миры w₀≤w₁. Атом P подтверждён в обоих, а Q — только в w₁. Проверьте в w₀ формулы P→Q и ¬Q→¬P.

  1. Монотонность атомов соблюдена: подтверждённый P не исчезает, а Q добавляется на следующем этапе.
  2. P→Q не подтверждается в w₀: сам w₀ доступен, в нём P подтверждено, а Q нет. Это явный нарушающий мир.
  3. ¬Q не подтверждается ни в w₀, ни в w₁, поскольку из каждого доступен w₁ с Q. Поэтому во всех проверяемых мирах предпосылка ¬Q отсутствует.
  4. Следовательно, ¬Q→¬P подтверждается в w₀. Его следствие не приходится требовать ни в одном доступном мире, а обратная импликация P→Q остаётся неподтверждённой.

Ответ. В w₀ подтверждено ¬Q→¬P, но не P→Q. Обратная контрапозиция в общем случае недопустима.

Проверка. Прямая рекурсивная оценка по двум доступным мирам даёт также ¬¬Q в w₀, но не Q. Это независимо локализует недостающий классический шаг.

Где легко ошибиться. Не отождествляйте «Q пока не подтверждено» с «подтверждено ¬Q». Отрицание в этой семантике требует отсутствия Q во всех будущих доступных мирах.

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

Какая формула подтверждается в w₀ из задачи?

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

Прямая контрапозиция тоже перестаёт работать?

Нет. Её доказательство использует применение импликации и введение отрицания через противоречие из допущения. Снятие двойного отрицания для неё не требуется.

Доступность обязательно означает реальное время?

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

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

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

  • Dafina Trufas: Intuitionistic Propositional Logic in Lean, §3.4

    Первичная исследовательская статья: прочитаны определение монотонной оценки модели Крипке и семантика импликации во всех доступных мирах, страницы 138–139. Двухмировой контрпример главы и его значения рассчитаны отдельно.

Хорновы правила и наименьшая модель прямого вывода

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

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

Тело правила должно быть подтверждено целиком

Рассмотрим конечные правила a₁∧…∧aₖ→b с положительными атомами и одной положительной головой. Пустое тело означает факт. Если все атомы тела уже известны, можно добавить голову. Известные атомы никогда не удаляются, а отрицательные предпосылки в выбранный язык не входят.

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

Индукция даёт и корректность, и наименьшую модель

Каждый добавленный атом истинен во всякой модели правил: это верно для фактов и сохраняется применением импликации к уже истинному телу. Поэтому итоговое множество C содержится в каждой модели. Когда ни одно правило больше не добавляет атомов, оценка «истинны ровно атомы C» сама удовлетворяет всем правилам.

Действительно, если тело истинно в этой оценке, все его атомы находятся в C, а остановка гарантирует наличие головы. Значит C — модель и одновременно подмножество всех остальных моделей: наименьшая по включению. Для положительного атома q получаем точный критерий: база влечёт q тогда и только тогда, когда q∈C.

Неподдержанный цикл не создаёт факты

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

Если q не попал в C, найдена модель с ложным q, значит q не следует из базы. Но ¬q также может не следовать: другая модель способна сделать q истинным. Договор замкнутого мира иногда принимает недоказанное за ложное для программного запроса; это дополнительная семантика, а не теорема классической импликации.

Цикл ждёт внешнего подтверждения

Условие. Даны факт a и правила a→b,(b∧c)→d,d→c,c→e,e→f. Найдите наименьшую модель и выясните, следует ли c или ¬c. Затем добавьте факт c.

  1. Из a выводится b. После этого известны только {a,b}: для d не хватает c, а для c — d.
  2. Ни e, ни f пока не получаются. Итог C={a,b} сам удовлетворяет всем правилам, поэтому c не является следствием.
  3. Оценка со всеми шестью истинными атомами тоже является моделью. Она опровергает вывод ¬c. Следовательно, база не влечёт ни c, ни его отрицание.
  4. После добавления факта c выводятся d из b,c, затем e и f. Новая наименьшая модель содержит все шесть атомов.

Ответ. До нового факта C={a,b}; ни c, ни ¬c не следуют. После добавления c получаем {a,b,c,d,e,f}.

Проверка. Перебор 64 двоичных оценок даёт четыре модели исходной базы; пересечение их истинных атомов равно {a,b}. С фактом c остаётся единственная модель всех истинных атомов.

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

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

Какой атом обязан быть истинным в каждой модели исходной базы?

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

Почему алгоритм всегда остановится?

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

Что изменится при отрицательных предпосылках?

Оператор может перестать быть монотонным: добавление факта способно отключить прежнее правило. Доказательство наименьшей модели из этой главы тогда не переносится автоматически.

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

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

  • David Poole, Alan Mackworth: Artificial Intelligence3E, §5.3

    Первичный авторский учебник: прочитаны definite clauses, Bottom-Up Proof Procedure, soundness и minimal model. Собственная база с неподдержанным циклом и все её модели не копируют электрический пример источника.

Две импликации на клаузу и критерий выполнимости 2-SAT

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

Перед началом: Импликация и дизъюнкция; Сильно связная компонента.

Каждая клауза порождает два направленных ребра

Для клаузы (ℓ∨m) создаём рёбра ¬ℓ→m и ¬m→ℓ. Если один литерал ложен, другой обязан быть истинным; это ровно два способа применения клаузы. Вершины графа — все литералы x и ¬x. Путь ℓ→m означает, что истинность ℓ последовательно вынуждает m в любой модели КНФ.

Нужно добавить оба ребра, даже если одно кажется повторением другого. Граф обладает симметрией контрапозиции: ребру u→v соответствует ¬v→¬u, а пути — обратный путь между отрицаниями. Именно эта структура используется в достаточной части критерия. Единичную клаузу можно записать как (ℓ∨ℓ), что создаёт обязательное ребро ¬ℓ→ℓ.

Одна компонента с противоположными литералами запрещает модель

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

Обратно, если ни одна компонента не содержит противоположных литералов, сожмём компоненты в DAG и дадим им топологические номера, возрастающие вдоль рёбер. Присвоим x=1, если номер компоненты x больше номера компоненты ¬x. Если бы существовало нарушенное ребро u→v с u истинным, v ложным, ребро ¬v→¬u и топологические неравенства дали бы невозможный цикл строгих сравнений. Значит все импликации и исходные клаузы выполнены.

Нумерация алгоритма не заменяет соглашение о порядке

Разные реализации SCC нумеруют компоненты в противоположных направлениях. Правило сравнения номеров нужно согласовать с тем, возрастают они вдоль рёбер или убывают. Произвольное сравнение внутренних идентификаторов может построить неправильную модель даже при верно найденных компонентах. Стоимость построения графа и SCC линейна по числу переменных и клауз; это специальное свойство 2-SAT, не обещание такого же алгоритма для произвольной КНФ.

Два пути между c и ¬c

Условие. Проверьте F=(a∨b)∧(¬a∨c)∧(¬b∨c)∧(¬c∨d)∧(¬c∨¬d) через импликационный граф.

  1. Из последних двух клауз есть рёбра c→d и d→¬c. Значит существует путь c→d→¬c.
  2. Из (¬a∨c) получаем ¬c→¬a, из (a∨b) — ¬a→b, из (¬b∨c) — b→c. Это обратный путь ¬c→¬a→b→c.
  3. Следовательно c и ¬c лежат в одной SCC. Ни одно значение c не совместимо со всеми импликациями, поэтому F невыполнима.
  4. Независимо первые три клаузы требуют c=1: при c=0 они заставляют a=b=0 и нарушают a∨b. Последние две при c=1 требуют одновременно d и ¬d.

Ответ. Формула невыполнима; свидетельство — два приведённых пути между c и ¬c.

Проверка. Полный независимый перебор 16 наборов a,b,c,d не находит модели. Каждое ребро двух путей отдельно сверено с конкретной исходной клаузой.

Где легко ошибиться. Не проверяйте только один путь x→¬x: он может просто вынуждать x=0. Противоречие требует пути и обратно либо иной структуры, заставляющей оба литерала.

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

Какой вывод верен для F из задачи?

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

Почему одно ребро x→¬x не делает формулу невыполнимой?

Оно выражает запрет значения x=1; значение x=0 может удовлетворять всей формуле. Для взаимного принуждения нужна сильная связность противоположных литералов.

Можно ли применить конструкцию к клаузе из трёх литералов?

Прямая замена такой клаузы парными импликациями меняет её смысл. Условие ложности одного литерала ещё оставляет выбор между двумя другими. Поэтому критерий здесь относится к исходной 2-КНФ.

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

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

  • Chun-Hung Liu: 2-SAT, lecture 2023-02-13

    Прочитан §1: две импликации из клаузы, противоположные литералы и сильно связные компоненты, порядок компонент для модели. Собственная формула из пяти клауз проверена независимо всеми 16 присваиваниями.

Бисимуляция сохраняет модальные наблюдения

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

Перед началом: Ориентированный граф; Рекурсивная семантика логики.

Модальные операторы наблюдают доступные состояния

Модель состоит из состояний, отношения перехода R и истинных в каждом состоянии атомов. Формула ◇φ истинна, если есть непосредственный преемник с φ; □φ — если φ истинна у всех непосредственных преемников. В терминальном состоянии ◇φ ложна, а □φ истинна независимо от φ. Здесь это обычная классическая модальная семантика, без монотонного накопления знаний из интуиционистских моделей.

Отношение Z между двумя моделями является бисимуляцией, если для каждой связанной пары совпадают все атомы и выполнены два условия. Forth: каждому переходу первой модели отвечает переход второй к связанной паре. Back: каждому переходу второй отвечает переход первой. Один преемник может соответствовать нескольким; отношение не обязано быть функцией или взаимно однозначным отображением.

Доказательство сохранения идёт по строению формулы

Для атомов сохранение заложено в определении, для отрицания и булевых связок следует из индукционного предположения. Если в первой модели истинна ◇φ, условие forth переносит свидетельствующий переход во вторую, а индукция сохраняет φ. Условие back даёт обратное направление. Для □ можно применить двойственность □φ=¬◇¬φ. Поэтому связанные состояния удовлетворяют одним и тем же формулам базовой модальной логики.

Совпадения атомарных меток всех достижимых состояний без согласования шагов недостаточно. Длина и ветвление переходов могут менять ◇◇p, даже если множество когда-либо встречающихся меток то же. Бисимуляция контролирует именно локальные шаги в обе стороны. Она сильнее простого перечня достижимых наблюдений, но слабее изоморфизма размеченных графов.

Число неразличимых преемников в языке не выражается

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

Одна ветвь соответствует двум

Условие. В M есть переход r→t, в N переходы u→v и u→w. Других переходов нет. Атом p истинен только в t,v,w. Проверьте бисимуляцию корней и сравните ◇p и ◇◇p.

  1. Возьмём Z={(r,u),(t,v),(t,w)}. В корнях p ложен, в остальных связанных парах истинен: атомарное условие выполнено.
  2. Для пары (r,u) переход r→t согласуем с u→v. Обратно оба перехода u→v и u→w согласуются с тем же r→t через разные пары Z.
  3. Пары (t,v),(t,w) терминальны с обеих сторон, поэтому forth и back выполнены без дополнительных требований. Z действительно бисимуляция, хотя размеры моделей различны.
  4. В обоих корнях ◇p истинна, а ◇◇p ложна: преемники имеют p, но не имеют собственных переходов. После добавления петли w→w в N в u станет истинной ◇◇p, и прежняя эквивалентность исчезнет.

Ответ. Корни r,u бисимилярны; ◇p истинна в обоих, ◇◇p ложна в обоих.

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

Где легко ошибиться. Не требуйте биекции состояний и не заменяйте back одним forth. Одностороннее моделирование переходов не гарантирует равенства всех модальных наблюдений.

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

Какая формула истинна в обоих исходных корнях r и u?

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

Почему □p истинна в обоих корнях?

Все их непосредственные преемники имеют p. Это не означает p в самом корне: оператор проверяет следующий шаг. Поэтому □p∧p в корнях ложна.

Почему после петли никакое другое отношение не спасёт эквивалентность?

Формула ◇◇p стала истинной во втором корне и осталась ложной в первом. Инвариантность при бисимуляции запрещает существование любой бисимуляции, связывающей эти корни, независимо от выбора отношения.

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

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

  • Yde Venema: Ultrafilter Unions, §2 Bisimulations

    Прочитаны prop/forth/back и Proposition2 о сохранении модальных формул. Ультрафильтры из дальнейшей статьи не используются. Две маленькие модели и контрпример с добавленной петлёй созданы отдельно. Попытка hml.pdf на Stanford завершилась timeout и не считается чтением.

Интерполянт Крейга разделяет несовместимые формулы общими переменными

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

Перед началом: Импликация и невыполнимость конъюнкции; Таблица истинности булевой формулы.

Три требования вместо одного противоречия

Пусть A∧B невыполнима. В пропозициональной постановке интерполянт I должен выполнять три условия: A⇒I общезначимо; I∧B невыполнима; переменные I входят одновременно в словари A и B. Первые два условия отвечают за логическое разделение, третье запрещает переносить частные подробности одной стороны. Само сообщение «противоречие найдено» ещё не предъявляет такой промежуточной формулы.

Эта постановка эквивалентна интерполяции импликации A⇒¬B. Здесь заранее фиксирована именно пара несовместимых формул, поэтому важно не перепутать B с ¬B при проверке. Например, требование I⇒B означало бы противоположный вывод. Далее работаем с конечными булевыми формулами; особенности арифметических теорий и кванторов в эту конструкцию не включаются.

Исключение частной переменной

Возьмём A=(u∨p)∧(¬u∨q), B=¬p∧¬q∧(v∨¬v). Общие переменные — p, q, а u и v частные. Если u=false, A сводится к p; если u=true — к q. Поэтому существование подходящего u выражает I=p∨q. Это проекция допустимых назначений A на общие координаты. Мы не утверждаем, что I и A эквивалентны на полном словаре с сохранённым u.

Докажем A⇒I без перебора: если p=q=false, первая скобка A требует u, а вторая ¬u, что невозможно. Далее I∧B требует одновременно p∨q и ¬p∧¬q, поэтому тоже невозможно. Формула I не содержит u или v. Так проверены все три требования, причём проверка словаря не заменяется логической эквивалентностью или похожей записью.

Как распознать слишком сильный и слишком слабый ответ

Кандидат p∧q слишком силён: A истинна при u=false, p=true, q=false, тогда как кандидат ложен. Константа true слишком слаба: она совместна с B при p=q=false. Сама A логически отделяет B, но содержит частную u и потому не подходит как интерполянт этой пары. Эти отказы относятся к разным условиям и помогают локализовать ошибку построения.

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

Устранить u, сохранив причину несовместности

Условие. Для A=(u∨p)∧(¬u∨q) и B=¬p∧¬q∧(v∨¬v) постройте интерполянт и объясните, почему p∧q и true не подходят.

  1. Общий словарь равен{p, q}; переменные u, v в искомой формуле запрещены.
  2. Подстановки u=false и u=true дают соответственно p и q, поэтому проекция A имеет вид I=p∨q.
  3. A⇒I: назначение p=q=false вынуждало бы одновременно u и¬u. I∧B несовместна из-за p∨q и¬p∧¬q.
  4. Кандидат p∧q опровергается моделью A: u=false, p=true, q=false. Кандидат true не противоречит B при p=q=false.

Ответ. I=p∨q удовлетворяет всем трём условиям. p∧q слишком силён, true слишком слабо.

Проверка. Перебор 16 назначений u, p, q, v подтверждает отсутствие модели A∧¬I и I∧B. Во всех формулах I используются только p, q.

Где легко ошибиться. Проверяйте общий словарь отдельно: логически достаточная формула с частными переменными ещё не является допустимым интерполянтом.

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

Какая из формул является интерполянтом разобранной пары?

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

Нужно ли сохранять значение частной u?

Нет. I описывает следствие на общих p, q. Разные значения u могут давать разные внутренние способы выполнения A, которые не требуется передавать второй стороне.

Почему нельзя просто взять первую формулу A?

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

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

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

  • CMU15-414: CEGAR & Craig Interpolation, §3

    Условия интерполяции и идея исключения частной булевой переменной. Пара A, B, таблица проверок и два отклонённых кандидата выбраны для этой главы.

Устранение целого квантора сохраняет остаточные классы

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

Перед началом: Целочисленное деление с остатком; Квантор существования и равносильность формул.

Замена переменной требует сохранить образ решётки

Переменные x и y целые; устраняется один квантор существования из полосы линейных неравенств с одним условием сравнения по модулю. Разбирается частный точный случай, а не реализация полного алгоритма Купера.

В условии 2y−1≤3x≤2y+7 и x≡2 mod 4 удобно обозначить z=3x. Однако z не становится произвольным целым числом: из x=4k+2 получается z=12k+6. Обратно, всякое такое z даёт целое x=4k+2. Поэтому исходная формула точно равносильна существованию z в той же полосе с остатком 6 по модулю 12.

Если оставить только неравенства, получится другая задача. Например, интервал всегда содержит вещественные точки, а многие целые точки не делятся на 3 или дают неверный остаток для x. Дополнительное условие делимости после масштабирования является частью доказательства равносильности, а не необязательным ускорением поиска.

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

Запишем y=6q+r, где 0≤r<6. Это евклидово деление применяется и к отрицательным y: например, −3=6·(−1)+3. После вычитания 12q полоса становится [2r−1,2r+7], а допустимые значения z−12q имеют вид 12j+6.

При всех шести остатках левая граница не меньше −1, правая не больше 17. Соседние допустимые точки −6 и 18 уже находятся снаружи. Следовательно, проверить достаточно единственную точку 6. Она лежит в полосе тогда и только тогда, когда 2r−1≤6≤2r+7, то есть r принадлежит {0,1,2,3}. Это одновременно доказывает полноту конечной проверки.

Результат должен описывать все параметры и давать обратное построение

Формула без квантора имеет вид y≡0∨1∨2∨3 mod 6, где запись означает дизъюнкцию четырёх отдельных сравнений. При любом разрешённом остатке свидетель x=4q+2 выполняет исходную систему. При двух запрещённых остатках нет другой подходящей точки решётки: обе соседние уже исключены оценками границ.

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

Полоса ширины восемь и редкая решётка

Условие. Для целого параметра y устраните x из ∃x∈Z: 2y−1≤3x≤2y+7 и x≡2 mod 4. Проверьте параметры 9,10,−3,−1.

  1. Полагаем z=3x. Допустимые z имеют точный вид 12k+6; это необходимое и достаточное преобразование сравнения для x.
  2. Делим y=6q+r с 0≤r≤5. В нормализованной полосе [2r−1,2r+7] единственным возможным представителем класса 6 mod 12 является 6.
  3. Неравенства для этой точки дают 2r−1≤6 и 6≤2r+7. Среди шести остатков подходят ровно 0,1,2,3.
  4. Для y=9 берём q=1 и x=6: 17≤18≤25. Для y=−3 берём q=−1 и x=−2: −7≤−6≤1. Остатки параметров 10 и −1 равны 4 и 5, поэтому свидетеля нет.

Ответ. Равносильное условие: y mod 6∈{0,1,2,3}. На этом множестве x=4⌊y/6⌋+2 является свидетелем; 9 и −3 разрешены, 10 и −1 запрещены.

Проверка. Независимо подставляем x=4k+2 в исходные границы: 2y−7≤12k≤2y+1. Для каждого из шести остатков y это даёт ту же таблицу существования целого k; общий сдвиг y на 6 сдвигает k на 1.

Где легко ошибиться. Усечение отрицательного частного к нулю не является евклидовым делением. Для y=−3 нужны q=−1,r=3; неверный остаток ломает готовую формулу.

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

Какое условие равносильно существованию целого x в разобранной системе 2y−1≤3x≤2y+7, x≡2 mod 4?

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

Почему ширина полосы не гарантирует существование свидетеля?

После нормализации соседние допустимые z отстоят на 12, а ширина полосы равна 8. Непустой вещественный интервал может целиком лежать между точками этой решётки; именно это происходит при остатках параметра 4 и 5.

Доказывает ли проверка многих y формулу для всех целых параметров?

Сама по себе нет. Все целые y охвачены доказанным разложением 6q+r и инвариантным сдвигом границ на 12q. Конечная таблица здесь полна благодаря этому тождеству, а не благодаря выбранной длине экспериментального перебора.

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

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

  • University of Iowa: Quantifier Elimination, Presburger Arithmetic

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

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

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

Перед началом: КНФ и проверка присваивания; Выполнимость конъюнкции клауз.

Два разных требования к маленькому объяснению

Конечная невыполнимая КНФ; каждый запрос о выполнимости решается точно. Минимальность понимается по включению, а наименьшая мощность — как отдельная оптимизационная задача.

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

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

Один проход использует монотонность выполнимости

Начинаем со всего невыполнимого набора U. Для очередной клаузы C проверяем U без C. Если оставшееся невыполнимо, C удаляем. Если появляется модель, C сохраняем: эта модель подтверждает необходимость C для текущего противоречия. После прохода U остаётся невыполнимым, потому что разрешены только удаления с доказанным сохранением этого свойства.

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

Сертификаты должны объяснять и противоречие, и необходимость

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

Практический решатель может вернуть неизвестность или исчерпать лимит. Такой ответ не равен ни SAT, ни UNSAT. Безопасно сохранить сомнительную клаузу, однако после этого нельзя объявлять результат доказанно минимальным, если для неё не установлена модель при удалении. Для небольшого примера полная таблица истинности даёт точный оракул и позволяет отдельно найти минимум мощности.

Проход оставляет длинную причину конфликта

Условие. Клаузы: C1=(p), C2=(¬p), C3=(q), C4=(¬q∨r), C5=(¬r). Выполните удаление в порядке 1,2,3,4,5 и сравните результат с ядром наименьшей мощности.

  1. Удаляем C1: клаузы C3,C4,C5 по-прежнему требуют q=true, затем r=true и r=false. Удаляем также C2, поскольку то же противоречие остаётся.
  2. Пробуем удалить C3 из {C3,C4,C5}. Назначение q=false,r=false удовлетворяет C4 и C5, поэтому C3 сохраняем.
  3. Пробуем удалить C4. Назначение q=true,r=false удовлетворяет C3,C5. Затем пробуем удалить C5: q=true,r=true удовлетворяет C3,C4. Обе клаузы сохраняем.
  4. Получено ядро {C3,C4,C5} размера 3, минимальное по включению. Однако {C1,C2} уже невыполнимо и имеет размер 2. Каждая отдельная исходная клауза выполнима, поэтому минимум мощности равен 2.

Ответ. Алгоритм возвращает {3,4,5}; это минимальное по включению, но не наименьшее по мощности ядро. Наименьшее ядро здесь {1,2}.

Проверка. Перебор восьми присваиваний p,q,r для всех 32 подмножеств клауз даёт ровно два минимальных ядра: {1,2} и {3,4,5}. Явные модели трёх удалений независимо подтверждают минимальность длинного ядра.

Где легко ошибиться. Слово «минимальное» без уточнения порядка вводит в заблуждение: локальная невозможность удаления не доказывает глобальный минимум числа ограничений.

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

Как верно описать результат удаления в порядке 1,2,3,4,5 для пяти клауз разобранного примера?

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

Может ли другой порядок найти ядро {1,2}?

Да. Если сначала проверять C3,C4,C5, противоречие p∧¬p позволяет удалить их все. После этого обе оставшиеся единичные клаузы необходимы. Порядок меняет найденное объяснение, сохраняя гарантию минимальности по включению.

Нужны ли значения всех переменных в моделях удалений?

Для проверки достаточно значений переменных оставшихся клауз; остальные можно дополнить произвольно. В примере проверка необходимости C3,C4,C5 использует только q,r, поскольку p уже не встречается в выбранном ядре.

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

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

  • PySAT: deletion-based MUS extractor

    Документация авторов реализации содержит точный цикл удаления и различает ответы SAT-оракула. Пяти-клаузная формула, модели удалений и сравнение размеров построены для этой главы.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться