Теория:
Как мы уже определили, истинность или ложность составных высказываний определяется алгеброй высказываний.
Обрати внимание!
Вводят замену: вместо простых высказываний используют логические переменные (\(A\), \(B\), \(C\), \(D\) и так далее); значения истинных высказываний обозначают \(1\), ложных высказываний — \(0\).
Математический аппарат алгебры логики имеет широкое применение: при проектировании ЭВМ, в теории автоматов, в теории алгоритмов, в теории информации, в целочисленном программировании.
Логические операции
В \(8\)-м классе были изучены основные логические операции: конъюнкция, дизъюнкция, инверсия. Напомним определения и таблицы истинностей для этих операций.
1. Конъюнкция (логическое умножение)
Обозначение: .
Таблица истинности
\(A\) | \(B\) | \(F\) |
\(0\) | \(0\) | \(0\) |
\(0\) | \(1\) | \(0\) |
\(1\) | \(0\) | \(0\) |
\(1\) | \(1\) | \(1\) |
2. Дизъюнкция (логическое сложение)
Обозначение: .
Таблица истинности
\(A\) | \(B\) | \(F\) |
\(0\) | \(0\) | \(0\) |
\(0\) | \(1\) | \(1\) |
\(1\) | \(0\) | \(1\) |
\(1\) | \(1\) | \(1\) |
3. Инверсия (логическое отрицание)
Обозначение: .
Таблица истинности
\(A\) | \(F\) |
\(0\) | \(1\) |
\(1\) | \(0\) |
Дополним и другими логическими операциями.
4. Импликация (логическое следование)
Импликация — сложное логическое выражение, истинное всегда, кроме как из истины следует ложь.
«» истинно, когда из \(A\) может следовать \(B\).
Обозначение: .
Таблица истинности
\(A\) | \(B\) | \(F\) |
\(0\) | \(0\) | \(1\) |
\(0\) | \(1\) | \(1\) |
\(1\) | \(0\) | \(0\) |
\(1\) | \(1\) | \(1\) |
5. Эквивалентность (логическая равнозначность)
Эквивалентность — сложное логическое выражение, является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
«» истинно, если \(A\) и \(B\) равны.
Обозначение: .
Таблица истинности
\(A\) | \(B\) | \(F\) |
\(0\) | \(0\) | \(1\) |
\(0\) | \(1\) | \(0\) |
\(1\) | \(0\) | \(0\) |
\(1\) | \(1\) | \(1\) |
6. Исключающее «или» (операция XOR; сложение по модулю \(2\))
«» истинно, если истинно \(А\) или \(В\), но не оба одновременно.
Обозначение: .
Таблица истинности
\(A\) | \(B\) | \(F\) |
\(0\) | \(0\) | \(0\) |
\(0\) | \(1\) | \(1\) |
\(1\) | \(0\) | \(1\) |
\(1\) | \(1\) | \(0\) |
В сложном логическом выражении существует определённый порядок действий:
- инверсия;
- конъюнкция;
- дизъюнкция;
- импликация;
- эквивалентность.