Розділ 5: Речення QL

Last updated
Save as PDF

Page ID: 52229

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

У цьому розділі ми надаємо формальне визначення добре сформованої формули (w) та речення QL.

Вирази

У QL існує шість видів символів:

предикати з індексами, за потребою	\(A\),\(B\),\(C\),... ,\(Z\) \(A\)₁,\(B\) ₁,\(Z\) ₁,\(A\) ₂,\(A\) ₂₅,\(J\) ₃₇₅,...
констант з індексами, за потребою	\(a\),\(b\),\(c\),... ,\(w\) \(a\)₁,\(w\) ₄,\(h\) ₇,\(m\) ₃₂,...
змінних з індексами, за потребою	\(x\),\(y\),\(z\) \(x\)₁,\(y\) ₁,\(z\) ₁,\(x\) ₂,...
сполучні	¬, &, ₵, →, ↔
круглі дужки	(,)
кількісники	,

Визначаємо вираз Ql як будь-який рядок символів QL. Візьміть будь-який із символів QL і запишіть їх, в довільному порядку, і у вас є вираз.

Добре сформовані формули

За визначенням, термін ql є або константою, або змінною.

Атомна формула ql - це присудок n-місця, за яким слідують n термінів.

Так само, як ми зробили для SL, ми дамо рекурсивне визначення для wQL. Насправді, більша частина визначення буде виглядати як визначення для a wof SL: Кожна атомна формула є w, і ви можете побудувати нові wff, застосовуючи речення з'єднання.

Ми могли б просто додати правило для кожного з квантіфікаторів і зробити з ним. Наприклад: Якщо\(\mathcal{A}\) є w, то x\(\mathcal{A}\) і x\(\mathcal{A}\) - це wff. Однак це дозволило б робити химерні речення, такі як xxDX та xDW. Що це може означати? Ми могли б прийняти деяке тлумачення таких речень, але замість цього ми напишемо визначення w, щоб такі гидоти навіть не вважалися добре сформованими.

Для того,\(\mathcal{A}\) щоб x був w,\(\mathcal{A}\) повинен містити змінну x і не повинен вже містити x-квантіфікатор. xDW не вважатиметься як w, оскільки «x» не зустрічається у Dw, а xxxDx не вважатиметься як w, оскільки xDx містить квантіфікатор x

1. Кожна атомна формула - це w.
2. Якщо\(\mathcal{A}\) є w, то ¬\(\mathcal{A}\) є w.
3. Якщо\(\mathcal{A}\) і\(\mathcal{B}\) є wffs, то (\(\mathcal{A}\)&\(\mathcal{B}\)), є w.
4. Якщо\(\mathcal{A}\) і\(\mathcal{B}\) є wffs\(\mathcal{A}\), (₵\(\mathcal{B}\)) є w.
5. Якщо\(\mathcal{A}\) і\(\mathcal{B}\) є wffs, то (\(\mathcal{A}\)→\(\mathcal{B}\)) є w.
6. Якщо\(\mathcal{A}\) і\(\mathcal{B}\) є wffs, то (\(\mathcal{A}\)↔\(\mathcal{B}\)) є w.
7. Якщо\(\mathcal{A}\) є w,\(\mathcal{x}\) є змінною,\(\mathcal{A}\) містить принаймні одне входження\(\mathcal{x}\) і не\(\mathcal{A}\) містить\(\mathcal{x}\) -квантіфікаторів, то\(\mathcal{x}\)\(\mathcal{A}\) є w.
8. Якщо\(\mathcal{A}\) є w,\(\mathcal{x}\) є змінною,\(\mathcal{A}\) містить принаймні одне входження\(\mathcal{x}\) і не\(\mathcal{A}\) містить\(\mathcal{x}\) -квантіфікаторів, то\(\mathcal{x}\)\(\mathcal{A}\) є w.
9. Всі і тільки wff QL можуть бути згенеровані за допомогою застосування цих правил.

Зверніть увагу, що\(\mathcal{x}\) «', що з'являється у визначенні вище, не є змінною\(x\). Це мета-змінна, яка стоїть для будь-якої змінної QL. Отже,??\(xAx\)????????????????\(yAy\)???\(zAz\)???\(x\)_??\(Ax\)_???????\(z\)_??\(Az\)_???

Тепер ми можемо дати формальне визначення для області видимості: Область дії квантіфікатора - це підформула, для якої квантіфікатор є основним логічним оператором.

Речення

Речення - це те, що може бути як істинним, так і хибним. У SL кожен wбув реченням. У QL цього не буде. Розглянемо наступний ключ символізації:

UD: люди
Lexy:\(x\) любить\(y\)
: Борис

Розглянемо вираз\(Lzz\). Це атомна формула: двомісне присудок, за яким слідують два члени. Всі атомні формули є wff, так\(Lzz\) і w. Це щось означає? Ви можете подумати, що це означає, що\(z\) любить себе, так само,\(Lbb\) як і Борис любить себе. Але\(z\) це змінна; вона не називає якусь людину так, як константа б. \(Lzz\)Wне говорить нам, як інтерпретувати\(z\). Чи означає це всіх? хто-небудь? хтось? Якби у нас був\(z\) -квантіфікатор, він би розповів нам, як інтерпретувати\(z\). Наприклад, означало\(zLzz\) б, що хтось любить себе.

Деякі формальні мови розглядають wlike\(Lzz\) як неявно мають універсальний квантор попереду. Ми не будемо цього робити для QL. Якщо ви маєте на увазі сказати, що всі люблять себе, то вам потрібно написати квантіфікатор: «Для\(zLzz\) того, щоб зрозуміти змінну, нам потрібен квантор, який розповість нам, як інтерпретувати цю змінну. Сфера застосування\(x\) -квантіфікатора, наприклад, є частиною формули, де квантор розповідає, як інтерпретувати\(x\).

Для того, щоб бути точним щодо цього, ми визначаємо зв'язану змінну, яка є появою змінної\(\mathcal{x}\), яка знаходиться в межах\(\mathcal{x}\) -квантіфікатора. Вільна змінна - це виникнення змінної, яка не пов'язана.

Наприклад, розглянемо w∨\(x\) (\(Ex\)∨\(Dy\)) →\(z\) (\(Ex\)→\(Lzx\)). Область застосування універсального квантіфікатора\(x\) - це (\(Ex\)∨\(Dy\)), тому перший\(x\) пов'язаний універсальним квантифікатором, але другий і третій\(x\) s вільні. Існує не\(y\) -квантіфікатор, тому\(y\) є вільним. Обсяг екзистенціального квантифікатора\(z\) є (\(Ex\)→\(Lzx\)), тому обидва\(z\) випадки пов'язані ним.

Ми визначаємо речення QL як wз QL, що не містить вільних змінних.

Нотаційні умовності

Ми приймемо ті ж нотаційні конвенції, які ми зробили для SL (стор. 30.) По-перше, ми можемо залишити oкрайні дужки формули. По-друге, ми будемо використовувати квадратні дужки '[' і ']' замість дужок, щоб збільшити читабельність формул. По-третє, ми будемо залишати дужки між кожною парою сполучників при написанні довгих рядів сполучників. По-четверте, ми будемо залишати дужки між кожною парою диз'юнктів при написанні довгих серій диз'юнкцій.