Необходимость и достаточность против обоснованности и полноты

Question

Я пытаюсь выучить доказательства. Я сталкивался с этими 4 терминами. Я пытаюсь связать все.

A: X>Y B: Y<X

Necessary Condition 
             B implies A
Sufficient Condition 
             A implies B

А также

A = { set of statements}  Q= a statement

Soundness 
        if A derives Q then A is a logical consequence of Q
Completeness
         if A is a logical consequence of Q then A derives Q.

Какая связь между всеми? Помощь приветствуется.

Answer 1

Необходимое / достаточное не имеет ничего общего с разумностью и полнотой, поэтому я объясню эти два понятия отдельно.

Необходимо / достаточно:

В вашем примере два утверждения эквивалентны: X>Y если и только если Y<X, Так что это действительно так B подразумевает A а также A подразумевает B, Возможно, лучшим примером будет:

A: X>Y+1
B: X>Y

Вот A будет означать, Bт.е. A будет достаточно для B держать. Другой способ не выдержал бы: B не подразумевает A (так как вы могли бы иметь X=10 а также Y=9 только в этом случае B будет держать). Это означает, что A не нужно для B,

---

Комплектность / обоснованность:

Мне потребовалось некоторое время, чтобы обернуть голову, когда я впервые столкнулся с этим. Но это действительно просто!

Предположим, у вас есть следующее:

A = { X>Y, Y>Z }
Q = X>Z

Теперь Soundsess говорит, что мы не можем достичь безумия, придерживаясь утверждений A, Более формально, если Q не держит, он не может быть получен из A, Или только действительные вещи могут быть получены из A,

Создать несостоятельный набор утверждений легко. Возьмите например

A = { x<Y, X>Y }

Они противоречат друг другу, поэтому мы можем, например, получить X>X (что неверно), используя доказательство от противного.

Полнота говорит о двойственном: все действительные вещи могут быть получены из A, Предположим, что X, Y а также Z единственные переменные в мире, и > это единственное отношение в мире. Затем набор утверждений, таких как

A = { X>Y, Y>Z }

завершено, так как для любых двух заданных переменных, a а также bмы можем вывести a>b если и только если a>b на самом деле держит.

Если бы мы только имели

A = { X>Y }  (and no knowledge about Z)

тогда набор утверждений не будет полным, поскольку будут Z о котором мы ничего не могли бы сказать.

---

В двух словах: разумность говорит о том, что вы не можете прийти к безумным выводам, а полнота говорит о том, что вы можете прийти ко всем разумным выводам.