Материал: 5540

R(x, r) : " x 1 r";

S (a, b, c) : " а нравится b больше, чем с”. Запишите следующие высказывания:

а) Р(3, 4, 5); б) Q(8, 2); в) R(3, 7);

г) S(Джон, Сью, Мэри). Задача 4.2. Заданы предикаты:

P(x, y, z) : "x2 y2 z2";

Q(x, y) : "если y x2 , то х у"; R(a, b, x) : "a x2 b";

S (a, b) : " а играет в теннис лучше, чем b”. Запишите следующие высказывания:

а) Р(3, 4, 5); б) Q(– 2, 2); в) R(0, 4, – 3);

г) S(Джон, Фред).

Над предикатами можно проделывать те же самые логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность.

Отрицание. Пусть n-местный предикат Р(х1, х2, ..., хn) определён на множествах М1, М2, ..., Мn. P(x1, x2 , ..., xn ) определяется как такой предикат, определённый на М1, М2, ..., Мn, что для любых предметов a1 M1 , a2 M 2 , ..., an Mn высказывание P(a1, a2 , ..., an ) является отрицанием высказывания Р(а1, а2, ..., аn).

Конъюнкция. Пусть n-местный предикат Р(х1, х2, ... , хn) определён на

определяется как такой (n + m)-местный предикат, определённый на множествах М1, М2, ... , Мn, N1, N2, ... , Nm, что для любых предметов a1 M1 , a2 M 2 , ..., an Mn и b1 N1, b2 N2 , ..., bm Nm

81

высказывание Р(а1, а2, ... , аn) Q(b1, b2, ... , bm) является конъюнкцией высказываний Р(а1, а2, ... , аn) и Q(b1, b2, ... , bm).

Аналогично определяются дизъюнкция, импликация и эквивалентность двух предикатов.

Задача 4.3. Даны предикаты:

Р(х): «Число х делится на 3» и Q(x): «Сумма цифр числа х делится на 9». Установите, какие из следующих импликаций истинны для всех натуральных чисел:

а) Р(х)

б) Q(х)

в) Р (х)

г) Q(х)

Задача 4.4. Выясните, являются ли следующие переменные высказывания равносильными, если x R :

4.2 Кванторы

Для ограничения области определения предметных переменных введём ещё одно логическое понятие, называемое квантором. Роль его выясним на следующих примерах:

1.«Все люди смертны. Сократ человек. Следовательно, Сократ смертен».

2.«Некоторые люди гениальны. Сократ человек, следовательно, Сократ гениален».

Во втором примере чувствуется ложность заключения, поскольку Сократ мог и не попасть в число гениальных людей.

82

является начальной буквой английского слова All – «все»). Предикат записывают после квантора всеобщности ( x)P(x) . На естественном языке эта формальная запись означает: «для всех х значение Р(х) истинно».

Термин «некоторые х» или «существует хотя бы одно значение х» обозначается через x и называется квантором существования (символ есть перевёрнутая буква Е, являющаяся первой буквой английского слова Exist – «существовать»). Предикат записывают после квантора существования ( x)P(x) . На естественном языке эта запись означает: «существуют такие элементы х, что Р(х) истинно».

Переход от Р(х) к ( x)P(x) или ( x)P(x) называется связыванием переменной х, или навешиванием квантора на переменную х (или на предикат Р), или квантификацией переменной х.

Переменная, на которую навешен квантор, называется связанной, несвязанная квантором переменная называется свободной.

Выражение, на которое навешивается квантор ( x) или ( x) , называется областью действия квантора; все вхождения переменной х в это выражение являются связанными.

Навешивать кванторы можно и на многоместные предикаты и вообще на любые логические выражения.

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

Например,

( x) ( y)P(x, y) : «Для всех целых чисел х существует меньшее число у».

( x) ( y) ( z) P(x, y, z) : «Для всех целых чисел х и у существует число z, которое является частным от деления х на у».

83

Применение кванторов превращает одноместные предикаты в высказывания. Если имеется какой-либо k-местный предикат Р(х1, х2, ..., хk)

на множестве М. Дать словесную формулировку высказыванию ( x) P(x) , определить его истинность.

Решение. Исходный предикат Р(х): «х – чётное число» является переменным высказыванием: при подстановке конкретного числа вместо переменной х он превращается в высказывание, являющееся истинным или ложным, например, при подстановке числа 5 превращается в высказывание «5 – чётное число», являющееся ложным. Высказывание ( x) P(x) означает «В М существует чётное число». Поскольку множество М, на котором задан предикат Р(х), не определено в условии (в таком случае говорят, что задача сформулирована не вполне корректно), доопределим М.

Пусть предикат Р(х) определён на множестве натуральных чисел N, т.е. x N , тогда высказывание – истинно. В общем случае высказывание ( x) P(x) истинно на любом множестве М, содержащем хотя бы одно чётное число, и ложно на любом множестве нечётных чисел.

Пример 4.3. Пусть N(x) – предикат «х – натуральное число». Рассмотреть варианты навешивания кванторов. Дать словесную формулировку высказываниям и определить их истинность.

Решение. ( x) N (x) – высказывание «Все числа – натуральные» истинно на любом множестве натуральных чисел и ложно, если М содержит хотя бы одно ненатуральное число, например, целое отрицательное.

– высказывание «Существует натуральное х» истинно на любом множестве М, содержащем хотя бы одно натуральное число, и ложно – в противном случае.

Пример 4.4. Рассмотреть все возможные варианты навешивания кванторов на предикат D(x,y): «х делится на у», определённый на множестве натуральных чисел (без нуля) N. Дать словесные формулировки полученных высказываний и определить их истинность.

84

Решение. Операции навешивания кванторов приводят к следующим формулам:

( x) D(x, y) – одноместный предикат (переменное высказывание) «всякое натуральное число из N делится на натуральное число y из N»; истинный только для одного значения свободной переменной y = 1;

( x) D(x, y) – переменное высказывание «Существует натуральное число, которое делится на у», истинное для любого значения свободной переменной у, взятой из множества N;

( y) D(x, y) – переменное высказывание «Натуральное число х делится на всякое натуральное число у», ложное для любого значения свободной переменной x, взятой из множества N;

( у) D(x, y) – переменное высказывание «Существует натуральное число, которое делит натуральное число х», истинное для любого значения свободной переменной;

( х)( у)D(x, y) ; ( y)( x)D(x, y) – высказывания «Для любых двух натуральных чисел имеет место делимость одного на другое», ложные;

( х)( у)D(x, y) ; ( y)( x)D(x, y) – высказывания «Существуют такие два натуральных числа, что первое делится на второе», истинны;

( х)( у)D(x, y) – высказывание «Существует натуральное число, которое делится на любое натуральное», ложное;

( y)( x)D(x, y) – высказывание «Для всякого натурального числа найдётся такое натуральное, которое делится на первое», истинное;

– высказывание «Для всякого натурального существует такое натуральное число, на которое оно делится», истинное;

( у)( х)D(x, y) – высказывание «Существует натуральное число, которое является делителем всякого натурального числа», истинное (таким делителем является единица).

Рассмотрим примеры перевода в символическую форму. Предположение «Всякое рациональное число есть действительное

число», обозначая через Q(x): «х есть рациональное число», а через R(x): «х есть действительное число», мы можем выразить в символической форме в виде

( x) (Q(x) R(x)),

85