Булева логика: отрицание, импликация и эквивалентность схем
Проверьте составное условие на всех входах, преобразуйте отрицание и соберите базовые операции из NAND. Отделите формальную импликацию от причинного утверждения.
Задачи модуля
Зададим атомарные высказывания и явно расставим скобки. После этого составное условие можно проверить на всех наборах истинности: такой полный перебор для малого числа переменных доказывает равенство двух булевых выражений.
Применим законы де Моргана, разберём единственный ложный случай импликации и построим НЕ, И и ИЛИ через NAND. В калькуляторе импликацию записываем как NOT A OR B, а NAND — как NOT (A AND B); смысл высказываний проверяется вне таблицы.
Строить таблицы истинности с явными скобками и проверять эквивалентность.
Корректно отрицать составные условия и различать импликацию с её обращением.
Представлять базовые операции через NAND и проверять каждый возможный вход.
Логические сертификаты
Преобразование Цейтина: выполнимость и новые переменные
Короткая конъюнктивная форма может использовать дополнительные переменные для значений внутренних узлов формулы. Она сохраняет выполнимость после проекции, но не обязана быть буквально эквивалентной исходной формуле на расширенном наборе переменных.
Перед началом: Булевы связки; КНФ.
Каждому узлу назначьте значение
Для подформулы z↔(a∧b) используют три дизъюнкта: (¬z∨a), (¬z∨b), (z∨¬a∨¬b). Первые два заставляют истинный z требовать оба входа, третий заставляет два истинных входа включить z. Аналогичные локальные ограничения строят для других связок. Общее число новых переменных и дизъюнктов линейно по размеру дерева или графа формулы. Важно кодировать эквивалентность узла, а не только одну импликацию, если далее требуется точное восстановление внутренних значений.
Корневое условие нельзя забывать
После кодирования узлов добавляют единичный дизъюнкт, требующий истинности корня. Без него ограничения лишь описывают корректное вычисление формулы, включая случаи ложного результата. Для любого набора исходных переменных внутренние значения можно продолжить согласованно; поэтому без корня даже невыполнимая исходная формула получила бы модель локальных определений. Именно корневой литерал связывает схему вычисления с вопросом выполнимости.
Сравнивайте модели после удаления служебных координат
Исходная формула не ограничивает новые переменные, поскольку их в ней нет. Закодированная КНФ ограничивает их значениями подформул. Поэтому буквальная эквивалентность на всех расширенных присваиваниях обычно неверна. Правильное утверждение: присваивание исходных переменных удовлетворяет формуле тогда и только тогда, когда существует его продолжение до модели КНФ. При полных определениях узлов это продолжение единственно. В SAT-проверке нужно вернуть пользователю именно исходные переменные, отделив технические свидетельства.
При совместном использовании одной подформулы несколькими ветвями достаточно одной служебной переменной и одного определения. Это сохраняет линейный размер относительно графа схемы, а не только её развёрнутого дерева.
Одна связка и четыре модели
Условие. Закодируйте F=a∧b переменной z и сравните число моделей F и КНФ на переменных a,b,z.
Добавляем три дизъюнкта определения z↔a∧b и единичный дизъюнкт z.
КНФ требует z=1, затем a=1 и b=1; её модель только (1,1,1).
Исходная F на расширенном наборе допускает (1,1,0) и (1,1,1), потому что z не упоминается.
После проекции обе модели F и единственная модель КНФ дают одно исходное присваивание a=b=1.
Ответ. Расширенные формулы не эквивалентны, но проекции моделей на a,b совпадают.
Проверка. Полный перебор восьми троек подтверждает единственную модель КНФ и две модели исходной F на расширенном пространстве.
Где легко ошибиться. Равновыполнимость не даёт права сравнивать дополнительные переменные так, словно они присутствовали в исходной задаче.
Проверьте понимание
Вопросы к этой главе
Зачем добавлять корневой литерал?
Определения узлов допускают и ложный итог вычисления; корневое требование оставляет только истинные случаи.
Можно ли выбросить служебные переменные из ответа?
Да, проекция на исходные переменные и является пользовательской моделью исходной формулы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§2.1: переменные Цейтина и локальная кодировка схемы в дизъюнкты; проекция моделей проверена перебором. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Резолюция: пустая дизъюнкция как проверяемый сертификат
Вместо полного перебора присваиваний невыполнимость иногда подтверждается короткой цепочкой резолюций. Каждая строка должна ссылаться на две предыдущие и один противоположный литерал.
Перед началом: Дизъюнкт; Выполнимость.
Один шаг сохраняет логическое следствие
Из (A∨p) и (B∨¬p) выводят A∨B. Если p ложно, первый родитель требует A; если истинно, второй требует B. Поэтому всякая модель обоих родителей удовлетворяет резольвенте. Это доказательство корректности не разрешает произвольно удалять другие литералы. Если в результат попали q и ¬q, получится тавтология, которая не помогает опровержению, но не делает шаг ложным. Повторяющиеся литералы можно свернуть как множество.
Пустой дизъюнкт отличается от пустого набора
Пустой дизъюнкт не имеет истинного литерала и всегда ложен. Его вывод доказывает невыполнимость исходного набора. Напротив, пустой набор дизъюнктов является пустой конъюнкцией и истинен. Эти два объекта часто имеют похожее машинное представление, поэтому проверяющий должен различать уровни вложенности. Единичные дизъюнкты особенно удобны: резолюция с ними распространяет обязательное значение переменной и может быстро дойти до противоречия.
Сертификат проверяют локально
Для каждой строки достаточно проверить индексы родителей, наличие выбранной пары p,¬p и точный набор оставшихся литералов. Ссылки должны вести только на уже доступные строки, иначе получится круговое обоснование. Полноценный SAT-поиск при такой проверке повторять не нужно. Однако короткий сертификат существует не для любой трудной задачи в выбранной системе доказательств; метод проверки и метод поиска имеют разную сложность. Для маленького примера независимый перебор всех присваиваний подтверждает итоговую невыполнимость и ловит ошибку в исходном наборе ограничений.
Если исходный набор имеет модель, корректная резолюция не может породить пустой дизъюнкт: та же модель удовлетворяла бы каждой выведенной строке. Это индуктивное объяснение звуковости всей цепочки, которое опирается на локальную корректность одного шага.
Каждый шаг удалил ровно одну противоположную пару; пустая строка доказывает невозможность модели всех четырёх исходных условий.
Ответ. Набор невыполним, сертификат содержит три резолюции.
Проверка. Из единичных условий q=r=0 первый дизъюнкт требует p=1, второй p=0; это независимое прямое противоречие.
Где легко ошибиться. Нельзя выводить пустой дизъюнкт простым удалением двух любых разных литералов: они должны быть противоположными значениями одной переменной.
Проверьте понимание
Вопросы к этой главе
Что означает единичный дизъюнкт?
Он требует истинности своего единственного литерала и задаёт обязательное значение переменной.
Почему проверка легче поиска?
В готовом сертификате уже указаны нужные родители и переменная шага; проверяющему не нужно выбирать их среди множества вариантов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Разделы о клауза́льных доказательствах и проверяемом опровержении. Учебные три шага резолюции проверены локально и таблицей истинности. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Разложение Шеннона: порядок переменных меняет BDD
Одна булева функция может иметь разные размеры упорядоченной диаграммы решений. Удаление одинаковых ветвей уменьшает граф, но результат зависит от того, какие переменные разрешено проверять раньше.
Перед началом: Таблица истинности; Ориентированный ациклический граф.
Разветвление задаёт две остаточные функции
Разложение Шеннона записывает f=(¬x∧f|x=0)∨(x∧f|x=1). Узел решения проверяет x и выбирает соответствующий остаток. В упорядоченной BDD переменные на любом пути идут в одном фиксированном порядке, хотя некоторые проверки можно пропустить. Терминалы 0 и 1 общие для всего графа. Число узлов в этой главе не включает эти два терминала, чтобы сравнение размеров не зависело от соглашения.
Редукция объединяет одинаковое поведение
Если обе ветви узла ведут в один результат, проверка переменной не нужна. Если два узла проверяют одну переменную и имеют одинаковых потомков, их объединяют. При фиксированном порядке это даёт каноническую редуцированную диаграмму функции. Каноничность не распространяется на смену порядка: другой порядок может породить другие промежуточные остаточные функции и существенно иной размер. Поэтому сравнивать две диаграммы по адресам узлов можно только при согласованных правилах построения.
Селектор выгодно проверить раньше
У функции выбора f=(x∧y)∨(¬x∧z) переменная x определяет, какой из двух остальных входов вообще нужен. Если проверить её первой, после ветвления достаточно одного простого узла. Если сначала проверить данные y,z, придётся хранить несколько вариантов того, что позже решит x. Это не правило для всех функций, а содержательный пример зависимости размера от порядка. Независимая проверка диаграммы состоит в вычислении всех её путей на таблице истинности.
Подсчёт пяти узлов использует общий узел для одинаковых остаточных функций, но разные узлы для x и ¬x. Если библиотека поддерживает инвертированные рёбра, размер может считаться иначе; такое расширение в нашей модели не используется.
Размер диаграммы селектора
Условие. Сравните f=(x∧y)∨(¬x∧z) в порядках x,y,z и y,z,x.
При x первым нулевая ветвь ведёт к z, единичная к y.
Получаются три нетерминальных узла: x,y,z.
При y первым случаи y=0 и y=1 дают соответственно ¬x∧z и x∨z; нужны два разных узла z.
Ниже возникают два разных узла x: для x и ¬x. Вместе с корнем y получаем пять узлов.
Ответ. Размеры 3 и 5 нетерминальных узлов.
Проверка. Перебор восьми присваиваний даёт одно и то же значение f в обеих диаграммах; изменение размера не означает изменение функции.
Где легко ошибиться. Каноничность ROBDD требует фиксированного порядка переменных; она не обещает одинаковый размер при любом порядке.
Проверьте понимание
Вопросы к этой главе
Почему можно пропускать переменную на пути?
Если остаточная функция от неё не зависит, обе ветви совпадают и редукция удаляет проверку.
Терминалы считаются узлами?
Это вопрос соглашения. Здесь два общих терминала исключены; если включить, оба размера увеличатся на два.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
§2.2: ROBDD, общий порядок и уникальные узлы; размеры селектора вычислены отдельно без инвертированных рёбер. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Порядок кванторов: один свидетель или разные ответы
Фраза «для каждого найдётся» разрешает менять свидетеля вместе с входом. Фраза «найдётся для всех» требует одного общего объекта; перестановка кванторов может превратить верное утверждение в ложное.
Перед началом: Предикаты; Конечное множество.
Кто выбирает первым
В ∀x∃y R(x,y) выбор y может зависеть от уже выбранного x. В ∃y∀x R(x,y) сначала фиксируют один y, который обязан работать для любого x. Второе утверждение влечёт первое на непустых стандартных областях, но обратное в общем случае неверно. На конечной таблице отношений первая формула требует хотя бы одну отмеченную клетку в каждой строке, вторая — столбец, целиком состоящий из отмеченных клеток.
Отрицание меняет и квантор, и предикат
Отрицание ∀x∃y R равносильно ∃x∀y ¬R: нужно предъявить один вход без подходящего ответа. Отрицание ∃y∀x R равносильно ∀y∃x ¬R: для каждого предложенного общего свидетеля достаточно собственного опровержения. Эти два способа опровержения различаются так же, как исходные утверждения. Перенос отрицания только внутрь предиката при сохранении кванторов неверен и часто меняет условие алгоритмической задачи.
Конечный перебор показывает зависимость явно
Чтобы доказать первую формулу конструктивно, можно предъявить функцию выбора y=f(x). Она не обязана быть постоянной. Для доказательства второй нужна одна константа. В бесконечной задаче существование такой функции и её вычислимость являются разными вопросами, но в маленькой конечной модели таблица даёт полный проверяемый ответ. Отдельно следует указывать области x и y: если одна из них пуста, некоторые интуитивные импликации требуют осторожности из-за вакуумной истинности универсальных утверждений.
При записи программной проверки две формулы соответствуют разному порядку циклов и месту остановки. Для первой ищут успех отдельно в каждой строке. Для второй ищут один столбец, успешный во всех строках. Ранний выход должен относиться к правильному квантору, иначе тест реализует другую формулу.
Ответ зависит от входа
Условие. Пусть x,y∈{0,1,2}, R(x,y) означает x≠y. Сравните ∀x∃y R(x,y) и ∃y∀x R(x,y).
Для каждого x выберем y=(x+1) mod3; он отличается от x.
Поэтому ∀x∃y R истинно, и функция выбора предъявлена явно.
Для любого фиксированного y можно взять x=y, тогда R ложно.
Значит ∃y∀x R ложно; ни один из трёх столбцов таблицы не заполнен целиком.
Ответ. Первая формула истинна, вторая ложна.
Проверка. В таблице 3×3 только диагональ ложна: каждая строка имеет два свидетеля, каждый столбец имеет одно опровержение.
Где легко ошибиться. Нельзя переносить существование свидетеля перед универсальным квантором, если свидетель зависит от ранее выбранного аргумента.
Проверьте понимание
Вопросы к этой главе
Как записать зависимый выбор?
Указать y=f(x) и проверить R(x,f(x)) для каждого допустимого x.
Достаточно ли трёх примеров для бесконечной области?
Нет. Здесь перебор полон только потому, что область содержит ровно три элемента.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Глава 3: предикаты, зависимые свидетели и отрицание кванторов. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Как читать составное условие с И и ИЛИ
Условие с И истинно, когда истинны все требуемые части. Условие с включающим ИЛИ истинно, когда верна хотя бы одна часть, в том числе обе. Сначала вычислите отдельные сравнения, затем соедините их по явно заданным скобкам и правилам языка.
Отрицание «A и B» означает «не A или не B», а отрицание «A или B» означает «не A и не B». Меняется и логическая связка, и каждое условие. Эти правила относятся к булевым высказываниям; правильность преобразования можно проверить на всех четырёх сочетаниях истинности двух частей.
Чтобы проверить правило P → Q на конечной таблице, найдите строки, где P истинно, а Q ложно. Только они нарушают импликацию. Отсутствие таких строк подтверждает правило для проверенной таблицы; оно не доказывает закон для всех будущих данных.
ИЛИ требует, чтобы ровно одна часть была истинной?
Обычное включающее ИЛИ допускает и одновременную истинность обеих частей. Для ровно одной нужен другой явно сформулированный критерий.
Нужно ли менять связку при отрицании каждой части?
Да. Для булевых высказываний отрицание И даёт ИЛИ отрицаний, а отрицание ИЛИ даёт И отрицаний. Сохранение старой связки обычно меняет условие.
Если строк с P=1 нет, правило нарушено?
Нет: в полностью известной конечной таблице нет строки с P=1 и Q=0. Но существование записей с P=1 этой проверкой не подтверждено; его проверяют отдельно.
Сохранять историю слов и ошибок в этом браузере? О cookies