Алгоритм построения, тавтологии, противоречия. Полный калькулятор формул.
Таблица истинности — это полный перебор всех возможных значений переменных. Для n переменных будет 2ⁿ строк. С ростом числа переменных таблица быстро растёт — это и есть сложность задач логики.
| 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 |
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.
Кванторы (∃, ∀) — логика «для всех» и «существует». Предикат — высказывание с переменной.
Предикат — это выражение с переменной, которое становится высказыванием (истинным или ложным) при подстановке конкретного значения.
Примеры предикатов:
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) — ложно (в действительных числах нет корня).
Отрицание «для всех» — «существует, для которого не». Отрицание «существует» — «для всех не».
«Не все студенты сдали экзамен» ≡ «Существует студент, который не сдал».
30 утверждений на быструю оценку
Стандартные формы: полная дизъюнктивная и полная конъюнктивная нормальные формы
СДНФ — это дизъюнкция (ИЛИ) конъюнкций (И) переменных. Каждая конъюнкция — элементарная конъюнкция (все переменные или с ¬, или без).
Строится по строкам таблицы, где F = 1.
СКНФ — это конъюнкция (И) дизъюнкций (ИЛИ) переменных.
Строится по строкам таблицы, где F = 0.
| 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)
| 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.
Визуальный метод минимизации булевых функций
Карта Карно — это таблица, в которой ячейки расположены так, что соседние отличаются всего в одном переменном. Это позволяет визуально «группировать» единицы и получить минимальную формулу.
Для 2 переменных (A, B) — карта 2×2. Для 3 переменных (A, B, C) — 2×4. Для 4 — 4×4.
| 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