Логическое исчисление для структуры доказательства Цель состоит в том, чтобы понять, как структурируются доказательства, превращая утверждения на естественном языке в символы. Каждое утверждение рассматривается как элемент, который можно механически отслеживать с помощью рассуждений. Присвоение фиксированных значений истинности позволяет нам проверять шаги и быть уверенными в правильности. Эта формализация лежит в основе строгого математического дискурса.
Утверждения и фиксированные задания на истинность Каждому элементарному утверждению присваивается значение истинности, которое не меняется в процессе анализа. В концептуальном столбце каждое утверждение сопоставляется с истинностью или ложью. Мы не решаем, что на самом деле истинно; мы только отслеживаем присвоенные значения для изучения аргументации.
От простых утверждений к сложным Представьте язык, который связывает базовые утверждения логическими связями. Используя такие символы, как x и y, новые утверждения создаются на основе существующих. Этот формальный язык становится инструментом для исследования математических объектов.
Конъюнкция: Таблица значений и истинности Конъюнкция связывает x и y, образуя x ∈ y. Она истинна только тогда, когда и x, и y истинны, и ложна в противном случае. Связка - это пропозициональная связь, которая приводит к новому утверждению с определенным значением истинности.
Дизъюнкция: таблица значений и истинности Дизъюнкция x ∈ y истинна, когда хотя бы одно из значений x или y истинно. Она ложна только тогда, когда оба значения ложны. Существуют разные обозначения, но семантика одинакова.
Бесконечно выразительный язык При многократном объединении утверждений с помощью связок возникает бесконечно много новых утверждений. Таким образом, язык содержит встроенную функцию infinity, необходимую для моделирования мира. На практике достаточно меньшего количества базовых связок, но выразительная сила остается безграничной.
Импликация и правила вывода Импликация x → y формализует “если x, то y”. Она ложна только тогда, когда x истинно, а y ложно, и истинна в противном случае, в том числе когда x ложно. Как правило, при выводе, исходя из общепринятых истин, выводятся новые утверждения; при ложной посылке вывод не несет никакой информации о y, но оценивается как истинный. Это показывает, как формальная дедукция переходит от посылок к выводам.
Эквивалентность как ‘Если и только если’ Эквивалентность x ∈ y утверждает, что x и y имеют одинаковое значение истинности. Если x истинно, то y истинно, а если x ложно, то y ложно. Многие теоремы естественным образом принимают форму “тогда и только тогда”.
Отрицание как унарная операция Отрицание x изменяет значение истинности утверждения. Если x истинно, то x ложно, и наоборот. Эта унарная операция дополняет бинарные связки.
Математика как определения, рассуждения, доказательства Математика развивается, давая определения, проводя обоснованные рассуждения и формулируя истинные результаты в виде теорем. Геометрические факты, такие как сумма углов треугольника или совпадение медиан, доказываются, а не измеряются. Рисунки направляют интуицию, но не являются доказательствами.
Символы, значение и границы формализма Гильберт подчеркивал, что математика манипулирует цепочками символов в соответствии с правилами, но эти символы представляют мысли. Проект Бурбаки стремился перестроить математику на основе основополагающих символов и теории множеств. Эта попытка раскрыла как силу формализации, так и остающуюся загадкой человеческого мышления.
Тавтологии и ассоциативность с помощью таблиц истинности Оценка всех восьми назначений для x, y, z показывает, что утверждения типа (x ∨ y) ∨ z и x ∨ (y ∨ z) всегда совпадают. Такие универсально истинные утверждения являются тавтологиями. Ассоциативность позволяет перемещать круглые скобки без изменения значения.
Ассоциативность Позволяет выполнять операции с несколькими операциями Поскольку ∨ и ∧ ассоциативны, выражения с большим количеством членов четко определены независимо от того, заключены ли они в круглые скобки. Это отражает принцип многократного сложения в арифметике. Ассоциативность чисел отражает свойства, уже присутствующие в логическом языке.
Коммутативность базовых связок Порядок следования операндов в ∨ и ∧ не влияет на значения истинности. Эта коммутативность соответствует равенствам типа 2 + 3 = 3 + 2. Числа наследуют эти структурные особенности от языка мышления.
Двойственность и законы Де Моргана Получается отрицанием дизъюнкции в конъюнкцию отрицаний, и наоборот. В частности, (Х ∨ У) ≡ Х ∧ Y и (Х ∧ У) ≡ Х ∨ У. Таким образом, конъюнкция и дизъюнкция двойственны под отрицание.
Дистрибутивность и дисциплина в круглых скобках Вместе распространяет над дизъюнкции и дизъюнкции распределяет по совокупности. Истина-таблица проверки подтверждают, равенств, например X ∧ (г ∨ Z в) ≡ (Х ∧ У) ∨ (Х ∧ З). Мастерство подобных законов предотвращает типичные кронштейн расширительного ошибки.
Трансформирующий подтекст Отрицание импликации удовлетворяет (x → y) ≡ x ∈ y. Это тождество фокусирует внимание на единственном фальсифицирующем случае x → y. Оно лежит в основе эффективных методов доказательства.
Доказательство следствий от противного Чтобы доказать x → y, предположим, что x истинно, а y ложно, и выведем невозможность. Показ того, что фальсифицирующий случай не может иметь места, делает вывод истинным. Этот метод использует единственную критическую строку в таблице истинности вывода.
Доказательство эквивалентности с помощью двух следствий Чтобы установить x ∈ y, докажите как x → y, так и y → x. Проверка двух направлений гарантирует, что значения истинности всегда совпадают. Классические примеры включают такие критерии, как условия разрешимости, привязанные к дискриминанту.
Построение дизъюнктивной нормальной формы Каждой строке, в которой целевое утверждение истинно, соответствует конъюнкция (minterm), которая истинна только в этой строке. Разбиение всех таких minterm воспроизводит требуемую таблицу истинности. Таким образом, любое утверждение может быть выражено с использованием только ∨, ∧ и .
Конъюнктивная нормальная форма по двойственности Начиная с строк false или путем отрицания DNF, получаем CNF: соединение дизъюнкций. Выбор между DNF и CNF зависит от того, является ли значение true или false разреженным. Оба являются систематическими нормальными представлениями.
Минимальные экзамены как основа Множество всех минимальных конъюнкций формирует базис для пространства таблиц истинности. Любая булева функция разлагается на комбинацию по этому базису, аналогично линейно-алгебраическим разложениям. Эта точка зрения определяет систематическое построение и упрощение.
От логики к цифровой коммуникации Цифровые системы многократно декомпозируют и перекомпоновывают информацию, используя эти логические основы. Коэффициенты определяют, какие minterms активны, что обеспечивает эффективную передачу, реконструкцию и сжатие дискретных данных. Эта основа обеспечивает работу таких повседневных технологий, как обработка изображений и сигналов на смартфонах.
Функциональная завершенность и отдельные операторы Трио ∧, ∨, достаточно для выражения любой пропозициональной функции. Даже один двоичный оператор, такой как штрих Шеффера или стрелка Пирса, может генерировать все выражения за счет неассоциативности и тщательного заключения в квадратные скобки. Таким образом, логические операции обеспечивают минимальный набор инструментов при максимальной выразительности.