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

Материал из Циклопедии
Перейти к: навигация, поиск
Информатика. Выпуск 6. Алгебра логики. Основные логические операции. Ведущая - Меркушева Людмила Владимировна, ассистент кафедры информационных систем и технологий МГИУ // LiveMSIU
Лекция: Основы алгебры логики - Логические операции // NAUCHI.ru

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

В классической логике высказываний логические операции — это отрицание, конъюнкция, дизъюнкция, импликация, в таком порядке выполнения. В теории множеств этим базовым логическим операциям соответствуют операции над множествами. В логике предикатов конъюнкции соответствует квантор всеобщности, дизъюнкции — квантор существования.

В традиционной нотации логическим операциям назначают собственные знаки-символы: унарная операция отрицания префиксным зна́ком ¬, бинарные операции и, или и влечёт — инфиксными знаками ∧, ∨ и →, соответственно. Атомарные (аксиоматически задаваемые) высказывания обозначаются знаками-константами, — заглавными или строчными латинскими буквами: например, A, B, p.

При помощи такой нотации записываются логические законы, например свойство ассоциативности дизъюнкции: ((a∨b)∨c) ⇔(a∨(b∨c)). Законы де Моргана: ¬(a∧b)=¬a∨¬b, ¬(a∨b)=¬a∧¬b.

Результат вычисления каждой операции в логике высказываний равен константам ⊤ (1, истинно) и ⊥ (0, ложно).

Для каждой операции может быть составлена таблица истинности, показывающая, какое значение будет возвращать операция при тех или иных значениях операндов. Обычно таблицы составляются для бинарных операций (количество операндов равно двум), но может быть составлена и для сколь угодно сложного выражения.

Содержание

[править] Основные операции

[править] Конъюнкция

Логическое умножение, выражение «AND», обозначается знаком «∧».

Таблица истинности для пары операндов — 1000. Конъюнкция возвращает 1 только тогда, когда оба операнда равны 1, иначе 0.

[править] Дизъюнкция

Логическое сложение, выражение «OR», обозначается знаком «⋁». Также называется «слабой дизъюнкцией».

Таблица истинности для пары операндов — 1110. Возвращает 0 только тогда, когда оба операнда равны 0, иначе 1.

[править] Отрицание

Инверсия, негация, выражение «NOT», обозначается знаком «¬».

Возвращает противоположный знак: для 0 — 1, для 1 — 0.

[править] Второстепенные операции

[править] Сильная дизъюнкция

Исключающая дизъюнкция, выражение «XOR», обозначается символами «⊻» или «⊕».

Таблица истинности для пары операндов — 0110. Возвращает 1 только тогда, когда только один из них равен 1, а второй равен 0.

Может быть определена через основные операции: (A ⊻ B) = ((A ∧ ¬ B) ⋁ (¬ A ∧ B)).

[править] Эквивалентность

Тождество, равенство, выражение «EQ», обозначается символами «↔», «⇔» или «≡».

Таблица истинности для пары операндов — 1001. Возвращает 1 только тогда, когда оба операнда равны одновременно 0 или 1.

Может быть определена через основные операции: (A ⇔ B) = ((A ∧ B) ⋁ (¬ A ∧ ¬ B)).

[править] Выражение «НЕ-ИЛИ»

Иначе стрелка Пирса, выражение «NOR», обозначается символом «↓».

Таблица истинности для пары операндов — 0001. Возвращает 1 только тогда, когда оба операнда одновременно равны 0.

Может быть определена через основные операции: (A ↓ B) = (¬ A ∧ ¬ B)

Также через NOR могут быть определены основные логические функции.

[править] Импликация

Выражает зависимость причины и следствия, обозначается символами «⇒», «→» или «⊃».

Таблица истинности для пары операндов — 1011. То есть возвращает ложь только тогда, когда первый операнд равен 1, а второй — 0.

Может быть определена через основные операции: (A → B) = (¬ A ⋁ B).

[править] Базовая логика в программировании

Формальная логика широко применяется в алгоритмических языках, например языках программирования. В них широко применяются условные выражения if-then-else, в блоке if которых вычисляется истинность логического выражения (например простейшее выражение вроде $var1 == 5 && !$var2 эквивалентно логическому выражению A ∧ ¬ B, при A: «$var1 == 5» и B: «$var2 определено и имеет ненулевое значение»). В языках программирования (основанных на Си) приняты обозначения:

  • && — конъюнкция,
  • || — дизъюнкция,
  •  ! — отрицание,
  • == — эквиваленция.

[править] См. также

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты