Основы дискретной математики и математической логики
Разбираем булеву алгебру простым языком: что такое логическая переменная, как работают операции И, ИЛИ, НЕ, зачем нужны таблицы истинности и где логические выражения встречаются в программировании, цифровой технике и базах данных.
45 минут — объём лекции
6 разделов
4 вопроса для самопроверки
М1 · Т2 Содержание лекции
Нажмите на пункт, чтобы перейти к разделуЧему вы научитесь
Результаты освоения темы сформулированы по рабочей программе дисциплины «Информатика».
- Определять место дискретной математики и логики в информатике, называть основные разделы: теорию множеств, теорию графов и математическую логику.
- Различать логические значения и переменные, понимать смысл трёх базовых операций: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (инверсия).
- Строить и читать таблицы истинности, применять основные законы булевой алгебры для упрощения логических выражений.
- Объяснять, как логические выражения используются в программировании, цифровой технике, базах данных и релейной автоматике.
Входные требования: умение работать с обычной алгеброй на уровне школьной программы. Предварительное знакомство с программированием не требуется — все примеры разбираются по шагам.
Раздел 1. Дискретная математика и логика — что изучает
Дискретная математика — раздел математики, изучающий прерывные (дискретные) структуры: наборы объектов, графы, логические высказывания. Проще говоря, всё то, что можно пересчитать поштучно, — а не измерять непрерывно.
В информатике дискретная математика играет особую роль: она даёт точный язык для алгоритмов, условий и данных. Без неё невозможно описать работу программы или схемы — каждое решение компьютера в итоге сводится к ответу «да» или «нет».
Наборы объектов и операции над ними: объединение, пересечение, разность. Основа для работы со списками и базами данных.
Описание сетей и связей: вершины и рёбра. Используется в навигаторах, компьютерных сетях и задачах на маршруты.
Формальный язык высказываний, доказательств и логических операций. Булева алгебра — важная часть этого раздела.
Методы дискретной математики
- абстрагирование
- формализация
- аксиоматика
- логический вывод
- доказательство
- индукция
Раздел 2. Булева алгебра — язык логики
Четыре базовых понятия образуют фундамент, на котором строится вся работа с логикой: значение, переменная, операция и выражение. Запомните их — дальше мы будем собирать из них всё остальное.
- Шаг 01
Логическое значение
В булевой алгебре всего два значения — 0 (ложь) и 1 (истина). Других состояний нет, и это упрощает все правила.
Пример: лампа выключена (0) или включена (1); условие не выполнено (0) или выполнено (1).
- Шаг 02
Логическая переменная
Переменная обозначается буквой (A, B, X) и в каждом конкретном случае принимает значение 0 или 1 — третьего не дано.
Пример: A = «пользователь вошёл»; B = «файл существует».
- Шаг 03
Логическая операция
Действие над переменными — И, ИЛИ, НЕ. Результат операции снова равен 0 или 1, и его можно использовать дальше.
Пример: (A И B) проверяет, что оба условия истинны: 1 ∧ 1 = 1.
- Шаг 04
Логическое выражение
Формула из переменных и операций — например, (A ∧ B) ∨ ¬C. Вычисляется шаг за шагом и даёт один итоговый 0 или 1.
Итог: ради этого единственного 0 или 1 и строится вся работа с логикой.
В булевой алгебре всего два значения — 0 и 1. Из простых операций над ними собирается любая сложная логика: условие в программе, фильтр в базе данных, схема в процессоре. Именно поэтому компьютеры умеют принимать решения «да/нет» на каждом шаге.
Раздел 3. Таблицы истинности и законы булевой алгебры
Таблица истинности показывает результат операции для всех возможных комбинаций входов. Это главный способ проверить и сравнить логические выражения.
- Коммутативность
От перестановки мест результат не меняется: A ∧ B = B ∧ A, A ∨ B = B ∨ A.
- Ассоциативность
Порядок выполнения операций одного типа не важен: (A ∧ B) ∧ C = A ∧ (B ∧ C); то же для «или».
- Дистрибутивность
Одна операция распределяется над другой: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C).
- Идемпотентность
Повторное применение операции ничего не меняет: A ∧ A = A, A ∨ A = A.
- Законы де Моргана
Отрицание операции равно обратной операции над отрицаниями: ¬(A ∧ B) = ¬A ∨ ¬B.
Базовая логика
Три операции, через которые выражаются все остальные: НЕ (инверсия), И (конъюнкция), ИЛИ (дизъюнкция). Этого набора достаточно для любой логической функции.
Производные операции
Собираются из базовых, но удобны в технике: И-НЕ (NAND), ИЛИ-НЕ (NOR), исключающее ИЛИ (XOR). Именно их чаще всего встретишь в микросхемах.
Условные связки
Импликация (A → B) и эквиваленция (A ↔ B). Используются в логических задачах, доказательствах и при записи правил «если …, то …».
Раздел 4. Логические выражения в технике и ИТ
Одна и та же булева алгебра работает в очень разных местах: в каждом из них логика помогает принять решение «да/нет» — на уровне схемы, запроса или условия в коде. База одна, прикладная часть — разная.
-
Программирование
Условие в коде — это логическое выражение. Запись if (a > 0 AND b < 100): работает по тем же правилам, что и таблица истинности, только записана в синтаксисе языка.
условия if/whileлогические типыоператоры сравнения -
Цифровая электроника
Логические элементы (вентили) AND, OR, NOT — основа любого процессора. Из миллионов таких элементов построена схема, выполняющая команды программы.
вентили AND/ORмикросхемыаппаратная логика -
Поисковые системы
Операторы AND, OR, NOT в поисковых запросах — те же логические операции. Они помогают точно находить нужную информацию среди миллионов документов.
поисковые операторыфильтрацияточные запросы -
Базы данных
SQL-запросы используют логические выражения в WHERE. Без логики И, ИЛИ, НЕ невозможно выбрать из таблицы нужные строки — например, по диапазону дат и статусу заказа.
SQL WHEREлогика запросовфильтрация данных -
Релейная автоматика
Контакты реле в схеме управления: соединение последовательно даёт логику «И», параллельно — «ИЛИ». По этой схеме работают лифты, станки и светофоры.
контакты релеавтоматикасхемы управления -
Шифрование данных
Операция XOR позволяет просто зашифровать и восстановить данные: применённая дважды с тем же ключом, она возвращает исходное значение. Это базовый приём криптографии.
XOR-шифрованиекриптографиязащита информации
Проверь себя
Раздел 5. Четыре вопроса по теме — выберите один вариант
Вопрос 1Сколько значений может принимать логическая переменная в булевой алгебре?
Вопрос 2Как называется операция, которая меняет логическое значение на противоположное?
Вопрос 3Чему равно значение выражения A ∧ B при A = 1 и B = 0?
Вопрос 4Чему равно выражение A ∨ ¬A независимо от значения A?
Результат: 0 из 4.
Раздел 6. Итоги и глоссарий темы
Главное из лекции
- Булева алгебра работает только с двумя значениями — 0 и 1, поэтому компьютер умеет принимать решения «да/нет».
- Три базовые операции — И (конъюнкция), ИЛИ (дизъюнкция), НЕ (инверсия) — достаточны для выражения любой логической функции.
- Таблица истинности показывает результат операции для всех возможных комбинаций входов — это основной способ проверки логики.
- Законы булевой алгебры позволяют упрощать выражения и применять их в программировании, цифровой технике, базах данных и автоматике.
Глоссарий темы
Раздел математики, изучающий прерывные структуры: множества, графы, логические высказывания.
Величина, принимающая одно из двух значений: 0 (ложь) или 1 (истина).
Операция, возвращающая 1 только тогда, когда оба аргумента равны 1.
Операция, возвращающая 1, если хотя бы один из аргументов равен 1.
Операция, меняющая значение на противоположное: 0 превращается в 1, а 1 — в 0.
Таблица всех комбинаций входов операции с результатами на выходе для каждой комбинации.