Учебник Логика и булева алгебра для начинающих

Программа курса

1. 1 Основы логики

   1. Высказывания и логические операции: НЕ, И, ИЛИ

      Что такое высказывание, логические переменные и три базовые операции: отрицание НЕ, конъюнкция И, дизъюнкция ИЛИ. Таблицы истинности и приоритет операций.

   2. Импликация и эквивалентность

      Импликация A→B и эквивалентность A≡B простыми словами: таблицы истинности, почему ложная посылка даёт истину, замена A→B = ¬A∨B и задачи ЕГЭ.

   3. Таблицы истинности сложных выражений

      Как пошагово построить таблицу истинности сложного логического выражения: число строк 2^n, порядок наборов, промежуточные столбцы, тавтология и противоречие.

   4. Законы алгебры логики и упрощение выражений

      Основные законы алгебры логики: де Моргана, дистрибутивность, поглощение, идемпотентность. Учимся упрощать булевы выражения шаг за шагом с примерами.

   5. Логика, множества и поисковые запросы

      Как логические операции И, ИЛИ, НЕ связаны с множествами и кругами Эйлера. Разбор задачи ЕГЭ на поисковые запросы и формула включений-исключений.

   6. Логические задачи ЕГЭ: поиск переменной и отрезки

      Разбор задания 15 ЕГЭ по информатике: как преобразовать импликацию, рассуждать через отрезки на числовой прямой и найти параметр A, проверив ответ программой.

2. 2 Логика в цифровой технике

   1. Логические вентили: И, ИЛИ, НЕ

      Логические вентили AND, OR, NOT, XOR: обозначения, таблицы истинности и формулы. Почему NAND и NOR — универсальные элементы, из которых собирается вся электроника.

   2. От формулы к логической схеме

      Как по булевой формуле собрать схему из вентилей и прочитать схему обратно в формулу. Порядок логических операций и разбор примера F = (A AND B) OR NOT C.

   3. Сумматор и триггеры

      Полусумматор и полный сумматор: сложение двоичных битов через XOR и AND, перенос в старший разряд. Таблицы истинности и идея триггера как ячейки памяти на 1 бит.

3. 3 Нормальные формы и синтез

   1. СДНФ и СКНФ

      Дизъюнктивная и конъюнктивная нормальные формы, совершенные СДНФ и СКНФ: что это, как записать формулу и зачем нужны нормальные формы.

   2. Построение функции по таблице истинности

      Алгоритм восстановления булевой формулы по таблице истинности: по единицам строим СДНФ, по нулям — СКНФ. Пошаговый разбор для трёх переменных.

   3. Минимизация: карты Карно

      Карты Карно для 2–3 переменных: зачем минимизировать формулы, как склеивать соседние единицы и получать упрощённую ДНФ. Разбор с таблицей-картой.

4. 4 Логика в программировании

   1. Булевы выражения и короткое замыкание

      Условия if как булевы функции, порядок and/or/not и короткое замыкание (ленивое вычисление) — зачем оно нужно, на примерах Python с выводом.

   2. Законы де Моргана в условиях

      Законы де Моргана для упрощения и инверсии условий в коде: как раскрывать not(...), баги с отрицанием диапазона. Примеры Python до и после.

   3. Битовые логические операции

      Битовые операции &, |, ^, ~ и сдвиги как побитовая логика; флаги и маски; отличие от and/or. Примеры Python с двоичным выводом bin().

5. 5 Продвинутые задачи ЕГЭ

   1. Задание 2: таблицы истинности

      Как по фрагменту таблицы истинности восстановить, какому столбцу соответствует каждая переменная: приёмы быстрого анализа и разбор задач ЕГЭ с числами.

   2. Логические уравнения и системы

      Решаем логические уравнения с импликацией и считаем число решений систем: метод «по цепочке переменных» с пошаговыми формулами и числами для ЕГЭ.

   3. Задание 15: множества, отрезки, ДЕЛ

      Задание 15 ЕГЭ: логические выражения с отрезками числовой прямой и предикатом ДЕЛ(n,k). Как найти параметр, при котором выражение истинно для всех x — с разбором.