5.15: Резюме

Last updated
Save as PDF

Page ID: 53039

\( \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}}\)

Template:MathJaxZach

Мова першого порядку складається з символів константи, функції та предикатів. Функціональні та постійні символи приймають задану кількість аргументів. У мові арифметики, наприклад, ми маємо єдиний постійний символ\(\Obj 0\), один символ функції на 1 місце\(\prime\), два два символи функції\(+\) та\(\times\), і один символ предиката на 2 місця\(<\). З змінних і постійних і функціональних символів формуємо терміни мови. З термінів мови разом з його присудком символом, а також символом\(\eq[][]\) ідентичності формуємо атомні формули. А в свою чергу з них, використовуючи логічні зв'язки\(\lnot\),\(\lor\),\(\land\),\(\lif\),\(\liff\) і квантори\(\lforall{}{}\) і\(\lexists{}{}\) формуємо його формули. Оскільки ми обережні, щоб завжди включати необхідні дужки в процес формування термінів і формул, завжди є точно один спосіб читання формули. Це дає можливість визначати речі шляхом індукції на структуру формул.

Входження змінних у формулах іноді регулюються відповідним квантором: якщо змінна зустрічається в області квантора, вона вважається зв'язаною, інакше вільною. Всі ці поняття мають індуктивні визначення, і ми також індуктивно визначаємо операцію підстановки терміна на змінну у формулі. Формули без вільних входжень змінних називаються реченнями.

Семантика мови першого порядку задається структурою для цієї мови. Він складається з домену, і елементи цього домену присвоюються кожному постійному символу. Функціональні символи інтерпретуються функціями та символами відношення на домені. Функція з набору змінних до домену є присвоєнням змінної. Співвідношення задоволеності стосується структур, змінних присвоєнь і формул;\(\Sat[,s]{M}{A}\) визначається індукцією на структуру\(A\). \(\Sat[,s]{M}{A}\)залежить тільки від інтерпретації символів, що відбуваються в\(A\), і, зокрема, не залежить від того,\(s\) чи не\(A\) містить вільних змінних. Отже, якщо\(A\) це речення,\(\Sat{M}{A}\) якщо\(\Sat[,s]{M}{A}\) для будь-якого (або всіх)\(s\).

Відношення задоволеності є основою для всіх смислових понять. Речення є дійсним\(\Sat{ {} }{A}\), якщо воно задовольняється в кожній структурі. Речення тягне за\(A\) собою набір речень\(\Gamma\), якщо\(\Sat{M}{A}\) для всіх\(\Gamma \Entails A\),\(\Struct{M}\) які задовольняють кожне речення в\(\Gamma\). Набір\(\Gamma\) є задовільним, якщо є якась структура, яка задовольняє кожне речення в\(\Gamma\), інакше незадовільне. Ці поняття взаємопов'язані, наприклад,\(\Gamma \Entails A\) якщо\(\Gamma \cup \{\lnot A\}\) є незадовільним.