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

Как читать составное условие с И и ИЛИ

Как проверять составные условия с И и ИЛИ: логические значения частей, включающее «или», скобки и короткое вычисление в Python.

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

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

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

Условие с И истинно, когда истинны все требуемые части. Условие с включающим ИЛИ истинно, когда верна хотя бы одна часть, в том числе обе. Сначала вычислите отдельные сравнения, затем соедините их по явно заданным скобкам и правилам языка.

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

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

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

Как скобки делают намерение видимым

В Python для таких проверок используются and, or и not. Запись (age >= 12 and age <= 16) and consent объединяет два сравнения возраста и логический флаг согласия. В данном примере все части являются логическими значениями. Само наличие числа в переменной age не сообщает ни разрешённый интервал, ни факт согласия: эти сведения возникают из отдельных проверок.

Скобки особенно полезны при смешении И и ИЛИ. Выражения (A or B) and C и A or (B and C) могут давать разные результаты. При истинном A и ложном C первая запись ложна, вторая истинна. Поэтому нельзя переставлять скобки ради внешней простоты, не сверив смысл полного условия с исходным правилом допуска.

Пример

Возраст 14, consent = False ⇒ (14 >= 12 and 14 <= 16) and False даёт False.

Обе возрастные части верны, но обязательное согласие отсутствует. Соединение через И сохраняет каждое требование, а не выбирает одно из них.

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

Python вычисляет and и or слева направо и может не вычислять правую часть, когда результат по истинности уже определяется левой. Например, b != 0 and a / b > 2 не выполняет деление при нулевом b. Такая запись безопасна для именно этого порядка частей. Если сначала написать деление, поздняя проверка ненулевого знаменателя уже не предотвратит ошибку.

В общем Python операторы and и or могут возвращать один из операндов, а не обязательно отдельное значение типа bool. В текущих примерах операнды — результаты сравнений и логические флаги, поэтому ответ читается как True или False. Это уточнение не позволяет перенести учебную таблицу истинности на произвольные строки и числа без понимания правил их истинности.

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

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

А теперь — вы

Для логических A = True и B = False чему равно A and B?

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

ИЛИ требует, чтобы ровно одна часть была истинной?

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

Можно ли проверку деления на ноль поставить после деления?

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

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

Монотонная булева функция и однобитовые переходы

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

Перед началом: Булева функция; Покоординатный порядок.

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

Для наборов x,y пишут x≤y, если каждая координата x не больше соответствующей координаты y. Монотонность функции f означает f(x)≤f(y) для всех таких пар. Переход разрешает менять некоторые нули на единицы и запрещает обратное изменение. Сравнение целых кодов наборов не заменяет этот частичный порядок: например, 011 и 100 не сравнимы покоординатно.

Формула, составленная из входов, констант, И и ИЛИ без отрицаний, монотонна: обе операции сохраняют порядок, а композиция сохраняющих порядок операций тоже его сохраняет. Наличие отрицания в конкретной записи ещё не опровергает монотонность функции. Например, x∨(x∧¬y)=x: отрицательная зависимость здесь полностью поглощена.

Достаточно проверить рёбра булева куба

Каждая сравнимая пара x≤y соединяется цепочкой однобитовых увеличений. Если на каждом таком ребре значение не уменьшается, транзитивность неравенства даёт f(x)≤f(y) для всей пары. Обратно, любое плохое ребро уже является контрпримером определению. Таким образом, локальный по рёбрам тест необходим и достаточен.

Для n входов направленных рёбер ровно n·2ⁿ⁻¹: выбирается изменяемый бит, остальные биты произвольны. Перебор остаётся экспоненциальным при явной таблице, но каждое нарушение получается коротким и воспроизводимым. Достаточно вывести два набора и два значения функции; пересказ сложной формулы не нужен.

Монотонность относится к выбранному смыслу единицы

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

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

Одно убывающее ребро

Условие. Исследуйте монотонность f(x,y,z)=(x∧¬y)∨z и g(x,y,z)=(x∧y)∨z на всех двоичных наборах.

  1. У трёхмерного куба 3·4=12 направленных однобитовых рёбер. Все их нужно проверить, если не использовать доказательство по составу формулы.
  2. Для f на ребре(1,0,0)→(1,1,0) значение меняется 1→0. Это достаточный контрпример монотонности.
  3. Если меняется x или z из 0 в 1, формула f не убывает. При увеличении y нарушение возможно только при x=1,z=0, так что найденное плохое ребро единственное.
  4. Функция g составлена только из положительных И и ИЛИ. Все 12 рёбер дают неубывание, согласуясь с общим доказательством.

Ответ. f не монотонна; g монотонна. Единственное плохое ребро f:(1,0,0)→(1,1,0).

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

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

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

Какой переход опровергает монотонность f из задачи?

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

Достаточно проверить только наборы 000 и 111?

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

Можно считать только увеличение одной координаты?

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

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

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

  • CMU15-859, Lecture16: Monotone Formula Lower Bounds

    Первичные лекционные записи: прочитаны Definition3 и связь монотонности с положительными AND/OR-формулами. Критерий однобитовых рёбер и пример нарушения главы доказаны отдельно; теоремы нижних оценок графовой энтропии не используются.

Неизвестный бит: композиционная логика и все достройки

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

Перед началом: Двоичная таблица; Повторные переменные.

Назовите выбранную трёхзначную модель

Возьмём значения 0,U,1 с порядком 0<U<1. Зададим И как минимум, ИЛИ как максимум, отрицание меняет 0 и 1 местами и оставляет U. Это полностью определяет композиционное вычисление: значение узла зависит только от значений его непосредственных аргументов. Здесь U означает недостаток информации о двоичном бите.

Например, U∧0=0,U∨1=1, но U∧1=U и U∨0=U. Такая таблица безопасно распространяет неопределённость без просмотра всей формулы. При этом она не помнит, что два разных провода могут выражать один и тот же скрытый бит либо его отрицание. Значение U не хранит идентичность неизвестной причины.

Достройки учитывают общую переменную сразу во всех местах

В другой семантике переберём все замены неизвестных исходных переменных на 0 или 1. Одна переменная получает одно значение сразу во всех своих вхождениях. Если формула истинна при каждой достройке, ответ определён как 1; если ложна при каждой —0; иначе остаётся U. Это точное множество допустимых двоичных результатов.

Вычисление узла по трём значениям заменяет реальные зависимости грубым независимым сочетанием возможностей. Поэтому оно способно дать U при точном единственном результате. Например, x и¬x не могут одновременно равняться 1 ни при одной достройке, хотя оба отдельно представлены одним символом U. Независимость проводов здесь была бы ошибкой модели.

Различайте неизвестность и отдельное третье физическое состояние

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

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

Общий неизвестный в двух ветвях

Условие. Пусть x=U,y=1 и F=(x∧y)∨(¬x∧y). Сравните композиционную таблицу с результатом всех согласованных двоичных достроек.

  1. По трёхзначной таблице x∧1=U и¬x∧1=U. Их дизъюнкция равна U.
  2. При достройке x=0 получаем(0∧1)∨(1∧1)=1. При достройке x=1 получаем(1∧1)∨(0∧1)=1.
  3. Таким образом, точное множество двоичных результатов равно{1}. В обеих ветвях используется один x, а не две независимо выбираемые неизвестные переменные.
  4. Двоичное тождество F=y также даёт 1. Оно независимо подтверждает перебор; при y=0 обе семантики уже вернут 0.

Ответ. Композиционная оценка U; по всем достройкам F=1.

Проверка. Полная таблица четырёх двоичных пар(x,y) совпадает с y. Расхождение возникает только из-за потери зависимости повторного x в промежуточной трёхзначной оценке.

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

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

Какая пара результатов получается в задаче: таблица, затем все достройки?

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

Трёхзначная таблица дала 1: может достройка дать 0?

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

Это ошибка трёхзначных операций?

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

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

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

  • PostgreSQL: Logical Operators, §9.1

    Официальная документация: вебом сверены только трёхзначные таблицы AND,OR,NOT. Глава задаёт абстрактный неизвестный бит, затем отдельно строит семантику всех согласованных двоичных достроек; это не утверждение об исполнении SQL-выражений.

Первая UIP-клауза и возврат через несколько уровней SAT

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

Перед началом: КНФ и резолюция; Единичное распространение.

Граф хранит причины, а не только текущие значения

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

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

Резолюция сворачивает конфликт до одного текущего литерала

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

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

Обучение исключает причину, не все модели

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

Промежуточная UIP перескакивает бесполезное решение

Условие. Даны клаузы C₁=(¬c∨r), C₂=(¬a∨¬r∨u), C₃=(¬r∨v), C₄=(¬u∨¬v). Решения a=1 на уровне 1, неиспользуемое b=1 на уровне 2, c=1 на уровне 3 вызывают r=u=v=1 и конфликт. Найдите первую UIP, обученную клаузу и уровень возврата.

  1. Причина r=1 — C₁. При a=r=1 клауза C₂ вынуждает u=1, а C₃ вынуждает v=1. Последняя C₄ ложна. Оба пути от решения c к конфликту проходят через r, затем расходятся через u и v.
  2. Резолвируем C₄ с C₃ по v: получаем ¬u∨¬r. Теперь резолвируем с C₂ по u: получаем ¬a∨¬r.
  3. В последней клаузе только ¬r относится к уровню 3; a относится к уровню 1. Поэтому r — первая UIP, резолюцию с C₁ до решения c продолжать не нужно.
  4. Возвращаемся сразу на уровень 1, отменяя b и весь уровень 3. Новая клауза при a=1 вынуждает r=0; затем C₁ вынуждает c=0. Формула при этом остаётся выполнимой.

Ответ. Первая UIP — r; обученная клауза ¬a∨¬r; возврат на уровень 1 утверждает r=0.

Проверка. Перебор всех присваиваний исходных переменных подтверждает, что каждая модель удовлетворяет новой клаузе. Модель a=1,c=0,r=0,u=0,v=0 показывает, что локальный конфликт не был доказательством общей невыполнимости.

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

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

На какой уровень возвращается описанный 1-UIP анализ?

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

Почему уровень 2 пропускается?

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

Можно ли продолжить резолюцию до c?

Можно получить более раннее следствие, но это уже другая схема анализа. Первая UIP останавливает сворачивание при r, потому что в текущей клаузе остался один литерал уровня 3.

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

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

  • Rohan Menezes, Penn CIS189: Modern Techniques in SAT Solving

    Прочитаны Implication Graphs, Unique Implication Points, 1-UIP Scheme и Backjump. Граф с промежуточной UIP r и неиспользуемым уровнем b построен самостоятельно; резолюции проверены перебором всех моделей.

Противник доказывает глубину дерева решений

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

Перед началом: Дерево решений; Булевы функции.

Считаем прочитанные биты, а не размер формулы

Алгоритм получает неизвестный двоичный вход и запрашивает отдельные координаты. Следующий запрос может зависеть от прежних ответов; вычисления между запросами считаем бесплатными. Лист дерева обязан выдавать правильное значение для всех полных входов, совместимых с пройденной ветвью. Глубина дерева — максимальное число запросов на входе, а D(f) — минимум такой глубины среди всех корректных детерминированных деревьев.

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

У непересекающихся пар противник откладывает нуль

Рассмотрим f=∨ᵢ₌₁ᵏ(xᵢ∧yᵢ). На первый запрос внутри ещё не тронутой пары противник отвечает 1, на второй — 0. Каждая полностью прочитанная пара поэтому ложна, но у каждой незавершённой пары всё ещё возможно значение AND=1. Все оставшиеся пары можно также завершить нулями. Пока есть незавершённая пара, существуют оба результата всей функции.

Следовательно на такой ветви алгоритм вынужден прочитать все 2k битов. Это доказывает D(f)≥2k, независимо от порядка запросов и вычислительной хитрости между ними. Обратная граница очевидна: чтение всего входа достаточно. Значит D(f)=2k. Важна непересекаемость пар; если одни и те же координаты встречаются в нескольких слагаемых, ответы могут одновременно раскрыть несколько пар и доказательство требует пересмотра.

Сертификат одного входа не равен худшей глубине поиска

Чтобы удостоверить f=1, достаточно показать одну пару единиц, то есть два бита. Но алгоритм заранее не знает, где такая пара, и на трудном отрицательном входе может не найти её вообще. Поэтому короткий положительный сертификат не даёт малого D(f). Также глубина запросов отличается от количества узлов сокращённой BDD: объединение одинаковых остаточных функций экономит хранение, но не обязательно уменьшает число чтений на самом длинном пути.

