Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
(перенаправлено с «Бинарная операция»)
Перейти к навигации Перейти к поиску
Информатика. Выпуск 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).

Штрих Шеффера[править]

Записывается обычно как «|»

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

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


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

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

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

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

 
Формальная

Логические операции с понятиями


Изменение содержания понятия: отрицаниеограничениеобобщениеделение
Изменение объёма понятия: сложениеумножениевычитание
Типы: Многозначная логикаБинарная логика
Законы: Закон обратного отношения между содержанием и объёмом понятия

Математическая
(теоретическая,
символическая)

Логические связки (операции) над высказываниями


Высказывание - построение над множеством {B, , , , 0, 1}
В - непустое множество, над элементами которого определены три базовые операции: конъюнкция ( или &,бинарная) • дизъюнкция (,бинарная) • отрицание (,унарная)
2 константы: 01

См. также

импликация () • Круги Эйлера/Диаграмма ВеннаПолилогизмТеория множеств