4.2. Элементы математической логики | Информатика 7

Высказывания

Высказывание — это любое осмысленное утверждение, которое может быть либо истинным, либо ложным, но не тем и другим одновременно.

Примеры высказываний

Утверждение	Является высказыванием?	Значение
«Москва — столица России»	✅ Да	Истина (1)
«2 + 3 = 5»	✅ Да	Истина (1)
«10 > 20»	✅ Да	Ложь (0)
«Какой сегодня день?»	❌ Нет	Вопрос — не утверждение
«Откройте окно!»	❌ Нет	Побуждение — не утверждение
«x + 1 = 5»	⚠️ Зависит от x	Не является высказыванием, пока x не задано

Простые и сложные высказывания

Простое высказывание — содержит одну информацию, не раскладывается на составляющие (например, «5 > 3»).
Сложное высказывание — составлено из нескольких простых с помощью логических связок (например, «5 > 3 и 2 + 2 = 4»).

Логические связки: Слова «и», «или», «если…то», «не», которые соединяют простые высказывания в сложные. Именно они образуют основу математической логики.

Обозначения

В математической логике высказывания обозначаются заглавными латинскими буквами: A, B, C, …

Значения высказывания записываются числами:

1 (Истина, True) — высказывание верное.
0 (Ложь, False) — высказывание неверное.

Важно: Высказывание должно быть однозначным. Предложение «Прекрасная погода» — субъективное и не может быть строго истинным или ложным, поэтому оно не является высказыванием в математической логике.

Логические операции

Над высказываниями определены пять основных логических операций. Каждая из них принимает одно или два высказывания и выдаёт результат — новое высказывание.

1. Конъюнкция (И, AND, ∧)

A ∧ B («A и B») — истинна тогда и только тогда, когда оба высказывания истинны.

A	B	A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

Пример: «Сегодня понедельник и идёт дождь» — истинно только если оба утверждения верны.

2. Дизъюнкция (ИЛИ, OR, ∨)

A ∨ B («A или B») — истинна, когда хотя бы одно из высказываний истинно.

A	B	A ∨ B
0	0	0
0	1	1
1	0	1
1	1	1

Пример: «Можно купить хлеб или молоко» — достаточно, чтобы хотя бы один товар был куплен.

3. Инверсия (НЕ, NOT, ¬)

¬A («не A») — меняет значение высказывания на противоположное. Является унарной операцией (применяется к одному высказыванию).

A	¬A
0	1
1	0

Пример: Если «Зима» — ложь (сейчас лето), то «¬Зима» — истина.

4. Импликация (следование, →)

A → B («если A, то B») — ложна только в одном случае: когда A истинно, а B ложно. Во всех остальных случаях — истина.

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Почему 0 → 0 истинно? Высказывание «Если число чётное, то оно больше 100» — не является ложью для нечётного числа (условие не выполняется, значит следствие не нарушено).

Эквивалентность: A → B ≡ ¬A ∨ B. Это ключевое равенство для преобразования импликаций.

5. Исключающее ИЛИ (XOR, ⊕)

A ⊕ B — истинно, когда ровно одно из высказываний истинно (но не оба).

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Связь с другими операциями: A ⊕ B ≡ (A ∨ B) ∧ ¬(A ∧ B) — «либо A, либо B, но не одновременно».

Не путайте! Обычная дизъюнкция (OR) допускает «A и B одновременно», а исключающее ИЛИ (XOR) — нет. В повседневной рече «или» бываетboth видов, поэтому в математике их разделяют.

Таблицы истинности

Таблица истинности — это способ представить результат логической операции для всех возможных значений переменных. Для двух переменных A и B существует 2² = 4 комбинации значений.

Сводная таблица для всех пяти операций

A	B	A ∧ B (И)	A ∨ B (ИЛИ)	¬A (НЕ)	A → B (если…то)	A ⊕ B (XOR)
0	0	0	0	1	1	0
0	1	0	1	1	1	1
1	0	0	1	0	0	1
1	1	1	1	0	1	0

Приоритет логических операций

Порядок вычислений (от старшего к младшему):
1. ¬ (инверсия) — выполняется первой
2. ∧ (конъюнкция)
3. ∨ (дизъюнкция)
4. → (импликация) — выполняется последней

Пример: ¬A ∧ B читается как (¬A) ∧ B
Пример: A ∨ B → C читается как (A ∨ B) → C
            

Скобки меняют порядок вычислений. Выражение ¬(A ∧ B) отличается от ¬A ∧ B: сначала берётся конъюнкция A и B, а затем результат инвертируется.

Трёх переменных — пример

Для трёх переменных A, B, C таблица истинности содержит 2³ = 8 строк:

A	B	C	A ∧ B ∧ C
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Формула: Для n переменных число строк таблицы истинности равно 2ⁿ.

Законы алгебры логики

Законы алгебры логики позволяют упрощать и преобразовывать логические выражения. Они аналогичны законам арифметики, но работают с операциями ∧, ∨, ¬.

Основные законы

Закон	Формула	Аналогия
Тождественный элемент	A ∧ 1 = A, A ∨ 0 = A	Умножение на 1, сложение с 0
Нулевой элемент	A ∧ 0 = 0, A ∨ 1 = 1	Умножение на 0, сложение единиц
Переместительный	A ∧ B = B ∧ A, A ∨ B = B ∨ A	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 × (b + c) = a×b + a×c
Двойного отрицания	¬(¬A) = A	— (минус минус a) = a
Де Моргана	¬(A ∧ B) = ¬A ∨ ¬B ¬(A ∨ B) = ¬A ∧ ¬B	—
Поглощения	A ∨ (A ∧ B) = A A ∧ (A ∨ B) = A	—

