Спирина, М.С. Дискретная математика

Из уравнения (х - 5)(х - 2) = О следует неравенство х > О, так как корни уравнения — числа 2 и 5 — удовлетворяют также и неравенству. Тождественно-истинное высказывание х2 + 5 > 0 может следо­ вать из любой высказывательной формы 0 , имеющей непустое множество истинности Г (0 ) с R, т.е. форма 0 -> (х2 + 5 > 0) истинна при любых значениях х. Отношения следования и равносильности для высказывательных форм, вообще говоря, зависят от того множества, на котором оно рассматривается. Например, высказывательная форма х > 9 следует из неравенства 8 < х < 12, если D = {2, 0, 4, 5, 7, 9, 10, 11, 13}, но не следует, если D(Q) = N. Действительно, при D = {2, 0, 4, 5, 7, 9, 10, 11} 7X0.) = {9, 10, 11}, a Г (0 2) = {9, 10, И , 13} и выполняется T(QX) с T(Q2), т.е. форма 0 , -> 0 2 истинна. Во вто­ ром случае (D(Q) = N), 7 \ 0 , ) = {8, 9, 10, 11}, а Г (02) = {9, 10, 11, 12, 13, 14 ...}, но отношение 7’( 0 1) с Г (0 2) не выполняется, поскольку 8 е T(Q2). Кванторы. Для количественных характеристик обычно исполь­ зуют понятия «все», «некоторые», «существуют» и др., кото­ рые называют кванторами (от лат. quantum — сколько). Мы часто пользовались символами V и 3, заменяющими слова «любой» и «существует». Покажем действие этих кванторов в высказыва­ тельных формах. Часть формулы, на которую распространяется действие квантора, называется областью действия этого кван­ тора. Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действий квантора, после которого стоит переменная. Все прочие вхождения —свободные. Напри­ мер, в выражении УхР(х) переменная х связывает свойство пре­ диката и квантор общности. Грубо говоря, от этой переменной, ее конкретного вида и имени, ничего не зависит, т.е. VxP(x) и Vy Р(у) суть одно и то же. Так, можно произвольно называть индекс суммирования в рядах и переменную интегрирования в определенных интегралах. В частности, в определении множества как совокупности всех объектов, удовлетворяющих характери­ стическому свойству, использовалась запись G - {х|Р(х)}. Оче­ видно, что в предикате со связанной переменной ее так же легко можно заменить на любую другую. При этом множество все рав­ но будет совокупностью тех же элементов, удовлетворяющих свой­ ству Р. Переменная, не являющаяся связанной, называется сво­ бодной, если после подстановки вместо нее имени некоторых конкретных объектов предикат превращается в осмысленное пред­ ложение. Между кванторами 3, V и логическими операциями существу­ ет тесная связь. Пусть предикат Р(х) определен на конечном мно­ жестве D = {ах, аъ ..., а„}. Тогда высказывание Vx е D(P(x)) будет 231