Кванторы общности и существования. Логические операции

Специфическая природа предикатов позволяет ввести над ними такие операции, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами.

Квантор общности

Для превращения одноместного предиката в высказывание нужно вместо его переменной подставить какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения – это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката.

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

Словесным аналогом квантору общности " является: «для любого», «для каждого», «для всякого» и т.п.

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

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно конъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 59 .

Пусть х определен на множестве людей М , а Р(х) – предикат «х – смертен» . Дать словесную формулировку предикатной формулы .

Решение.

Выражение означает «все люди смертны». Оно не зависит от переменной х , а характеризует всех людей в целом, т. е. выражает суждение относительно всех х множества М .

Определение. Операцией связывания квантором общности n-местному ( n , сопоставляется новый ( , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно истинен, и ложное в противном случае, то есть:

Квантор существования

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

Словесным аналогом квантору существования $ является: «существует», «найдется» и т.п.

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

Если одноместный предикат Р(х) задан на конечном множестве М = { a 1 , a 2 , …, a n } , то высказывание эквивалентно дизъюнкции Р(а 1) Р(а 2) … Р(а n).

Пример 60.

Пусть Р(х) – предикат «х – четное число» , определенный на множестве N . Дать словесную формулировку высказыванию , определить его истинность.

Решение.

Исходный предикат Р(х): «х – четное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в простое высказывание, являющееся истинным или ложным, например,

при подстановке числа 5 – ложным, при подстановке числа 10 – истинным.

Высказывание означает «во множестве натуральных чисел N существует четное число». Поскольку множество N содержит четные числа, то высказывание истинно.

Определение. Операцией связывания квантором существования по переменной х 1 называется правило, по которому каждому n-местному (n 2) предикату Р(х 1 , х 2 , …, х n), определенному на множествах М 1 , М 2 , …, М n , сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов , превращается в высказывание , ложное в том и только в том случае, когда одноместный предикат , определенный на множестве М 1 , тождественно ложен, и истинное в противном случае, то есть:

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

Пример 61.

Пусть предикат Р(х, у) описывает отношение «х любит у» на множестве людей. Рассмотреть все варианты навешивания кванторов на обе переменные. Дать словесную интерпретацию полученных высказываний.

Решение.

Обозначим предикат «х любит у» через ЛЮБИТ(х, у) . Предложения, соответствующие различным вариантам навешивания кванторов, проиллюстрированы на рис. 2.3-2.8, где х и у показаны на разных множествах, что является условностью и предпринято только для объяснения смысла предложений (реальные множества переменных х и у , очевидно, должны совпадать):

— «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит» (рис. 2.3).

Рис. 2.3. Иллюстрация к высказыванию «для любого человека х существует человек у , которого он любит» или «всякий человек кого-нибудь любит»

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

Квантор - некоторый способ приписать наличие каких-либо свойств целому множеству объектов: (квантор общности) или просто (), (квантор существования).

1. Квантор общности. Пусть R (x) - вполне определенный предикат, принимающий значение И или Л для каждого элемента х некоторого поля М. Тогда под выражением (x)R(x) мы будем подразумевать высказывание истинное, когда R(х) истинно для каждого элемента х поля М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «для всякого х R (х) истинно».

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

2. Квантор существования. Пусть R(х) - некоторый предикат. Мы свяжем с ним формулу (x)R(x), определив ее значение как истину, если существует элемент поля М, для которого R(х) истинно, и как ложь в противном случае. Тогда если И(х) - определенная формула логики предикатов, то формула (x)И(x) также определена и от значения х не зависит. Знак (x) называется квантором существования .

Кванторы (х) и (х) называются двойственными друг другу.

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

Предметное переменное, не связанное никаким квантором, мы будем называть свободным переменным . Таким образом, мы описали все формулы логики предикатов.

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

Если две формулы равносильны на любых полях М, то мы будем их называть просто равносильными. Равносильные формулы могут быть замещаемы одна другой.

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

В частности, имеет место: И→ В равносильно И В.

Пользуясь этим, мы можем для любой формулы найти равносильную, в которой из операций алгебры высказываний имеются только &, и -.

Пример: (x)(А(х)→(у)В(у)) равносильна (x)(А(х)(у)В(у)).

Кроме того, для логики предикатов имеются равносильности, связанные с кванторами.

Существует закон, связывающий кванторы со знаком отрицания. Рассмотрим выражение (х)И(х).

Высказывание «(х)И(х) ложно», равносильно высказыванию: «существует элемент у, для которого И(у) ложно» или, что то же, «существует элемент у, для которого И(у) истинно». Следовательно, выражение (х)И(х) равносильно выражению (у)И(у).

Рассмотрим таким же образом выражение (х)И(х).

Это есть высказывание «(х)И(х) ложно». Но такое высказывание равносильно высказыванию: «для всех у И(у) ложно» или «для всех у И(у) истинно». Итак, (х)И(х) равносильно выражению (у)И(у).

Мы получили, таким образом, следующее правило:

Знак отрицания можно ввести под знак квантора, заменив квантор на двойственный.

Мы уже видели, что для каждой формулы существует равносильная ей формула, которая из операций алгебры высказываний содержит только &, и -.

Пользуясь равносильностями для каждой формулы можно найти равносильную, в которой знаки отрицания относятся к элементарным высказываниям и элементарным предикатам.

Для аксиоматического описания логики предикатов предназначено исчисление предикатов.

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

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

Р(х):” х - простое число”. Подставив х = 7, получим высказывание

“ 7 - простое число”. Мы познакомимся ещё с двумя логическими операциями: навешивание квантора общности и квантора существования, которые позволяют получить из высказывательных форм высказывания.

Подставим перед высказывательной формой Р(х) слово “любое”: “ любое х - простое число”. Получили ложное высказывание. Подставим перед Р(х) слово “некоторые”: “ некоторые числа х - простые”. Получили истинное высказывание.

В математике слова “любые”, “некоторые” и их синонимы называются кванторами, которые соответственно называются квантор общности (") и квантор существования ($). Квантор общности заменяется в словесных формулировках словами: любой, все, каждый, всякий и т.д. Квантор существования в словесной формулировке заменяется словами: существует, хотя бы один, какой-нибудь найдётся и т.д.

Пусть Р(х) - высказывательная форма на М. Запись

("хÎМ) Р(х)

означает: для любого элемента х (из множества М) имеет место Р(х), что уже представляет собой высказывание. Чтобы доказать, что высказывание ("х)Р(х) - истинно, надо перебрать все элементы а, b, с и т.д. из М и убедиться, что Р(а), Р(b), Р(с),... истинны, и, если невозможно перебрать элементы М, должны доказать с помощью рассуждений, что для любого а из М высказывание Р(а) истинно. Чтобы убедиться, что ("х)Р(х) ложно, достаточно найти лишь один элемент аÎМ, для которого Р(а) ложно.

ПРИМЕР . Дана высказывательная форма

В(х):” - простое число”.

В(1): 2 2 + 1 = 5 - простое число;

В(2): = 17 - простое число;

В(3): = 257 - простое число;

В(4): = 65537 - простое число.

Можно ли сказать, что ("х)В(х) ? Это необходимо доказывать. Леонард Эйлер доказал, что В(5) - ложно, т.е. + 1 = 2 32 + 1 делится на 641 и, следовательно, ("х)В(х) - ложно.

ПРИМЕР . Рассмотрим высказывание ("х)С(х), где на N задано С(х): “х 3 + 5х делится на 6”.

Очевидно, С(1), С(2), С(3), С(4) истинны. Но если мы проверим даже миллион значений х всегда есть опасность, что для миллион первого значения х утверждение С(х) окажется ложным.

Доказать можно, например, так:

х 3 + 5х = х 3 - х + 6х = х(х 2 - 1) + 6х = (х - 1)х(х + 1) + 6х

Выражение (х - 1)х(х + 1) делится на 3, так как из трех последовательных натуральных чисел по крайней мере одно делится на 3; это выражение делится и на 2, так как из трех последовательных чисел одно или два числа чётны. Второе слагаемое 6х делится на 6, следовательно и вся сумма делится на 6, т.е. ("х)С(х) - истинно.

Пусть С(х) некоторая высказывательная форма. Запись

означает: существует элемент х из множества М, для которого имеет место С(х). ($х)С(х) уже высказывание. Если во множестве М можно найти элемент а, для которого С(а) истинно, то высказывание($х)С(х) - истинно. Если же в М нет ни одного элемента а, для которого С(а) истинно, высказывание ($х)С(х) - ложно.

ПРИМЕР . На множествеN задано С(х):” ”. С(1) - ложно, С(2) - ложно, С(5) - истинно. Следовательно, ($х)С(х) - истинное высказывание.

ПРИМЕР . На множестве N задано К(х):” х 2 + 2х + 3 делится на 7”. К(1) = 6, 6 не делится на 7; К(2) = 11, 11 не делится на 7 и т.д.

Гипотеза: ($х)К(х) - ложно.

Докажем это. Любое натуральное число по теореме о делении с остатком можно представить в виде n = 7q + r, где r < 7.

n 2 + 2n + 3 = (7q + r) 2 + 2(7q + r) + 3 = 7(7q 2 + 2qr + 2q) + r 2 + 2r + 3.

Итак, число n 2 + 2n + 3 делится на 7 тогда и только тогда, когда r 2 + 2r + 3 делится на 7. Остаток r Î { 0, 1, 2, 3, 4, 5, 6 }. Методом перебора убедимся, что r 2 + 2r + 3 не делится на 7. Итак, ($х)К(х) - ложно.

Как построить отрицание высказывания с квантором?

Для того чтобы построить отрицание высказывания с квантором, нужно заменить квантор общности (") на квантор существования ($) и, наоборот, квантор существования на квантор общности, а предложение, стоящее после квантора, на его отрицание, т.е.

[("x)P(x) Û ($x) P(x);

[($x)P(x) Û ("x) P(x).

Например, пусть даны два высказывания:

А: “каждое простое число нечётно”;

В: “ каждое простое число чётно”.

Будет ли В отрицанием высказывания А? Нет, так как ни одно из высказываний не является истинным. В данном случае

А: “не каждое простое число нечётно, т.е. существует чётное простое число” - истинное высказывание.

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

Пусть А(х,у) - высказывательная форма с двумя переменными.

Тогда ("х)А(х,у), ($х)А(х,у), ("х)А(х,у), ($х)А(х,у) тоже высказывательные формы но уже с одной переменной. В этом случае говорят, что квантор связывает одну переменную. Чтобы получить из высказывательной формы А(х,у) высказывание необходимо связать обе переменные. Например, ("х)($у)А(х,у) - высказывание.

Для высказывательной формы Р(х,у): “ x < y”, заданной на Z , рассмотрим все случаи получения высказывания путем добавления (навешивания) кванторов:

1) ("х)("у)Р(х,у) Û л - “ Для всякого х и для всякого у х < y”;

2) ("у)("х)(х < y) Û л - “Для всякого у и для всякого х х < y”;

3) ($x)($y) (x < y) Û и - “Существует х и существует у такие, что x < y”;

4) ($у)($х) (х < y) Û и - “Существует х и существует у такие, что x < y”;

5) ("х)($у) (x < y) Û и - “Для всякого х существует у такое, что x < y”;

6) ($у)("х) (x < y) Û л - “Существует у такое, что для всякого х х < y”;

7) ("у)($х) (х < y) Û и - “Для всякого у существует х такое, что x < y”;

8) ($х)("у) (x < y) Û л - “Существует x такое, что для всякого y х < y”.

` Обратите внимание на высказывания (1) и (2), (3) и (4). Структуры этих высказываний отличаются лишь порядком следования одноименных кванторов, но при этом не меняются смысл и значения истинности высказываний.

Высказывания (5) и (6), (7) и (8) отличаются порядком следования разноимённых кванторов, что приводит к изменению смысла и, возможно, значения истинности высказывания. Высказывание (7) утверждает о наличии в Z наименьшего числа, что ложно. (8) утверждает об отсутствии такого, что истинно.

Теоретические вопросы:

1. Понятие предиката от одного, нескольких переменных.

2. Примеры одноместных и двуместных предикатов. 3. Область истинности предиката.

4. Кванторы общности и существования. Свободные и связанные переменные. Операции над предикатами. Какова область истинности ; ; ; ? Дать геометрические интерпретации.

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

Упражнения

5.1. Укажите несколько значений переменных, при которых следующие предикаты истинны, ложны:

1. х 2 , х Î N; 9. = - x, x Î R;

2. х < 1 , x Î N ; 10. > 0 ,

3. x > 6® x ³ 3 , xÎZ; 11. sin x = - , xÎ R;

4. x + 3x +6 = 0 , x Î R; 12. cos x = , x ÎR;

5. = 0, xÎR; 13. x ³ y , x,y Î R;

6. | x - 5 | < 2, 14. x + y < 3, x,yÎ N;

7. | 2x + 3 | ³ 2x + 3, x Î R; 15. x (y - 1) = 0, x,yÎR;

8. = x, x Î R; 16. x + y =4, x, y ÎR.

5.2. Найдите область истинности предикатов упражнения 5.1. Случаи 13 - 16 изобразите на координатной плоскости.

5.3.

1. = 0; 7. | 3x - 2 | > 8;

2. = ; 8. | 5x - 3 | < 7;

3. - > ; 9. 2 - | x | = 1,7;

4. ; 10. | 3x - 1 | = 3x - 1;

5. < 0 ; 11. | 3x - 1 | = 1 - 3x;

6. > 0; 12. | 2x + 4 | ³ 2x + 4.

5.4. Найдите область истинности предикатов:

1. ( < x + 1,5) Ù (2x - 8 > 3 - 0,5 x);

2. ( - 4 < - 1) Ù ( x + 2 (2x- 1) < 3(x +1);

3.( - +2x<3x-3) Ù ( - 3(1-x)+2x< );

4.( - + x < 2x - 4)Ù( + 3 (x - 1)< );

5.((x+3) (x - 1) < 0) Ù (x + 4x + 6 > x (x - 5);

6.((x - 6x + 9)(2x - 10) < 0) Ù (6 + x (7 - x) < x +2x(5-x);

7.(1 + £ ) Ú (- 1 < 5x - 5)

8.( - > 2) Ú (- 3x - 1 > 2) ;

9.( + 6x > + 4) Ú ( - > - );

В любом национальном языке употребляемые в обычной речи связки “и”, “или”, “если …, то …”, “тогда и только тогда, когда …” и т.п. позволяют из уже заданных высказываний строить новые сложные высказывания. Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями . Логическая операция полностью может быть описана таблицей истинности , указывающей, какие значения принимает сложное высказывание при всех возможных значениях простых высказываний.

Логической операцией называется способ построения сложного высказывания из элементарных высказываний, при котором истинностное значение сложного высказывания полностью определяется истинностными значениями исходных высказываний (см. статью “”).

В алгебре логики логические операции и соответствующие им логические связки имеют специальные названия и обозначаются следующим образом:

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

Рассмотрим два высказывания: p = “Завтра будет мороз ” и q = “Завтра будет идти снег ”. Очевидно, новое высказывание p & q = “Завтра будет мороз, и завтра будет идти снег ” истинно только в том случае, когда одновременно истинны высказывания p и q , а именно, что завтра будет и мороз и снег. Высказывание p & q будет ложно во всех остальных случаях: будет идти снег, но будет оттепель (т.е. не будет мороза); мороз будет, а снег не будет идти; не будет мороза, и снег не будет идти.

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

Рассмотрим два высказывания: p = “Колумб был в Индии ” и q = “Колумб был в Египте p q = “Колумб был в Индии или был в Египте ” истинно как в случае, если Колумб был в Индии, но не был в Египте, так и в случае, если он не был в Индии, но был в Египте, а также в случае, если он был и в Индии, и в Египте. Но это высказывание будет ложно, если Колумб не был ни в Индии, ни в Египте.

Союз “или” может применяться в речи и в другом, “исключающем” смысле. Тогда он соответствует другому высказыванию - разделительной, или строгой, дизъюнкции.

Строгая , или разделительная , дизъюнкция - логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным только тогда, когда только одно из высказываний является истинным. Логическая операция разделительная дизъюнкция определяется следующей таблицей истинности:

Рассмотрим два высказывания: p = “Кошка охотится за мышами ” и q = “Кошка спит на диване ”. Очевидно, что новое высказывание p q истинно только в двух случаях - когда кошка охотится за мышами либо когда кошка мирно спит. Это высказывание будет ложно, если кошка не делает ни того, ни другого, т.е. когда оба события не происходят. Но это высказывание будет ложным и тогда, когда предполагается, что оба высказывания произойдут одновременно. В силу того, что этого произойти не может, высказывание и является ложным.

В логике связкам “либо” и “или” придается разное значение, однако в русском языке связку “или” иногда употребляют вместо связки “либо”. В этих случаях однозначность определения используемой логической операции связана с анализом содержания высказывания. Например, анализ высказывания “Петя сидит на трибуне А либо на трибуне Б ” заменить на “Петя сидит на трибуне А или Б ”, то анализ последнего высказывания однозначно укажет на логическую операцию разделительная дизъюнкция , т.к. человек не может находиться в двух разных местах одновременно.

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

Логическая операция импликация

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

Допустим, 1 = 2, тогда и 2 = 1. Складывая эти равенства, мы получим 3 = 3, т.е. из ложной посылки путем тождественных преобразований мы получили истинное высказывание.

Импликация, образованная из высказываний А и В , может быть записана при помощи следующих предложений: “Если А , то В ”, “Из А следует В ”, “А влечет В ”, “Для того чтобы А , необходимо, чтобы В ”, “Для того чтобы В , достаточно, чтобы А ”.

Эквивалентность - логическая операция, ставящая в соответствие двум элементарным высказываниям новое, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Логическая операция эквивалентность задается следующей таблицей истинности:

Рассмотрим возможные значения сложного высказывания, являющегося эквивалентностью: “Учитель поставит ученику 5 в четверти тогда и только тогда, когда ученик получит 5 на зачете” .

1) Ученик получил 5 на зачете и 5 в четверти, т.е. учитель выполнил свое обещание, следовательно, высказывание является истинным.

2) Ученик не получил на зачете 5, и учитель не поставил ему 5 в четверти, т.е. учитель свое обещание сдержал, высказывание является истинным.

3) Ученик не получил на зачете 5, но учитель поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

4) Ученик получил на зачете 5, но учитель не поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

Отметим, что в математических теоремах эквивалентность выражается связкой “необходимо и достаточно”.

Рассмотренные выше операции были двухместными (бинарными), т.е. выполнялись над двумя операндами (высказываниями). В алгебре логики определена и широко применяется и одноместная (унарная) операция отрицание .

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

В русском языке для построения отрицания используется связка “неверно, что …”. Хотя связка “неверно, что …” и не связывает двух каких-либо высказываний в одно, она трактуется логиками как логическая операция, поскольку, поставленная перед произвольным высказыванием, образует из него новое.

Отрицанием высказывания “У меня дома есть компьютер” будет высказывание “Неверно, что у меня дома есть компьютер” или, что в русском языке то же самое, “У меня дома нет компьютера” . Отрицанием высказывания “Я не знаю китайского языка” будет высказывание “Неверно, что я не знаю китайского языка” или, что в русском языке одно и то же, “Я знаю китайский язык” .

Кванторы

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

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

Кванторы позволяют из конкретной высказывательной формы (см. “Высказывания. Логические значения ”) получить высказывательную форму с меньшим числом параметров, в частности, из одноместной высказывательной формы получить высказывание 9 .

Квантор общности позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Для всех x …”. Результат применения квантора общности к высказывательной форме A(x ) обозначают x A(x ). Высказывание x A(x ) будет истинным тогда и только тогда, когда при подстановке в A(x ) вместо свободной переменной x любого объекта из области возможных значений всегда получается истинное высказывание. Высказывание x A(x ) может читаться следующим образом: “Для любого x имеет место A(x )”, “A(x ) при произвольном x ”, “Для всех x верно A(x )”, “Каждый x обладает свойством A(x )” и т.п.

Квантор существования позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Существует такой x , что …”. Результат применения квантора общности к высказывательной форме A(x ) обозначают x A(x ). Высказывание
x A(x ) истинно тогда и только тогда, когда в области возможных значений переменной x найдется такой объект, что при подстановке его имени вместо вхождения свободной переменной x в A(x ) получается истинной высказывание. Высказывание x A(x ) может читаться следующим образом: “Для некоторого x имеет место A(x )”, “Для подходящего x верно A(x )”, “Существует x , для которого A(x )”, “Хотя бы для одного x верно A(x )” и т.п.

Кванторы играют для формализованных языков математической логики ту же роль, которую играют для естественного языка так называемые “количественные” (“кванторные”) слова, - определяют область применимости данного высказывания (или высказывательной формы).

При построении отрицания к высказыванию, содержащему квантор, действует следующее правило: частица “не” добавляется к сказуемому, квантор общности заменяется на квантор единственности и наоборот. Рассмотрим пример. Отрицанием высказывания “Все юноши 11-х классов - отличники” является высказывание “Неверно, что все юноши 11-х классов - отличники” или “Некоторые юноши 11-х классов - не отличники”.

В информатике кванторы применяются в логических языках программирования (см. “Языки программирования ”) и языках запросов к базам данных.

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

С логическими операциями дизъюнкция, конъюнкция и отрицание школьники знакомятся в основной школе. Там же вводится и понятие таблицы истинности. Скорее всего знакомство с данными понятиями возникает в языках программирования, но использовать их можно и в электронных таблицах - там логические операции реализованы через соответствующие функции OR, AND, NOT.

Более сложные логические операции могут быть рассмотрены в старшей школе. Задачи, использующие импликацию, встречаются в каждом из опубликованных вариантов ЕГЭ по информатике. Например: для какого числа X истинно высказывание ((X > 3) (X < 3)) –> (X < 1)? (Демоверсия ЕГЭ, 2007 г. )

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

Задания на построение достаточных и необходимых условий для школьников оказываются непростыми. При формировании этого умения необходимо особо отметить три момента:

а) используемая в математических утверждениях форма “необходимо и достаточно” соответствует связке “тогда и только тогда” (эквивалентность);

б) связка “для того чтобы …(A ), необходимо, чтобы …(B )” реализуется прямой импликацией A B . (Для того чтобы квадратное уравнение имело решение, необходимо, чтобы дискриминант был неотрицательным );

в) достаточное условие реализуется обратной импликацией B ® A и может на русском языке выражаться, например, так: “для того чтобы... (А), достаточно, чтобы... (В)”.

В старшей школе (10–11-е классы) у учащихся полезно сформировать умение строить отрицание к высказыванию на русском языке. Это умение необходимо, например, для доказательства теорем методом “от противного”. Строить отрицание даже к простым высказываниям не всегда просто. Например, к высказыванию На стоянке стоят красные “Жигули ” следующие предложения отрицаниями являться не будут:

1) На стоянке стоят не красные “Жигули ”;

2) На стоянке стоит белый “Мерседес ”;

3) Красные “Жигули ” стоят не на стоянке .

Отрицанием к этому высказыванию будет “На стоянке не стоят красные “Жигули”. Объяснить школьникам это можно так: отрицание к предложению должно полностью исключать истинность исходного высказывания. Если же на стоянке стоит белый “Мерседес”, то ничто не мешает красным “Жигулям” стоять тоже.

Об алгоритме построения отрицания к сложному высказыванию можно прочитать в книге Е.Андреевой, Л.Босовой, И.Фалиной “Математические основы информатики”.

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

6 От латинских слов idem - тот же самый и potens - сильный; дословно - равносильный.

7 Это определение легко распространяется на случай n высказываний (n > 2, n - натуральное число).

8 Это определение, как и предыдущее, распространяется на случай n высказываний (n > 2, n - натуральное число).

9 Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. М.: Физматлит, 2002.

Логика и аргументация: Учебн. пособие для вузов. Рузавин Георгий Иванович

4.2. Кванторы

4.2. Кванторы

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

Для квантификации (количественной характеристики) высказываний эта теория вводит два основных квантора: квантор общности, который мы будем обозначать символом (х), и квантор существования, обозначаемый символом (Ех). Они ставятся непосредственно перед высказываниями или формулами, к которым относятся. В том случае, когда кванторы имеют более широкую область действия, перед соответствующей формулой ставятся скобки.

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

Так, суждение: "Все материальные тела обладают массой" можно перевести на символический язык так:

где х - обозначает материальное тело:

М - массу;

(х) - квантор общности.

Аналогично этому утверждение о существовании экстрасенсорных явлений можно выразить через квантор существования:

где через х обозначены явления:

Э - присущее таким явлениям свойство экстрасенсорности;

(Ex) - квантор существования.

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

(х) (Т(х) ? P(х)),

где (х) - квантор общности;

Т(х) - температура тела;

Р(х) - его расширение;

Знак импликации.

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

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

Связанными называются переменные, подпадающие под действие знаков кванторов общности или существования. Например, формулы (х) А (х) и (х) (Р (х) ? Q(x)) содержат переменную х. В первой формуле квантор общности стоит непосредственно перед предикатом А(х), вовторой - квантор распространяет свое действие на переменные, входящие в предыдущий и последующий члены импликации. Аналогично этому квантор существования может относиться как к отдельному предикату, так и к их комбинации, образованной с помощью логических операций отрицания, конъюнкции, дизъюнкции и др.

Свободная переменная не подпадает под действие знаков кванторов, поэтому она характеризует предикат или пропозициональную функцию, а не высказывание.

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

где R обозначает свойство радиоактивности.

Утверждение, что существует опасность для курящего заболеть раком, можно выразить так: (Ех) (К(х) ? P(x)), где К обозначает свойство "быть курящим", а Р - "заболеть раком". С известными оговорками то же самое можно было выразить» посредством квантора общности: (х) (К(х) ? Р(х)). Но утверждение, что всякий курящий может заболеть раком, было бы некорректным, и поэтому его лучше всего записать с помощью квантора существования, а не общности.

Квантор общности используется для высказываний, в которых утверждается, что определенному предикату А удовлетворяет любой объект из области его значений. В науке, как уже говорилось, квантор общности используется для выражения утверждений универсального характера, которые словесно представляются с помощью таких фраз, как "для всякого", "каждый", "всякий", "любой" и т.п. Путем отрицания квантора общности можно выразить общеотрицательные высказывания, которые в естественном языке вводятся словами "никакой", "ни один", "никто" и т.п.

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

Чаще всего кванторы общности и существования встречаются вместе. Например, чтобы выразить символически утверждение: "Для каждого действительного числа х существует такое число у, что х будет меньше у", обозначим предикат "быть меньше" символом <, известным из математики, и тогда утверждение можно представить формулой: (х) (Еу) < (х, у). Или в более привычной форме: (х) (Еу) (х < у). Это утверждение является истинным высказыванием, поскольку для любого действительного числа х всегда существует другое действительное число, которое будет больше него. Но если мы переставим в нем кванторы, т.е. запишем его в форме: (Еу) (х) (х < у), тогда высказывание станет ложным, ибо в переводе на обычный язык оно означает, что существует число у, которое будет больше любого действительного числа, т.е. существует наибольшее действительное число.

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

1. Законы перестановки кванторов:

(х) (у) А ~ (у) (х) А;

(Ех) (Еу) А ~ (Еу) (Ех) А;

(Ех) (у) А ~ (у) (Ех) А;

2. Законы отрицания кванторов:

¬ (х) А ~ (Ех) ¬ А;

¬ (Ех) А ~ (х) ¬ А;

3. Законы взаимовыразимости кванторов:

(х) А ~ ¬ (Ех) ¬ А;

(Ех) А ~ ¬ (х) ¬ А.

Здесь всюду А обозначает любую формулу объектного (предметного) языка. Смысл отрицания кванторов очевиден: если неверно, что для любого х имеет место А, тогда существуют такие х, для которых А не имеет места. Отсюда также следует, что если: любому х присуще А, тогда не существует такого х, которому было бы присуще не-А, что символически представлено в первом законе взаимовыразимости.