Навешивание кванторов на предикат.

Пусть Р(х) какой-нибудь предикат. Навешивание квантора всеобщности – это операция, которая сопоставляет предикату Р(х) высказывание «Для всякого х имеет место Р(х)».

Для обозначения этой операции употребляется знак ". В словесных формулировках этот знак заменяет слова «все», «всякий», «любой», «каждый». Символическая запись операции имеет вид: .

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

Навешивание к вантора существования – это операция, которая предикату Р(х)сопоставляет высказывание «существует такое х, что имеет место Р(х)». Его символическая запись имеет вид .

Высказывание истинно тогда и только тогда, когда в области определения М предиката найдется хотя бы один объект а такой, что высказывание истинно. Отсюда следует, что – истинное высказывание для всех выполнимых предикатов .

Знак существования $ употребляется вместо слов «хотя бы один», «найдется», «существует».

Несмотря на то, что в записях формул ("х)Р(х) и ($х)Р(х) встречается буква х, обозначающая переменную, обе эти формулы обозначают высказывания: от переменной х они больше не зависят. Принято говорить, что в формулах ("х)Р(х) и ($х)Р(х) кванторы " и $ связывают переменную х.

Навешивание квантора всеобщности есть обобщение операции конъюнкции на произвольное конечное или бесконечное множество членов конъюнкции (сомножителей).

Навешивание квантора существования на предикат есть обобщение операции дизъюнкции на произвольное, конечное или бесконечное, множество членов дизъюнкции (слагаемых).

Если предикат зависит от нескольких переменных, то навешивание одного квантора понижает число переменных на единицу. Чтобы получить из предиката высказывание, надо связать кванторами все его переменные. Например, из предиката Q (x, y): x > y, определенного на множестве пар действительных чисел, навешиванием кванторов можно получить 8 высказываний с соответствующими значениями истинности:

Этот пример показывает, что разноименные кванторы, вообще говоря, менять местами нельзя: при перестановке кванторов значение истинности получаемого высказывания меняется. Попытайтесь выяснить, в каком случае разноименные кванторы можно переставлять.

Заметим, наконец, что между кванторами имеют место соотношения, позволяющие сводить один из этих кванторов к другому:

Задача. Записать высказывание, используя символы кванторов и предикатов, и построить его отрицание: В каждом городе, на каждой улице есть дом с балконом.

Решение. Пусть P (x): x – город; Q (x, y): y – улица города x; R (z): z – дом с балконом, M (x, y, z): z - дом на улице y в городе x. Тогда формула высказывания имеет вид

.

Построим отрицание этой формулы:

Задачи

76. Какие из следующих выражений являются предикатами?

а) Человек x – преступник.

б) .

в) Человек x – адвокат человека y.

г) a и b проходят подозреваемыми по делу № z.

д) .

е) Иван и Марья – супруги.

ж) .

77. Определить множество истинности предиката, если

| х есть четное число}, .

78. Даны предикаты и . Найти множество истинности следующих предикатов

a) b) ; c) ;

d) ; e) ; f) .

79. Записать множество истинности предиката

определенного на:

а) множестве натуральных чисел;

b) множестве целых чисел;

c) множестве рациональных чисел;

d) множестве вещественных чисел.

80. Пусть имеются предикаты и . Изобразите в виде кругов Эйлера их множества истинности, затем изобразите множества истинности следующих предикатов:

1) ; 2) ; 3) ;

4) ; 5) ; 6) ;

7) ; 8) .

81. В аристотелевской логике рассматривалось четыре вида так называемых категорических суждений:

1. «Все S суть Р» – общеутвердительное суждение.

2. «Ни одно S не есть Р» – общеотрицательное суждение.

3. «Некоторые S суть Р» – частноутвердительное суждение.

4. «Некоторые S не суть Р» – частноотрицательное суждение.

Пусть S – переменное, а P – фиксированное утверждение. Запишите данные схемы высказываний на языке логики предикатов. Постройте отрицания к ним. Решите эту же задачу для случая, когда и S, и P – переменные.

82. Используя предикаты Р (х) = { х – простое число},

S (x) = { х – четное число}, Q (x) = { х – отрицательное число},

R (x, y) = { х > y }, операции над ними и кванторы, запишите следующие высказывания:

а) существует простое четное число,

б) всякое простое число, большее двух, нечетно.

в) не существует отрицательного числа, большего нуля;

г) не существует простого четного числа, большего двух;

83. Сформулируйте следующие высказывания и укажите их значения истинности:

а) (" х)($ у)(х + у = 4); б) ($ у)(" х) (х + у = 4);

в) ($ х)($ у)(х + у = 4); г) (" х)(" у)(х + у = 4).

84. Пусть на множестве натуральных чисел определены следующие предикаты: Р (х) = { х – простое число}, R (x) = { х – четное число}, Q (х) = { х – нечетное число}, S (х, у) = { х делится на у }. Сформулируйте следующие утверждения:

а) ; б) R (2)Ù P (2);

в) (" х)(S (x, 2)Þ R (x)); г) ($ х)(R (x) Ù S (x, 6));

д) ($ х)(Q (x) Ù P (x)); е) );

ж)

з) (" х)((Р (х)Þ($ у)(R (y) Ù S (y, x)));

и) .

85. Даны следующие предикаты, определенные на множестве людей:

А (х) = { х – преступник}, В (х) = { х – судья},

С (х) = { х – мужчина}; D (x) = { х – свидетель}; Е (х) = { х – соучастник}.

Дайте словесную формулировку следующих утверждений:

а) ($ х)(А (х) Ù С (х)); б) ; в)

86. Сформулируйтевысказывания, которые являются отрицаниями следующих:

а) существует наибольшее простое число;

б) любое вымогательство наказывается лишением свободы;

в) в некотором поезде, идущем из Москвы в Ярославль, в каждом вагоне есть свободное место.

г) каждый, совершивший преступление, должен быть подвергнут справедливому наказанию.

д) ни один невиновный не должен быть привлечен к уголовной ответственности

87. Выразите следующие высказывания на языке логики предикатов. Постройте их отрицания и переведите их на русский язык.

а) Все работники подлежат обязательному медицинскому страхованию.

б) Все люди рождаются свободными и равными в своих достоинствах и правах.

в) Некоторые люди освобождаются от уплаты судебных расходов в доход государства.

г) Некоторые приговоры суда являются обвинительными.

д) Ни один приговор суда не должен быть необоснованным.

е) Существует книга, которую все прочитали.

ж) Не все осужденные за совершение преступлений освобождаются

по амнистии.

з) Ни один образец производственного оборудования не может быть передан в серийное производство, если он не отвечает требованиям охраны труда.

88. Запишите с помощью логической символики высказывания:

а) существует точно одно х, такое, что Ф (х);

б) существует по крайней мере два х, таких, что Ф (х);

в) существует не более двух х, таких, что Ф (х).

г) два и только два х обладают свойством Ф.

89. Постройте отрицания следующих высказываний и дайте их словесную формулировку.

а) (" х)(" у)((x > y)Ú (x < y) Ú (x = y));

б) ;

в) .

90. Предикаты Р (х) и Q (x) определены на некотором множестве Т. В каком отношении должны находиться области истинности данных предикатов, чтобы предикат

1) Р (х)Ù Q (x) принимал значение 1:

а) для некоторых х Î , б) для всех х Î ,

в) для всех х Î , г) ни для одного значения х Î Т.

2) Р (х)Þ Q (x) принимал значение 1:

а) для всех х Î Т, б) ни для одного значения х Î Т.

91. Почему высказывания в следующих парах не являются отрицаниями одно другого? Ответ обоснуйте на основе определения операции отрицания.

а) Все преступления носят экономический характер.

Все преступления не носят экономический характер.

б) Некоторые юристы работают адвокатами.

Некоторые юристы не работают адвокатами.

92. Придумайте два высказывания, имеющие соответственно форму и , так чтобы:

а) оба они были истинными;

б) оба были ложными;

в) первое – ложным, а второе – истинным.

93. Даны предложения: «Каждую задачу решил, по крайней мере, один студент» и «По крайней мере, один студент решил каждую задачу». Имеют ли эти предложения один и тот же смысл? Следует ли хотя бы одно из них из другого? Почему?

94. Запишите символически следующие предложения и определите их значения истинности.

а) Всякое число, умноженное на нуль, есть нуль.

б) Произведение любого числа и единицы равно этому числу.

в) Существует число, которое больше своего квадрата.

г) Квадрат любого числа неотрицателен.

д) Модуль любого числа положителен.

95. Запишите символически следующие предложения и определите их значения истинности. Укажите области определения предикатов:

а) Существует рациональное число, квадрат которого равен 2;

б) Всякое натуральное число либо четно, либо нечетно;

в) Всякое рациональное число представимо в виде дроби , где p – целое число, а q - натуральное число;

г) Некоторые натуральные числа делятся на 7.

Определите множества истинности предикатов, на которые навешиваются кванторы. Приведите, где это возможно, примеры чисел из множеств истинности.

96. Запишите символически:

а) положительные оценки на всех экзаменах являются необходимым условием для перевода любого студента на следующий курс;

б) имеет смысл при любых значениях x и y;

в) функция принимает любое неотрицательное значение.

97. Сформулируйте следующие высказывания, используя квантор всеобщности:

а) не существует такого числа x, что ;

б) нет человека, не имеющего матери;

в) не найдется студента, не сдавшего экзамена по уголовному праву и в то же время переведенного на следующий курс;

г) ни один человек не бессмертен.

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

а) Из всякого положения есть выход;

б) В каждой стране найдется город, у всех жителей которого один и тот же цвет глаз;

в) В каждом городе есть вуз, в котором есть факультет, где есть курс, в каждой группе которого ни один студент не занимается спортом.

г) Существует книга, в которой есть страница, в каждой строке которой найдется хотя бы одна буква «а».

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

1) есть реки, которые впадают в Волгу;

2) Не все то золото, что блестит;

3) Всякий кулик свое болото хвалит;

4) Не всякий человек может добиться осуществления своей мечты;

5) Каждый студент-физик выполнил хотя бы одну лабораторную

работу.

100. Пусть даны предикаты:

М(x) – «x – мужчина»; V(x) – «x – женщина»; I(x, y) –«человек x моложе, чем y); K(x, y) – «x есть ребенок y); G(x, y) – «x состоит в браке с y); U(x) – «x живет в Ярославле»; A(x) – «x живет в Архангельске».

Запишите в символической форме следующие предложения.

1) каждый человек имеет отца и мать;

2) каждый, кто имеет отца, имеет и мать;

3) всякий человек моложе своих родителей;

4) не всякий человек состоит в браке;

5) каждый человек моложе своего деда;

6) существует мужчина, у которого сын женат на женщине младше

себя;

7) если в Ярославле есть женщина, имеющая брата в Архангельске, то в Архангельске есть мужчина, имеющий сестру в Ярославле.

8) не всякий женатый мужчина проживает в Архангельске.

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

1) Все ученики нашей группы подготовились к семинару по уголовному праву.

2) Некоторые ученики нашей группы подготовились к семинару по уголовному праву.

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

4) Некоторые ученики нашей группы не подготовились к семинару по уголовному праву.