Шесть чтений несмотря на короткий сертификат

Условие. Для f=(x₁∧y₁)∨(x₂∧y₂)∨(x₃∧y₃) докажите точную детерминированную глубину. Проследите порядок запросов x₁,y₂,x₃,y₁,x₂,y₃.

  1. По парной стратегии ответы равны 1,1,1,0,0,0: каждый первый запрос пары получает 1, второй 0. Они задают один согласованный полный вход.
  2. После первых пяти запросов пары 1 и2 уже ложны, но x₃=1 и y₃ ещё не прочитан. Завершение y₃=0 даёт f=0, завершение y₃=1 даёт f=1.
  3. Значит этот алгоритм обязан сделать шестой запрос. Та же стратегия работает при любом порядке: пока какая-либо пара не завершена, сохраняются два результата.
  4. Чтение всех шести битов всегда достаточно. Объединяя нижнюю и верхнюю границы, получаем D(f)=6. Положительный сертификат xᵢ=yᵢ=1 всё ещё имеет длину 2 и не противоречит результату.

Ответ. Точная худшая глубина равна 6 запросам; адаптивность не уменьшает её.

Проверка. Независимый динамический перебор всех остаточных функций использует рекурсию D(g)=1+minᵢ max(D(g|xᵢ=0),D(g|xᵢ=1)), с нулём для констант, и также находит 6.

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

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

Чему равна D(f) для трёх непересекающихся пар в примере?

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

Доказана ли такая же граница для случайного алгоритма с ошибкой?

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

Можно ли повторно спрашивать прочитанный бит?

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

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

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

  • Illinois CS579: Decision Trees, Lecture23

    Прочитаны определение DTree как min алгоритма/max входа и Adversary Argument с сохранением несовместимых ответов. Источник иллюстрирует OR; собственная задача OR из трёх непересекающихся AND требует другой парной стратегии противника.

Булева выполнимость не гарантирует совместности числовых предикатов

Булева модель выбирает, какие числовые утверждения считать истинными, но ещё не назначает значения самим числам. В DPLL(T) отдельная проверка теории отсеивает невозможные сочетания. Разберём ветвь, которая проходит булевы условия, однако приводит к противоречию при сложении неравенств; затем найдём допустимую другую ветвь.

Перед началом: Булевы переменные, дизъюнкции и конъюнкции; Сложение линейных неравенств.

Атом имеет внутренний математический смысл

Пусть p обозначает x−y≥1, q — y−z≥2, s — z−x≥0, а r — x≥0. Все числовые переменные действительные. Формула F=(p∨r)∧q∧s содержит четыре булевых атома. Если временно забыть их определения, назначение p=q=s=true удовлетворяет F независимо от r. Это корректный результат булевого решателя для абстракции, но не свидетельство существования тройки x, y, z.

Проверка теории получает не произвольную строку формулы, а выбранные литералы вместе с их числовой интерпретацией. При отрицании атома меняется и ограничение: например, ¬p означает x−y<1. В вещественной арифметике его нельзя без основания заменить на x−y≤0; такая замена была бы верной для соответствующей целочисленной разности. Тип переменных является частью задачи.

Конфликт становится полезным новым ограничением

Из p, q, s сложением получается (x−y)+(y−z)+(z−x)≥1+2+0, то есть 0≥3. Никакие действительные числа не выполняют это условие. Поэтому теория доказывает общезначимость дизъюнкции ¬p∨¬q∨¬s. Это обученная теоретическая лемма: она запрещает не один случайный числовой набор, а любое будущее булево назначение с одновременной истинностью этих трёх атомов.

Лемму добавляют к булевой части, после чего поиск продолжается. Поскольку q и s обязательны в F, новое ограничение вынуждает ¬p. Тогда дизъюнкция p∨r требует r. Проверяем уже иной набор: ¬p, q, s, r. Теоретический конфликт одной ветви не разрешает объявить всю F невыполнимой: в формуле есть альтернатива, которую ещё нужно исследовать.

Числовой свидетель завершает проверку

Тройка x=0, y=2, z=0 даёт x−y=−2<1, y−z=2, z−x=0 и x=0. Следовательно, ¬p, q, s, r выполняются одновременно. Мы получили настоящее числовое решение исходной формулы. Сохранённая лемма не устраняет этот свидетель, потому что ¬p истинно. Это простая независимая проверка того, что обучение не отбросило допустимую ветвь.

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

