Свойства всеобщности и существования

Проверка свойств «для всех» и «существует» довольно часто производится программами и заслуживает отдельного рассмотрения. В математической логике для этого существуют кванторы всеобщности и существования. На самом деле они просто являются сокращенным обозначением логических операций И (одновременности все) и ИЛИ (хотя бы одно) над результатами проверки какого-либо условия над всеми элементами множества. В программе этому соответствует цикл последовательной проверки, логика которого может включать такие контексты как счетчик, признак, место остановки цикла. В самом простом случае можно подсчитать число элементов, удовлетворяющих условию. По его значению можно судить о выполнении указанных свойств:

// Проверка свойств «для всех» и «существует» при помощи счетчика

int i, s =0;

for (i=0; i<n; i++)

     if (A[i]<0) s++;

// if (s==0) «все >=0»

// if (s==n) «все <0»

// if (s!=0) «существуют <0»

// if (s!=n) «существуют >=0»

 

На самом деле не всегда нужно выполнять проверку до конца. Если на очередном шаге проверяемое условие не выполняется, то это означает нарушение свойства «для всех», и дальнейшая проверка теряет смысл. Этот факт можно зафиксировать отдельным признаком.

 

//Проверка свойств «для всех» и «существует» с помощью признака

int i, s = 1; // признак  установлен в значение «для всех»

for (i=0; i<n; i++)

if (A[i] < 0)         // условие всеобщности нарушается

{ s = 0; break; } // сбросить признак и выйти

// if (s == 1) «все >0»

// else «существуют <=0»

Если же условие выполняется для очередного элемента, то на самом деле ничего конкретного сказать пока нельзя, нужно продолжать проверку до конца. И только по естественному завершению цикла и сохранению установленного признака можно утверждать, что условие всеобщности выполняется.

И, наконец, можно отказаться от переменной-признака, сохранив логику работы цикла, и судить о выполнении свойств всеобщности и существования косвенно по месту остановки цикла – значению переменной цикла. В заголовке цикла записываются два условия, объединенные по И: ограничение по размерности и проверяемой условие всеобщности. Если свойство «для всех» выполняется, то цикл дойдет до конца, иначе завершится на одном из предыдущих шагов цикла.

//Проверка свойств «для всех» и «существует» по месту остановки цикла

for (i=0; i<n && A[i]>0; i++) ;   // «пустой» цикл с выходом по двум условиям

// if (i==n) «все >0»             // был выход по окончании последовательности

// else «существуют <=0»         // был выход по обнаружению неположительного

Из формальной логики известно, что свойства всеобщности и существования взаимосвязаны. Отрицание свойства «для всех» эквивалентно свойству существования для обратного условия, и наоборот.

! " усл (A)≡ $! усл (A)! $ усл (A)≡ "! усл (A)

Пример. Проверка свойства всеобщности при определении, является ли заданное число простым (делится только на 1 и на само себя). Слово «только» означает исключительное выполнение условия для этих значений, на самом деле сформулировать это условие нужно иначе: «для всех» чисел k=2..m-1 (m – само число) число m не делится на k. Этот факт можно установить путем анализа условий завершения цикла проверки.

Функция F 1 находит все простые числа, меньшие заданного числа val, и помещает их в массив А размера n, завершая его 0.

// Поиск простых чисел

void F1(int val, int A[], int n){

 int i, m, k;

 for (i = 0, m = 2; i < n-1 && m < val; m++) {

for (k = 2; k < m && m % k!= 0; k++); // Пустой цикл проверки делимости

if (k == m) A[i++] = m;           // Дошли до конца - на все НЕ ДЕЛИТСЯ

 }

 A[i] = 0;

}

Более эффективный алгоритм имеет другую схему: проверяется свойство «не делится» по отношению ко всем уже накопленным простым числам (решето Эратосфена). Если в первом случае проверялось, дошло ли проверяемое значение k до проверяемого (k == m), то во втором случае – дошел ли индекс k до конца последовательности накопленных простых чисел (k == i).

 

// Поиск простых чисел - проверка деления на накопленные простые

void F2(int val, int A[], int n){

 int i, m, k;

 for (i = 0, m = 2; i < n-1 && m < val; m++) {

    for (k = 0; k < i && m % A[k]!= 0; k++);

    if (k == i) A[i++] = m;   // Цикл дошел до конца массива простых -

 }                             // на все НЕ ДЕЛИТСЯ

 A[i] = 0;

}

-----------------------------------------------------------------------------------------