Предикаты что это в алгебре
Предикат
Предика́т (n-местный, или n-арный) — это функция с областью значений 
(или «Истина» и «Ложь»), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M он характеризует либо как «истинную», либо как «ложную».
Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1.
Предикат называют тождественно-истинным и пишут:
P
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно-ложным и пишут:
P
если на любом наборе аргументов он принимает значение 0.
Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1.
Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д.
Примеры
Например, обозначим предикатом EQ(x, y) отношение равенства («x = y»), где x и y принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.
Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y», где множество M — это множество всех людей.
См. также
cs:Predikát eo:Predikato (logiko) et:Predikaat pl:Funkcja zdaniowa
MT1102: Линейная алгебра (введение в математику)
При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение %%P(x) : x^2 + 1 > 2%% с переменной %%x \in \mathbb R%%. Это предлождение не является высказыванием, так как нельзя сказать истинно оно или ложно. Однако, если заменить переменную %%x%% на какое-либо значение, например, %%x = 1%%, получаем высказывание %%2 > 2%%, которое является ложным. Заменив переменную %%x%% на значение %%x = 2%%, получим истинное высказывание %%5 > 2%%. Итак есть выражение %%P(x)%% не являющиееся высказыванием, но превращающееся в него при замене переменной %%x%% на ее произвольное значение из соответствующего множества.
Определение
Одноместным предикатом, определенным на множестве %%D%%, называется предложение с переменной, которое превращается в высказывание при замене этой переменной на ее значение из множества %%D%%. Одноместный предикат будем называть унарным или предикатом от одной переменной.
Примеры
Следующие предложения являются одноместными предикатами:
Следующие предложения не являются одноместными предикатами:
%%n%%-местный предикат
%%n%%-местым предикатом с областью определения %%D = D_1 \times D_2 \times \ldots \times D_n%% называется предикат %%P(x_1, x_2, \ldots, x_n)%% от %%n%% переменных, который превращается в высказывание при замене переменных %%x_1, x_2, \ldots, x_n%% на их значения из множеств %%D_1, D_2, \ldots, D_n%% соответственно.
Тогда предложение прямая %%x%% параллельна прямой %%y%% является двуместным предикатом %%P(x, y)%%, где %%X, Y%% — множество всех прямых.
Область определения предиката
Рассмотрим %%n%%-местный предикат %%P(x_1, x_2, \ldots, x_n)%%. В этом случае переменные берутся из множеств %%D_1, D_2, \ldots, D_n%% соответственно. Можно рассмотреть множество %%D = D_1 \times D_2 \times \ldots \times D_n%% — декартово произведение множеств %%D_1, D_2, \ldots, D_n%%, элементами которого являются всевозможные упорядоченные %%n%%-ки %%(d_1, d_2, \ldots, d_n)%% элементов исходных множеств.
Множество %%D%% называется областью определения предиката.
Область истинности
Пример
На множестве %%D = \< 1, 2, 3, 4, 5, 6, 7, 8, 9\>%% рассмотрим одноместный предикат %%P(x): x%% — простое число. Найти область истинности предиката %%P(x)%%.
Обозначим область истинности буквой %%A%%. Тогда %%A%% состоит из таких элементов, при которых выполняется предикат %%P(x)%%. Поэтому %%A = \<2, 3, 5, 7\>%%.
Операции над предикатами
Аналогично операциям для высказываний вводятся операции для предикатов.
Пусть %%P(x)%% и %%Q(x)%% — одноместные предикаты, определенные на множестве %%D%%.
Отрицанием предиката %%P(x)%% называется новый предикат, обозначаемый %%\overline
Конъюнкцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \land Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% истинны.
Дизъюнкцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \lor Q(x)%% и являющийся ложным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% ложны.
Импликацией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \rightarrow Q(x)%% и являющийся ложным для тех и только тех %%x%%, для которых предикаты %%P(x)%% истинный, а %%Q(x)%% ложный.
Эквиваленцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) \leftrightarrow Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% имеют одинаковые значения.
Применяя операции над предикатами, мы получаем составные предикаты, которые будем называть формулами алгебры предикатов.
Законы алгебры предикатов
В случае тождественно истинных и тождественно ложных предикатов имеем следующие определения.
Предикат %%P(x_1, x_2, \ldots, x_n)%% называется тождественно истинным если при любой замене переменных %%x_1, x_2, \ldots, x_n%% на их значения предикат превращается в истинное высказывание.
Предикат %%P(x_1, x_2, \ldots, x_n)%% называется тождественно ложным если при любой замене переменных %%x_1, x_2, \ldots, x_n%% на их значения предикат превращается в ложное высказывание.
Высказывание является частным случаем предиката, когда в предикате нет переменных. То есть высказывание является предикатом %%0%% порядка (от %%0%% переменных).
Предикаты и кванторы
Вы будете перенаправлены на Автор24
Понятие предиката
Предикатом в программировании является функция, которая принимает один или более аргументов и возвращает значения булева типа.
Предикат называется тождественно-истинным, если на любом наборе аргументов он принимает истинное значение:
Предикат называется тождественно-ложным, если на любом наборе аргументов он принимает ложное значение:
Предикат называется выполнимым, если хотя бы на одном наборе аргументов он принимает истинное значение.
Примеры предикатов
Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.
Готовые работы на аналогичную тему
Операции над предикатами
Рассмотрим применение операций алгебры логики к предикатам.
Логические операции:
Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.
Кванторы
Чаще всего используют кванторы:
В математической логике существует понятие связывание или квантификация, которые обозначают приписывание квантора к формуле.
Примеры применения кванторов
С помощью квантора всеобщности можно записать следующие ложные высказывания:
который будет иметь вид:
Для записи истинных высказываний используем квантор существования:
Запись будет иметь вид:
Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.
Операции над кванторами
Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов:
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них:
Получи деньги за свои студенческие работы
Курсовые, рефераты или другие работы
Автор этой статьи Дата написания статьи: 07 04 2016
Высказывания и предикаты. Кванторы
п.1. Высказывания
Например:
«Число 13 – нечётное» – высказывание, истинное
«2 + 2 = 5» – высказывание, ложное
«Мы живём в XXI веке» – высказывание, истинное
«Который час?» – не высказывание, т.к. вопросительное предложение
«Вася Пупкин – хороший человек» – не высказывание, т.к. неоднозначно. Но, если определить множество людей, которые оцениваются, и правила их оценки так, что предложение приобретёт однозначность, оно станет высказыванием.
Например:
A: натуральное число a делится на 2;
B: натуральное число a чётное.
Заметим, немного забегая наперёд, что в данном случае из А следует В, и из В следует А. Говорят, что эти высказывания эквивалентны: A ⇔ B.
п.2. Предикаты
Например:
P(x): x – объект с четырьмя ногами
При x = слон – предикат становится истинным высказыванием, P(«слон» )=1
При x = муравей – предикат становится ложным высказыванием, т.к. у муравья 6 ног, P(муравей)=0
При x = стол – предикат становится истинным высказыванием, P(«стол» )=1
При x = человек – предикат становится ложным высказыванием, т.к. у человека 2 ноги, P(человек)=0
Например:
P(x):|x| ≥ 0 – выполняется при любом значении x, это тождественный предикат.
\(\mathrm
Например:
P(x, y): x делится на y – двуместный предикат, который становится истинным высказыванием на парах значений переменных (15;5), (14;7), (16;4) и т.д.
P(a, b):(a + b) 2 = a 2 + 2ab + b 2 – является тождественным двуместным предикатом, т.к. выполняется для любых a и b.
п.3. Кванторы
«для любого…», «для всех…», «любой…»
Единственности и существования
«существует точно одно такое, что…», «существует и единственно…»
Существуют натуральные числа, которые делятся на 13
Существуют треугольники, у которых все углы равны
Например, равносторонний треугольник со стороной 1
Любое натуральное число делится на 5
Например x = 6 на 5 не делится
У любого выпуклого четырехугольника диагонали перпендикулярны
Например, у прямоугольника со сторонами 3 и 4 угол между диагоналями ≈ 74° ≠ 90°
Разность квадратов двух любых выражений равна произведению суммы и разности
Сумма углов любого треугольника равна 180°.
Третий класс задач (теорема) – самый сложный, т.к. требует не просто одного примера, а доказательства в общем случае.
п.4. Примеры
Пример 1. Запишите по два высказывания (A – истинное, B – ложное), относящиеся к
а) физике
A: Плотность равна отношению массы тела к его объему.
B: КПД механизма может быть больше 1.
б) химии
A: Гидроксид натрия – сильное основание.
B: Сульфат натрия – нерастворимая соль.
в) географии
A: На Земле шесть материков.
B: На Земле три океана.
Пример 3. С каким из кванторов предикат x 2 + 4 = 12 станет истинным высказыванием?
Если запишем (∀x) x 2 + 4 = 12 – это ложное высказывание, т.к., например, при x=0 оно не выполняется.
Если запишем (∃x) x 2 + 4 = 12 – это истинное высказывание, т.к., например, при \(\mathrm
Если запишем (∃x!) x 2 + 4 = 12 – это ложное высказывание, т.е. решений у данного уравнения не одно, а два: \(\mathrm
Ответ: квантор существования ∃.
Алгебра предикатов
Логика, алгебра и исчисление предикатов
Определение. Одноместным предикатом P(x)называется произволь-ная функция переменного x, определённая на множестве Mи принимаю-щая значения из множества <1,0>.Множество M, на котором определён предикат P(x), называется областью определения предиката. Множество всех элементов xÎM, при которых предикат P(x), принимает значение “истина” называется множеством истинности предиката и обозначается Ip. Предикат P(x) называется тождественно истинным (тождественно ложным) на множестве M, если Ip = M (Ip= Æ).
Пример:Предикат P(x) ”Диагонали параллелограмма x перпендикуляр-ны” определён на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.
Одноместные предикаты выражают свойства предметов. Обобщением по-нятия одноместного предиката является понятие многоместного предиката с помощью которого выражаются отношения между предметами.
Простейшими логическими операциями над предикатами, так же как и для высказываний, являются: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность, которые обозначаются с помощью тех же символов, что и для высказываний.
Определение. Отрицаниемпредиката P(x)называется новый предикат ù P(x),который принимает значения “истина” при всех значениях xÎM, при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях xÎM, при которых предикат P(x)принимает значение “истина”. Областью истинности предиката является: ùI p =-Ip.
Пример: Для одноместного предиката “X больше двух”, определённого на множестве действительных чисел, отрицанием будет одноместный предикат “X не больше двух”, также определённый на множестве действительных чисел.
Определение. Конъюнкцией двух одноместных предикатов P(x)и Q(y)называется новый двухместный предикат P(x)ÙQ(y), который принимает значение “истина” при тех и только тех значениях xÎM yÎN, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях. Областью истинности предиката является: I pÙq = IPÇIQ.Пример: Для одноместного предиката “X-чётное число” и одноместного предиката “точка y лежит на прямой”, определённых на множестве натуральных чисел и множестве точек, конъюнкцией этих предикатов будет двухместный предикат “X-чётное число и точка y лежит на прямой”.
Определение. Импликацией двух одноместных предикатов P(x) и Q(y) называется двухместный предикат P(x)®Q(y), который принимает значение “ложь” при тех и только тех значениях xÎMиyÎN,при которых P(x) принимает значение “истина” и Q(y) принимает значение “ложь”,во всех остальных случаях предикат P(x)®Q(y) принимает значение “истина”. Областью истинности предиката является: Ip®q=IùPÈIQ-это следует из A ® B = ù A Ú B. Пример: Для одноместных предикатов, определённых на одном и том же множестве целых чисел “x-делится на шесть” и “x-делится на три” импликацией будет одноместный предикат, определённый на том же множестве: “если x-делится на шесть, то x-делится на три”.
Определение. Эквивалентностью двух одноместных предикатов P(x) и Q(y) называется двухместный предикат P(x)«Q(y), который принимает значение “истина” при тех и только тех значениях xÎMиyÎN, при которых P(x) и Q(y)принимают одинаковые значения и “ложь” во всех остальных случаях. Областью истинности предиката является: I p«q =(IùPÈIQ)Ç(IùQÈIP)-это следует из A « B = ( A ® B ) Ù ( B ® A ) и A ® B = ù A Ú B. Пример: Для двух одноместных предикатов “x-делится на два” и “x-чётное число” эквивалентностью будет “x-делится на два тогда и только тогда, когда x-чётное число”.Операции конъюнкции, дизъюнкции, импликации и эквивалентности можно применять также к предикатам, у которых общие переменные (с одинаковой областью определения). В таком случае число переменных конъюнкции и дизъюнкции, а следовательно и местность этих предикатов будет равняться числу различных (с разной областью определения) переменных предикатов, составляющих эти дизъюнкцию, конъюнкцию, импликацию и эквивалентность (смотри два последних примера).
В алгебре предикатов по сравнению с алгеброй высказываний появляются новые, дополнительные логические операции квантификации, которыми являются квантор всеобщности и квантор существования.
Определение. Пусть P(x)-предикат определённый на множестве M. Под выражением «x P(x) понимают высказывание, истинное, когда P(x) тождественно истинный на множестве M предикат и ложное в противном случае. Соответствующее ему словесное выражение будет: “Для всякого x P(x) истинно”. Символ « называют квантором всеобщности.
Можно показать, что перестановка любых кванторов местами для многоместных предикатов изменяет логическое значение высказывания. Пример: Пусть предикат Q(x,y) “y делитель x“ определён на множестве натуральных чисел. Тогда высказывание «y$xQ(x,y),-”Для всякого натурального числа y существует натуральное число xтакое, что y является делителем x“ истинно, а высказывание $x»yQ(x,y), отличающееся от предыдущего перестановкой кванторов и означающее, что “Есть натуральное число x, которое делится на любое натуральное число y“ ложно.
В алгебре предикатов будем пользоваться следующей символикой:
— P(·),F(·)-одноместные предикатные переменные; Q(·,·. ·),R(·,·. ·)— n-местные предикатные переменные;
—P°(·),Q°(·,·. ·)-символы постоянных предикатов.
— символы логических операций: Ù,Ú,®,ù.
— символы кванторных операций:»x,$y.
— вспомогательные символы: скобки, запятые.
Правилами описания формул алгебры предикатов являются следующие:
-каждое высказывание как переменное, так и постоянное, является формулой(элементарной).
-если F(·,·. ·)- n-местная предикатная переменная или постоянный предикат, а x1,x2,¼xn предметные переменные или предметные постоянные (не обязательно все различные), то F(x1,x2,¼xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
-если P(x)-формула, в которую предметная переменная x входит свободно, то слова «xP(x) и $xP(x)являются формулами, причём предметная переменная входит в них связано.
— всякое слово, отличное от тех, которые выше названы формулами, формулами не являются.
здесь в формулу «xQ(x,y) переменная x входит связано, а в формулу P(x), переменная xвходит свободно. Логическое значение формулы алгебры предикатов зависит от значений трёх видов переменных:
· значений, входящих в формулу переменных высказываний;
· значений свободных предметных переменных из множества M;
· значений предикатных переменных.
При конкретных значениях каждого из трёх видов переменных формула алгебры предикатов становится высказыванием, имеющим истинное или ложное значение.
Пример: Рассмотрим формулу: $y»z(P(x,y)®P(Y,Z)),в которой двухместный предикат P(x,y)-определён на множестве M´M, где M = <0,1,2. n. >.В эту формулу входит переменный предикат P(x,y)-предметные переменные x, Y, Z, две из которых Y и Z-связанные квантором, а x-свободная. Возьмём за конкретное значение предиката P(x,y)фиксированный предикат P°(x,y): “x
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет