книги / Математическая логика и теория алгоритмов. Логика предикатов
.pdfНаиболее часто используемая логическая связка, кроме введённых выше, называется эквиваленцией и обозначается знаком
F <+ G ^ (F -> G) Л (G -> F).
Как видно из этого определения, эквиваленция служит для формальной записи часто используемого в математических текстах выражения вида «F тогда и только тогда, когда G», где F и G — некоторые утвержде ния (напомним, что для передачи того же самого смысла существуют и другие стандартные словесные конструкции — см. начало главы I).
Пример 3.12. Запишем на формальном языке утверждение «Число делится на б тогда и только тогда, когда оно делится на 2 и на 3»: а) без знака эквиваленции, б) с ним.
Переформулируем утверждение так: «Для всех х имеет место свой ство: если х делится на 6, то а; делится на 2 и а; делится на 3; и если х делится на 2 и £ делится на 3, то х делится на 6». На формальном языке получаем:
Vz((6 | х -> (2 | х А 3 | а:)) А ((2 | х А 3 | х) -> б | а;)). Со знаком эквиваленции получаем:
Va?(6 | х «-> (2 | х А 3 | а?)).
Рассмотрим ещё один удобный способ сократить формальную запись и сделать её более наглядной.
Пусть F —логико-математическая формула. Тогда выражения VxF и тоже являются логико-математическими формулами. При этом предполагается, что переменной х может быть поставлен в соответствие любой элемент универсального множества, что не всегда удобно: напри мер, формула F сама может содержать квантор, стоящая после которого переменная принимает значения из другого множества — какое множе ство в этом случае считать универсальным? Поэтому в математических текстах множество значений переменных часто специально указывается.
Втаких случаях используются выражения вида:
1)Для всех х € М имеет место свойство F\
2)Существует х € М, для которого имеет место свойство F .
На формальном языке пишут соответственно Va; G M(F) и За; € M(F). Исследуем смысл этих выражений.
Нетрудно понять, что выражения 1 и 2 могут быть сформулированы равносильным образом так:
1*) Для всех x f если х € М, то F;
2*) Существует такое х , что х € М и F.
А также так:
1**) Не существует такого х, что х fi М и F;
2**) Неверно, что для всех х если х G М, то -*F.
Далее, отметим, что выражение х € М является не чем иным, как обо значением предиката. Формулу F тоже можно рассматривать как пре дикат, зависящий от переменной х. Положим
М(х) ^ х € М;
F(x) ^ свойство F имеет место.
Получаем следующие переводы выражений 1 и 2 соответственно на язык логики предикатов:
Vх(М(х) -> .F(x)) = ->3x(M(х) A ->F(х));
Зх(М(х) Л F(x)) = -лVx(M(x) -¥ ->F(x))
(соотнесите с примером 3.3). Таким образом,
Va; G M(F) ^ Vx(x е М F); 3 x e M ( F ) ^ 3 x { x e M / \ F ) .
У пражнение 3.4. Является ли верным перевод выражения 2 фор мулой Зх(М(х) ->> F(x))? Почему?
П ример 3.13. Пусть универсальное множество U = R. Тогда:
Vx > 1(х2 > х) & Vx((x > 1) -> (х2 > х)); Зх < 1(х2 > х) -ФФ- Зх((х < 1) Л (х2 > х)).
Вообще, в выражении Vx G М(Р(х)) вместо предикатах G М может стоять другой предикат, определяющий множество М.
Заметим, однако, что нельзя писать, например,
VI < х < 100(Р(х)), 31 < х < 100(Р(х)),
поскольку квантор должен относиться к символу, следующему непосред ственно за ним. Таким образом, сочетание символов типа VI бессмыслен но. Правильными выражениями являются соответственно
Vx G (1,100)(Р(х)), Зх G (1,100)(Р(х)).
Выражения типа Vx > у(Р(х)) допустимы в случае, когда из кон текста ясно, что у — константа: тогда множество {х \ х > у} определено, иначе — нет.
Проиллюстрируем рассмотренный способ сокращения логико-мате матических формул, записав формально классическое определение из курса математического анализа22.
Число а называется пределом функции f в точке XQ, если для любого е > 0 найдётся такое 8 > 0, что для любого х ф хо имеем: если |х - хо| < 8, то |/(х) - а| < е.
Пусть функция / задана. Тогда по своему смыслу утверждение, что она имеет в точке хо предел а, является двуместным предикатом: оно истинно или ложно в зависимости от значений двух параметров XQ и а. Будем для определённости считать, что хо,а G R, то есть универсаль ным множеством является R. Остальные использованные в определении переменные Е, 8 и х играют вспомогательную роль: они являются связан ными2324и на местность предиката влияния не оказывают: выше мы уже говорили, что это явление происходит всякий раз, когда используются кванторы.
Таким образом, определение предела функции выражает^4 следую щее. Для данной функции f определяется двуместный предикат — отоб ражение множествам2 во множество В. Если для пары чисел (а, хо) G R2
“ Определение предела функции по Коши или на языке эпсилон-дельта. 23Или немыми.
24<В переводе на непонятный язык». Пользоваться таким языком в повседневной речи не стоит, но владеющий им отучается произносить слова только потому, что они красивые и длинные, а говорит только то, что понимает.
он принимает значение И, то число а называется пределом функции f в точке XQ. Этот факт символизируется записью а — / 0 е), кото рая является не чем иным, как индивидуальным предикатным символом.
На формальном логико-математическом языке имеем:
а = lim f(x) Ve > 035 > OVx ФXO(|Æ - хо| < 5 \f(x) — a\< e).
X—tXf)
Задачи
Везде ниже P и Q — предикатные символы.
3.1. Докажите, что выражения
Vx(P(x) A Q{x)) и \УхР{х)) Л ('ixQ(x))
имеют одинаковый смысл.
3.2. Докажите, что выражения
Ух(Р(х) V <?(я)) и (УжР(я)) V (VxQ(x))
имеют разный смысл. Для этого найдите такие предикаты Р и Q, чтобы одно из выражений было истинно, другое — ложно.
3.3. Докажите, что выражения
3х(Р(х) V Q[x)) и (3хР(х)) V (3xQ(x))
имеют одинаковый смысл.
3.4. Докажите, что выражения
3х{Р{х) A Q(x)) и (3хР{х)) А (3xQ(x))
имеют разный смысл.
3.5. Одинаков ли смысл выражений
ЩР{х) Q{x)) и (V®P(s)) О (4xQ(x))?
3.6. Одинаков ли смысл выражений
3х{Р(х)+¥ Q(x)) и (ЭхР(х)) |
(3xQ(x))7 |
3.7.Выполните задание примера 3.12, не используя квантор всеобщности и конъюнкцию.
3.8.Четверо преподавателей некоторой кафедры обсуждали свои представледния о том, что такое лёгкая контрольная работа. Каждый дал своё определение. Обозначим эти определения буквами a, 6, с, d:
акаждую задачу решил хотя бы один студенщ
Ь^ хотя бы один студент решил все задачц
с Î=± каждый студент решил хотя бы одну задачу, d *=* хотя бы одну задачу решили все студенты.
• Запишите определения а, 6, с, d на формальном языке.
•Сформулируйте по-русски отрицания ->а, —»6, -ic, -id.
•Из всех возможных импликаций: а —> Ь, b —ï с, с —>а и т. д. — выберите верные.
•Есть ли среди определений лёгкой контрольной равносильные?
•Равносильны ли высказывания: «Есть задача, которую решили не все» и «Есть студент, который решил не всё»?
3.9.Рассмотрим следующее известное рассуждение из советской песен ной классики: «В хоккей играют настоящие мужчины. Трус не иг рает в хоккей». Какой из него следует вывод?
•Настоящие мужчины — не трусы.
•Трусы — не настоящие мужчины.
•Множества трусов и ненастоящих мужчин совпадают.
•Никакой вывод не следует.
Ответы, указания, решения
1.1. Поскольку В = [a,d], имеем:
А х В = ([а, Ь] х [а,tfj) U ([с, d\ х [а, cf]).
Это множество изображается на плоскости R2 двумя прямоуголь никами.
1.2. Множество {О, I} 2 содержит четыре элемента: (0,0), (0,1), (1, 0), (1, 1). При определении какого-нибудь подмножества для каждого из этих элементов определяется одно из двух: входит он в подмно жество или нет. Значит, всего подмножеств 24 = 16.
1.3.Каждому элементу (xyy,z) Е А х В х С поставим в соответствие элемент {y}z,x) Е В х С х А.
1.4.Допустим, что Л С В и С С D. Тогда если х Е А х С )то х = (xi, хг), где х\ Е А и х2 Е С. Значит, х\ Е В и хг Е Д а тогда х Е В х D. Поскольку выбор элемента х 6 А х С произволен, заключаем, что
Ах С Ç В х D. Наоборот, допустим, что А х С С В х D. Тогда
если х Е А и у Е С, то (х, у) € А х С. Значит, (х,г/) Е В х D, а тогда х Е В и у Е D. Таким образом, AÇ. В и С Ç D. Заметим, что второе рассуждение справедливо только в предположении, что оба множества Л и С не пусты. Если же, например, Л = 0 , то для любых множеств В, С и D имеем
A x C = 0 x C = 0 C B x D ,
при этом соотношение С %D может быть верным.
1.5. Указание. Докажите, что (х,у) = |
(х/,yf), где |
|
|
х = |
(fli,... , ai) G U1, |
у = (Ьи . .. , bm) € |
и т, |
х' = |
(а,, . .. , 0(_i) G С/'-1, |
ÿ = (at, bi....... bm) G Um+1. |
|
Выполняя далее аналогичные преобразования, докажите, что |
|||
|
(i,|/) = (ai, ... ,aj, 6i , . .. ,b m). |
(*) |
Для к = 2 задача решена. Решение для к > 2 выведите из ра венств (*) и (1.1).
1.6. Искомое количество предикатов равно количеству подмножеств множества U2) которое содержит 52 = 25 элементов. Число под множеств множества U2 равно 22° (см. решение задачи 1.2), то есть больше тридцати миллионов.
2.1.Докажем, например, первое равенство. Базой индукции считаем за кон де Моргана для двух высказываний: -i(aj V аг) = (-»ai) Л (-^аг). Допустим, для данного п ^ 2 требуемое доказано:
->(ai V V an) = (—*ai) Л ... A (->an).
Отсюда, используя закон де Моргана для двух и для п высказыва ний, получаем:
-»(ÛI V ... V an+1) = -i((ai V V ап) V an+i) =
=H a , V Va„))A (-« * « ) =
=(("’ûi) Л ... A (~'an)) A (-’On+i) =
=(~’ûi) A ... A (-1a„) A (-’ûn+i)-
2.2. {(*, y) | |
x 6 |
Л V y € B} = (Л x B) U ((U \ A) x B) U {A x (U \ B)). |
2.3. Пусть P |
= |
{gi,.,. >qm} Ç Bn - множество всех таких кортежей |
Qi = (sa , ... , 5j„), что высказывание p истинно, если и только если (ai,... , ап) Е Р. Для каждой пары (г,у) положим
|
I |
|
если Sij = И; |
|
|
|
если |
= JI. |
|
Получаем то, что требовалось: |
|
|
|
|
p = PiV ...V pm, |
где pi = baA...Abin' |
|||
Например, пусть р = а Л (Ь |
с). Тогда р = И, если и только если |
|||
(а, Ь,с) € {(И, Л, Л), (И, Л,И), (И, И,И)}. |
||||
Следовательно, р = |
(а Л (-ib) Л (-ю)) V (a Л (-16) Л с) V (а Л bЛ с). |
|||
2.4. Пусть P = |
С Вп - |
множество всех таких кортежей |
||
q%= (sti,... ,Sin)y что высказывание р ложно, если и только если |
||||
(ai,... , On) 6 Р. Для каждой пары (г, j) |
положим |
|||
|
-ia„ |
если Sij = И; |
||
|
üj, |
|
если |
= Л. |
Получаем то, что требовалось:
P = Pi Л •••Арт) |
где Pi = Ьц V |
Vbin. |
Например, пусть р = (а Ь) |
с. Тогда р = JI, если и только если |
(а, 6, с) € {(Л, Л, Л), (Л, И, Л), (И, И, Л)}.
Следовательно, р = (а V b V с) А (о V (-A) V с) А ((-кг) V (-»Ь) V с).
2.5. Если высказывание р не'является тождественно истинным или тож дественно ложным, то т — некоторое число от 1 до 2П —1.
3.1.Каждое из выражений означает, что значениями Р(х) и Q(x) явля ется И для всех х € U (оба предиката Р и Q являются тождественно истинными).
3.2.Определим предикаты Р и Q на универсальном множестве U = К:
Р(х) O x ^ Q , Q(x) х < 0.
Очевидно, что утверждение Vx(P(x) V Q{x)) является истинным,
а утверждение (VxP(x)) V (VxQ(x)) —ложным.
3.3.Каждое из выражений означает, что для некоторого х е U хотя бы одно из значений Р(х) и Q(x) есть И (хотя бы один из предикатов Р и Q не является тождественно ложным).
3.4.Пусть предикаты Р и Q определены так же, как в решении зада
чи 3.2. Тогда утверждение (ЗяР(а;)) A (3xQ(x)) является истинным,
аутверждение Зх(Р(х) A Q(x)) — ложным.
3.5.Выражения имеют разный смысл. Действительно, пусть предикаты Р и Q определены так же, как в решении задачи 3.2. Тогда утвер ждение (УхР(х)) 4+ (VÆQ(X)) является истинным, а утверждение
Vx(P(x) ++ Q(x)) — ложным.
3.6.Выражения имеют разный смысл. Действительно, пусть предикаты Р и Q определены так же, как в решении задачи 3.2. Тогда утвер ждение (3хР(х)) f* (3xQ(x)) является истинным, а утверждение 3х(Р(х) •H' Q(x)) — ложным.
3.7.Чтобы уменьшить количество скобок, договоримся, что отрицание выполняется раньше дизъюнкции. Используя выражение имплика
ции через дизъюнкцию и отрицание и законы де Моргана, получаем:
а) |
| х V —*(—»2 | х V -i3 | х)) V -»(6 | х V -»2 | х V -i3 ) х))\ |
б) |
| х —i(—>2I x V ->3 I x)). |
3.8. Пусть S — множество студентов, P — множество задач. Определим двуместный предикат R: 3 x Р В:
R(x, У) ^ студент х решил задачу у.
• Определения а, Ъ, с, d на формальном языке:
а = Уу е РЗх е 5(Л(х,у));
Ь— Б хе SVy G Р(Д(я, у));
е= Vrc е € Р(Я(я, 2/));
d = 3y е F ix 6 S(-R(s, Î/)).
• Перевод отрицаний —»а, —'Ь, -te, -id на русский язык:
-«а = найдётся задача, которую не решил ни один студент, -1b = не найдётся студента, который решил все задачи,
-ic = найдётся студент, который не решил ни одной задачи, ->d = не найдётся задачи, которую решили все студенты
•Пусть три студента А, В к С решают контрольную, содержащую три задачи 1, 2 и 3. Рассмотрим следующие четыре ситуации:
а) студент А решил задачи 1. и 2, студент В — задачу 3, сту дент С не решил1ни одной задачи — такая контрольная яв ляется лёгкой по определению а, но не является лёгкой по определениям Ь, с и d;
б) студент А решил все задачи, студенты В н С не решили ни одной — такая контрольная является лёгкой по определени ям а и Ь, но не является лёгкой по определениям e n d ;
в) задачу 1 решил студент Д задачу 2 — студенты В и <7, за дачу 3 не решил никто — такая контрольная является лёгкой по определению с, но не является лёгкой по определениям а,
Ьи d;
г) все студенты решили задачу 1, остальные задачи не решил никто — такая контрольная является лёгкой по определени ям с и d, но не является лёгкой по определениям а и 6.
Таким образом, для каждой такой импликации р -4 g, что G {a,6,c,d} и V Ф Q\ кроме 6 -4 а и d -4 с, существует такая контрольная, что р = И и g = Л, а значит, р -4 g = Л.
Импликации b —> а и d с, как нетрудно видеть, истинны.
•Среди определений а, Ь, с, d нет равносильных — это следует из предыдущнго пункта.
•Высказывания равносильны: на формальном языке по свойству перестановочности одинаковых кванторов имеем
3у € РЗх 6 S(-»i?(x,y)) = Зх € S3y € Р(-»Д(х,у)).
3.9. Определим на множестве мужчин три одноместных предиката:
Я(х) ч=±мужчина х играет в хоккей;
Щх) |
мужчина х |
—настоящий; |
(7(х) ^ |
мужчина х |
—трус. |
Выводы из слов песни определяются тем, как мы понимаем эти сло ва. Обозначим:
а в хоккей играют настоящие мужчины; b трус не играет в хоккей
Высказывание а наиболее естественно, видимо, понимать так: только настоящие мужчины играют в хоккей; иначе говоря, если
мужчина играет в хоккей, то он настоящий. Значит, |
|
а = Ух(Я(х) -4 Д(х)). |
(Я1) |
Предложение b естественно понимать так: |
|
b = Vx(C(x) -4 - 1#(яг)). |
((71) |
Песня утверждает истинность обоих высказываний а и Ь, то есть высказывания
а Л b= Ух((Я(х) -4 Д(х)) Л (С7(х) -4 -Я (х ))) =
= Ух((Я(х) -4 Я(х)) Л (Я(х) -4 -О Д )) =
= Ух(Я(х)-4(Д(х)Л-С(х))).