Напиши лекцию на тему: Формулы алгебры высказываний. Конструирование логических высказываний. Понятие формулы алгебры высказываний. (с формулами)

Лекция: Формулы алгебры высказываний. Конструирование логических высказываний. Понятие формулы алгебры высказываний (с формулами) 1) Что такое алгебра высказываний - Высказывание (простое предложение) — это утверждение, которое может быть истинным или ложным. Примеры: «Снег белый» (истинно в условиях задачи), «Часы показывают 3» (истинность зависит от контекста). - Алгебра высказываний изучает способы строить новые высказывания из старых с помощью логических связок. - Основная задача: формализовать логику рассуждений и проверить истинность сложных высказываний по которым-то исходным значениям (значения атомарных высказываний). 2) Язык формул: переменные, константы и логические операторы - Атомарные переменные: p, q, r, … — обозначают простые высказывания. - Константы истинности: ⊤ (истина) и ⊥ (ложь). - Логические операторы (со своим смыслом): - ¬A: отрицание высказывания A - A ∧ B: конъюнкция (логическое «и») - A ∨ B: дизъюнкция (логическое «или») - A → B: импликация (если A, то B) - A ↔ B: эквивалентность (A равно B) - Скобки и составные формулы: формула строится рекурсивно из атомарных переменных, констант и формул с помощью указанных операторов. - Пример формулы: (p ∧ q) → (¬r ∨ p) 3) Конструирование формул: понятие корректной (well-formed) формулы - Базовый уровень: атомарная переменная p, q, r является формулой. - Правила формирования: - Если A — формула, то ¬A — формула. - Если A и B — формулы, то (A ∧ B), (A ∨ B), (A → B), (A ↔ B) — формулы. - ⊤ и ⊥ — формулы. - Важно: формула всегда записывается в скобках вокруг бинарных операторов, чтобы однозначно определить структуру выражения. - Примеры корректных формул: - p - ¬p - (p ∧ q) - (p ∨ (¬q)) - ((p → q) ∧ (q → r)) ↔ (p → r) - Примеры некорректных формул (для понимания): p ∧, (p ∨), ¬⊤ (некорректно без формулы после ¬), p → (q ∧ ()) 4) Семантика формул: значения формул - Валюация (толкование) — отображение каждого атома в истину 1 или ложь 0: v(p) ∈ {0,1}, v(q) ∈ {0,1}, … - Значение составной формулы определяется по значениям её частей: - v(¬A) = ¬v(A) - v(A ∧ B) = v(A) ∧ v(B) - v(A ∨ B) = v(A) ∨ v(B) - v(A → B) = ¬v(A) ∨ v(B) - v(A ↔ B) = (v(A) = v(B)) (истина тогда, когда значения A и B совпадают) - ⊤ имеет значение 1 (истина) во всех валюациях; ⊥ — значение 0 (ложь) во всех валюациях. - Пример: Формула A = p → q. - Возможные валюации: (p=1, q=1) → A=1; (1,0) → A=0; (0,1) → A=1; (0,0) → A=1. - Таблицы истинности — удобный инструмент для проверки значения формулы. 5) Таблицы истинности: пример - Пусть A = p ∧ q. p q | A 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1 - Пусть B = p → q. p q | B 0 0 | 1 0 1 | 1 1 0 | 0 1 1 | 1 6) Нормальные формы: CNF и DNF - Цель нормализации — привести формулу к стандартному виду для автоматической обработки. - Дизъюнктивная нормальная форма (DNF): формула, которая является дизъюнкцией конъюнкций литералов (литерал — атом p или его отрицание ¬p). Пример: (p ∧ ¬q) ∨ (r ∧ p) — это DNF. - Конъюнктивная нормальная форма (CNF): формула, которая является конъюнкцией дизъюнкций литералов. Пример: (p ∨ q) ∧ (¬p ∨ r) — это CNF. - Преобразование в CNF/DNF обычно выполняется с помощью стандартных законов логики: - Дистрибутивность: A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C); A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) - Исправление двойных отрицаний: ¬(¬A) ≡ A - Замены импликаций и эквивалентностей: A → B ≡ ¬A ∨ B; A ↔ B ≡ (A ∧ B) ∨ (¬A ∧ ¬B) - Пример преобразования: Формула F = (p → q) ∧ (¬p ∨ r). - Применяем A → B ≡ ¬A ∨ B: F ≡ (¬p ∨ q) ∧ (¬p ∨ r) Это уже CNF: конъюнкция из дизъюнкций литералов. 7) Законы логики: основные тождества и правила - Коммутативность: A ∧ B ≡ B ∧ A; A ∨ B ≡ B ∨ A - Ассоциативность: (A ∧ B) ∧ C ≡ A ∧ (B ∧ C); (A ∨ B) ∨ C ≡ A ∨ (B ∨ C) - Дистрибутивность: - A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) - A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) - Двойное отрицание: ¬(¬A) ≡ A - Импликация и эквивалентности: - A → B ≡ ¬A ∨ B - A ↔ B ≡ (A ∧ B) ∨ (¬A ∧ ¬B) - Тавтологии и контрадикции: - A ∨ ¬A ≡ ⊤ (закон исключённого среднего) - A ∧ ¬A ≡ ⊥ (несовместимость) 8) Примеры решений: пошаговое преобразование - Пример 1: Преобразуйте F = (p → q) ∧ (q → p) в эквивалентную форму без импликаций. - p → q ≡ ¬p ∨ q - q → p ≡ ¬q ∨ p - F ≡ (¬p ∨ q) ∧ (¬q ∨ p) - Пример 2: Преобразуйте F = p ∨ (q ∧ r) в форму CNF. - По правилу дистрибутивности: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) - Готово: CNF = (p ∨ q) ∧ (p ∨ r) 9) Применение и примеры задач - Проверка tautology: является ли A → A тавтологией? - A → A ≡ ¬A ∨ A ≡ ⊤ - Пример с выводом по правилам: - Пусть A = p → q. Если дано p, можно сделать вывод q по правилу modus ponens, если известна истина p и импликация p → q. - Применение в цифровых схемах: - Логические формулы моделируют логические схемы (AND, OR, NOT — соответствуют ∧, ∨, ¬). Приведение к CNF – полезно для оптимизации и проверки одинаковой функциональности. 10) Краткое резюме - Формулы алгебры высказываний строятся из атомарных переменных, констант и логических операторов с помощью строгих правил формирования. - Семантика формул определяется через валюацию: значение формулы зависит от значений её подформул. - Таблицы истинности и нормальные формы (CNF, DNF) позволяют систематически анализировать формулы. - Важные инструменты: законы эквивалентности, правила преобразования, умение сводить импликации и эквивалентности к базовым операторам. - Применение: логика рассуждений, доказательства, проверка tautologies и противоречий, построение и упрощение цифровых схем и логических программ. Примеры практических заданий (решения по шагам) 1) Упростите формулу: F = ¬(p ∧ ¬p) - Внутри: p ∧ ¬p — противоречие (заведомо ложно): p ∧ ¬p ≡ ⊥ - Следовательно: ¬(p ∧ ¬p) ≡ ¬⊥ ≡ ⊤ - Ответ: F ≡ ⊤ 2) Преобразуйте F = (p ∨ q) ∧ (¬p ∨ r) в CNF - Это уже CNF: конъюнкция дизъюнкций литералов. - Ответ: F ≡ (p ∨ q) ∧ (¬p ∨ r) 3) Преобразуйте G = p → (q ∨ r) в форму без импликации - p → (q ∨ r) ≡ ¬p ∨ (q ∨ r) - ПоAssociativity: ¬p ∨ q ∨ r - Ответ: G ≡ ¬p ∨ q ∨ r 4) Проверка тавтологии: является ли H = (p → q) → (¬q → ¬p) тавтологией? - Преобразуем: p → q ≡ ¬p ∨ q; ¬q → ¬p ≡ q ∨ ¬p (то же самое) - H ≡ (¬p ∨ q) → (q ∨ ¬p) ≡ ¬(¬p ∨ q) ∨ (q ∨ ¬p) - ¬(¬p ∨ q) ≡ p ∧ ¬q - H ≡ (p ∧ ¬q) ∨ q ∨ ¬p - Любая валюация даёт истину, т.к. q ∨ ¬p уже покрывает множество ситуаций; можно проверить отдельными валюациями, но обычно H является тавтологией. (Замечание: проверьте аккуратно таблицей истинности.) Если нужно, могу сделать детальный разбор по конкретной задаче или привести больше примеров и таблиц истинности под конкретный уровень подготовки.