Тривиальные
доказательства

[предыдущая глава]  [оглавление]  [следующая глава]

Имеется ряд примитивных ("тривиальных") приемов доказательства, общих для всех дедуктивных систем. Перечислим их.

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

Если имеется доказательство G₁, G₂,... G_N X,
то можно составить доказательство G₁, G₂,... G_N, G_N+1, G_N+2,...G_N+M X.

"Составление" нового доказательства заключается в простом переписывании старого. Новые добавленные гипотезы просто игнорируются, не используются в доказательстве, разве что они там уже были ранее.

2. Аксиома доказуема на основании любого списка гипотез.

Другими словами, можно составить доказательство G₁, G₂,... G_N X, где X - аксиома.

Доказательство будет содержать 0 строк, ведь аксиомы считаются изначально доказанными.

3. Теорема доказуема на основании любого списка гипотез.

Другими словами, можно составить доказательство G₁, G₂,... G_N X, где X - теорема.

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

4. Гипотеза доказуема на основании списка гипотез, где она присутствует.

Другими словами, можно составить доказательство G₁, G₂,... G_N G_i, где 1 ≤ i ≤ N.

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

Не смотрите на то, что приемы 1-4 вносят усложнения в прежние доказательства или формулы. Как ни странно, иногда эти усложнения оказываются полезны. Верно и обратное утверждение:

5. Из списка гипотез можно убирать неиспользуемые.

Другими словами, если имеется доказательство G₁, G₂,... G_N, X Y, в котором X ни разу не использовалась, то можно составить доказательство: G₁, G₂,... G_N Y

Новое доказательство будет копией старого.

6. Доказательства можно объединять, если результат предыдущего доказательства служит гипотезой для следующего.

Другими словами, если имеется доказательство F₁, F₂,... F_M X и G₁, G₂,... G_N, X Y, то можно составить доказательство F₁, F₂,... F_M, G₁, G₂,... G_N Y.

Составление нового доказательства будет представлять собой простое переписывание всех строк первого доказательства, а следом - всех строк второго доказательства. В первой части будет доказано X, поскольку все необходимые гипотезы имеются. Потом будет доказана Y, поскольку имеются все необходимые гипотезы, кроме X, а X доказана перед началом второй части. Как обычно, допустимо N = 0 и M = 0.

7. Дублирующие гипотезы в списке можно удалять.

Другими словами, если имеется доказательство G₁, G₂,... G_N, G_i Y, где 1 ≤ i ≤ N,
то можно составить доказательство G₁, G₂,... G_N Y

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

8. Гипотезы в списке можно переставлять местами, выписывать их в любом порядке.

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