Из истории логики предикатов

Раздел математической логики, изучающий логические законы, общие для любой области объектов

исследования (содержащей

хоть один объект) с заданными на этих объектах

предикатами (т. е.

свойствами и отношениями) называется логикой предикатов.

Основателем логики предикатов считается немецкий математик Готлоб

                           Готлоб ФРЕГЕ                           ^Фреге

Субъект – это то, о чем что-то  утверждается в высказывании

Предикат – это то, что утверждается о субъекте

Переменное высказывание, истинностное значение которого зависит от параметра, называется предикатом или высказывательной формой

Предикат от лат. Praedicatum – «сказанное»

Таким образом, предикат есть функция, определенная на некотором множестве параметров со значениями в {0, 1}

«7 - простое число» – высказывание

Если заменить конкретное число 7 переменной х из множества натуральных чисел, то получим

предикат (высказывательную форму):

«х – простое число»

При одних значения х (например, х=13, х=17) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания

Эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0}

Одноместным предикатом Р(х) называется такая функция одной переменной, в которой аргумент х принимает значения из некоторого множества М, а функция при этом принимает одно из двух значений: истина или ложь

Множество М называется предметным множеством, а аргументы x₁,...,x_n M - предметными переменными

Множество М, на котором задан предикат, называется областью определения предиката

Множество, на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х) N-местным предикатом называется такая функция n переменных

Q(x₁, x₂, …,x_n), определенная на множестве М=М₁М₂…М_n и принимающая на этом множестве одно из двух значений: истина или ложь.

Можно считать, что высказывание - это нульместный предикат, то есть предикат, в котором нет переменных для замены

«ВСЕ любят У» - одноместный предикат   

«ВСЕ любят  КОГО-ТО [некоторого]» нульместный  предикат, то есть высказывание  

«Х  любит  У»  - двухместный  предикат

Пусть предметное множество М есть класс млекопитающих.

Рассмотрим одноместный предикат Р(х): «У х четыре ноги».

Тогда Р(слон) = 1,

Р(кошка) = 1,  Р(человек) =0.

Пусть предметное множество М - множество натуральных чисел. Рассмотрим двухместный предикат G(x,y): х<у.

Тогда, например, G(l,3) = 1, G(8,5) = 0.

 Пусть задан предикат A(Х):

«Город  Х находится в Российской Федерации»

-города Российской Федерации – область истинности предиката А(Х)

Классификация предикатов

Предикат называется тождественно истинным, если значение его для любых аргументов есть «истина»

Пример

Предикат «x+y=y+x» – тождественно истинный

Предикат называется тождественно ложным, если значение его для любых аргументов есть «ложь»

Предикат «x+1=x» – тождественно ложный

Предикат называется выполнимым, если существует, по крайней мере, одна n-система его аргументов, для которой значение предиката есть «истина»

Предикат «x+y=5» – выполнимый

Равносильность предикатов

Два n-местных предиката Р(х₁, х₂, ..., х_n) и Q(x₁, x₂, ..., х_n), заданных над одними и теми же множествами М₁, М₂, …,

М_n, называются равносильными, если набор предметов

(элементов) а₁М₁, а₂М₂, .., a_nМ_n превращает первый предикат в истинное  высказывание Р(а₁, а₂, …, а_n) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное  высказывание Q(а₁, а₂, …, а_n)

Предикаты Р(х₁, х₂, ..., х_n) и Q(х₁, х₂, ..., х_n) равносильны тогда и только тогда, когда их множества истинности совпадают Р+ = Q+

Переход от одного равносильного предиката к другому называется равносильным преобразованием первого

Так как предикаты при подстановке переменных становятся высказываниями и принимают два значения,

«истина» и «ложь» (1 и 0), к ним можно применить все операции алгебры логики

Отрицание предикатов

Довольно часто в математике приходиться строить предложения, в которых что-либо отрицается.

Треугольник АВС не прямоугольный.

Отрицая ложь, мы получаем истину. Отрицая истину, мы получаем ложь

Отрицание предикатов

Отрицание предиката можно образовать с помощью связки «неверно, что» или с помощью частицы «не»

Неверно, что пингвины летают. Пингвины не летают

Обозначают отрицание предиката так же, как и отрицание высказываний

Отрицание предикатов

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

и принимает значение «ложь» при всех переменных, при которых P(x) принимает значение «истина»

