4.2: Переклад на логіку першого порядку
- Page ID
- 65347
Тепер у нас є всі шматки. Переклад тверджень (незалежно від того, наскільки складним) з англійської мови на математичні позначення буде лише питанням знання правильного способу об'єднання предикатів, констант, кванторів, зв'язків та множин. Розглянемо ці твердження:
- Кожна монета в кишені - це копійка.
- Якась монета на столі - це копійка.
- Не всі монети в кишені коштують копійок.
- Жодна з монет на столі не є копійками.
Надаючи ключ символізації, нам потрібно вказати\(\mathcal{U}\). Оскільки ми не говоримо ні про що, крім монет, ми можемо дозволити\(\mathcal{U}\) бути набором всіх монет. (Не обов'язково включати всі монети\(\mathcal{U}\), але, оскільки ми говоримо про монети в кишені та монети на столі,\(\mathcal{U}\) повинні принаймні містити всі ці монети.) Оскільки ми не говоримо про якісь конкретні монети, нам не потрібно визначати будь-які константи. Оскільки ми будемо явно говорити про монети в кишені та монети на столі, буде корисно, щоб вони були визначені як набори. Ключ символізації також повинен сказати щось про копійки; давайте зробимо це з присудком. Отже, ми визначаємо цей ключ:
\(\mathcal{U}\): Набір всіх монет.
\(P\): Набір всіх монет в кишені.
\(T\): Набір всіх монет на столі.
\(D(x)\)це копійка.
Твердження 5. найбільш природно перекладається за допомогою універсального квантора. У ньому йдеться про всі монетки в кишені (тобто елементи набору\(P\)). Це означає, що для будь-якої монети в кишені ця монета - це копійка. Таким чином, ми можемо перевести це як\(\forall p\in P, D(p)\).
Твердження 6. говорить, що на столі є якась монета, така, що монета є копійкою. Таким чином, ми перекладаємо це як\(\exists t \in T, D(t)\).
Твердження 7. можна перефразувати як: «Це не так, що кожна монета в моїй кишені - це копійка». Таким чином, ми можемо перевести це як\(\neg(\forall p \in P, D(p))\). Це просто заперечення.
Твердження 8. можна перефразувати як: «Це не той випадок, що якась монета на столі - це копійка». Це можна перекласти як\(\neg\bigl(\exists t\in T, D(t) \bigr)\). Це заперечення твердження 6.
Крім того, ми могли б визначити набір\(D\), набір усіх копійок, замість присудка\(D(x)\). У цьому випадку:
- Твердження 5. буде перекладено як\(\forall p \in P, \ p \in D\).
- Твердження 6. буде перекладено як\(\exists t \in T, \ t \in D\).
- Твердження 7. буде перекладено як\(\neg (\forall p \in P, \ p \in D)\).
- Твердження 8. буде перекладено як\(\neg (\exists t \in T, \ t \in D)\).
Будь-який підхід цілком законний.
Однак якщо нам потрібно кількісно оцінити понад копійки, то набагато краще використовувати набір, ніж присудок. Наприклад, давайте символізуємо твердження «Кожен копійок у мене в кишені».
- Якщо\(D\) набір всіх копійок, ми можемо написати:\(\forall d \in D, \ d \in P\).
- Це менш просто, якщо ми використовуємо присудок\(D(x)\), тому що ми не можемо прямо сказати «для всіх копійок» (оскільки набір всіх копійок недоступний). У перекладі необхідно розглянути всі монети, а потім сказати, що ті, які є копійками, знаходяться в моїй кишені:\(\forall x, \bigl( D(x) \Rightarrow d \in P \bigr)\).
З цієї причини (та інших) математики схильні використовувати множини, а не присудки, і ми будемо робити те ж саме.
Якби ми визначили присудок\(P(x)\) (для «\(x\)у мене в кишені») замість відповідного набору\(P\), нам потрібно було б перевести так\(\forall x, \bigl( P(x) \implies D(x) \bigr)\): тобто «для будь-якої монети, якщо вона в кишені, то це копійка». Оскільки твердження стосується монет, які є як у моїй кишені, так і копейки, можливо, буде спокусливо перевести його за допомогою\(\eand\). Однак твердження\(\forall x, \bigl(P(x) \eand D(x) \bigr)\) означало б, що все в моїй кишені і копійки: Всі монети, які існують, - це копійки в кишені. Це було б божевільною річчю сказати, і це означає щось зовсім інше, ніж. Однак цього питання повністю уникається, коли ми використовуємо набори. Таким чином, визначення\(P\) бути множиною, а не присудком, є найкращим підходом у цій задачі (і аналогічно для\(T\)).
Тепер ми можемо перевести відрахування зі сторінки, той, що мотивував потребу в квантифікаторах:
Мерлін - чарівник. Всі чарівники носять смішні капелюхи.
\(\therefore\)Мерлін носить смішну шапку.
\(\mathcal{U}\): Безліч всіх людей.
\(W\): Безліч всіх чарівників.
\(H\): Набір всіх людей, які носять смішну шапку.
\(m\): Мерлін
Переводячи, отримуємо:
Гіпотези:\ [\ begin {вирівняні}
&m\ in W\\
&\ для всіх w\ in W, (w\ in H)
\ end {вирівняні}\]
Висновок:\(m \in H\)
Це фіксує структуру, яка була залишена, коли ми перевели відрахування на, і це дійсний відрахування. Ми зможемо довести це суворо після того, як ми обговоримо правила введення та усунення для\(\forall\) (і\(\exists\)) в розділі\(4.4\).
Використовуючи вказаний ключ символізації, перекладіть кожне англомовне твердження на логіку першого порядку.
\(\mathcal{U}\): Набір всіх тварин.
\(A\): Набір всіх алігаторів.
\(R\): Безліч всіх рептилій.
\(Z\): Безліч всіх тварин, які мешкають в зоопарку.
\(M\): Набір всіх мавп.
\(x\)♥\(y\): \(x\) loves \(y\).
\(a\): Амос
\(b\):
\(c\) Вибивала: Клео
- Амос, Bouncer, і Клео все живуть в зоопарку.
- Вибивала - це рептилія, але не алігатор.
- Якщо Клео любить Bouncer, то Bouncer - мавпа.
- Якщо обидва Bouncer і Клео є алігаторами, то Амос любить їх обох.
- Деякі рептилії мешкають в зоопарку.
- Кожен алігатор - це рептилія.
- Кожна тварина, яка живе в зоопарку - це або мавпа, або алігатор.
- Є рептилії, які не є алігаторами.
- Клео любить рептилію.
- Вибивала обожнює всіх мавп, які мешкають в зоопарку.
- Всі мавпи, яких любить Амос, люблять його назад.
- Якщо якась тварина - алігатор, то це рептилія.
- Кожну мавпу, яку любить Клео, також любить Амос.
- Є мавпа, яка любить Bouncer, але Bouncer не відповідає взаємністю на цю любов.
Використовуючи вказаний ключ символізації, перекладіть кожне англомовне твердження на логіку першого порядку.
\(\mathcal{U}\): Набір всіх тварин.
\(D\): Набір всіх собак.
\(S\): Безліч всіх рептилій.
\(Z\): Безліч всіх тварин, які люблять плавати.
\(x\)\(L\)\(y\): \(x\) is larger than \(y\).
\(b\): Берті
\(e\): Емерсон
\(f\): Фергіс
- Берті - собака, яка любить плавати.
- Берті, Емерсон і Фергіс - все собаки.
- Емерсон більший за Берті, а Фергіс більший за Емерсона.
- Всі собаки люблять плавати.
- Кожна тварина, яка любить плавати, - це собака.
- Є собака, яка більша за Емерсона.
- Жодна тварина, яка любить плавати, не є більшою за Емерсона.
- Будь-яка тварина, яка не любить плавати, крупніше Берті.
- Немає тварини, яка більша за Берті, але менше Емерсона.
- Немає собаки, яка більша за Берті, але менша за Емерсона.
- Жодна собака не більша за себе.
Для кожного відрахування напишіть ключ символізації і перекладіть відрахування в First-Oder Logic.
- Ніщо на моєму столі не уникає моєї уваги. На моєму столі є комп'ютер. Тому є комп'ютер, який не уникає моєї уваги.
- Всі мої мрії чорно-білі. Старі телепередачі в чорно-білому кольорі. Тому деякі мої мрії - це старі серіали.
- Ні Холмс, ні Уотсон не були в Австралії. Людина могла побачити кенгуру тільки в тому випадку, якщо він побував в Австралії або в зоопарку. Хоча Уотсон не бачив кенгуру, Холмс має. Тому Холмс побував у зоопарку.
- Ніхто не очікує іспанської інквізиції. Ніхто не знає неприємностей, які я бачив. Тому кожен, хто очікує іспанської інквізиції, знає неприємності, які я бачив.
- Кожна антилопа більша за хлібницю. Те, про що я думаю, не більше, ніж хлібниця, і це або антилопа, або диня. Тому я думаю про диню.
4.2A. Кілька кількісних показників
Розглянемо наступний ключ символізації та твердження, що слідують за ним:
\(\mathcal{U}\): Безліч всіх людей.
\(D\): Набір всіх друзів Карла.
\(S\): Набір всіх сусідів Імре.
\(x\)\(L\)\(y\): \(x\) likes \(y\).
\(i\): Імре.
\(k\): Карл.
- Усі сусіди Імре, як і всі друзі Карла.
- Принаймні одному з друзів Карла подобається принаймні один із сусідів Імре.
- Усі друзі Карла люблять принаймні одного з сусідів Імре.
- Є один із сусідів Імре, який є другом Карла і який любить всіх сусідів Імре.
Рішення
Починаючи перекладати Assertion 9., ми починаємо з усіх сусідів Імре:\(\forall n \in N.\) Тепер ми хотіли б сказати\(n \mathrel{L}f\), де\(f\) представляє кожного з друзів Карла. Перш ніж ми зможемо це зробити, нам потрібно ввести змінну\(f\), і надати їй бажане значення і відповідний квантор:\(\forall f \in F\). Таким чином, Assertion 9. можна перекласти як\(\forall n \in N, \bigl(\forall f \in F, (n \mathrel{L}f)\bigr)\).
Для твердження 10., Ми починаємо принаймні з одного з друзів Карла. Ще один спосіб сказати це, що є якийсь друг Карла:\(\exists f \in F\). Аналогічно, тепер нам потрібно представити принаймні одного з сусідів Імре:\(\exists n \in N\). Завершений переклад є\(\exists f \in F, \bigl(\exists n \in N, (f \mathrel{L}n)\bigr)\bigr)\).
Для твердження 11., Ми починаємо з усіх друзів Карла:\(\forall f \in F\). Тепер нам потрібен хоча б один із сусідів Імре:\(\exists n \in N\). Завершений переклад є\(\forall f\in F, \bigl(\exists n\in N, (f \mathrel{L} n)\bigr)\).
Нарешті, для твердження 12., ми починаємо з одного з сусідів Імре:\(\exists n \in N\). Тепер нам потрібна ця людина, щоб бути другом Карла:\(n \in F\). Для наступної частини речення нам потрібні всі сусіди Імре. Заманливо писати\(\forall n \in N\), але ми вже використовували змінну\(n\) для конкретного з сусідів Імре, тому ми не можемо використовувати його знову тут, щоб означати щось інше. Давайте\(n'\) замість цього використаємо:\(\forall n' \in N\). Тепер ми готові перекласти Assertion 12:\[\exists n \in N,\left(n \in F \&\left[\forall n^{\prime} \in N,\left(n L n^{\prime}\right)\right]\right) .\]
(Крім того, ми могли б використовувати\(n_{1}\) і\(n_{2}\) замість\(n\) і\(n^{\prime}\).)
Символізуючи твердження з декількома кількісними показниками, найкраще діяти невеликими кроками. З'ясуйте, хто обговорюється в реченні, і які квантори потрібні для введення цих змінних. Перефразовуйте англійське твердження так, щоб логічна структура легко символізувалася в. Потім перекладіть по бітах, замінюючи складне завдання перекладу довгого твердження простішим завданням перекладу коротших формул.
Знак\(=\) рівності «» є частиною кожного ключа символізації (хоча ми не намагаємося включити його явно). Це двійковий присудок, і, як і слід було очікувати, «\(x = y\)» означає «\(x\)дорівнює»\(y\). Це не означає просто, що\(x\) і\(y\) виглядають дуже схожими, або що вони не відрізняються, або що вони мають однакові властивості. Швидше, це означає, що\(x\) і\(y\) є (різними) іменами одного і того ж об'єкта.
Важливо поставити квантори в правильному порядку. Наприклад, розглянемо наступні твердження (з\(\mathcal{U}\)) сукупністю всіх об'єктів):
- \(\forall x,\bigl( \exists y, (x=y)\bigr)\)
- \(\exists y, \bigl(\forall x, (x=y)\bigr)\)
Вони точно такі ж, за винятком того, який з\(\forall x\) і\(\exists y\) є першим, а який є другим. Очевидно, вірно: «Для кожної речі є щось, чому вона дорівнює». (А саме, кожна річ дорівнює собі.) Але каже: «Є якась річ (назвемо її\(y\)), така, що все рівно»\(y\). Такого немає\(y\), тому це явно помилково.
Використовуючи ключ символізації з вправи\(4.2.5\), перекладіть кожне англомовне твердження на логіку першого порядку.
- Якщо є собака більша за Фергіса, то є собака більша за Емерсона.
- Кожна собака більша за якусь собаку.
- Є тварина, яка менше кожної собаки.
- Якщо є тварина, яке більше кожної собаки, то Емерсон не любить плавати.
- Для кожної собаки, яка любить плавати, є більш дрібна собака, яка їх не любить.
- Кожна собака, яка любить плавати, більша за кожну собаку, яка їх не любить.
- Якась тварина більша за всіх собак, які люблять плавати.
- Якщо є собака, яка не любить плавати, то є собака, яка більша за кожну тварину, яка любить плавати.
Використовуючи вказаний ключ символізації, перекладіть кожне англомовне твердження на логіку першого порядку.
\(\mathcal{U}\): Безліч всіх людей.
\(D\): Набір всіх артистів балету.
\(F\): Безліч всіх самок.
\(M\): Безліч всіх самців.
\(x\)\(C\)\(y\): \(x\) is a child of \(y\).
\(x\)\(S\)\(y\): \(x\) is a sibling of \(y\).
\(e\): Елмер
\(j\): Джейн
\(p\): Патрік
- Кожен, хто танцює балет, - це дитина того, хто танцює балет.
- Кожен чоловік, який танцює балет, - це дитина того, хто танцює балет.
- У кожного, хто танцює балет, є сестра, яка також танцює балет.
- Джейн - тітка.
- Брати Патріка не мають дітей.
4.2B. Унікальність
Сказати «є унікальне так-так» означає не тільки те, що є так-так, але і те, що є тільки один з них - не існує двох різних так-так, наприклад, сказати, що «є унікальна людина, яка заборгувала гроші Хікару» означає
якась людина зобов'язана Хікару і ніхто інший не винен Хікару.
Це перекладається на\[\exists h\in H, \bigl( \forall y, (y \neq h \Rightarrow y \notin H) \bigr);\]
або, еквівалентно,\[\exists h\in H, \bigl( \forall y, ( y \in H \Rightarrow y =h ) \bigr).\]
На жаль, обидва вони є досить складними виразами (і є прикладами «декількох кванторів», тому що вони використовують обидва\(\exists\) і\(\forall\)). Щоб спростити ситуацію, математики вводять спеціальні позначення:\[\text { " } \exists ! x \text { " means "there is a unique } x \text {, such that..." }\]
Якщо\(X\) є який-небудь набір, то\(\exists ! x \in X\) "" означає
«є унікальний\(x\) в\(X\), такий, що.»
Наприклад,\(\exists!\, h, h \in H\) означає точно те ж саме, що і складний вираз вище.
Якщо ми додамо
\(R\): Безліч людей, які багаті.
до нашого символічного ключа ми можемо перевести «Є унікальна багата людина, яка повинна Хікару гроші». А саме воно перекладається як:\[\exists!\, r \in R, (r \in H).\]
Використовуючи вказаний ключ символізації, перекладіть кожне англомовне твердження на логіку першого порядку.
\(\mathcal{U}\): Безліч всіх істот.
\(H\): Набір всіх коней.
\(W\): Набір всіх істот з крилами.
\(B\): Набір всіх істот на полі Фермера Брауна.
- Існує унікальна крилата істота, яка знаходиться в полі Фермера Брауна.
- Якщо якась кінь має крила, то є унікальна кінь, яка знаходиться в полі Фермера Брауна.
- Якщо є кінь, який знаходиться в полі Фермера Брауна, то є унікальний кінь, який знаходиться в Фермера Брауна і має крила.
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.
4.2C. Зв'язані змінні
Нагадаємо, що твердження - це твердження, яке є або істинним, або хибним. Наприклад, розглянемо наступний ключ символізації:
\(\mathcal{U}\): Набір всіх учнів.
\(M(x)\):\(x\) приймає клас математики.
\(a\): Анна
Потім:
- \(M(a)\)є твердженням. Або Анна приймає клас математики, або вона ні.
- \(M(x)\)не є твердженням. Буква\(x\) - це змінна, а не якийсь конкретний об'єкт. (Ми називаємо\(x\) вільну змінну.) Якщо ми підключимо певне значення для\(x\) (наприклад,\(a\)), то у нас буде твердження. Однак, поки деяке значення не буде підключено для\(x\), ми не можемо сказати, чи є вираз істинним чи помилковим. Таким чином, вираз не є твердженням, якщо змінна залишається вільною.
- \(\exists x, M(x)\)і\(\forall x, M(x)\) є твердженнями. Буква\(x\) є змінною в обох цих виразах, але вона більше не безкоштовна, тому що на неї діє квантор. (Ми\(x\) називаємо зв'язану змінну.)
Важливим принципом є те, що в твердженні кожна змінна повинна бути пов'язана деяким кількісним показником:\[\text { Assertions cannot have free variables. }\]
Припустимо, що\(p\) це константа, але всі інші малі літери представляють змінні. Для кожного з наступних, a. чи є у нього вільна змінна? б. Це твердження?
- \(\forall x\in X, (x \mathrel{L} y)\)
- \((p \in S) \eand \exists y \in Y, (y \mathrel{T} p)\)
- \(\forall v \in V, \bigl( (\exists!\, y \in Y, v \mathrel{R} y) \Rightarrow (v=z) \bigr)\)
- \(y \in Y \eand \bigl(\forall x \in X, (x \in T) \bigr)\)
- \((p \mathrel{L} p) \Rightarrow \exists x, (x \mathrel{L} p)\)
- \(\forall x \in X, (x \mathrel{L} x)\)
- Відповідь
-
Додайте сюди тексти. Не видаляйте цей текст спочатку.