Сложение замкнутого контура ограничений

Условие. Для действительных x, y, z и атомов p, q, s, r, определённых выше, проверьте ветвь p=q=s=true формулы F=(p∨r)∧q∧s. Постройте лемму конфликта и действительное решение другой ветви.

  1. В абстрактной булевой формуле p, q, s=true обеспечивают обе конъюнкции q, s и дизъюнкцию p∨r.
  2. В теории сумма трёх выбранных неравенств требует 0≥3; эта ветвь несовместна.
  3. Добавляем ¬p∨¬q∨¬s. При обязательных q, s получаем ¬p, затем из p∨r получаем r.
  4. Назначаем x=0, y=2, z=0. Все четыре литерала ¬p, q, s, r истинны; следовательно, сама F выполнима.

Ответ. Ветвь p, q, s исключается, но формула имеет решение (0,2,0). Лемма конфликта: ¬p∨¬q∨¬s.

Проверка. Непосредственная подстановка даёт −2<1,2≥2,0≥0,0≥0. Сумма исходной конфликтующей тройки независимо доказывает её невозможность.

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

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

Что установлено противоречием 0≥3 в выбранной ветви?

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

Зачем хранить лемму, если ветвь уже отброшена?

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

Доказывает ли перебор нескольких числовых точек несовместность?

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

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

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

  • Z3 Guide: разностная арифметика

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

Простые импликанты и покрытие карты единиц

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

Перед началом: ДНФ и двоичная таблица истинности; Покрытие конечного множества подмножествами.

Терм является кубом входов без запрещённых нулей

Частично заданная булева функция четырёх переменных; минимизируется сначала число конъюнктивных термов ДНФ, затем суммарное число литералов; неопределённые входы не обязательны к покрытию.

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

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

Таблица покрытия содержит только обязательные единицы

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

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

Неопределённость не разрешает ошибаться на заданных нулях

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

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

Шесть простых импликант, но нужны только три

Условие. Биты набора идут как A,B,C,D, A старший. Обязательные единицы имеют номера {1,3,4,5,7,9,11,12,13}, неопределённые {0,2}; остальные входы нулевые. Найдите минимальную ДНФ по числу термов, затем литералов.

  1. Полная склейка даёт простые кубы 00--,0-0-,0--1,-0-1,-10-,--01. Каждый имеет два фиксированных бита; куба с одним литералом без заданного нуля не существует.
  2. Единица 7 покрывается только 0--1, единица 11 — только -0-1, единица 12 — только -10-. Поэтому все три строки существенны и любой ответ содержит минимум три терма.
  3. Их объединение уже покрывает все девять обязательных единиц. Получаем ¬A∧D ∨ ¬B∧D ∨ B∧¬C. Остальные три простые импликанты не требуются.
  4. Все три выбранных терма имеют по два литерала, итого шесть. Нижняя граница три существенных терма достигнута, и ни один нельзя заменить однословным литералом: такой допустимой импликанты нет.

Ответ. Минимальная ДНФ: (¬A∧D)∨(¬B∧D)∨(B∧¬C), три терма и шесть литералов.

Проверка. Независимая проверка всех 16 наборов даёт ровно требуемые обязательные значения. Перебор 81 куба находит те же шесть простых, а перебор 64 их подмножеств подтверждает единственный трёхтермный минимум; неопределённые 0,2 не обязаны становиться единицами.

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

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

Какой набор кубов даёт минимальное покрытие обязательных единиц в разобранном примере?

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

Почему нельзя склеить любые два куба, отличающиеся одной буквой записи?

Нужны одинаковые позиции уже удалённых переменных и различие ровно в одном фиксированном бите. Иначе объединение может не быть одним кубом и включить запрещённые наборы.

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

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

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

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

  • Steven Nowick — Quine-McCluskey handout

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

Счётчик в КНФ кодирует ограничение не более k

Запрет всех наборов из k+1 одновременно истинных переменных может породить много длинных клауз. Последовательный счётчик передаёт сведения о достигнутых порогах вдоль префикса и запрещает переполнение. В сокращённой кодировке вспомогательные биты не всегда равны точным порогам на каждой модели. Гарантия состоит в существовании согласованного расширения ровно для исходных наборов с допустимой суммой.

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

