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

При «навешивании» кванторов на двухместную высказыватель- ную форму (?(х, у) можно получить одну из восьми комбинаций: 1) VxVy(Q(x, у)) — «для любого х и любого у Q(x, у)»; 2) VyVx(0(x, у)) — «для любого у и любого х Q{x, у)»; 3) 3x3у((7(х, у)) — «существует х и существует у, такие, что Q(x, у)»; 4) ЗуЗх((2(х, у)) — «существует у и существует х, такие, что Q(x, у)»; 5) 3xVy(0(x , у)) — «существует х, такой, что для любого у Q(x, у)»; 6) Vx3y(Q(x, у)) — «для всякого х существует у, такой, что Q(x, у)»; 7) Зу Vx(Q(x, у)) — «существует у, такой, что для любого х Q(x, у)»; 8) Vy3x(Q(x, у)) — «для всякого у существует х, такой, что Q(x, у)». Очевидно, что первое и второе высказывания, а также третье и четвертое тождественны между собой, их значения истинности совпадают. Между остальными полученными высказываниями нельзя установить тождественности: если истинно высказывание 5, то истинным будет и высказывание 8, причем обратное неверно. Аналогично, если истинно высказывание 7, то истинно и выска­ зывание 6, но не наоборот. То есть, если кванторы одноименны (1 —4), то их порядок не играет роли и полученные высказывания эквивалентны. Если кванторы разноименные (5—8), то их поря­ док в полученном высказывании принципиально важен. Например, для двухместного предиката «Город х находится в стране у» высказывание \/уЗхР(х, у) имеет вид 0-местного пре­ диката и читается «В каждой стране у есть некоторый город х». Оно будет истинным, в то время как высказывание 3 х\ /уР(х , у) чита­ ется «Существует город х, находящийся во всех странах у» будет ложным. Пусть даны х, у — две различные переменные, F(x), Ф(х) и Q(x, у) — любые формулы логики предикатов и М — формула, не содержащая свободных вхождений х. Тогда справедливы равно­ сильности, представленные с учетом двойственности кванторов 3 и V в табл. 5.5. Формулы . Определение формулы лежит в основе так называе­ мой логики предикатов первого порядка , в которой разрешается квантифицировать (связывать кванторами) только предметные переменные. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисле­ ния высказываний, а также большинство правил вывода умоза­ ключений из классической логики. Поэтому язык логики преди­ катов дает возможность анализировать рассуждения естественно­ го языка и науки, делать выводы в различных формальных системах. 234