1.6.2. Синтаксические приемы в кванторных утверждениях

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

Запишем утверждение: Если x<y, тоx<zприy<z.

(x)(y) Меньше(x,y)((z)Меньше(y,z)Меньше(x,z)).

В данном случае порядок первых двух кванторов несущественен. При такой записи, как правило, справедливо будет следующее:

(x)(y) = (y)(x) = (x, y)

Третья форма записи короче и прямо указывает на несущественность порядка записи переменных. Можно вынести вперед и квантор по переменной z, т.к. она не входит в предшествующий предикат Меньше.

Запишем утверждение: Для любого числа yнайдется такоеx, чтоy=x+1. Введем имя функцииplus, возвращающей сумму аргументов, и имя предикатаEq, определяющего равенство аргументов.

(y)((x)Eq(plus(1, x), y)).

Если изменить порядок следования кванторов, получится ложное утверждение:

(x) ((y)Eq(plus(1,x),y)), т.е. может найтись такоеx, что сумма 1+xбудет равна любомуy.

Вхождение переменной xв формулу называется связанным, если оно находится в области действия квантора, использующего эту переменную или является вхождением в этот квантор. Вхождение, не являющееся связанным, называется свободным.

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

((x) Поставляется_заводом_А (x))((x)Меньше(x, 5000р.)),

то его нельзя переписать в виде:

(x)(Поставляется_заводом_А (x)Меньше(x, 5000р.)),

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

(x,y)(Поставляется_заводом_А (y)Меньше(x, 5000р.)).

Еще одной сложной ситуацией является наличие в утверждении импликации. Например, не будут эквивалентны два следующих утверждения:

(y)((x)P(x))R(x, y)

(y, x)P(x)R(x, y)

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

1.6.3. Отрицание кванторов

При отрицании кванторов используются следующие правила:

~((x)p(x)) = (x)~p(x)

~((x)p(x)) = (x)~p(x)

Рассмотрим пример, иллюстрирующий отрицание кванторов:

~((x)P(x)Q(x)) = ~((x)~P(x)Q(x)) = (x)~(~P(x)Q(x)) = (x)P(x)~Q(x)

Из приведенных правил видно, что при отрицании утверждения, содержащего кванторы:

1. Меняются друг на друга кванторы общности и существования.

2. Меняются друг на друга операторы И и ИЛИ.

3. Знаки литер меняются на противоположные.

1.7. Семантика исчисления высказываний

Семантика - есть смысловое наполнение высказывания. Интерпретировать формулу - означает приписать ей значение из семантической области {T,F}.

Оператором ВЛЕЧЕТ в логике называется импликация. Следование BизA- есть семантическое наполнение операции импликации. ЗаписьABозначает, что еслиA=T, тоB=T, и читается "AвлечетB". Если же приA=TB=F, то выражениеAB- ложно. Стрелка говорит о том, что рассуждать можно только в одном направлении. Из высказывания "Если пройдет дождь, то будет урожай" не следует "Если есть урожай, то был дождь" (может быть, вместо дождя был произведен искусственный полив). Однако справедливо "Если нет урожая, то не было дождя". Данное соображение доказывается при помощи некоторых выше приведенных правил:

AB = ~AB = ~(~B)~A = ~B~A

Дедукция (от лат. введение) - переход в процессе познания от общего к частному. Индукция, в противоположность дедукции, есть переход от частного к общему. Процесс логического вывода представляет собой переход от посылок к заключениям на основе применяемых правил логики. Определять общезначимость и выполнимость формул позволяет ряд алгоритмов.

Большинство алгоритмов основаны на:

1. Переборе.

2. Упрощении формул для определенных сочетаний значений переменных.

3. Приведении формул к абсурду. К таким алгоритмам относится, например, алгоритм редукции, являющийся упрощением метода резолюций.