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

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 15 · страница 15.2
Таблицы истинности
Алгоритм построения, тавтологии, противоречия. Полный калькулятор формул.
Таблица истинности — это
полный перебор
всех возможных значений переменных. Для n переменных будет 2ⁿ строк. С ростом числа переменных таблица быстро растёт — это и есть сложность задач логики.
ФГОС
ФОП
ОГЭ №3
ЕГЭ №2
01
Алгоритм построения
Подсчитать n
— число различных переменных в формуле.
Число строк = 2ⁿ.
Например, для 3 переменных — 8 строк.
Выписать столбцы
для каждой переменной (все 2ⁿ комбинаций).
Добавить столбцы
для каждой подформулы (по приоритету операций).
Заполнить
по правилам операций (∧, ∨, ¬, →, ↔).
Пример: построить таблицу для (A∨B)→¬A
A
B
A∨B
¬A
(A∨B)→¬A
0
0
0
1
1
0
1
1
1
1
1
0
1
0
0
1
1
1
0
0
Размер таблицы
Уже при 5 переменных таблица содержит 32 строки. При 10 — 1024. При 20 — миллион. Для сложных формул используют специальные методы (карты Карно, Квайна) — глава 27.
02
Тавтологии, противоречия, выполнимость
Тавтология (тождественно истинная)
F = 1 при
всех
наборах переменных.
Примеры: A∨¬A, A→A, A↔A, (A→B)↔(¬B→¬A).
Противоречие (тождественно ложное)
F = 0 при
всех
наборах.
Примеры: A∧¬A, (A∧B)∧(¬A∨¬B), A↔¬A.
Выполнимая (не тавтология, не противоречие)
F = 1 хотя бы для одного набора и F = 0 хотя бы для одного.
Примеры: A∧B, A→B, A⊕B.
03
Кванторы и предикаты
Кванторы (∃, ∀) — логика «для всех» и «существует». Предикат — высказывание с переменной.
Предикат
Предикат
— это выражение с переменной, которое становится высказыванием (истинным или ложным) при подстановке конкретного значения.
Примеры предикатов:
P(x): x > 5
— при x=7 истинно, при x=3 ложно
Q(n): n делится на 2
— при n=4 истинно, при n=7 ложно
R(a,b): a + b = 10
— при a=3,b=7 истинно
Квантор всеобщности ∀
∀x P(x)
читается «для всех x выполняется P(x)». Истинен, когда P(x) истинно для
каждого
элемента области определения.
Пример
Область: натуральные числа. ∀x (x > 0) —
истинно
(все натуральные положительны).
∀x (x² > x) —
ложно
(при x=1: 1² = 1, не строго больше).
Квантор существования ∃
∃x P(x)
читается «существует x, для которого P(x)». Истинен, когда
хотя бы один
элемент удовлетворяет P(x).
Пример
Область: целые числа. ∃x (x² = 16) —
истинно
(x=4 или x=−4).
∃x (x² = −1) —
ложно
(в действительных числах нет корня).
Отрицание кванторов
¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)
Отрицание «для всех» — «существует, для которого не». Отрицание «существует» — «для всех не».
Пример
«Не все студенты сдали экзамен» ≡ «Существует студент, который не сдал».
Для ЕГЭ №15
Задачи на кванторы — типичная тема ЕГЭ №15. Умение отрицать кванторные высказывания — ключевой навык. Помни: отрицание ∀ → ∃ (и наоборот), при этом предикат отрицается.
🔍
Проверщик кванторных высказываний
Введи предикат и область — получи проверку ∀ и ∃ с подробным разбором
Область (через запятую)
Условие P(x) на JS
Нажми «Проверить» или выбери пресет.
05
Истина/Ложь марафон
30 утверждений на быструю оценку
⚡
Марафон: высказывание или нет?
0/0
06
СДНФ и СКНФ
Стандартные формы: полная дизъюнктивная и полная конъюнктивная нормальные формы
СДНФ (Стандартная Дизъюнктивная Нормальная Форма)
СДНФ
— это дизъюнкция (ИЛИ) конъюнкций (И) переменных. Каждая конъюнкция —
элементарная конъюнкция
(все переменные или с ¬, или без).
Строится по строкам таблицы, где
F = 1
.
Находим все строки, где F = 1
Для каждой строки пишем конъюнкцию: если переменная = 1 → берём её как есть, если = 0 → с отрицанием
Соединяем все конъюнкции через ∨
СКНФ (Стандартная Конъюнктивная Нормальная Форма)
СКНФ
— это конъюнкция (И) дизъюнкций (ИЛИ) переменных.
Строится по строкам таблицы, где
F = 0
.
Находим все строки, где F = 0
Для каждой строки пишем дизъюнкцию: если переменная = 0 → берём её как есть, если = 1 → с отрицанием
Соединяем все дизъюнкции через ∧
Пример 1: A ⊕ B (XOR)
A
B
A⊕B
0
0
0
0
1
1
1
0
1
1
1
0
СДНФ
(строки F=1): (¬A∧B) ∨ (A∧¬B)
СКНФ
(строки F=0): (A∨B) ∧ (¬A∨¬B)
Пример 2: A→B (Импликация)
A
B
A→B
0
0
1
0
1
1
1
0
0
1
1
1
СДНФ
(F=1): (¬A∧¬B) ∨ (¬A∧B) ∨ (A∧B) =
¬A ∨ B
СКНФ
(F=0): (A∨¬B)
Обрати внимание: СДНФ можно упростить — ¬A∧¬B и ¬A∧B объединяются в ¬A, а ¬A∧B и A∧B — в B.
Зачем это нужно?
СДНФ и СКНФ используются для: доказательства эквивалентности формул (две формулы равны, если у них одинаковые СДНФ), классификации (таутология если СКНФ пуста, противоречие если СДНФ пуста), перевода между формами (СКНФ → СДНФ через закон де Моргана). В ЕГЭ часто встречаются задачи на построение СДНФ/СКНФ по таблице истинности.
07
Карты Карно
Визуальный метод минимизации булевых функций
Что такое карта Карно?
Карта Карно
— это таблица, в которой ячейки расположены так, что соседние отличаются всего в одном переменном. Это позволяет визуально «группировать» единицы и получить минимальную формулу.
Для 2 переменных (A, B) — карта 2×2. Для 3 переменных (A, B, C) — 2×4. Для 4 — 4×4.
Алгоритм минимизации
Заполняем карту значениями функции (0 или 1)
Группируем смежные единицы в прямоугольники размером 2ⁿ (1, 2, 4, 8)
Группы не должны пересекаться, но могут накладываться
Каждая группа даёт один слагаемый в минимизированной формуле
Переменная, которая меняется внутри группы — исчезает
Пример: F = A∨(¬A∧B) = A∨B
B=0
B=1
A=0
0
1
A=1
1
1
Группа 1: (A=1, B=0) + (A=1, B=1) →
A
(B меняется)
Группа 2: (A=0, B=1) + (A=1, B=1) →
B
(A меняется)
Результат:
F = A ∨ B
🗺️
Интерактивная карта Карно
Введи формулу или заполни ячейки вручную — получи минимизацию
Введи формулу из 2 переменных (A, B) в поле ниже и нажми «Построить»
Или заполни ячейки вручную — нажимай на ячейки карты, переключая 0/1
Нажми «Примеры» для случайной формулы
Карта покажет группы единиц и минимизированную формулу
Формула (2 переменных: A, B)
B=0
B=1
A=0
0
0
A=1
0
0
Нажми на ячейку, чтобы переключить 0/1