Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

{Е) ни одно S не есть Р - Vx(S(x) lP(x)); (Г) некоторые S суть Р - 3c(S(x)&P(x)); (О) некоторые S не есть Р - 3c(S(x)& —iP(x)). Приведенные примеры позволяют записывать в символическом виде до­ вольно сложные выводы, использующие всевозможные комбинации предложе­ ний {А)-{0). Рассмотрим для множества Мвсех целых чисел высказывание вида (А): All «Все четные числа делятся на 2» Пусть предикаты S(x) и Р(х) на множестве М обозначают соответственно <а- четное число» и <а делится на 2». Тогда для предложения Ai имеем сим­ вольную запись: AgimvVx(S(x) ^Р(х)). Если попытаться записать ^7 в виде^* = Vx(S(x)&P(x)), то означает, что каждое целое число является целым и делится на 2, что не так. Рассмотрим теперь на том же множестве всех целых чисел предложение вида (7): If. «Некоторые четные числа являются простыми». Пусть предикат S(x), как и выше, обозначает <а - четное число», аР(х) обо­ значает: <а - простое число». Тогда для предложения /7 имеем символьную за­ пись: J-simv = 3x(S(x)&P(x)). Если записать предложение /7 в виде /* =3c(S(x)^P(x)), то /* означает, что существуют целые числа, которые при условии их четности будут простыми. Ясно, что такая запись будет иметь другой смысл, отличный от исходного. По­ этому нужна связка &. Таким образом, в предложениях типов (А)-(О) с квантором общности V>c используется связка а с квантором существования Зх - связка &. Продемонстрируем нетривиальность перевода с естественного языка на символьный язык примером из [22]. Пусть имеем предложение: 77: «Все убывающие и возрастающие функции монотонны». Введем следующие предикаты на множестве всех функций: иф\ «/убывающая функция»; Уф : «/возрастающая функция»; Мф : «/монотонная функция». Если записать предложение П в виде: Р^=У/(иф&Уф^Мф), то очевидно, что формула F* истинна только за счет того, что для любой функ­ ции/посылка будет ложной. Поэтому высказывание 77 нужно записать в виде: Р=(У/(иф^Мф))& УДУф^Мф). 31