Математическая логика
Модель. Формула алгебры предикатов сигнатуры
жүктеу/скачать 0.93 Mb.
|
| 2. Модель. Формула алгебры предикатов сигнатуры .
Ряд важнейших понятий алгебры предикатов основывается на понятии модели. Моделью называется любое множество M с заданными на нем предикатами : = < M ; >. Множество M называется основным множеством модели , предикаты – основными предикатами модели , и их набор = < > называется сигнатурой модели . Натуральные числа k1, , kn обозначают арности соответствующих предикатов, а их набор = < k1, , kn > называется типом модели. Примеры. N – множество натуральных чисел, E, S, P – определенные на множестве N равенства, сложения и умножения. Модель = < N; E, S, P > является арифметикой натуральных чисел. Ее сигнатура = < E, S, P > и тип = < 2, 3, 3 >. Любое множество моделей с одной и той же сигнатурой называется классом K моделей сигнатуры . Определим формулу алгебры предикатов сигнатуры . Так же как и в алгебре высказываний, такое определение является индуктивным. Если и – предметные переменные, то выражение есть формула. Такая формула называется атомарной, в ней все вхождения предметных переменных называются свободными. Если U есть формула, в которой имеются свободные вхождения переменной xi, то выражения xi (U) и xi (U) – формулы, в которых все вхождения xi являются связанными, а все вхождения остальных предметных переменных такие же, какими они были в формуле U. При этом формула U называется областью действия соответствующего квантора общности или существования. Если U есть формула, то U – также формула, и все свободные и связанные вхождения предметных переменных в формулу U являются соответственно свободными и связанными вхождениями в формуле U. Если U и V есть формулы, то выражения (U) (V), (U) (V), (U) (V), (U) ~ (V) также являются формулами, причем все вхождения предметных переменных в этих формулах такие же, как и в формулах U и V. Формулы могут быть образованы только с помощью правил 1 – 4. Число скобок в формуле можно уменьшить, если условиться: не заключать в скобки атомарные формулы и формулы, над которыми записан знак отрицания; вместо записи , где – некоторые кванторы, допускать запись ; не использовать скобки, если порядок выполнения операций соответствует приоритету операций, причем приоритет операций утверждения общности и существования наивысший, для остальных операций такой же, как и в алгебре высказываний; не заключать в скобки подформулы, обозначенные буквами; не указывать явно с помощью верхнего индекса местность предиката. Если формула U не содержит свободных вхождений предметных переменных, то используя определения операций, можно вычислить ее логическое значение. В общем случае, если в формуле U есть свободные вхождения предметных переменных, то она не является высказыванием. Но при каждой замене в этой формуле всех свободных вхождений предметных переменных элементами множества M она становится высказыванием, значение которого вычисляется так же, как и в первом случае. Формула называется выполнимой на модели , если для некоторой системы элементов модели сигнатуры значение формулы сигнатуры , т.е. высказывание , является истинным. Формула U сигнатуры называется выполнимой, если существует модель сигнатуры , на которой выполнима формула U. Если высказывание является истинным для любой системы значений , то формула U называется истинной на модели . Если формула не выполнима на модели , то она называется ложной на модели . Если формула U истинна на любой модели класса K , то она называется истинной на классе K . жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|