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

становятся высказываниями, следовательно, принимают значение И либо Л. Например, пусть М есть множество всех действительных чи­ сел. Рассмотрим предложение: "х делится нацело на у". Если вместо х и у подставить конкретные числа из 5W, получится высказывание истинное либо ложное. Так, при л'=б, у=3 высказывание "б делится нацело на 3" - истинное, а при х=5, у=1 высказывание "5 делится нацело на 7" - ложное. Рассмотренное предложение "х делится нацело на у" можно обозначить, например, через С{х,у). Такого типа предло­ жения, порождающие функции одного или нескольких переменных, будем считать предикатами. Точнее: предикатом называется повествовательное предложе­ ние об элементах некоторого заданного множества СМ, которое (пред­ ложение) становится высказыванием, если все переменные в нем за­ менить фиксированными элементами из высказывание тоже будем считать предикатом - нулъместным предикатом. Часто вместо "предикат от п переменных " говорят "п-местный предикат". Упражнение. Пусть на множестве М, состоящем из т элемен­ тов, задан 3-местный предикат A{x,y,z). Сколько высказываний об элементах М можно получить, фиксируя переменные предиката А(х^^)1 Введем операции над предикатами. Пусть А(х), Б(х) - заданные на Ж предикаты. Будем считать, что ']А(Х) тоже определяет предикат на М, причем при каждом фиксированном х=Ь значение вы­ сказывания "U(i) противополоясно значению высказывания А(Ь). Так же будем образовывать из предикатов А{х), В(х) новые предикаты с помощью операций &, v, =:>, =. Например, А(х)&В(х) обозначает пре­ дикат, который при фиксированном превращается в сложное вы­ сказывание Аф)&В{Ь), образованное из высказываний Аф) и В(Ь) со­ единением их связкой &. Точно таклсе будем образовывать новые предикаты из произвольных многоместных предикатов. Например, A(x,y)=^C(x,y,z) обозначает предикат, который при фиксированных переменных: х=а, у- Ь, z-c (a,b,ce !М) превращается в высказывание A{a,b):=i>C(a,b,c), образованное из двух высказываний ^(а,6) и С(а,Ь,с соединением их связкой =:>. 48