Предикаты. Кванторы

Предикат – это функция с множеством значений {0,1}, определенная на множестве М=M₁xM₂x…xM_n. Каждый набор элементов множества М он характеризует либо как истинный, либо как ложный. Предикат также называют функцией-высказыванием. Пример: «Река х впадает в озеро Байкал» - одноместный предикат, определенный над множеством всех названий рек. Подставим вместо х реку «Баргузин» - высказывание истинно. Подставим вместо х реку «Днепр» - высказывание ложно. Предикаты бывают: тождественно истинными (при любых подстановках превращается в истинное высказывание), тождественно ложными (при любых подстановках превращается в ложное высказывание) и выполнимыми [опровержимыми] (при подстановке может превратиться как в истинное, так и в ложное высказывание в зависимости от подставляемых значений). Справедливы следующие закономерности: 1) каждый тождественно истинный предикат является выполнимым, но обратное неверно 2) каждый тождественно ложный предикат является опровержимым, но обратное неверно 3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным 4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным. Множество истинности предиката Р(x₁,x₂, …, x_n) заданного на множествах М₁, М₂, М_n – совокупность всех упорядоченных n-систем (a₁,a₂, …, a_n), в которых a₁ЄM₁, a₂ЄM₂, …, a_nЄM_n, таких что данный предикат обращается в истинное высказывание Р(a₁,a₂, …, a_n) при подстановке x₁=a₁, x₂=a₂, …, x_n=a_n. Это множество обозначается P⁺. P⁺={(a₁,a₂, …, a_n): λ(P(a₁,a₂, …, a_n))=1}. Равносильность предикатов. Два n-местных предиката P(x₁, x₂, …, x_n) и Q(x₁, x₂, …, x_n), заданных над одними и теми же множествами M₁, M₂, …, M_n называются равносильными, если набор элементов a₁ЄM₁, a₂ЄM₂, …, a_nЄM_n превращает первый предикат в истинное выражение в том и только в том случае, когда этот набор элементов превращает второй предикат в истинное выражение. Иначе говоря, когда совпадают их множества истинности. Символически равносильность записывается так: P↔Q. Следствие предикатов. Предикат Q(x₁, x₂, …, x_n) заданный над множествами M₁, M₂, …, M_n называется следствием предиката P(x₁, x₂, …, x_n), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат P(x₁, x₂, …, x_n). Другими словами, когда множество истинности одного является подмножеством истинности другого. Например, предикат «n делится на 3» является следствием предиката «n делится на 6». Следствие символически записывается так: P→Q (Q - следствие P). Справедливы следующие теоремы: 1) Каждые два тождественно истинных (ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (ложному) предикату сам является тождественно истинным (ложным). 2) Каждый тождественно истинный n-местный предикат является следствием любого другого n-местного предиката, определенного на тех же множествах. Каждый n-местный предикат является следствием любого тождественно ложного n-местного предиката, определенного на тех же множествах. Над предикатами можно проделывать те же самые операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность. Кроме того над предикатами можно проделывать кванторные операции. Квантор - общее название для логических операций, ограничивающих множество истинности какого-либо предиката. Чаще всего упоминают квантор всеобщности () – «для всех» и квантор существования () – «существует». В математической логике приписывание квантора к формуле называется связыванием или навешиванием квантора. Существует также квантор плюральности (квантор Решера) W (перевёрнутая M). Wx означает «для большинства x». Используя кванторы можно получить, например, следующее высказывания: 1) любое натуральное число кратно 5; 2) каждое натуральное число кратно 5; 3) все натуральные числа кратны 5; 4) существуют натуральные числа, кратные 5; 5) найдется натуральное число кратно 5; 6) хотя бы одно натуральное число кратно 5. Первое высказывание запишется так: , где P(x): «Простое число х – нечетно». Это высказывание ложно. Высказывание означает, что множество истинности предиката P(x) совпадает с областью значений переменной x. Высказывание означает, что множество истинности предиката P(x) непустое.