Информатика · объяснение и практика
Как отрицать условие, не потеряв И или ИЛИ
Как отрицать составное логическое условие: заменить И на ИЛИ, отдельно отрицать части и проверить строгие границы на примере допуска и диапазона.

В теме Логика и логические схемы · Учебная карта
Главная мысль
Отрицание «A и B» означает «не A или не B», а отрицание «A или B» означает «не A и не B». Меняется и логическая связка, и каждое условие. Эти правила относятся к булевым высказываниям; правильность преобразования можно проверить на всех четырёх сочетаниях истинности двух частей.
Как отказ отличается от двух одновременных нарушений
Для участия в условной мастерской нужны возраст не меньше двенадцати лет и полученное согласие. Обозначим выполнение возрастного ограничения через A, наличие согласия через B. Допуск выражается как A и B. Отказ происходит, если не выполнено хотя бы одно требование: возраст меньше двенадцати или согласия нет.
Запись «слишком мал и нет согласия» описывает только один из вариантов отказа. Она пропускает тринадцатилетнего участника без согласия и одиннадцатилетнего с согласием. Именно такие пограничные случаи помогают увидеть ошибку. Отрицание всего допуска должно охватывать каждую ситуацию, когда исходная пара требований не выполнена одновременно.
Как проверить обе формулы без заучивания
Если A и B истинны, выражение A и B истинно, его отрицание ложно, и обе отрицательные части ложны. Если истинна только одна часть, исходное И ложно, а среди отрицаний найдётся истинное. Если ложны обе, исходное И также ложно. Во всех случаях получается та же таблица, что у выражения «не A или не B».
Для отрицания ИЛИ рассуждение другое. Пусть достаточно билета или приглашения. Не выполнить это условие можно только при отсутствии и билета, и приглашения. Здесь слово «или» включающее: наличие обоих документов тоже удовлетворяет исходному условию. Исключающее «ровно одно» является другой логической операцией и требует другого разбора.
Пример
Не выполнено условие «2 ≤ x и x ≤ 5». Значит, x < 2 или x > 5.
Граничные числа два и пять удовлетворяют исходному диапазону. При отрицании нестрогих сравнений границы становятся строгими, а И заменяется на ИЛИ.
Как перенести правило в код и сохранить смысл
Сначала заключите отрицаемое выражение в скобки. Затем смените связку и отрицайте каждую законченную часть. Сравнение «не меньше» превращается в «меньше», а не в «меньше или равно». Отдельно проверьте числа на границах: там ошибка в одном знаке меняет результат, хотя большинство обычных значений проходит проверку.
В учебной таблице все части являются значениями истина или ложь. В Python операции and и or в общем случае могут возвращать один из операндов, а не отдельное булево значение. Поэтому равносильность условий по истинности не следует путать с обещанием одинакового типа и значения произвольного выражения, составленного из строк или других объектов.
Для условий с вызовами функций учитывайте порядок вычисления и возможные побочные эффекты. Математическая таблица истинности сама по себе не описывает изменение внешнего состояния. Удобнее сначала проверить правило на чистых сравнениях, где каждое обращение даёт устойчивый результат, и только затем применять преобразование к реальному коду.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно ли менять связку при отрицании каждой части?
Да. Для булевых высказываний отрицание И даёт ИЛИ отрицаний, а отрицание ИЛИ даёт И отрицаний. Сохранение старой связки обычно меняет условие.
Почему отдельно проверяют края диапазона?
Отрицание ≤ является >, а отрицание ≥ является <. Ошибка в равенстве проявляется именно на границе, которую легко пропустить при случайном тестировании.
Углублённый разбор
Принцип двойственности булевой алгебры
Двойственность меняет И с ИЛИ и одновременно меняет константы 0 и 1. Удобная семантическая формула показывает, почему так переносятся тождества и как распознать функцию, совпадающую со своей двойственной.
Перед началом: Булевы тождества; Отрицание.
Преобразование применяется ко всему дереву
Двойственное выражение строят заменой каждого И на ИЛИ, каждого ИЛИ на И, константы 0 на 1 и 1 на 0. Переменные оставляют на своих местах. Операция НЕ сохраняется, если она присутствовала в исходном дереве. Важно менять все уровни, а не только внешний знак: двойственность рекурсивна.
Для функции f от n входов результат описывается формулой f*(x)=¬f(¬x), где внутри одновременно инвертируются все входы. Доказательство идёт по дереву выражения: для переменной две инверсии сокращаются, для константы она меняется, а законы де Моргана объясняют обмен операций. Поэтому синтаксическое правило имеет точное семантическое значение.
Тождества переходят в другие тождества
Если f=g на всех входах, то f(¬x)=g(¬x), а после внешнего отрицания получаем f*=g*. Так из доказанного тождества получается двойственное без нового полного перебора. Например, закон поглощения x∨(x∧y)=x переходит в x∧(x∨y)=x. Обе стороны нужно преобразовать целиком.
Двойственность не является обычным отрицанием функции: внешнее НЕ сопровождается инверсией всех её аргументов. Для f=x∧y двойственная равна x∨y, а дополнение равно¬(x∧y). Эти две функции различаются уже на входе 00. Нельзя заменить обмен операций одним общим отрицанием и сохранить смысл.
Самодвойственность связывает противоположные наборы
Функция самодвойственна, если f(x)=¬f(¬x) для любого x. Значения на каждой паре противоположных наборов должны различаться. Поэтому достаточно проверить половину строк таблицы, если явно сгруппировать их в пары. Для нечётного числа входов функция большинства является естественным примером: дополнение меняет большинство единиц на большинство нулей.
Самодвойственность сама по себе не означает монотонности либо линейности. Это отдельная симметрия таблицы. Для конкретной функции полезно проверить и синтаксически полученное выражение, и семантическое дополнение входов. Так обнаруживается забытая константа, которая не видна при примерах только из середины таблицы.
Большинство в двух формах
Условие. Для f=(x∧y)∨(x∧z)∨(y∧z) постройте двойственную функцию и докажите, что f самодвойственна.
- Рекурсивный обмен операций даёт f*=(x∨y)∧(x∨z)∧(y∨z). Констант в этой формуле нет.
- Исходная f равна 1 тогда и только тогда, когда среди трёх входов хотя бы две единицы.
- Двойственная формула требует, чтобы ни одна пара входов не была одновременно нулевой. Это также равносильно наличию хотя бы двух единиц.
- Либо используем противоположный набор: при k единицах дополнение имеет 3−k, а отрицание результата большинства возвращает прежний порог k≥2.
Ответ. f*=(x∨y)∧(x∨z)∧(y∨z)=f; функция большинства самодвойственна.
Проверка. Перебор восьми наборов подтверждает равенство двух выражений и условие f(x)=1−f(1−x). Обычное дополнение f напротив меняет каждый результат и не совпадает с f.
Где легко ошибиться. Меняются обе операции и обе константы, но не имена переменных. Двойственная функция отличается от обычного отрицания из-за одновременного дополнения всех входов.
Проверьте понимание
Вопросы к этой главе
Почему константы тоже нужно менять?
Семантическая формула даёт для постоянного нуля постоянную единицу. Если оставить 0 на месте, нарушатся уже законы нейтрального и поглощающего элементов.
Всякое выражение равно своему двойственному?
Нет. Общий принцип переносит истинные равенства, а не утверждает f=f*для любой функции. Например, И и ИЛИ двойственны, но не совпадают на смешанных входах.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Zdravko Markov: CS354, Boolean algebra lecture notes
Первичные авторские лекции CCSU: прочитаны аксиомы, пункт Duality principle и обмен констант. Семантическая формула двойственной функции и пример большинства подготовлены отдельно.
Экспоненциальный рост эквивалентной КНФ
Распределительный закон может сделать короткую формулу экспоненциально длинной. Для дизъюнкции независимых двухлитерных конъюнкций рост эквивалентной КНФ неизбежен даже при самом удачном преобразовании без новых переменных.
Перед началом: КНФ и ДНФ; Эквивалентность формул.
Каждый выбор литерала порождает отдельную клаузу
Рассмотрим F=(x₁∧y₁)∨…∨(xₙ∧yₙ), где все 2n переменных различны. Распределяя ИЛИ относительно И, получаем конъюнкцию клауз: в каждой выбирается ровно один положительный литерал из каждой пары. Вариантов выбора 2ⁿ, каждая клауза имеет длину n. Само исходное дерево имеет линейный размер.
Полученная КНФ эквивалентна F на исходных переменных. Это верхняя граница размера, но пока не доказательство необходимости. Возможно, другой маршрут упрощения даст меньше клауз. Чтобы исключить такую надежду, нужно показать нижнюю границу для любой эквивалентной КНФ, а не только посчитать результат одного распределения.
Максимальные ложные наборы требуют разных клауз
Возьмём наборы, где в каждой паре ровно одна единица. Их 2ⁿ, и на каждом F ложна. Поэтому любая эквивалентная КНФ должна иметь хотя бы одну ложную клаузу на каждом таком наборе. Покажем, что одна клауза не способна обслужить два различных набора из этого семейства.
Если клауза ложна на двух наборах, каждый её литерал ложен на обоих. Она останется ложной и на их покоординатном ИЛИ: положительный литерал был нулём в обоих, отрицательный имел единицу в обоих. Но два разных семейственных набора отличаются в некоторой паре; их ИЛИ содержит там две единицы, поэтому F истинна. Получается противоречие эквивалентности.
Нижняя граница зависит от языка представления
Значит любая эквивалентная КНФ на тех же переменных имеет не меньше 2ⁿклауз; распределительная конструкция достигает этой границы. Доказательство допускает даже отрицательные литералы в произвольной КНФ, поэтому ограничение положительными клаузами не было скрытой предпосылкой. Тавтологические клаузы не помогают, поскольку нигде не ложны.
Дополнительные служебные переменные меняют задачу. Можно кодировать значения внутренних узлов и сохранить выполнимость после их удаления, избежав явной экспоненциальной записи. Это не опровергает нижнюю границу, которая относится к буквальной эквивалентности на исходном наборе переменных. Поэтому размер преобразования следует обсуждать вместе с тем, что именно требуется сохранять.
Три пары и восемь обязательных условий
Условие. Для F=(a∧b)∨(c∧d)∨(e∧f) найдите минимальное число клауз эквивалентной КНФ без новых переменных.
- Выбираем один литерал из a/b, один из c/d иодин из e/f. Получаются 2·2·2=8 клауз длины 3.
- Например, входят(a∨c∨e),(a∨c∨f),(b∨d∨e),(b∨d∨f); остальные четыре получаются оставшимися независимыми выборами.
- Есть восемь ложных наборов с ровно одной единицей в каждой паре. Каждую пару разных таких наборов их покоординатное ИЛИ переводит в истинный набор F.
- Одна импликатная клауза не может быть ложной на двух из этих наборов. Нужны минимум восемь клауз, и построение из первого шага достигает минимума.
Ответ. Минимум равен 8 клаузам; суммарно в этой КНФ 24 вхождения литералов.
Проверка. Перебор 64 наборов подтверждает эквивалентность полной восьмиклаузной конструкции. Удаление любой из её клауз допускает ровно соответствующий ложный набор из семейства, показывая необходимость каждой.
Где легко ошибиться. Размер результата одной дистрибуции не доказывает минимальность. В этой главе её обеспечивает отдельный аргумент о ложных наборах; новые переменные в его условия не входят.
Проверьте понимание
Вопросы к этой главе
Если некоторые переменные совпадут?
Тогда независимые выборы могут слиться или поглотиться. Нижняя граница использует различие всех переменных и конкретное семейство из 2ⁿложных наборов.
Это нижняя граница любой логической схемы?
Нет. Исходная формула уже имеет линейный размер. Ограничение касается именно эквивалентной КНФ без расширения набора переменных, а не всех способов описать функцию.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Chaki et al.: Efficient Verification of Sequential and Concurrent C Programs
Первичная исследовательская статья: прочитано предупреждение об exponential blowup при распределительном преобразовании на печатной странице 29. Семейство попарных конъюнкций и доказательство точной нижней границы 2ⁿ разработаны в главе самостоятельно.
AG и EF на конечной модели: отрицание меняет квантор пути
«Можно однажды достичь цели» и «на каждом пути всегда безопасно» требуют разных операций над множествами состояний. На конечном графе CTL позволяет вычислить их до неподвижной точки. Покажем, почему отрицание всеобщей безопасности даёт существование плохого пути, а не неизбежность ошибки на всех путях.
Перед началом: Достижимость в ориентированном графе; Множества, дополнение и кванторы существования и всеобщности.
Какой путь проверяется
Рассматривается конечный граф переходов, у каждой вершины есть хотя бы один следующий шаг. Самопетли делают завершившиеся состояния бесконечными постоянными путями. EFg означает, что существует путь, на котором g выполнится сейчас или позже. AGp означает, что на всех путях p истинно во всех посещённых состояниях, включая исходное. Буквы E и A нельзя опускать: они задают разные требования к ветвлению.
Для множества Z определим EXZ как вершины хотя бы с одним преемником в Z, а AXZ — как вершины, все преемники которых входят в Z. В принятой модели отсутствие продолжений не приходится интерпретировать через пустую всеобщность. Если в другом описании разрешены тупики, сначала нужно согласовать их семантику, а не механически переносить результат вычисления.
Малая и большая неподвижные точки
Множество EFg получают из пустого Z повторением Z←G∪EXZ, где G — вершины с меткой g. Первый шаг добавляет сами цели; следующие добавляют их предшественников. Выбирается наименьшая неподвижная точка. Если вместо неё без проверки взять весь граф, уравнение может выполняться и в компоненте, которая никогда не достигнет цели.
Для AGp начинают со всех вершин и повторяют Z←P∩AXZ. Удаляются состояния вне P, затем их предшественники, способные выйти из оставшейся безопасной области. Здесь нужна наибольшая неподвижная точка: безопасный замкнутый цикл должен сохраниться. На конечном графе монотонная последовательность стабилизируется после конечного числа добавлений или удалений.
Отрицание меняет квантор пути
Эквивалентность ¬AGp=EF¬p следует из отрицания двух всеобщих требований: найдётся путь и момент нарушения p. Она не равна AF¬p, где ошибка должна наступить на каждом пути. Достаточно одной безопасной ветви, чтобы AF¬p оказалось ложным, хотя другая ветвь нарушает безопасность. При объяснении результата полезно предъявить конкретный плохой путь и отдельный безопасный цикл.
На проверяемом графе 0→1,2; 1→1; 2→3,4; 3→3; 4→4 положим G={3}, P={0,1,2,3}. Из 0 можно попасть в 3, но можно и остаться в 1. Путь 0→2→4 нарушает p; путь 0→1→1→… не нарушает. Оба свидетеля нужны, чтобы не перепутать возможность с неизбежностью.
Цель достижима, безопасность не всеобщая
Условие. На графе из объяснения вычислите EFg и AGp для G={3}, P={0,1,2,3}. Верны ли EFg, AGp, AF¬p в вершине 0?
- Для EFg начинаем с∅. Последовательность множеств: {3}, затем {2,3}, затем {0,2,3}; дальнейший шаг ничего не меняет.
- Для AGp начинаем с{0,1,2,3,4}. Получаем {0,1,2,3}, затем {0,1,3}, затем {1,3}; это неподвижное множество.
- Вершина 0 входит в EFg, но не в AGp. Путь 0→2→3 достигает цели, а путь 0→2→4 предъявляет нарушение p.
- AF¬p в 0 ложно: бесконечный путь 0→1→1→… остаётся внутри P. Следовательно, ¬AGp не означает неизбежность ошибки.
Ответ. EFg={0,2,3}, AGp={1,3}. В 0: EFg истинно, AGp ложно, AF¬p ложно.
Проверка. Независимый поиск достижимости до 3 даёт {0,2,3}; поиск достижимости до единственной плохой 4 даёт {0,2,4}. Дополнение второго множества равно {1,3}.
Где легко ошибиться. Не заменяйте существование контрпримера утверждением о том, что ошибочны все продолжения.
Проверьте понимание
Вопросы к этой главе
Почему безопасный цикл не удаляется из AGp?
Каждый его преемник остаётся в безопасном множестве. Если из цикла нет пути к плохому состоянию, он входит в наибольшую неподвижную точку.
Зачем цели добавляются уже на первом шаге EF?
Достижение допускает ноль переходов: цель истинна в текущем состоянии. Иная трактовка проверяла бы другое временное условие.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- CMU15-414: CTL model checking, теорема 3
Определения операторов и выбор наименьшей либо наибольшей неподвижной точки. Пятивершинный граф и обе траектории проверки составлены отдельно.
Квантор существования в BDD и образ множества состояний
Диаграмма решений может хранить не только отдельную функцию, но и множество допустимых состояний вместе с отношением перехода. Чтобы получить следующие состояния, сначала соединяют эти два ограничения, затем устраняют старые биты квантором существования. Исключение переменной складывает две ветви через ИЛИ; оно не выбирает произвольную ветвь и не означает отрицание переменной.
Перед началом: Разложение Шеннона и редуцированная BDD; Отношение между старыми и новыми состояниями.
Образ отношения требует одного общего свидетеля
Конечные булевы состояния; отношение перехода задано точно. Используются редуцированные упорядоченные BDD без приближённого удаления узлов, с одним общим порядком переменных.
Пусть S(x,y) отмечает допустимые старые состояния, а T(x,y,u,v) — переходы к новым битам u,v. Образ задаётся формулой I(u,v)=∃x∃y[S(x,y)∧T(x,y,u,v)]. Каждый включённый новый набор должен иметь хотя бы один общий старый свидетель, удовлетворяющий и S, и всем частям отношения.
Конъюнкцию можно построить операцией Apply: пара узлов разбивается по первой доступной переменной, результаты ветвей снова объединяются с редукцией. Таблица уникальных узлов и запоминание уже обработанных пар предотвращают повторную обработку одинаковых подзадач. Однако промежуточная диаграмма всё равно может сильно вырасти; каноничность не является обещанием малого размера.
Экзистенциальная абстракция объединяет обе ветви
Для любой булевой функции ∃x f равносильно f|x=0∨f|x=1. Поэтому при устранении узла x его потомки соединяют операцией ИЛИ. На узлах других переменных абстракция рекурсивно обрабатывает обе ветви и восстанавливает узел через обычную редукцию. Если нужная переменная вообще не встречается, функция остаётся прежней.
Для нескольких старых битов операцию повторяют или выполняют одним рекурсивным проходом с множеством устраняемых переменных. Совмещённая операция конъюнкции и абстракции может избегать части промежуточных узлов. Она должна сохранять точную семантику той же формулы; приближённые библиотечные операции с похожими именами имеют отдельные гарантии.
Покоординатные возможности не сохраняют совместимость
Рассмотрим S=x⊕y: допустимы 01 и 10. Каждый отдельный бит может быть и нулём, и единицей. Но произведение двух проекций даёт все четыре набора и теряет условие противоположности. Если заменить S этим прямоугольным приближением до вычисления перехода, появятся новые старые свидетели, которых исходная система не разрешала.
В нашем переходе u=x, v=x⊕y. Для настоящих старых состояний всегда v=1; при потерянной корреляции состояния 00 и 11 создадут v=0. Поэтому точный образ нужно строить до такого упрощения. После вычисления I старые имена исчезают, а новые можно переименовать для следующего шага; переименование также обязано быть согласованным и не смешивать два поколения битов.
Два состояния превращаются в одну проверку нового бита
Условие. Старые биты x,y удовлетворяют S=x⊕y. Переход детерминирован: u=x, v=x⊕y. Вычислите I(u,v)=∃x,y[S∧(u↔x)∧(v↔(x⊕y))] и сравните с предварительным покоординатным забыванием S.
- Составляем R=S∧T. Старый набор 01 ведёт в 01, а 10 — в 11. Остальные старые наборы запрещены S, хотя сами формулы перехода для них определены.
- При x=0 условие S требует y=1, а отношение требует u=0,v=1. Устранение y даёт ветвь ¬u∧v.
- При x=1 условие S требует y=0, и получается ветвь u∧v. Устранение x соединяет ветви: (¬u∧v)∨(u∧v)=v.
- Таким образом, точный образ равен {01,11}. Если сначала заменить S произведением проекций, разрешатся все x,y. Тогда переход создаёт все четыре новых набора; состояния 00 и 10 будут ложным добавлением.
Ответ. Точный образ I=v: бит u свободен, v обязан быть единицей. Предварительное независимое забывание корреляции даёт строгое надмножество из четырёх состояний.
Проверка. Проверяем все 16 наборов x,y,u,v непосредственно по R и собираем пары последних битов. Получаются ровно 01 и 11. Их характеристическая ROBDD имеет один нетерминальный узел v независимо от того, стоял ли u раньше в общем порядке.
Где легко ошибиться. Равенство ∃x(A∧B)=(∃x A)∧(∃x B) вообще неверно: справа разные части могут использовать разные значения x. Для экзистенциального квантора свободно распределяется дизъюнкция, а не произвольная конъюнкция.
Проверьте понимание
Вопросы к этой главе
Почему нельзя просто удалить узел устраняемой переменной?
У него могут быть разные допустимые продолжения для значений 0 и 1. Один выбранный потомок потеряет часть свидетелей. Нужна дизъюнкция обеих остаточных функций; только при совпадающих ветвях обычная редукция уже позволяет обойти узел.
Доказывает ли маленькая итоговая BDD малую стоимость вычисления?
Нет. Реляционное произведение может иметь крупные промежуточные диаграммы при результате из одного узла. Порядок переменных и совмещённая абстракция влияют на память и время, но не меняют точный набор новых состояний.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- CUDD: existential abstraction and relational product
Документация Cudd_bddExistAbstract и Cudd_bddAndAbstract задаёт точное устранение переменных и совмещённую конъюнкцию. Отношение двухбитного перехода и контрпример потери корреляции построены отдельно.
Компактность булевой логики связывает конечные и бесконечные ограничения
Компактность позволяет перейти от моделей всех конечных частей системы к одной оценке, удовлетворяющей всей системе. Модели отдельных частей могут различаться; поэтому их нельзя просто склеить произвольным выбором. Дерево конечных согласованных оценок объясняет, откуда берётся общая бесконечная ветвь и почему существенны конечное ветвление и конечная длина каждой формулы.
Перед началом: Булева оценка и выполнимость множества формул; Дерево и бесконечная ветвь.
Условие относится ко всем конечным наборам одновременно
Классическая пропозициональная логика со счётным множеством переменных; каждая отдельная формула конечна. Предполагается совместная выполнимость каждого конечного подмножества, а не только каждой формулы отдельно.
Система {p,¬p} показывает различие: каждая формула имеет модель, но их двухэлементный набор не имеет общей модели. Конечная выполнимость требует модели для любого конечного совместного выбора ограничений. Если система перечислена как F0,F1,…, достаточно доказать выполнимость каждого начального префикса: любое конечное подмножество целиком помещается в некоторый такой префикс.
Из существования общей модели конечная выполнимость следует сразу, ограничением списка требований. Обратное направление является содержанием компактности. Оно утверждает существование одной оценки всех переменных, а не только последовательности разных конечных ответов и не автоматически вычислимого алгоритма её нахождения.
Конечное ветвление сохраняет согласованный путь
Перечислим переменные p0,p1,… . На уровне n дерева оставим оценки первых n переменных, которые можно продолжить до модели первых n формул. Каждый уровень непуст по конечной выполнимости. Усечение допустимого узла снова допустимо, а у каждого узла не больше двух детей. Поэтому бесконечное дерево имеет бесконечную ветвь по лемме Кёнига.
Полученная ветвь задаёт одну оценку всех битов. Возьмём любую формулу Fi. На достаточно большом уровне уже включена Fi и назначены все её переменные: их конечное число. Узел ветви продолжается до модели этого префикса, поэтому сама ветвь также делает Fi истинной. Это рассуждение для произвольного i доказывает общую выполнимость.
Конечный эксперимент не заменяет универсальный аргумент
Проверка первых миллиона ограничений не доказывает, что следующий префикс тоже выполним. Для применения теоремы нужен довод для произвольной длины, например явная формула продолжения. При невыполнимости всей системы компактность, напротив, гарантирует существование некоторого конечного невыполнимого поднабора, но не задаёт заранее его размер.
Граница языка существенна. Если разрешить одну бесконечную дизъюнкцию p0∨p1∨… и одновременно потребовать ¬pi для каждого i, все конечные поднаборы имеют модель: можно выбрать ещё не запрещённый бит. Вся система модели не имеет. Такая дизъюнкция не является формулой рассматриваемой финитарной пропозициональной логики, поэтому пример не опровергает её компактность.
Один чередующийся сигнал для всех времён
Условие. Для каждого i≥0 заданы две клаузы pi∨p(i+1) и ¬pi∨¬p(i+1), а также единичная клауза p0. Докажите существование и единственность общей бесконечной оценки. Что изменится при добавлении ¬p6?
- Две клаузы для соседей запрещают одновременно 00 и 11. Поэтому p(i+1)=¬pi; каждая следующая переменная однозначно определяется предыдущей.
- Для произвольного N назначаем p0,…,pN по правилу pi=true при чётном i и false при нечётном. Это удовлетворяет единичной клаузе и всем N соседним парам. Любой конечный поднабор исходной системы входит в такой префикс.
- Компактность даёт общую модель; здесь она также предъявлена явно тем же правилом для всех i. Индукция от p0 доказывает, что другой общей оценки нет.
- Если добавить ¬p6, уже конечный набор p0, шести соседних пар для i=0,…,5 и ¬p6 противоречив: последовательное чередование требует p6=true. Поэтому условие конечной выполнимости для расширенной системы нарушено.
Ответ. Единственная общая оценка: pi истинно ровно для чётных i. Добавление ¬p6 делает систему невыполнимой и имеет явный конечный свидетель конфликта.
Проверка. Для каждого индекса соседние значения противоположны, что проверяет сразу обе клаузы. Перебор 128 оценок семи битов оставляет ровно 1010101 для префикса до p6 и ни одной после добавления ¬p6; бесконечное утверждение обосновано правилом и индукцией, а не этим перебором.
Где легко ошибиться. Нельзя выбрать произвольную модель каждого префикса и объявить их последовательность одной моделью: на пересекающихся переменных значения должны совпадать. Компактность обеспечивает согласованный выбор, а не согласованность любых выбранных ответов.
Проверьте понимание
Вопросы к этой главе
Зачем здесь теорема, если оценка выписана явно?
Явная оценка независимо проверяет пример и сильнее простого утверждения существования. Дерево объясняет общий переход, когда такого удобного правила не видно. Единственность в примере доказывает чередование; сама компактность единственности не обещает.
Если каждый префикс выполним, могут ли их модели не быть единственными?
Да. Например, без p0 любой конечный соседний префикс имеет два чередования, как и вся бесконечная система. Теорема требует существования моделей, а не единственности; для выбора ветви достаточно конечного ветвления.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Makoto Kanazawa, Hosei University: König’s Lemma and Compactness
Лемма о конечном ветвлении и теорема компактности для счётного множества формул. Доказательство через конечные оценки, чередующийся сигнал и пример границы финитарного языка изложены самостоятельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как читать составное условие с И и ИЛИ
Как проверять составные условия с И и ИЛИ: логические значения частей, включающее «или», скобки и короткое вычисление в Python.
Открыть темуПочему ложное условие не опровергает импликацию
Проверяем импликацию на конечной таблице: выделяем контрпримеры, отличаем проверку данных от доказательства общего правила и разбираем пустую выборку.
Открыть тему