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

Глава 2. ЛОГИКА ПРЕДИКАТОВ § 1. Понятие предиката Логика предикатов представляет собой развитие логики высказываний. Она содержит в себе всю логику высказываний, но помимо этого, язык логики предикатов вводит в рассмотрение утверждения, отнесенные к предметам, т.е. производится более детальный анализ предложений. Рассмотрение логики пре­ дикатов вызвано тем, что логика высказываний не позволяет моделировать рас­ суждения всех видов, в частности, рассуждения с использованием понятий «каждый», «некоторый». Отметим, что логика предикатов тоже не охватывает всевозможных случаев рассуждений, например, когда нужно исследовать рас­ суждения, истинность которых зависит от времени, или вводятся понятия «должно быть» и «может быть» и т.п. Для введения произвольного предиката предполагается, что задано неко­ торое множество. Предикатом считается повествовательное предложение об элементах не­ которого заданного множества М, которое (предложение) становится высказы­ ванием, если все переменные в нем заменить фиксированными элементами из Ж Часто вместо "предикат от п переменных " говорят "п-местный предикат". Высказывание тоже считается предикатом - нулъместным предикатом. Например, если М является множеством всех натуральных чисел, то AfxJ может обозначать "х - простое число". Это предложение становится высказыва­ нием, если X заменить числом, например, "3 -простое число", "4-простое чис­ ло". При этом получаем высказывания, которые истинны, либо ложны. Следо­ вательно, AfxJ порождает функцию, область определения которой есть множе­ ство а область значений - множество {И,Л). Предложения, в которых имеются две и более переменных, будем обозна­ чать, например, А(х,у), B(x,y,z) и т. п. При этом х, у, z пробегают все множество !М, аА(х,у), B(x,y,z) при фиксированных х, у, z становятся высказываниями, сле­ довательно, принимают значение И либо Л. Более строго, п-местным предикатом на множестве М называется п- аргументная функция, отображающая множество в множество {И,Л}. Введем операции над предикатами. Пусть А(х), В(х) - заданные на пре­ дикаты. Будем считать, что —AfxJ тоже определяет предикат на причем при фиксированном х=Ь значение высказывания —Afb) противоположно значению высказывания Так же будем образовывать из предикатов Bfx) новые 28