Решать логические задачи очень увлекательно.
В них вроде бы нет никакой математики - нет ни чисел, ни функций, ни треугольников, ни векторов, а есть только лжецы и мудрецы, истина и ложь. В то же время дух математики в них чувствуется ярче всего - половина решения любой математической задачи (а иногда и гораздо больше половины) состоит в том, чтобы как следует разобраться в условии, распутать все связи между участвующими объектами.
Логические операции
|
1) Логическое умножение или конъюнкция: Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложенное выражение ложно. Обозначение: F = A & B. |
Таблица истинности для конъюнкции
|
|||||||||||||||
|
2) Логическое сложение или дизъюнкция: Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны. Обозначение: F = A v B. |
Таблица истинности для дизъюнкции
|
|||||||||||||||
|
3) Логическое отрицание или инверсия: Инверсия - это сложное логическое выражение. Если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими словами, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Обозначение: F = ¬A. |
Таблица истинности для инверсии
|
|||||||||||||||
|
4) Импликация или логическое следование: Импликация - это сложное логическое выражение, которое ложно тогда и только тогда когда из истины следует ложь. Обозначение: F = A → B. |
Таблица истинности для импликации
|
|||||||||||||||
|
5) Логическая равнозначность или эквивалентность: Эквивалентность - это сложное логическое выражение, которое является истинно тогда и только тогда, когда оба простых логических выражения истинны или оба ложны.«A ↔ B» истинно тогда и только тогда, когда А и B равны.
Обозначение: F = A ↔ B.
|
Таблица истинности для эквивалентности
|
|||||||||||||||
|
6) Строгая дизъюнкция (Исключающее ИЛИ, XOR)
«A ⊕ B» истинно тогда, когда истинно А или B, но не оба одновременно. Похоже на дизъюнкцию, но исключает одновременную истинность обоих высказываний.
Обозначение: F = A ⊕ B.
|
Таблица истинности для
строгой дизъюнкции
|
Порядок выполнения логических операций в сложном логическом выражении: инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность. Для изменения указанного порядка выполнения логических операций используются скобки.
ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Закон двойного отрицания ¬¬А = A
Законы для конъюнкции и дизъюнкции
| № | Конъюнкция(V) | Дизъюнкция (&) | Законы логики |
| 1 | A \/ 0 = A | A & 1 = A | Законы операций с 0 и 1 |
| 2 | A \/ 1 = 1 | A & 0 = 0 | Законы операций с 0 и 1 |
| 3 | A \/ B = B \/ A | A & B = B & A | Переместительный (коммутативности) |
| 4 | A \/ ¬A = 1 |
Закон исключения третьего
|
|
| 5 | A & ¬A = 0 |
Закон непротиворечия
|
|
| 6 | A \/ A = A | A & A = A | Закон повторения |
| 7 | (A \/ B) \/ C = A \/ (B \/ C) | (A & B) & C = A & (B & C) | Ассоциативный закон |
| 8 | (A \/ B)&C=(A&C)\/(B&C) | (A&B) \/ C = (A \/ C)&(B \/ C) | Дистрибутивный закон |
| 9 | (A \/ B)&(¬A \/ B) = B | (A&B) \/ (¬A&B) = B | Склеивания |
| 10 | ¬(A \/ B) = ¬A &¬B | ¬(A&B) = ¬A \/ ¬B | Правило де Моргана |
| 11 | A \/ (A&C) = A | A&(A \/ C) = A | Поглощения |
Законы для импликации и эквиваленции
| Импликация (→) | Эквиваленция (↔) | Исключающее ИЛИ (⊕) |
| A → B = (¬B) → ¬A |
A ↔ B = (A → B) & (B → A) | A ⊕ B = (A v B) & ((¬A) v ¬B) |
| A → B = (¬A) v B | A ↔ B = (A & B) v ((¬A) &¬B) |
A ⊕ B = (A &¬B) v ((¬A) & B) |
| ¬(A → B) = A & ¬B | A ↔ B = (A v¬B) & ((¬A) v B) |
A ⊕ B = ¬(A ↔ B) |
Таблицы истинности
Таблицы истинности можно составить для произвольной логической функции F(a, b, c…). В общем случае таблицы истинности имеют размер 2N строк комбинаций для N независимых логических переменных. Поскольку таблица истинности выражения состоит из строк со всеми возможными комбинациями значений переменных, она полностью определяет значение выражения.
