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

VxP(x) равносильно P(ai)&P (a2 )&...&P (arJ, ЗхР(х) равносильно P(aj) vP(a2) v... vP(ar). (2.7) (2.8) Следовательно, квантор всеобщности является обобщением (аналогом) конъюнкции, а квантор существования - обобщением (аналогом) дизъюнкции на произвольное, не обязательно конечное, множество. ^•Хдаедем следующие множества символов: V= [х, у, Z,.., XJ, X2,...,YI, ^2, } - множество (предметных) переменных. А = {а, Ь, с,..., Qi, a2,...,bi, b2,...,ci, С2,...} - множество (предметных) постоян Р= {Af, i >1, « >0} - множество предикатных букв. F = {fP ,i >\, п >1} - множество функциональных букв. Верхний индекс предикатной или функциональной буквы указывает число аргументов, а нижний индекс служит для различения букв с одним и тем же числом аргументов. Символы из V, а также символы —i, &, v, =, (, ) и ,(запятая) считаются логическими символами, а символы из А, Р и F - специальными символами. Будем по возможности опускать числовые индексы у предикатных и функ­ циональных букв, считая, что их легко можно восстановить. Например, вместо Ai fx,у) будем писать АJ fx,у) и, если нет других двухаргументных (двуместных) предикатных букв А, то вместо Ajfx,yJ будем писать А fx,у); кроме того, иногда будем использовать буквы Р, Q, R, S для обозначения предикатных букв Af . Определение терма: а) всякая предметная постоянная или предметная переменная есть терм; б) если f P - функциональная буква и ti,t2,...,t „ - термы, то f P fti,t2,...,Q есть терм; в) выражение является термом только в том случае, если это следует из правил а) и б). 2 2 / Примеры термов: a,xi, f j fx ,а), /5 fa, /2 fy)). Предикатные буквы, примененные к термам, порождают элементарные фор­ мулы или атомы, точнее: если Af - предикатная буква, а ti,t2,...,tn - термы, то Af ft],t2,...,trj - элементарная формула или атом. § 3. Формулы логики предикатов ^ Здесь приведена некоторая копия древнеегипетских записей - иероглифов. Она перерисована из книги С. Коваль, От развлечения к знаниям. Варшава, 1972. 33