В лекции курса CS221 Стэнфордского университета, посвященной искусственному интеллекту, рассматривается логика как фундаментальный метод рассуждений. Хотя современные системы ИИ часто опираются на вероятностные модели и машинное обучение, логический подход предлагает уникальную выразительность и точность, которые остаются незаменимыми для символьных вычислений и представления знаний.
🧠 Логика как язык: синтаксис, семантика и инференс 4:11
Логику следует воспринимать не просто как набор правил, а как формальный язык, предназначенный для представления знаний о мире и рассуждений на их основе . В отличие от естественного языка (английского или русского), который часто бывает двусмысленным и «скользким» (например, парадокс: «ничего не лучше вечного мира, грош лучше ничего, значит, грош лучше мира»), логика обеспечивает строгую структуру .
Любая логическая система состоит из трех обязательных ингредиентов:
- Синтаксис: определяет набор допустимых формул (предложений).
- Семантика: определяет значение этих формул (связь с реальным миром).
- Правила логического вывода (Inference rules): позволяют извлекать новые формулы из уже существующих .
Один из лекторов (предположительно, Перси Лян) подчеркивает различие между синтаксисом и семантикой на примере: выражения 2 + 3 и 3 + 2 имеют разный синтаксис (написание), но одинаковую семантику (число 5) . Напротив, выражение 3 / 2 в Python 2.7 (результат 1) и Python 3 (результат 1.5) имеет одинаковый синтаксис, но разную семантику .
🏗️ Пропозициональная логика: кирпичики знаний 9:20
Пропозициональная (логика высказываний) — это простейшая форма логики. Она начинается с атомарных формул (символов), таких как P, Q, Rain (дождь) или Wet (мокро) .
Синтаксис позволяет комбинировать их с помощью логических связок:
- Отрицание (not):
¬P - Конъюнкция (and):
P ∧ Q - Дизъюнкция (or):
P ∨ Q - Импликация (implies):
P → Q(если P, то Q) - Эквивалентность (equivalence):
P ↔ Q.
Формулы строятся рекурсивно. Например, (Rain ∧ (Rain → Wet)) → Wet является валидной формулой, тогда как P ∧ ∨ Q — нет, из-за нарушения правил синтаксиса .
🌍 Модели и интерпретация: что есть истина? 12:42
В логике понятие модели (W) отличается от машинного обучения. Здесь модель — это состояние мира, представляющее собой присвоение значений «истина» (true) или «ложь» (false) всем пропозициональным символам . Если у нас есть 3 символа (A, B, C), то существует $2^3 = 8$ возможных моделей (миров) .
Функция интерпретации (I) связывает синтаксис и семантику. Она берет формулу $F$ и модель $W$, возвращая ответ: истинна ли эта формула в данном конкретном мире .
- Если формула — это
Rain ∨ Wet, а в мире $W$Rain = true, то функция вернетtrue. - Семантика формулы — это множество всех моделей $M(F)$, в которых эта формула истинна .
📚 База знаний: сужение круга возможностей 25:18
База знаний (Knowledge Base, KB) — это набор формул, которые мы считаем истинными. Семантически KB представляет собой пересечение моделей всех формул, входящих в неё .
Ключевой вывод лекции: по мере добавления новых фактов в базу знаний, количество возможных моделей (миров) сокращается .
- База знаний накладывает ограничения на мир.
- Чем больше мы знаем, тем меньше остается неопределенности.
- В отличие от вероятностных моделей, логика монотонна: добавление нового факта не может увеличить количество возможных миров, оно только сужает их или оставляет прежним .
⚖️ Логические отношения: Следование, Противоречие, Случайность 31:34
Отношение между базой знаний (KB) и новой формулой (F) может быть трех типов:
- Логическое следование (Entailment): $KB ⊨ F$. Формула $F$ не дает новой информации; она уже истинна во всех мирах, где истинна KB. Множество моделей не сокращается .
- Противоречие (Contradiction): $F$ несовместима с KB. Пересечение моделей KB и $F$ пусто. Такого мира не может существовать .
- Случайность (Contingency): $F$ не следует из KB и не противоречит ей. Она отсекает часть миров, делая наше знание более конкретным. Мы узнаем что-то новое .
На этих принципах строятся операции Ask (запрос к базе: «Верно ли это?») и Tell (сообщение базе нового факта) .
🤖 SAT-солверы и связь с Байесовскими сетями 51:27
Математически логика тесно связана с вероятностными графическими моделями. Байесовская сеть задает распределение вероятностей над моделями (мирами). Логика же работает в двоичном режиме: вероятность либо равна 0 (невозможный мир), либо больше 0 (возможный мир) . Однако логика выразительнее в плане запросов: она позволяет легко оперировать конструкциями вроде «или» (Rain ∨ Snow), что в Байесовских сетях требует введения дополнительных переменных .
Для эффективной проверки выполнимости формул (Satisfiability) на практике используются SAT-солверы (например, библиотека Z3 от Microsoft) . Хотя задача SAT является NP-полной, современные инструменты способны обрабатывать сотни тысяч переменных благодаря десятилетиям оптимизаций и эвристик .
🛠️ Правила вывода: как рассуждают люди
В финале лекции обсуждается логический вывод (Inference) как манипуляция символами без перебора всех миров. Самым известным правилом является Modus Ponens: если у нас есть $P$ и $P → Q$, мы можем вывести $Q$ .
Ключевые характеристики правил вывода:
- Обоснованность (Soundness): мы выводим «ничего, кроме истины» (все выведенные формулы логически следуют из KB) .
- Полнота (Completeness): мы можем вывести «всю истину» (любая формула, которая логически следует из KB, может быть получена через правила) .
Лектор подводит итог: логика — это мощный фундамент, который позволяет ИИ рассуждать компактно и выразительно, переходя от простого поиска к аналитическим доказательствам .
