Контрпример
Материал из Википедии — свободной энциклопедии
Пример, который опровергает верность некоторого утверждения. Построение контрпримера — классический способ опровержения гипотез.
Если есть утверждение типа «Для любого X из множества M выполняется свойство A», то контрпримером для этого утверждения будет любой объект X0 из множества M, для которого свойство A не выполняется.
Часто найти контрпример вручную очень сложно. В таких случаях можно воспользоваться компьютером. Программа для нахождения контрпримера может просто перебирать элементы множества M и проверять выполнения свойства A. Более сложный, но и более эффективный, подход заключается в построении контрпримера «по частям». При этом при выборе очередной «части» сразу отбрасываются варианты, которые заведомо не ведут к опровержению рассматриваемого утверждения. Это позволяет значительно ускорить работу, зачастую на порядок.
Необходимо помнить, что отсутствие контрпримера не служит доказательством гипотезы. Доказательство такого рода можно строить, только если рассматриваемое множество конечно. В этом случае, достаточно перебрать все его элементы, и, если контрпримера среди них нет, то утверждение будет доказано.
[править] Примеры
Рассмотрим утверждение «Все простые числа нечётны». Очевидным контрпримером будет являтся число 2, которое хоть и простое, но чётное.
[править] См. также
Контрпримеры в анализе
Контрпримеры в теории вероятностей