Примеры преобразований

Пример 1: Упрощение ¬(A ∧ B) ∨ (¬A ∧ B)
  Шаг 1: Применим закон де Моргана:
    ¬(A ∧ B) = ¬A ∨ ¬B
  Шаг 2: Подставим:
    (¬A ∨ ¬B) ∨ (¬A ∧ B)
  Шаг 3: По переместительному закону:
    ¬A ∨ (¬B ∨ (¬A ∧ B))
  Шаг 4: По закону поглощения ¬B ∨ (¬A ∧ B) = ¬B ∨ ¬A:
    ¬A ∨ (¬B ∨ ¬A) = ¬A ∨ ¬B ∨ ¬A
  Шаг 5: По идемпотентности (A ∨ A = A):
    = ¬A ∨ ¬B
  Результат: ¬A ∨ ¬B (или ¬(A ∧ B) по де Моргану)
            

Пример 2: Преобразование A → B
  По определению: A → B ≡ ¬A ∨ B

  Проверим по таблице истинности:
  A=0, B=0: ¬0 ∨ 0 = 1 ∨ 0 = 1, A→B = 1  ✓
  A=0, B=1: ¬0 ∨ 1 = 1 ∨ 1 = 1, A→B = 1  ✓
  A=1, B=0: ¬1 ∨ 0 = 0 ∨ 0 = 0, A→B = 0  ✓
  A=1, B=1: ¬1 ∨ 1 = 0 ∨ 1 = 1, A→B = 1  ✓
            

Пример 3: Применение закона де Моргана
  Дано: ¬(A ∨ ¬B)
  По закону де Моргана: ¬(X ∨ Y) = ¬X ∧ ¬Y
  Подставим X=A, Y=¬B:
    ¬(A ∨ ¬B) = ¬A ∧ ¬(¬B) = ¬A ∧ B
            

Закон де Моргана — один из самых важных. Он связывает конъюнкцию с дизъюнкцией через отрицание и широко применяется при упрощении логических выражений и при работе с компьютерными запросами.

Логические элементы

Логические операции реализуются в компьютере с помощью электронных компонентов — логических элементов (вентилей). Каждый элемент принимает на вход сигналы (0 или 1) и выдаёт результат согласно таблице истинности.

Инвертор (НЕ-элемент, Inverter)

Схема:    A ──[ ¬ ]── Output

Таблица истинности:
  A  │  Output
  0  │    1
  1  │    0
            

Инвертор — самый простой логический элемент. Он имеет один вход и один выход. На выходе всегда противоположное значение входу.

Обозначение на схеме: треугольник с кружком на вершине.
Кружок означает инверсию (отрицание).
Применение: генерация противоположного сигнала, задержка, формирование тактовых импульсов.

И-элемент (AND-вентиль)

Схема:    A ──┐
              ├─[ & ]── Output
    B ──┘

Таблица истинности:
  A  │  B  │  Output
  0  │  0  │    0
  0  │  1  │    0
  1  │  0  │    0
  1  │  1  │    1
            

И-элемент имеет два (или более) входов и один выход. Выход равен 1 только тогда, когда все входы равны 1.

Обозначение: D-образная фигура (как буква D).
Микросхемы: 7408, CD4081.
Применение: разрешение сигнала (вход-строб), совпадение чисел в арифметико-логическом устройстве (АЛУ).

ИЛИ-элемент (OR-вентиль)

Схема:    A ──┐
              ├─[ ≥1 ]── Output
    B ──┘

Таблица истинности:
  A  │  B  │  Output
  0  │  0  │    0
  0  │  1  │    1
  1  │  0  │    1
  1  │  1  │    1
            

ИЛИ-элемент выдаёт 1, когда хотя бы один из входов равен 1.

Обозначение: фигурная скобка с выпуклой задней стороной.
Микросхемы: 7432, CD4071.
Применение: объединение сигналов прерываний, формирование управляющих сигналов.

Почему это важно для информатики?

Связь с темой 4.1: Компьютер работает с двоичными числами (0 и 1). Логические элементы обрабатывают эти числа на аппаратном уровне. Совокупность миллионов логических элементов образует процессор, память и другие устройства компьютера.

Запомните: Любая логическая функция может быть реализована с помощью комбинации И-элементов, ИЛИ-элементов и инверторов. Это называется базисом (complete set of gates).

Калькулятор логики

Калькулятор логических выражений

Выберите значения A и B, а затем логическую операцию. Результат вычисляется мгновенно.

A:

B:

Операция:

Практические задания

Задание 1. Определите логическую операцию

По таблице истинности определите, какая логическая операция соответствует:

A	B	Результат
0	0	1
0	1	1
1	0	1
1	1	0

Задание 2. Постройте таблицу истинности

Постройте таблицу истинности для выражения: (A ∨ B) ∧ ¬A

A	B	A ∨ B	¬A	(A ∨ B) ∧ ¬A
0	0	0	1	0
0	1	1	1	1
1	0	1	0	0
1	1	1	0	0

Задание 3. Упрощение по закону де Моргана

Упростите выражение ¬(¬A ∨ B), используя закон де Моргана и закон двойного отрицания.