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