Сделай Сам Свою Работу на 5

Формулы логики предикатов





При определении формул возникает ещё одно осложнение. Из чистой аккуратности хочется избежать появления странных формул типа , в которой квантор навешивается на переменную, отсутствующую в этой формуле. Для этого одновременно с определением формулы р будет строиться некоторое множество, ей соответствующее – множество параметров этой формулы . Параметры формулы иногда также называют её свободными переменными. Переменные, входящие в формулу, но не являющиеся свободными, обычно называют связанными. Свободная переменная становится связанной, если навесить на неё квантор.

Определение 6.2.Множество Ф называется множеством формул логики предикатов, если удовлетворяет условиям:

(1) O и I (эти две формулы называются тривиальными), ;

(2) , (такие формулы называются атомарными), есть множество всех предметных переменных, входящих в термы ;

(3) если , то и , ;

(4) если , то и , ;

(5) если , , то , ;

(6) если множество W удовлетворяет свойствам (1) – (5), то .

Замечания.(1) Определение множества формул снова индуктивное.

(2) Множество формул существует и единственно, доказательство этого факта снова аналогично многому, приведённому ранее.



(3) Символы отношений во многом аналогичны функциональным символам. Символ заменяет собой привычное ; на нём не написана арность отношения, так что в отсутствие коллизий всегда считается, что арность как раз соответствует количеству термов, стоящих следом за знаком отношения; формулой не является выражение .

(4) «Победив» «противоестественные кванторы», мы теперь можем (при желании) их восстановить, заменив в пункте (5) определения формулу на более общую .

(5) В формуле иксы, стоящие до и после буквы Е – различные! При этом оба вида иксов – связанные. Вообще, появление квантора слева «закрывает» (связывает!) переменную так же, как появление символа заканчивает использование x в качестве переменной интегрирования.

(6) Впрочем, вполне возможно, что одна и та же буква использована для обозначения одной свободной и одной или нескольких связанных переменных: .

(7) В действительности почти никогда не требуется разрешать использовать в формулах все возможные символы функций и отношений. Как правило, рассматривается множество тех функций и отношений, которые предполагается использовать, у всех функциональных символов (явно или неявно) указывается количество аргументов, а у всех символов отношений – арность. Такой набор называется сигнатурой, и можно говорить о множествах формул данной сигнатуры.



(8) Равным образом, приведённый набор логических связок, использованных при построении формул (и даже кванторов, трудно представить, да? J) не является единственно возможным.

(9) Очень похожее на формулу выражение , и даже более определённое формулой не является, потому что неизвестно, сколько в ней переменных (как это – неизвестно? Их n штук J).

(10) Дав определения в терминах языка, полезно вернуться к скобочной записи функций и отношений, равно как и к обычным обозначениям логических связок: так понятнее J.

Лемма 6.1.Для любой формулы множество её параметров определено однозначно.

Доказательствопроводится индукцией по множеству формул. Пусть U – множество тех формул, для которых утверждение верно. Тогда и удовлетворяет условиям (1) – (5) из определения множества Ф: если для предыдущей формулы множество параметров было определено однозначно, то оно однозначно определено и для следующей, чуть более сложной (в определении прямо написано, чему оно равно J). Тогда, в силу условия (6), .

QED

 

Пример.Формула является таковой только при условии, что f – символ функции двух переменных, G – символ двухместного отношения, S – символ трёхместного отношения. При этом . Она является формулой потому, что формулами являются выражения , , , и . Последние две формулы являются атомарными. Они, в свою очередь, являются формулами потому что выражения , , x, y, z являются термами. Далее, .



 

Интерпретации

Определение 6.3.Пусть задана некоторая сигнатура и непустое множество , которое в данном контексте называется предметным множеством или носителем. Интерпретацией данной сигнатуры (на данном носителе) называется соответствие, сопоставляющее каждому символу функции от k переменных (конкретную) функцию , а каждому символу n-арного отношения (конкретное) n-арное отношение на множестве (которое можно отождествить с функцией ).

Замечание. Среди символов отношений весьма часто встречается двухместный символ равенства =. Интерпретации, в которых этот символ интерпретируется как равенство элементов множества , называются нормальными или собственными.

Пример.Рассмотрим аксиомы теории групп. При этом сигнатуры можно выбирать по-разному.

Вариант 1. Рассмотрим сигнатуру , где – символ функции двух переменных, – символ функции одного переменного, е – символ функции от нуля переменных, то есть константы, = – символ двухместного отношения. Тогда аксиомы теории групп можно записать формулами так:

(Г1) ;

(Г2) ;

(Г3) .

Вариант 2. Предположим, что решено не включать функцию обращения в сигнатуру, то есть рассмотреть сигнатуру поменьше: . Тогда вместо формулы (Г3) можно добавить формулу, которая её заменит:

(Г4) .

Вариант 3. Попробуем обойтись без термов. Заменим функциональный символ символом трёхместного отношения S, которое будем понимать так: . В этом случае вместо формулы (Г1) следует написать ужасное:

(Г5) .

 

Определение истинности

Пусть фиксирована сигнатура (и, соответственно, множество всех формул этой сигнатуры) и некоторая её интерпретация. Значения термов и формул удобнее всего определять «коллективно», для всех термов и формул сразу.

Определение 6.4.(1) Оценкой назовём отображение , сопоставляющее каждой предметной переменной x некоторый элемент предметного множества – её значение .

(2) Пусть – оценка. Определим значение терма t на оценке индуктивно посредством правил:

а) если , , то ;

б) если , , то не зависит от ξ и равно значению , которое принимает эта функция в рассматриваемой интерпретации;

в) если , где , то .

 

В этот момент определение следует прервать, чтобы сформулировать одно тривиальное утверждение.

Лемма 6.2.Для любого терма рассматриваемой (то есть – тоже любой наперёд заданной J) сигнатуры и для любой оценки значение этого терма определено однозначно.

Доказательствопроводится абсолютно аналогично рассуждению, доказывающему лемму 6.1.

QED

 

Вернёмся к определению истинности.

(3) Значение формулы q на данной оценке в данной интерпретации может быть равно 0 или 1 (истина или ложь) и определяется индуктивно посредством правил:

а) , для любой оценки ξ;

б) если – атомарная формула, то , где – интерпретация символа n-арного отношения А;

в) ;

г) , , .

д) Для определения истинности формул вида и на оценке ξ следует рассмотреть множество всевозможных оценок, совпадающих с оценкой ξ всюду, кроме, возможно, её значения на переменной x. Положим:

i) ;

ii) .

(4) Формула, не имеющая параметров, называется замкнутой или суждением. Истинность суждения, очевидно, зависит только от интерпретации и не зависит от конкретной оценки.


 

 

Выразимость предикатов

Выразимые предикаты

Пусть фиксировано множество формул некоторой сигнатуры и некоторая её интерпретация с носителем Ω.

Определение 7.1.Пусть k-местный предикат. Назовём его выразимым в рассматриваемой интерпретации, если существует формула с k параметрами , такая что для любой оценки ξ . В этом случае говорят, что формула выражает предикат S.

Замечание.Формула имеет фиксированный набор переменных, являющихся её параметрами. Предикат – не имеет, они имеет только арность, она же – местность (количество аргументов). Соответственно, выразимый предикат выражается не одной только формулой. Впрочем, возможно, что предикат выражается вообще несколькими принципиально различными формулами. Собственно, не возможно, а – наверняка J!

Примеры. Важнейшей из выразимостей для нас является выразимость в арифметике. Соответствующая сигнатура состоит из двух двухместных функциональных символов: сложения и умножения и одного символа двухместного отношения – равенства. При этом рассматривается собственная интерпретация со стандартным смыслом сложения и умножения. В качестве предметного множества рассматривается множество натуральных чисел, начинающееся с нуля. Выразимые в этой сигнатуре предикаты называются арифметическими. Их важность связана с теоремой Гёделя о неполноте, которая уже обсуждалась. Арифметическими, например, являются следующие предикаты:

(1) : ;

(2) : ;

(3) : ;

(4) для любого фиксированного натурального n: – при фиксированном n это «настоящая» формула;

(5) : ;

(6) «x – простое число»: ;

(7) «x является степенью двойки»: , то есть: «любой делитель, не являющийся единицей, является чётным числом», не вполне тривиально, что это равносильно тому, что число является двойкой.

(8) Предикат «x является степенью четверки» является арифметическим, хотя приём из предыдущего примера тут явно не проходит. Могла бы выручить «формула» вида , но она не является настоящей формулой, так как количество переменных в ней заранее неизвестно. К счастью, в точности для таких случаев у нас есть β-функция Гёделя (есть и другой приём). Аналогично показывается, что арифметическим является двухместный предикат .

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.