Конспект лекций Дискретная математика

Предикаты.

Определение. Предикатом называется функция , где произвольное множество, а определённое ранее двоичное множество .

Иначе говоря, местным предикатом, определённым на множестве называется двузначная функция от аргументов из произвольного множества . Множество называется предметной областью предиката, переменные - предметными переменными. В принципе, можно определить предикат как функцию , то есть допустить, что переменные принимают значения из различных множеств – в некоторых случаях это оказывается удобным.

Для любых и существует взаимно однозначное соответствие между местными отношениями и местными предикатами на множестве , определяемое следующим образом. Каждому местному отношению соответствует предикат такой, что тогда и только тогда, когда ; всякий предикат определяет отношение такое, что тогда и только тогда, когда . При этом задаёт область истинности предиката.

Всякой функции можно поставить в соответствие местный предикат такой, что тогда и только тогда, когда . Поскольку функция должна быть однозначной, то это соответствие требует, чтобы для любого выполнялось . Поэтому обратное соответствие (от предиката к функции) возможно только при выполнении указанного условия.

В дальнейшем, в случаях, не вызывающих разночтения, будем употреблять одинаковые обозначения для предикатов и соответствующих им отношений. При этом, помимо функциональных обозначений вида , для двухместных предикатов будем пользоваться обозначениями вида , которые употреблялись ранее для бинарных отношений.

Пример 1.

а) Предикат является двухместным предикатом, предметной областью которого могут служить любые множества действительных чисел. Высказывание истинно, а высказывание ложно. Если вместо одной из переменных подставить число, то получится одноместный предикат: и так далее.

б) Великая теорема Ферма (до сих пор не доказанная) утверждает, что для любого натурального числа не существует натуральных чисел , которые удовлетворяли бы равенству . Этому равенству можно поставить в соответствие предикат , истинный тогда и только тогда, когда оно выполняется.

в) В описаниях вычислительных процедур и, в частности, в языках программирования, часто встречаются указания типа “повторять цикл до тех пор, пока переменные и не станут равными или прекратить вычисление цикла после ста повторений”. Если обозначить через счётчик повторений, то описанное здесь условие примет вид , а само указание в целом описывается выражением: “повторять, если ”.

Содержание