Отрицанием предиката P(x) называется новый предикат,  множество истинности которого является дополнением множества истинности  предиката  Р(х)

Конъюнкция предикатов

Конъюнкцией предикатов P(x) и Q(x) называется новый предикат, который принимает значение «истина» при тех и только тех значениях, при которых каждый из

предикатов P(x) и Q(x) принимает значение «истина», и принимает значение «ложь» во всех остальных случаях

Множество истинности есть пересечение множеств

истинности входящих предикатов

IPQ  Ip IIq

Предикаты P(x) – «x>-3» и Q(x) – «x<3»

Конъюнкция предикатов – «(x>-3) Λ (x<3)»

Дизъюнкция предикатов

Дизъюнкцией предикатов P(x) и Q(x) называется новый предикат, который принимает значение «истина» при

тех и только тех значениях, при которых хотя бы один

из предикатов P(x) и Q(x) принимает значение «истина», и принимает значение «ложь» во всех остальных случаях

Множество истинности есть объединение множеств

истинности входящих предикатов

IPQ  Ip UIq

Предикаты P(x) – «x≠0» и Q(x) – «y ≠0»

Дизъюнкция предикатов – «(x ≠0)  v (y ≠0)»

Импликация предикатов

Импликацией предикатов P(x) и Q(x) называется предикат, который имеет значение «ложь» на тех и только на тех наборах аргументов х, на которых

P(x) имеет значение «истина», а Q(x) – значение «ложь»

PxQx

Множество истинности есть объединение  множеств

истинности

IPQ СIp UIq

Импликация предикатов

Импликация предикатов образуется с помощью связки «если….., то»

Предикат «Если 48 кратно 6,то 48 кратно 3» составлен из двух простых предикатов:

А(х): число 48 кратно 6 В(х): число 48 кратно 3

Эквиваленция предикатов

Эквиваленцией предикатов P(x) и Q(x) называется предикат, который имеет значение «истина» на тех и только на тех наборах аргументов х,  на которых

значения истинности P(x) и Q(x) совпадают. 

Множество истинности есть объединение  множеств

истинности

I_PQ  (CI_p ICI_q)U(I_p II_q)

Импликация предикатов

Импликация А(х): Если х+2>0, то x>0 составлена из предикатов Р(х): х+2>0 и Q(x): х>0 T(P)=(-2;+∞)      T(Q)=(0;+∞)

Следовательно, TP  ;2

TPQ TP TQ  ;20;

Пусть даны предикаты P(x): «х – четное число» и Q(x): «х кратно 3», определенные на множестве N. I_p =

{2,4,6,8,10,12,…2n,…}, I_q= { 3,6,9,12,...3n,…}

Найти области истинности предиката: P(x) Λ Q(x)

I _{P(x) Λ} Q(x) = I_p I_q = {2,4,6,8,10,12,…2n,…} { 3,6,9,12,...3n,…} = ={6,12,…6n,…}

Понятие квантора

Квантор — общее

название для логических операций,

ограничивающих

область истинности

какого-либо предиката и создающих

высказывание.

Термин «квантор» был введен английским

логиком Чарльзом

                              Чарльз ПИРС                          Пирсом

Понятие квантора

Квантор (от лат. quantum - сколько) - логическая операция, дающая количественную характеристику

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

В обычном языке носителями таких характеристик служат слова типа "все", "каждый", "некоторый",

"существует", "имеется", "любой", "всякий",

"единственный", "несколько", "бесконечно много",

"конечное число", а также все количественные числительные

Обозначения кванторов

Используют кванторы двух видов:

n  квантор общности (всеобщности)∀— читается

«для любого», «для каждого», «для всех»

n  квантор существования ∃— читается «существует», «найдётся».

Кроме самих кванторов и вместе с ними используют обозначения, которые являются сокращениями:

n  ! – «единственный»;

n  : – «такой, что»; _n | – «такой, что».

Знак «:» обычно используется в формулировках определений или теорем, которые записываются с помощью кванторов.

Знак «|» применяется в определениях множеств

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

Кванторными операциями называются операции, преобразующие предикаты в высказывания

Пусть имеется предикат Р(х), определенный на множестве Х: Р(х): х-четное число

Р(4): «4 - четное число»  - истинное высказывание

Р(5): «5 - четное число» - ложное высказывание

Существуют еще две операции, которые превращают предикат в высказывания

