logic

Логика с нуля

Высказывания, доказательства и строгие рассуждения — слой мышления, на котором стоят алгоритмы.

6 юнитов·19 уроков·~5 ч

Высказывания, связки, таблицы истинности

Любое условие в программе — высказывание; И/ИЛИ/НЕ и импликация — вся грамматика корректных ветвлений.

01 Высказывания и истинность: что на самом деле проверяет ваш if 16 мин 02 И, ИЛИ, НЕ: таблицы истинности, де Морган и искусство отрицать условия 17 мин 03 Импликация и эквивалентность: если-то, вакуумная истинность и guard clauses 17 мин

Аргументы, кванторы, индукция

Корректные формы рассуждений, ∀/∃ и индукция — ровно те инструменты, на которых держатся инварианты циклов и рекурсия.

01 Валидные аргументы: modus ponens, modus tollens и ловушки, которые обманывают отладчиков 16 мин 02 Кванторы: для-всех, существует и почему «все тесты прошли» может лгать 16 мин 03 Индукция и инварианты: доказываем корректность кода для каждого n 17 мин

Множества и отношения

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

01 Множества и принадлежность: внутри или нет 14 мин 02 Операции над множествами и диаграммы Венна: объединение, пересечение, разность, дополнение 15 мин 03 Отношения: упорядоченные пары и сетка того, кто с кем связан 15 мин 04 Эквивалентность и порядок: классы, разбиения и что можно сравнивать 16 мин

Техники доказательства

Четыре приёма доказывают почти всё: прямая цепочка, контрапозиция, противоречие и контрпример — код-ревью использует все четыре.

01 Прямое доказательство и контрапозиция: цепочки импликаций и когда их переворачивать 16 мин 02 Доказательство от противного: предположи ложность и выведи невозможное 16 мин 03 Контрпримеры и утверждения: на ком лежит бремя доказательства 14 мин

Рекурсия и рекурренты

Рекурсивное определение — база плюс правило через меньшее себя; разверни рекурренту, чтобы посчитать работу, индукция докажет корректность.

01 Рекурсивные определения: базовые случаи, меньшие себя и контракт за прыжком веры 16 мин 02 Развёртывание рекуррент: линейная и квадратичная цена 12 мин 03 03-recursion-and-induction

Комбинаторные рассуждения

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

01 Принципы счёта: «и затем» перемножается, «или» складывается 16 мин 02 Принцип Дирихле: гарантированные коллизии и искусство выбирать клетки 15 мин 03 Инварианты на практике: доказать недостижимость цели без перебора 17 мин

Проекты по этому треку

Guided-проекты, которые закрепляют изученное здесь.

◆ Проекты

Прувер по таблицам истинности

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

Следующий трек

React с нуля до senior

Как React рендерит на самом деле — reconciliation, батчинг состояния, эффекты, мемоизация — глубже туториалов.