Математическая логика и теория алгоритмов

§ 2. Кванторы Введем специальные обозначения. Пусть М - мноясество, P(x) - определенный на 94. одноместный предикат. Тогда выражение \fxP{x) читается: "для всех х Р(х)" или "для всех л: выполняется Р(х)", или "для любого л: Р{хУ\ или "для каждого х Р(х)". Под выражением "\/хР(х)" будем подразумевать высказывание истинное, когда Р{х) истинно для каждого х т М и ложное - в про­ тивном случае. Символ \/х называется квантором всеобщности. Выражение ЗхР(:с) читается; "существует х такое, что Р{х)" или "хотя бы Д.ПЯ одного X Р(х)", иЛи "для некоторого (некоторых) х Р(х)". Под выражением "3xP(x)" будем подразумевать высказывание, кото­ рое истинно, если Р(х) принимает значение И хотя бы для одного значения переменной хе и ложно, если Р(х) для всех значений переменной х принимает значение Л. Символ 3.x: называется кванто­ ром существования. Квантор 3:)с будем называть двойственным к квантору \/х, и наоборот. В литературе применяются и другие обозначения. Так, вместо пишут ЛхР(х) или ЛхР {х), а вместо 3xP(jc) пишут VxP(x) или V j: P { X ), и л и ЕХР(Х). Введенные обозначения позволяют записывать предложения в символической форме, которая оказывается более удобной для анализа и логических действий над этими предложениями. При символизации языка требуется определенная аккуратность и правильное понимание контекста. В естественном языке часто слово "все" опускается. Например, предложение "рыбы дышат жабрами" означает, что все рыбы дышат жабрами или что каждая рыба дышит жабрами. Поэтому при символизации необходимо ввести квантор общности. Таким образом, если положить для множества живых су- ш^еств, что R(x) означает "х - рыба", а G(x) - "х дышит жабрами", то имеем \/x(R(x)=>G{x)). Но в то же время не в кансдом случае встречающиеся в предло­ жениях слова "все" понимаются как "каждый". Например, предложе­ 49