Достигнутый порог необходимо передать вправо

Булевы x₁,…,xₙ и целое 1≤k<n; последовательная кодировка ограничения суммы xᵢ≤k использует вспомогательные переменные, сравниваются проекции моделей.

Вводим sᵢ,ⱼ для первых i переменных и порогов j=1,…,k, где i=1,…,n−1. Нам достаточно принудительно включать sᵢ,ⱼ, когда префикс уже содержит хотя бы j единиц. Это даёт импликации xᵢ→sᵢ,₁, sᵢ₋₁,ⱼ→sᵢ,ⱼ и xᵢ∧sᵢ₋₁,ⱼ₋₁→sᵢ,ⱼ в соответствующих внутренних диапазонах.

Каждая импликация превращается в клаузу: например, ¬xᵢ∨¬sᵢ₋₁,ⱼ₋₁∨sᵢ,ⱼ. Первую строку задаём x₁→s₁,₁ и ¬s₁,ⱼ для j≥2: одна переменная не могла достичь порога два. Неопределённые индексы нулевой строки нельзя подставлять как обычные переменные.

Клаузы переполнения запрещают следующую единицу

Для i=2,…,n добавляем ¬xᵢ∨¬sᵢ₋₁,ₖ. Если предыдущий префикс достиг k, новая единица запрещена. Для последней переменной не нужна отдельная строка sₙ: нас интересует только отсутствие переполнения, а не полный итоговый счётчик.

Если исходный набор имеет k+1 единиц, к моменту последней из них распространение достигнутых порогов вынуждает sᵢ₋₁,ₖ=1, и клауза переполнения нарушается. Если единиц не больше k, присваиваем каждому s точное значение соответствующего порога; все клаузы выполняются. Эти два аргумента доказывают совпадение проекций без требования уникальности расширения.

Вспомогательные модели нельзя считать исходными решениями

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

Число вспомогательных переменных равно (n−1)k, число клауз порядка nk. При k=0 ограничение проще кодируется единичными ¬xᵢ; при k≥n оно тождественно истинно. Эти границы обрабатывают отдельно. Компактность КНФ не означает равенство числа её расширенных моделей числу допустимых наборов x, поэтому для подсчёта исходных решений нужна проекция.

Четыре входа и предел две единицы

Условие. Закодируйте x₁+x₂+x₃+x₄≤2 последовательным счётчиком. Проверьте допустимый набор 1010 и недопустимый 1011; установите число допустимых исходных наборов.

  1. Нужны шесть переменных s₁,₁,s₁,₂,s₂,₁,s₂,₂,s₃,₁,s₃,₂. База включает ¬x₁∨s₁,₁ и ¬s₁,₂. Для внутренних i=2,3 добавляем перенос первого и второго порогов, включение первого по xᵢ и включение второго по xᵢ∧sᵢ₋₁,₁.
  2. Три клаузы переполнения имеют вид ¬x₂∨¬s₁,₂, ¬x₃∨¬s₂,₂, ¬x₄∨¬s₃,₂. Всего получаем 13 клауз.
  3. Для 1010 точные пороговые строки равны (1,0),(1,0),(1,1). Последний вход равен нулю, поэтому переполнения нет и это расширение удовлетворяет всей КНФ.
  4. Для 1011 первые три входа вынуждают s₃,₂=1, а x₄=1 нарушает последнюю клаузу. Допустимых исходных наборов ровно C(4,0)+C(4,1)+C(4,2)=1+4+6=11.

Ответ. Кодировка содержит 6 вспомогательных переменных и 13 клауз. 1010 допускает расширение, 1011 не допускает; исходных решений 11.

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

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

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

Сколько исходных четырёхбитных наборов допускает расширение в разобранную КНФ для суммы не больше двух?

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

Зачем запрещать s₁,₂ отдельно?

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

Можно заставить все s иметь точный смысл?

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

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

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

  • Sinz — Towards an Optimal CNF Encoding, §2

    Односторонняя последовательная unary-кодировка, клаузы переполнения и гарантия расширения. Четырёхбитный случай и все 1024 присваивания исходных и служебных битов проверены отдельно.

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

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

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