Необходимость и достаточность - Necessity and sufficiency

В логике и математике , необходимости и достаточности термины , используемая для описания условных или импликационных отношений между два отчетностью . Например, в условном утверждении: «Если P, то Q », Q необходимо для P, потому что истинность Q гарантируется истинностью P (эквивалентно, невозможно иметь P без Q ). Точно так же P достаточно для Q, потому что истинность P всегда означает, что Q истинно, но не истинность P не всегда означает, что Q не истинно.

В общем, необходимое условие - это то, которое должно присутствовать, чтобы возникло другое условие, в то время как достаточное условие - это то, которое порождает указанное условие. Утверждение, что высказывание является «необходимым и достаточным» условием другого, означает, что первое утверждение истинно тогда и только тогда, когда истинно второе. То есть два утверждения должны быть либо одновременно истинными, либо одновременно ложными.

В обычном английском языке «необходимо» и «достаточно» обозначают отношения между условиями или положениями дел, а не утверждения. Например, принадлежность к мужскому полу является необходимым условием для того, чтобы быть братом, но этого недостаточно, в то время как принадлежность к мужскому полу является необходимым и достаточным условием для того, чтобы быть братом. Любое условное утверждение состоит хотя бы из одного достаточного и хотя бы одного необходимого.

Определения

В условном выражении «если S , то N » выражение, представленное S , называется антецедентом , а выражение, представленным N , называется консеквентом . Это условное выражение может быть записано несколькими эквивалентными способами, такими как « N, если S », « S, только если N », « S подразумевает N », « N подразумевается из S », SN , SN и « N». всякий раз, когда S ".

В приведенной выше ситуации, Н называется быть необходимым условием для S . На обычном языке это эквивалентно утверждению, что если условное утверждение является истинным утверждением, то консеквент N должен быть истинным - если S должно быть истинным (см. Третий столбец « таблицы истинности » непосредственно ниже). Другими словами, антецедент S не может быть истинным, если N не является истинным. Например, для кого - то в порядке , чтобы называться S ocrates, это нужно для того чтобы кто - то N AMED. Точно так же, чтобы люди могли жить, у них должен быть воздух.

В приведенной выше ситуации можно также сказать, что S является достаточным условием для N (снова обратитесь к третьему столбцу таблицы истинности непосредственно ниже). Если условное утверждение истинно, то если S истинно, N должно быть истинным; тогда как если условное утверждение истинно, а N истинно, то S может быть истинным или ложным. Проще говоря, «истинность S гарантирует истинность N ». Например, продолжая из предыдущего примера, можно сказать , что , зная , что кто - то называется S ocrates достаточно знать , что кто - то имеет N AME.

Необходимое и достаточное условие требует, чтобы оба из последствий и (последние из которых также может быть записана в виде ) удержания. Первый вывод предполагает , что S является достаточным условием N , в то время как второй вывод предполагает , что S является необходимым условием для N . Это выражается как « S необходимо и достаточно для N », « S тогда и только тогда, когда N » или .

Таблица истинности
S N
Т Т Т Т Т
Т F F Т F
F Т Т F F
F F Т Т Т

Необходимость

Нахождение солнца над горизонтом - необходимое условие попадания прямых солнечных лучей; но это не достаточное условие, поскольку что-то еще может отбрасывать тень, например, луна в случае затмения .

Утверждение, что Q необходимо для P, в просторечии эквивалентно « P не может быть истинным, если Q не истинно» или «если Q ложно, то P ложно». По контрасту , это то же самое, что «всякий раз, когда P истинно, Q истинно ».

Логическая связь между P и Q выражается как «если P , то Q » и обозначается « PQ » ( P подразумевает Q ). Он также может быть выражен как любое из « P, только если Q », « Q , если P », « Q, если P » и « Q, когда P ». В математической прозе часто можно найти, например, несколько необходимых условий, которые вместе взятые составляют достаточное условие (т. Е. Индивидуально необходимые и совместно достаточные), как показано в примере 5.

Пример 1
Чтобы было правдой то, что «Джон холостяк», необходимо, чтобы также было правдой то, что он
  1. Незамужняя,
  2. мужчина,
  3. взрослый
поскольку утверждение «Джон - холостяк» подразумевает, что у Джона есть каждый из этих трех дополнительных предикатов .
Пример 2
Для целых чисел больше двух, чтобы быть простым, необходимо быть нечетным, поскольку два - единственное целое число, которое одновременно является четным и простым.
Пример 3
Рассмотрим гром, звук, вызванный молнией. Говорят, что гром необходим для молнии, так как молния никогда не возникает без грома. Когда есть молния, всегда бывает гром. Гром не вызывает молнии (поскольку молния вызывает гром), но поскольку молния всегда приходит с громом, мы говорим, что гром необходим для молнии. (То есть в формальном смысле необходимость не предполагает причинности.)
Пример 4
Для работы в Сенате США необходимо быть не моложе 30 лет. Если вам меньше 30 лет, то вы не можете быть сенатором. То есть, если вы сенатор, значит, вам должно быть не менее 30 лет.
Пример 5
В алгебре для некоторого множества S вместе с операцией по формированию группы необходимо, чтобы оно было ассоциативным . Также необходимо, чтобы S содержал специальный элемент e, такой, чтобы для каждого x в S было то, что оба e x и x e равны x . Также необходимо, чтобы для каждого x в S существовал соответствующий элемент x ″ , такой, что оба x x ″ и x ″ x равны специальному элементу e . Ни одно из этих трех необходимых условий само по себе не является достаточным, но достаточно их сочетания .

Достаточность

