n-местный предикат Р(х1,…хn) называется функция Р отображается М1х…..Мn->{И,Л}. Переменные этой функции принимают значения их множеств М1 , а сама функция истину или ложь. Говорят , что предикат определен на множествах М1……Мn которые определены обычно контекстом задачи.
Нульместный предикат является высказыванием т.к. при подстановки вместо переменных значений из множеств М1 предикат обращается в высказывания истинное или ложное , то над предикатом можно производить обычные логические операции и в итоге получим новый предикат.
Предикат называется тождественно истинным (ложным) если при любой подстановке вместо х1……хn конкретных значений из Мi он образуется в истинное (ложное) высказывание.
Множеством истинности Р(х1,…хn) заданного на множестве М1……Мn называется совокупность всех упорядоченных наборов значений переменных а1…..аn ? М1х……хМn таких , что функция предикат обращается в истинное высказывание Р(а1,…аn) при подстановке вместо х1=а1 и т.д.
Предикаты P и Q заданы на одних и тех же множествах называются равносильными или эквивалентными если они обращаются в истинное высказывание на одних и тех же наборах значений переменных из соответствующих множеств.
Предикат Q следствие Р заданного на тех – же множествах , что и Q если он обращается в истинное высказывание на всех тех наборах значений переменных из соответствующих множеств на которых в истинное высказывание отображается Р.
Рассмотрим операторы связывания кванторами :
1 Квантор всеобщности . Пусть Р(Х) некоторый предикат принимающий значения истина или ложь для каждого х? М . Тогда под ?х(Р(х)) понимают высказывание “истинное тогда когда ” Р(х) истинно для каждого х из множества М
2 Квантор существования Пусть Р(Х) некоторый предикат принимающий значения истина или ложь для каждого х? М . Тогда под ?х(Р(х)) понимают высказывание истинное тогда когда существует элемент х из множества М, для которого предикат Р(х) истинен.
Кванторы можно применять также к n-местному предикату и в результате получим
n-1местный предикат, переменная к которой относится квантор называют связанной , а остальные свободными .
Формулами логики предикатов называют
1 всякий нульместный предикат есть формула , т.е. предикатным символом 2 всякий n-местный предикат Р(х1,…хn) где х1,…хn предметные переменные 3 если F1 и F2 формулы то @F F=>F формулы. 4 если F формула , то ?х(F(х)) и ?х(F(х)) формулы .
Формулы алгебры предикаты превращаются в формулы при подстановке вместо всех ее предикатных переменных конкретных предикатов.
Формула предикатов называется выполнимой (опровержимой) на М1 если при некоторой подстановке вместо предикатных переменных любых конкретных предикатов задаваемых на этом множестве она превращается в тождественно истинный (ложный) предикат.
Формула алгебры предикатов называется общезначимой или тавтологией (противоречие) если при любой подстановке вместо предикатных переменных любых конкретных предикатов заданных на каких угодно множествах она превращается в тождественно истинный (ложный)
Предикат.
Две формулы алгебры предикатов А и В с одноименными предикатными переменными называются равносильными или эквивалентными если при любой подстановки вместо предикатных переменных любых конкретных предикатов заданных на одних и тех же множествах , эти формулы обращаются в равносильные предикаты.
Свойства операций связывания кванторами.
1 . Пусть -местный предикат Р(х1,…хn) n – местный предикат заданный на множестве М={a1…am} m,n >=1, Тогда n-1 местный предикат для любого равносилен предикату
Р(a1,x2…хn)^ Р(a2,х2,…хn)^……..^ Р(am,х2,…хn).
2 тоже для ? и V .
3 ?х1 Р(х1,…хn) на некотором множестве является тождественно истинным тогда и только тогда когда Р(х1,…хn) n>=2.
4 тоже для ?
Основные равносильности алгебры предикатов.
1 в алгебре предикатов сохранены все равносильности алгебры высказываний для операций ^ V и @ .
2 пусть А(х) любая предикатная формула содержащая свободную переменную х , в А могу быть и другие свободны переменные.