Квантор общности 

Пусть Р(х) – предикат, определенный на множестве Х.

Под выражением

xP(x)

понимают высказывание, истинное, когда

Р(х) истинно для каждого элемента х из множества Х, и ложное в противном случае.

Это высказывание уже не зависит от х.

Соответствующее ему словесное выражение звучит так:

«Для всякого х истинно Р(х)»

Квантор существования 

Пусть Р(х) – предикат, определенный на множестве Х.

Под выражением

xP(x)

понимают высказывание, которое является

истинным, если существует элемент, для которого P(x) истинно, и ложным – в противном случае.

Это высказывание уже не зависит от x.

Соответствующее ему словесное выражение звучит так:

«Существует x, при котором P(x) истинно»

Обозначения кванторов

x(x² 1 (x1)(x1)) Для всех х выполняется предикат…

x(x  0)

x(x  0)

y | (5y 5)

y(y² y1 0) y | (y² y1 0)

x(x³ x²)

Для некоторого х справедливо неравенство...

Для всех х справедливо…..

Существует y такой, что …

Для всех y выполняется предикат

Существует y такой, что …

Для некоторого х справедливо неравенство...

Переменную х в предикате Р(х) называют свободной.

Ей можно придавать различные значения из Х.

В высказываниях

xP(x) и xP(x) переменную х называют связанной квантором (на нее навешен квантор)

Пусть задан предикат Р(х): «x кратно 5»

1) С помощью квантора общности можно записать высказывания:

q  любое натуральное число делится на 5;

q  каждое натурально число делится на 5; q все натуральные числа делятся на 5.

Формула любого из высказываний будет выглядеть так: (∀x∈N)P(x).

Составленные высказывания ложны

2) С помощью квантора существования можно записать высказывания:

q  существуют натуральные числа, которые делятся на 5;

q  найдется натуральное число, которое делится на 5; q хотя бы одно натуральное число делится на 5.

Формула любого из высказываний будет выглядеть так: (∃x∈N)P(x).

Составленные высказывания истинны

На множестве x простых чисел существует предикат: «Простое число является нечетным».

Если перед предикатом поставить слово «любое», то получим ложное высказывание

«Любое простое число является нечетным».

Если перед предикатом поставить слово «существует», то получим истинное высказывание

«Существует простое число, которое является нечетным».

Таким образом, предикат можно превратить в высказывание, если поставить перед ним квантор

Сравните!

Предикат Мать(x,y) означает, что x является матерью для y. Тогда

yxМать(x,y) означает, что у каждого человека есть мать, истинное утверждение.

x yМать(x,y) означает, что существует мать всех людей, что является другим утверждением, истинность которого зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, а в противном случае оно ложно.

Таким образом, перестановка кванторов всеобщности и существования может изменить смысл и значение выражения

Задание 1

Среди следующих предложений выделите предикаты:

1)         Луна есть спутник Венеры

2)         Планеты х и y принадлежат Солнечной системе

3)         5⁵ 70⁶ 10 150

4)         x^[1] 3x20

5)         x⁴ 3x8

6)         Любое простое число не имеет делителей, отличных от себя и 1

7)         Натуральное число n не меньше 1

8)         Треугольник АВС равен треугольнику А₁В₁С₁

9)         x² 2x10

Среди следующих предложений выделить предикаты и для каждого из них указать область истинности: 1) x+5=1

2) При х=2 выполняется равенство х²-1=0 3) х²-2x+1=0 4) Существует такое число х, что х^2-2x+1=0

5)   x+2<3x-4

6)   Однозначное число x кратно 3

7)   (x+2)-(3x-4)

Пусть даны предикаты P(x): «х – четное число» и Q(x):

«х кратно 3», определенные на множестве N. I_p =

{2,4,6,8,10,12,…2n,…}, I_q= { 3,6,9,12,...3n,…}

Найти области истинности предикатов:

1)       P(x) v Q(x)

2)       ¬P(x)

3)       P(x) -> Q(x)

Задание 4

Если значения x,y принадлежат отрезку [2;5], то в списке выражений следующего вида:

1)             х=2 или y=7

2)             x-y=7

3)             x+y<2

4)             x² 50

5)             3<x<y<5

6)             x>12 число истинных и ложных предикатов соответственно равно:

А) 2,4

Б) 1,4

В) 3,3

Г) 1,5

Д) 2,3