То, что поезд ходит по расписанию, может быть достаточным условием для своевременного прибытия (если кто-то садится в поезд и он отправляется вовремя, то он прибудет вовремя); но это не всегда является необходимым условием, поскольку есть другие способы передвижения (если поезд не успеет вовремя, все равно можно прибыть вовремя другим видом транспорта).

Если P достаточно для Q , то знание того, что P истинно, является достаточным основанием для заключения, что Q истинно; однако знание того, что P ложно, не отвечает минимальной необходимости сделать вывод, что Q ложно.

Логическая связь, как и раньше, выражается как «если P , то Q » или « PQ ». Это также может быть выражено как « P, только если Q », « P подразумевает Q » или несколько других вариантов. Может случиться так, что несколько достаточных условий, взятые вместе, образуют одно необходимое условие (то есть индивидуально достаточное и совместно необходимое), как показано в примере 5.

Пример 1
«Джон - король» подразумевает, что Джон - мужчина. Итак, зная, что Иоанн - король, достаточно знать, что он мужчина.
Пример 2
Делящегося числа на 4 достаточно (но не обязательно), чтобы оно было четным, но деление числа на 2 одновременно и достаточно, и необходимо.
Пример 3
Возникновение грома является достаточным условием для возникновения молнии в том смысле, что слышание грома и однозначное признание его как такового оправдывает заключение о том, что это была молния.
Пример 4
Если Конгресс США примет законопроект, его подписания президентом будет достаточно, чтобы он стал законом. Обратите внимание, что случай, когда президент не подписал законопроект, например, применив президентское вето , не означает, что закон не стал законом (например, он все еще мог стать законом в результате отмены Конгресса ).
Пример 5
То, что центр игральной карты должен быть отмечен одной большой лопатой (♠), достаточно для того, чтобы карта была тузом. Три других достаточных условия: центр карты должен быть отмечен одним ромбом (♦), сердечком (♥) или булавой (♣). Ни одно из этих условий не является обязательным для того, чтобы карта была тузом, но их разъединение необходимо , поскольку никакая карта не может быть тузом без выполнения хотя бы (фактически, точно) одного из этих условий.

Взаимосвязь между необходимостью и достаточностью

Находиться в фиолетовой области достаточно, чтобы быть в А, но не обязательно. Пребывание в A необходимо для того, чтобы находиться в фиолетовой области, но этого недостаточно. Пребывание в А и в Б необходимо и достаточно для пребывания в фиолетовой области.

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

Условие может быть как необходимым, так и достаточным. Например, в настоящее время «сегодня четвертое июля » является необходимым и достаточным условием для того, чтобы «сегодня в США День независимости ». Аналогичным образом , необходимое и достаточное условие обратимости в виде матрицы М , что М имеет ненулевой определитель .

С математической точки зрения необходимость и достаточность двойственны друг другу. Для любых утверждений S и N утверждение, что « N необходимо для S », эквивалентно утверждению « S достаточно для N ». Другой аспект этой двойственности состоит в том, что, как проиллюстрировано выше, соединения (с использованием «и») необходимых условий могут достигать достаточности, в то время как дизъюнкции (с использованием «или») достаточных условий могут достигать необходимости. Для третьего аспекта идентифицируйте каждый математический предикат N с набором T ( N ) объектов, событий или утверждений, для которых N выполняется; то утверждать о необходимости N для S эквивалентно утверждают , что Т ( Н ) является подмножеством из T ( S ), в то время как утверждать достаточность S для N эквивалентно утверждают , что Т ( S ) представляет собой подмножество из T ( N ).

Одновременная необходимость и достаточность

Сказать, что P необходимо и достаточно для Q, значит сказать две вещи:

  1. что Р является необходимым для Q , и что Р является достаточным для Q , .
  2. эквивалентно, можно понять, что P и Q необходимы для другого , что также может быть указано, поскольку каждое из них является достаточным для другого или подразумевает другое.

Любой, а значит, и все эти случаи можно резюмировать утверждением « P тогда и только тогда, когда Q », которое обозначается , тогда как случаи говорят нам, что это идентично .

Например, в теории графов граф G называется двудольным, если каждой его вершине можно присвоить черный или белый цвет таким образом, чтобы каждое ребро G имело по одной конечной точке каждого цвета. А для того, чтобы любой граф был двудольным, необходимо и достаточно, чтобы он не содержал циклов нечетной длины . Таким образом, обнаружение нечетных циклов в графе говорит о том, является ли он двудольным и наоборот. Философ может характеризовать это положение дел следующим образом: «Хотя понятия bipartiteness и отсутствие нечетных циклов отличаются интенсионалом , они имеют одинаковое расширение .

В математике теоремы часто формулируются в форме « P истинно тогда и только тогда, когда Q истинно». Их доказательства обычно сначала доказывают достаточность, например . Во-вторых, доказано обратное,

  1. либо напрямую, предполагая, что Q истинно и демонстрируя, что круг Q расположен внутри P, либо
  2. наоборот , это демонстрирует, что, выйдя за пределы круга P, мы выпадаем Q : если предположить, что не P, не Q результатов .

Это доказывает, что круги для Q и P совпадают на диаграммах Венна выше.

Потому что, как описано в предыдущем разделе, необходимость одного для другого эквивалентна достаточности других для первого, например , это равносильно , если Р является необходимым и достаточным для Q , то Q является необходимым и достаточным для P . Мы можем написать и сказать, что утверждения « P истинно тогда и только тогда , когда Q истинно» и « Q истинно тогда и только тогда, когда P истинно» эквивалентны.

Смотрите также

использованная литература

внешние ссылки