Импликация

Импликация
Не больше, IMPLY
Диаграмма Венна
Определение	${\displaystyle x\rightarrow y}$
Таблица истинности	${\displaystyle (1101)}$
Логический вентиль
Нормальные формы
Дизъюнктивная	${\displaystyle {\overline {x}}+y}$
Конъюнктивная	${\displaystyle {\overline {x}}+y}$
Полином Жегалкина	${\displaystyle 1\oplus x\oplus xy}$
Принадлежность предполным классам
Сохраняет 0	Нет
Сохраняет 1	Да
Монотонна	Нет
Линейна	Нет
Самодвойственна	Нет

Импликация (от лат. implicatio — «связь») — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…».

Импликация записывается как посылка ${\displaystyle \Rightarrow }$ следствие; применяются также стрелки другой формы и направленные в другую сторону, но всегда указывающие на следствие.

Суждение, выражаемое импликацией, выражается также следующими способами^[1][2]:

• посылка является условием, достаточным для выполнения следствия;
• следствие является условием, необходимым для истинности посылки.

Импликация играет очень важную роль в умозаключениях. С её помощью формулируются определения различных понятий, теоремы, научные законы^[3].

При учёте смыслового содержания высказываний импликация подразумевает причинную связь между посылкой и заключением^[4]:.

Булева логика

В булевой логике импликация — это функция двух переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества ${\displaystyle \{0,1\}}$. Результат также принадлежит множеству ${\displaystyle \{0,1\}}$. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ${\displaystyle 0,1}$ может использоваться любая другая пара подходящих символов, например ${\displaystyle false,true}$ или ${\displaystyle F,T}$ или «ложь», «истина».
Правило:
Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно. Иными словами, импликация ${\displaystyle A\to B}$ — это сокращённая запись для выражения ${\displaystyle \neg A\lor B}$.
Таблицы истинности:
прямая импликация (от a к b) (материальная импликация (англ.)русск., материальный кондиционал (англ.)русск.)

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle a\to b,a\leqslant b}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$

если первый операнд не больше второго операнда, то 1,
если ${\displaystyle a\leqslant b}$, то истинно (1),

«Житейский» смысл импликации. Для более лёгкого понимания смысла прямой импликации и запоминания её таблицы истинности может пригодиться житейская модель: А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация — не что иное, как послушание подчиненного начальнику. По таблице истинности легко проверить, что послушания нет только тогда, когда начальник приказывает работать, а подчиненный бездельничает.

обратная импликация (англ.)русск. (от b к a, ${\displaystyle A\lor (\neg B)}$)

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle a\leftarrow b,a\geqslant b}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$

если первый операнд не меньше второго операнда, то 1,
если ${\displaystyle a\geqslant b}$, то истинно (1),
обратная импликация — отрицание (негация, инверсия) обнаружения увеличения (перехода от 0 к 1, инкремента).

отрицание (инверсия, негация) прямой импликации

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle \lnot (a\to b),a>b}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 0}$

если первый операнд больше второго операнда, то 1,
если ${\displaystyle a>b}$, то истинно (1).

отрицание (инверсия, негация) обратной импликации (англ.)русск. (${\displaystyle \lnot A\land B}$),
разряд займа в двоичном полувычитателе,

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle \lnot (a\leftarrow b),a<b}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 0}$

если первый операнд меньше второго операнда, то 1,
если ${\displaystyle a<b}$, то истинно (1).

Другими словами, две импликации (прямая и обратная) и две их инверсии — это четыре оператора отношений. Результат операций зависит от перемены мест операндов.

Синонимические импликации выражения в русском языке

• Если А, то Б
• Б в том случае, если А
• При А будет Б
• Из А следует Б
• В случае А произойдет Б
• Б, так как А
• Б, потому что А
• А — достаточное условие для Б
• Б — необходимое условие для А

Многозначная логика

Теория множеств

Импликация высказываний означает, что одно из них следует из другого. Импликация обозначается символом ${\displaystyle \Rightarrow }$, и ей соответствует вложение множеств: пусть ${\displaystyle A\subset B}$, тогда

${\displaystyle x\in A\Rightarrow x\in B}$.

Например, если ${\displaystyle A}$ — множество всех квадратов, а ${\displaystyle B}$ — множество прямоугольников, то, конечно, ${\displaystyle A\subset B}$ и

(a — квадрат) ${\displaystyle \Rightarrow }$ (a — прямоугольник).

(если a является квадратом, то a является прямоугольником).

Классическая логика

В классическом исчислении высказываний свойства импликации определяются с помощью аксиом.

Можно доказать эквивалентность импликации ${\displaystyle A\rightarrow B}$ формуле ${\displaystyle \neg A\lor B}$ (с первого взгляда более очевидна её эквивалентность формуле ${\displaystyle \neg (A\land \neg B)}$, которая принимает значение «ложь» в случае, если выполняется A (посылка), но не выполняется B (следствие)).

Интуиционистская логика

В интуиционистской логике импликация никоим образом не сводится к отрицаниям. Скорее напротив, отрицание ¬A можно представить в виде ${\displaystyle A\rightarrow \nvDash }$, где ${\displaystyle \nvDash }$ — пропозициональная константа «ложь». Впрочем, такое представление отрицания возможно и в классической логике.

В интуиционистской теории типов импликации соответствует множество (тип) отображений из A в B.

Логика силлогизмов

В учении о силлогизмах импликации отвечает «общеутвердительное атрибутивное высказывание».

Программирование

В языках программирования импликация используется, как правило, неявно. Например, конструкция, предполагающая истинность условия B в данном участке программы:

 if ( выражение A ) {
    if ( выражение B ) {
       сделать_что-то_полезное
    }
       else {
       <font color=Red>сбой</font>
    };
 }

будет успешно выполняться тогда и только тогда, когда верна импликация A→B. В то же время эти условия можно спокойно написать в одной строке, объединив их оператором конъюнкции.

 if ( выражение A ) and ( выражение B ) {
    сделать_что-то_полезное
 }

При стандартных опциях компилятора (Delphi, C++ Builder) проверка идет до тех пор, пока результат не станет очевидным, и если А ложно, то (А и В) ложно вне зависимости от В, и не нужно ставить еще один условный оператор.

 //выражение A - ложно
 if ( выражение A ) {
    //Дальше проверка не идет
    ... if ( выражение B ) {
       сделать_что-то_полезное
    } ...
 }

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

Ссылки

• Импликация и эквивалентность

Примечания

Литература

• Эдельман С.Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.
• Игошин В.И. Задачник-практикум по математической логике. — М.: Просвещение, 1986. — 158 с.
• Гиндикин С.Г. Алгебра логики в задачах. — М.: Наука, 1972. — 288 с.