Что такое предикат в программировании
Перейти к содержимому

Что такое предикат в программировании

  • автор:

Что такое предикат в программировании

Объекты-функции – это объекты, у которых перегружен оператор вызова функций operator(). В библиотеке STL уже определено несколько полезных арифметических и других объектов-функций (описание в файле ):

Рассмотрим пример с отрицанием всех элементов вектора. Можно выполнить этот пример с помощью цикла, а можно сделать намного проще с использованием алгоритма transform и стандартной функции negate.

vectorint> v; vectorint>::iterator it=v.begin(); while(it != v.end()) < *it = -(*it); it++; >// то же самое с использованием объекта-функции negate transform(v.begin(),v.end(), v.begin(), negateint>()); // вывод контейнера на экран copy(v.begin(), v.end(), ostream_iteratorint>(cout, " "));

Алгоритмы (описание в файле < algorithm>) позволяют выполнять некоторые типовые действия надо контейнерами с использованием объектов-функций стандартной библиотеки или своих объектов-функций. Подробно алгоритмы, функции, и другие возможности библиотеки STL приводятся в Приложении 5.

Стандартные алгоритмы можно использовать и для ввода и вывод контейнера на экран. При чтении ввод происходит до ввода первого не числового символа.

Программисты могут определить свои объекты-функции, которые могут быть наследниками от стандартных. В объектах-функциях обязательно должен быть перегружен оператор вызова функции (), в конструкторе могут задаваться необходимые параметры, или он может быть пустым (см.пример 6.5).

Функции могут быть двух типов:

  • Унарная функция – это функция, в которой участвует один операнд (например, x=-y — унарный минуc)
  • Бинарная функция – это функция, в которой участвуют два операнда (например, x=y+z — сложение, умножение, и т.д.)

Для унарных функций перегруженный оператор вызова функции должен содержать один параметр, в бинарных – два параметра.

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

Функция binder2nd – преобразует бинарную функцию в унарную, и принимает второй аргумент как параметр бинарной функции (описание в файле )

// умножение каждого элемента на 2 transform (v.begin(), v.end(), v.begin(), bind2nd(multipliesint>(), 2));
Пример 6.5. Использование объектов-функций
///////////////////////////////////////////////////////////////////////////// // Прикладное программирование // Пример 6.5. Использование объектов-функций // // Кафедра Прикладной и компьютерной оптики, http://aco.ifmo.ru // Университет ИТМО ///////////////////////////////////////////////////////////////////////////// #include #include #include #include #include using namespace std; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции для заполнения случайными числами // функция Rand - шаблон, наследник от стандартной функции unary_function // параметры шаблона: PAR - тип данных, void - возвращаемое значение оператора () template class PAR> class Rand : public unary_functionvoid> < // диапазон случайных чисел PAR m_min, m_max; public: // конструктор, в котором задается диапазон случайных чисел Rand(PAR min, PAR max) : m_min(min), m_max(max) < >// перегруженный оператор вызова функции, в котором число value заполняется случайным числом void operator() (PAR& value) < value=(PAR)(rand()*(m_max-m_min))/RAND_MAX+m_min; >>; ///////////////////////////////////////////////////////////////////////////// // тестирование объектов-функций STL - negate, ввод-вывод void main() < vectorint> v; // чтение контейнера из потока ввода (до первого не числового символа) copy(istream_iteratorint>(cin), istream_iteratorint>(), back_inserter(v)); // вывод контейнера на экран copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// использование объекта-функции negate transform(v.begin(),v.end(), v.begin(), negateint>()); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// заполнение контейнера случайными числами при помощи объекта-функции Rand for_each(v.begin(), v.end(), Randint>(-10, 10)); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// умножение каждого элемента на 2, // использование стандартной бинарной функции multiplies, // преобразованной в унарную при помощи функции bind2nd transform (v.begin(), v.end(), v.begin(), bind2nd(multipliesint>(), 2)); copy (v.begin(), v.end(),ostream_iteratorint>(cout, " ")); cout /////////////////////////////////////////////////////////////////////////////

6.4.2. Предикаты. Пример 6.6 (использование предикатов)

Предикаты позволяют без изменения шаблона изменять критерии сравнения элементов контейнера и другие подобные действия. У предикатов объект-функция возвращает значение bool.

В файле уже определено несколько полезных предикатов:

  • equal_to бинарный предикат равенства
  • not_equal_to бинарный предикат неравенства
  • greater бинарный предикат >
  • less бинарный предикат < (используется по умолчанию)
  • greater_equal бинарный предикат >=
  • less_equal бинарный предикат
  • logical_and бинарный предикат И
  • logical_or бинарный предикат ИЛИ
  • logical_not унарный предикат НЕ

Например, стандартный алгоритм сортировки сортирует по возрастанию, если мы хотим сделать сортировку по убыванию – можно использовать предикат greater:

// сортировка в порядке убывания sort(v.begin(), v.end(), greaterint>());

Можно определять свои предикаты, как наследники от стандартных объектов-функций.

Пример 6.6. Использование предикатов
///////////////////////////////////////////////////////////////////////////// // Прикладное программирование // Пример 6.6. Использование предикатов // // Кафедра Прикладной и компьютерной оптики, http://aco.ifmo.ru // Университет ИТМО ///////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include using namespace std; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции для заполнения случайными числами // функция Rand - шаблон, наследник от стандартной функции unary_function // параметры шаблона: PAR - тип данных, void - возвращаемое значение оператора () template class PAR> class Rand : public unary_functionvoid> < // диапазон случайных чисел PAR m_min, m_max; public: // конструктор, в котором задается диапазон случайных чисел Rand(PAR min, PAR max) : m_min(min), m_max(max) < >// перегруженный оператор вызова функции, в котором число value заполняется случайным числом void operator() (PAR& value) < value=(PAR)(rand()*(m_max-m_min))/RAND_MAX+m_min; >>; ///////////////////////////////////////////////////////////////////////////// // создание объекта-функции определения попадания числа в диапазон // функция InRange - шаблон, наследник от стандартной функции unary_function // параметры шаблона: int - тип данных, bool - возвращаемое значение оператора () class InRange : public unary_functionint, bool> < // диапазон чисел int m_left, m_right; public: // конструктор, в котором задается диапазон InRange(int left, int right) : m_left(left), m_right(right) <> // перегруженный оператор вызова функции, в котором определяется // попадание числа value в диапазон от m_left до m_right bool operator() (const int& value) < return (value>m_left && value >; ///////////////////////////////////////////////////////////////////////////// // тестирование предикатов void main() < vectorint> v(10); // заполнение контейнера случайными числами при помощи объекта-функции Rand for_each(v.begin(), v.end(), Randint>(-10, 10)); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// сортировка с использованием предиката greater sort(v.begin(), v.end(), greaterint>()); copy(v.begin(), v.end(), ostream_iteratorint>(cout, " ")); cout// использование InRange для подсчета количества элементов в диапазоне от 0 до 10 cout /////////////////////////////////////////////////////////////////////////////

Что такое предикат в программировании

На этом шаге мы рассмотрим использование унарных предикатов .

Особую разновидность вспомогательных функций, используемых алгоритмами, составляют предикаты. Предикатом называется функция, которая возвращает логическое значение. С помощью предикатов часто определяют критерии сортировки или поиска. В зависимости от способа применения предикаты делятся на унарные и бинарные . Учтите, что не любая унарная или бинарная функция, возвращающая логическую величину, является действительным предикатом. STL требует, чтобы при неизменности входных данных предикат всегда давал постоянный результат. Тем самым из категории предикатов исключаются функции, внутреннее состояние которых изменяется в процессе вызова.

Унарные предикаты

Унарный предикат проверяет некоторое свойство одного аргумента. Типичный пример — функция, используемая в качестве критерия поиска первого простого числа:

//--------------------------------------------------------------------------- #include #include #include #include #include //необходимо для getch() #include //для abs <)#pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) < char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; > // Предикат проверяет, является ли целое число простым bool isPrime (int number) < // Знак числа игнорируется number = abs(number); // 0 и 1 не являются простыми числами if (number == 0 || number == 1) < return false; > // Поиск множителя, на который число делятся без остатка int divisor; for (divisor = number/2; number%divisor != 0; --divisor) < ; >// Если не найдено ни одного множителя, большего 1. // проверяемое число является простым. return divisor == 1; > int main(int argc, char* argv[]) < listcoll; // Вставка элементов со значениями от 24 до 30 for (int i=24; i // Поиск простого числа list::iterator pos; pos = find_if (coll.begin(), coll.end(), // Интервал isPrime); // Предикат if (pos != coll.end()) < // Найдено простое число cout else < // Простые числа не найдены cout cout return 0; > //--------------------------------------------------------------------------- 

Текст этого примера можно взять здесь.

В приведенном примере алгоритм find_if() ищет в заданном интервале первый элемент, для которого передаваемый унарный предикат возвращает true . В качестве предиката передается функция isPrime() , которая проверяет, является ли число простым. В итоге алгоритм возвращает первое простое число в заданном интервале. Если алгоритм не находит ни одного элемента, удовлетворяющего предикату, возвращается конец интервала (второй аргумент). Это условие проверяется после вызова. Коллекция из нашего примера содержит простое число между 24 и 30, поэтому результат выполнения программы выглядит так:

Рис.1. Результат работы приложения

На следующем шаге мы рассмотрим бинарные предикаты .

Предикат

