Предикаты и кванторы
- Понятие предиката
- Примеры предикатов
- Операции над предикатами
- Кванторы
- Примеры применения кванторов
- Операции над кванторами
Понятие предиката
Утверждения, содержащие в себе переменные, обладающие способностью принимать значения 0 или 1 (ложно или истинно) в зависимости от принимаемых переменными значений, называют предикатами.
В качестве примера может быть рассмотрено выражение x=x^5 представляет собой предикат, поскольку оно будет истинным исключительно в случае принятия переменной x значений 0 или 1 и будет ложным в случае присвоения переменной x всех стальных отличных от 0 и 1 значений.
Множеством истинности Ip любого предиката называют такое множество значений, которое может принимать переменная, позволяющих предикату принимает исключительно истинные значения.
В программировании предикатом принято считать функции, принимающие значения одного или большего числа аргументов и возвращающих значения логического (булевого) типа.
Тождественно-истинным называют предикат, способный принимать истинное значение в случае использования любого набора значений аргумента:
(P(x1,…,xn)=1)
Предикат, для которого использование любого набора значений аргумента приводит к принятию им ложного значения, называют тождественно-ложным:
(P(x1,…,xn)=0)
В случае если предикат приобретает истинное значение при использовании хотя бы одного набора значений аргумента, его считают выполненным.
Поскольку предикаты обладают способностью принимать исключительно значения двух видов – ложно или истинно (0 или 1), к ним могут быть применены все операции, относящиеся к алгебре логики: дизъюнкция, конъюнкция, отрицание и т.п.
Примеры предикатов
Допустим, что предикат, имеющий вид R(x,y): «x = y», где переменные x и y являются целыми числами, является обозначением отношения равенства. Принятие предикатом R истинного значения будет происходить исключительно в случае равенства всех x и y.
В качестве другого примера может быть рассмотрен предикат, имеющий вид ТРУДИТСЯ(x,y,z) образованный для отношения «x трудится в населённом пункте y на предприятии z».
Примером ещё одного вида может служить предикат - СИМПАТИЗИРУЕТ(x,y) характеризующий отношение «x симпатизирует y» для переменных x и y, принадлежащих к множеству М, включающему в себя всех людей.
На основании сказанного выше можно сделать вывод о том, что предикат представляет собой любое суждение об объекте, которое отрицается либо, утверждается.
Операции над предикатами
К предикатам могут быть применены операции, относящиеся к алгебре логики. Рассмотрим особенности применения подобных операций.
Операции логического характера:
Конъюнкцией предикатов A(x) и B(x) называют предикат нового вида, принимающий истинное значение исключительно при тех значениях переменной x из множества значений T, которые позволяют каждому из обоих предикатов приобретать истинное значение, в то время как ложное значение будет ими приниматься во всех иных случаях. Подобному предикату соответствует множество истинности T представляющее собой пересечение соответствующих заданным предикатам A(x) и B(x) множеств истинности. К примеру, если предикат A(x) характеризует отношение «x – число чётное», а предикат B(x) обозначает отношение «x делится на число 5», то конъюнкцией подобных предикатов станет предикат, характеризующий отношение следующего вида: «x – число чётное и кратно числу 5» или «x кратно 10».
Дизъюнкцией для предикатов A(x) и B(x) является предикат нового вида, принимающий ложное значение исключительно при тех значениях переменной x из множества значений T, которые позволяют каждому из обоих предикатов приобретать ложное значение, в то время как истинное значение будет ими приниматься во всех иных случаях. Ему соответствует множество истинности, представляющее собой пересечение соответствующих заданным предикатам A(x) и B(x) множеств истинности.
Отрицанием предиката A(x) является предикат нового вида, принимающий истинное значение в случае принятия переменной x всех значений из множества T, которые позволяют принимать предикату A(x) ложное значение или наоборот. Для подобного предиката множество истинности будет представлять собой дополнение T’ к соответствующему предикату A(x) множеству истинности.
Импликацией для предикатов A(x) и B(x) является предикат нового вида, принимающий ложное значение исключительно при тех значениях переменной x из множества значений T, которые позволяют предикату A(x) обретать истинное значение, в то время как предикат B(x) принимает значение ложное, принимая истинное значение во всех иных случаях. Запись подобной операции обычно имеет вид: «Если A(x), то B(x)».
Допустим, существуют предикаты A(x): «число x является натуральным и делится на 3» и B(x): «число x является натуральным и делится на 4».
Может быть составлен предикат определяющий отношение «если число x является натуральным и делится на 3, то такое число делится и на 4».
Для такого предиката множеством истинности будет иметь вид объединения множества истинности для B(x) и дополнения к множеству истинности для A(x).
Кроме операций логического характера над предикатами могут выполняться квантовые операции – это использование кванторов существования, всеобщности и т.п.
Кванторы
Применяемые к предикатам логические операторы, превращающие их в высказывания, имеющие истинное или ложное значение, называются кванторами.
Существует другое определение кванторов, согласно которому, это логические операции, создающие высказывание и ограничивающие для предикатов, к которым они применяются, их область истинности.
Наиболее часто применяемыми являются следующие кванторы:
- обозначаемый символом ∀, квантор всеобщности, который соответствует выражениям, имеющим вид «для всех значений x», «для любого значения x» и т.п.;
- обозначаемый символом ∃, квантор существования, который соответствует выражению, имеющему вид «существует значение x такое, что…»;
- обозначаемый символом ∃!, квантор существования и единственности, который соответствует выражению имеющему вид «существует всего одно такое значение x, что…».
Процессу приписывания квантора к формуле в математической логике соответствует понятие квантификации или связывания.
Примеры применения кванторов
Допустим, существует предикат, описывающий отношение «x кратно 7».
Применяя квантор всеобщности, ложные высказывания могут быть записаны следующим образом:
- любое число, являющееся натуральным, делится на 7;
- каждое из чисел, являющихся натуральным, делится на 7;
- все существующие числа, являющиеся натуральными, способны делиться на 7.
Такой квантор будет иметь следующий вид:
- ( (∀x ∈ N)P(x) )
Применяя квантор существования, истинные высказывания в отношении этого же предиката могут быть записаны следующим образом:
- существуют числа, являющиеся натуральными, которые делятся на число 7;
- может быть найдено натуральное число, кратное числу 7;
- существует хотя бы одно число, являющееся натуральным, способное делиться на число 7.
Запись данного квантора приобретёт вид:
- ( (∃x ∈ N)P(x) )
Допустим, для множества некоторых простых чисел x образован предикат, описывающий отношение «простое число является числом нечётным». Если перед предикатом вставить слово «любое» получим в результате ложное высказывание, имеющее вид: «любое простое число одновременно является числом нечётным» (число 2, например, будучи числом простым, являясь при этом чётным числом).
Если перед предикатом вставить слово «существует» получим в результате истинное высказывание в виде: «существует простое число, одновременно являющееся нечётным» (x=3, к примеру).
На основании сказанного выше можно заключить, что предикат может быть превращён в высказывание путём присоединения квантора перед ним.
Операции над кванторами
Применяемым для образования отрицания высказываний, содержащих кванторы, является правило отрицания кванторов, имеющее вид:
( ¬(∀x)P(x) = (∃x)¬P(x) )
( ¬(∃x)P(x) = (∀x)¬P(x) )
Для примера рассмотрим некоторые предложения, определив среди них предикаты и область истинности для них:
- предложение x – 2 = 0 – представляет собой предикат с множеством истинности Ip = {2};
- выполняемое при x=3 равенство x^2 - 8 = 0 - не является предикатом, являясь ложным высказыванием;
- предложение x^2 - 4 x + 4 = 0 - является предикатом с множеством истинности Ip = {2};
- существует такое значение переменной x при котором x^2 - 4 x + 4 = 0 - не является предикатом, являясь истинным высказыванием;
- предложение x – 2 < 3x + 4 – является предикатом с множеством истинности Ip = {-3;∞};
- однозначное число x кратно 5 - предикат с множеством истинности Ip = {0;5};
- предложение x – 6 + (2x + 5) – не является предикатом;
- предложение x^2 + y^2 > 0 – является предикатом, для которого область истинности это вся плоскость координат за исключением точки с координатами (0;0).