Необходимые и достаточные по сравнению с звуком и полнотой

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 говорит, что мы не можем достичь crazyness, прикрепляя к высказываниям A. Более формально, если Q не выполняется, его нельзя получить из A. Или, только действительные вещи могут быть получены из A.

Легко создать набор unsound. Возьмем, к примеру

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, которые мы не могли сказать ничего.

---

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