Предика́т (лат. praedicatum — заявленное, упомянутое, сказанное) — это то, что утверждается о субъекте. Субъектом высказывания называется то, о чём делается утверждение.

Предикат в программировании — функция, принимающая один или более аргументов и возвращающая значения булева типа.

Далее в этой статье слово предикат используется в значении высказывательной формы.

Определение [ править ]

Предика́т (n-местный, или n-арный) — это функция с множеством значений \< 0,1 \>» /> (или ), определённая на множестве <img decoding=

Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам.

Предикат называют тождественно-истинным и пишут:

 P\left ( x_1, . x_n \right) \equiv 1

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

 P\left ( x_1, . x_n \right) \equiv 0

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д.

Примеры [ править ]

Обозначим предикатом EQ(x, y) отношение равенства («x = y»), где x и y принадлежат R (множеству вещественных чисел). В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.

Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y» для x и y принадлежащих M , где множество M — это множество всех людей.

Предикат — это то, что утверждается или отрицается о субъекте суждения.

Операции над предикатами [ править ]

Предикаты, так же, как высказывания, принимают два значения: истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Логические операции [ править ]

Конъюнкцией двух предикатов A(x) и B(x) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката является пересечение множеств истинности предикатов A(x) — T1 и B(x) — T2, то есть T = T1 ∩ T2. Например: A(x): «x — чётное число», B(x): «x кратно 3». A(x) B(x) — «x — чётное число и x кратно 3». То есть предикат «x делится на 6».

Дизъюнкцией двух предикатов A(x) и B(x) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях x из T, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката является объединение областей истинности предикатов A(x) и B(x).

Отрицанием предиката A(x) называется новый предикат, который принимает значение «истина» при всех значениях x из T, при которых предикат A(x) принимает значение «ложь», если A(x) принимает значение «истина».

Множеством истинности предиката x X является дополнение T’ к множеству T в множестве X.

A\left( x \right)\Rightarrow B\left( x \right)

Импликацией предикатов A(x) и B(x) называется новый предикат , который является ложным при тех и только тех значениях x из T, при которых A(x) принимает значение «истина», а B(x) — значение «ложь», и принимает значение «истина» во всех остальных случаях. Читают: «Если A(x), то B(x)».

A\left( x \right)\Rightarrow B\left( x \right)

Например. A(x): «Натуральное число x делится на 3». B(x): «Натуральное число x делится на 4», можно составить предикат: «Если натуральное число x делится на 3, то оно делится и на 4». Множеством истинности предиката является объединение множества T2 — истинности предиката B(x) и дополнения к множеству T1 истинности предиката A(x).

Кванторные операции [ править ]

  • Квантор всеобщности\forall
  • Квантор существования\exists
  • Квантор существования по переменной x1

См. также [ править ]

В Викисловаре есть статья «предикат»

  • Исчисление предикатов
  • Предикатив
  • Определяющий предикат

Литература [ править ]

  • Гуц А.К. Математическая логика и теория алгоритмов. — Наследие, Диалог-Сибирь, 2003.
  • Ершов Ю.Л., Палютин Е.А. Математическая логика. — М.: Наука, Физматлит, 1987.
  • Игошин В.И. Математическая логика и теория алгоритмов. — Academia, 2008.
  • Клини С.К. Математическая логика. — М.:Мир, 1973.
  • Мендельсон Э. Введение в математическую логику. — М. Наука, 1971.
  • Новиков П.С. Элементы математической логики. — М.:Наука, 1973.
  • Проставив сноски, внести более точные указания на источники.
  • Переработать оформление в соответствии с правилами написания статей.

Python: Предикаты

Функция is_infant() — это функция-предикат или функция-вопрос. Предикат отвечает на утвердительный вопрос «да» или «нет», возвращая значение типа bool. Предикаты во всех языках принято именовать особым образом для простоты анализа. В Python предикаты начинаются с префикса is или has :

  • is_infant() — «младенец ли?»
  • has_children() — «есть ли дети?»
  • is_empty() — «пустой ли?»
  • has_errors() — «есть ли ошибки?»

Функция считается предикатом, если она возвращает булевы значения True или False .

Напишем еще одну функцию-предикат. Она принимает строку и проверяет, является ли она словом ‘Castle’ :

def is_castle(string): return string == 'Castle' print(is_castle('Sea')) # False 

Задание

Напишите функцию is_mister() , которая принимает строку и проверяет, является ли она словом ‘Mister’ .

is_mister('Mister') # True is_mister('Missis') # False 

Упражнение не проходит проверку — что делать? ��

Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:

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

В моей среде код работает, а здесь нет ��

Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.

Мой код отличается от решения учителя ��

Это нормально ��, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.

В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.

Прочитал урок — ничего не понятно ��

Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.

Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.

Полезное

Определения

  • Предикат — выражение, отвечающее на вопрос «да» или «нет» с помощью типа bool.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *