Предикат. операции над предикатами

Неформально предикат возможно выяснить как некое высказывание, значение которого зависит от значений предметных переменных из множества M, на котором выяснен предикат.

Примеры:

a) P(x) : “x имеется простое число”;

(Тут и везде в будущем для задания предиката будем применять краткую форму записи, которая детально расписывается следующим образом: “x имеется простое число”.)

b) D(x,y) : “x нацело делится на y”;

c) R(x,y) : “x y”.

В качестве предметного множества для этих примеров возможно разглядывать каждые числовые множества, например, в примерах a), b) – M = I, а в c) – M = N.

Более строго предикат возможно выяснить как отображение n-ной степени множества M, именуемой местностью либо арностью предиката в двухэлементное множество B = {1, 0}

.

При подстановке в предикат вместо предметных переменных комплекта значений возьмём логическое высказывание (так , а ). Так, предикат представляет собой переменное высказывание (либо совокупность высказываний), истинность которого определяется подстановкой разных значений предметных переменных.

Так как предикаты принимают значения из множества B, то для них выяснены логические операции ~. Помимо этого, для предикатов вводятся операции утверждения существования и утверждения всеобщности.

Операция утверждение всеобщности ставит в соответствие высказывательной форме P(x) высказывание (читается как, P(x) действительно для всех x из множества M, на котором выяснен предикат). Высказывание действительно тогда и лишь тогда, в то время, когда высказывание P(a) действительно для любого элемента .

Операция утверждение существования ставит в соответствие высказывательной форме P(x) высказывание (читается как, существует таковой x из множества M, для которого высказывание P(x) действительно). Высказывание действительно тогда и лишь тогда, в то время, когда высказывание P(a) действительно хотя бы для одного элемента .

Символы и $ именуются кванторами всеобщности и существование (квантор в переводе с латинского – определение количества). Переход от высказывательной формы P(x) к высказываниям либо именуется навешиванием квантора либо связыванием переменной x (время от времени – квантификацией переменной x). Переменная, на которую навешен квантор, именуется связанной, несвязанная переменная именуется свободной. Суть связанных и свободных переменных в предикатных выражениях разен. Свободная переменная – это простая переменная, которая может принимать разные значения из M, а выражение P(x) – переменное высказывание, зависящее от значения x. Выражения и не зависят от переменной x и при фиксированных P и M имеют в полной мере определенное значение. Переменные, являющиеся по существу связанными, видятся не только в математической логике. К примеру, в выражениях либо переменная x связана, при фиксированной f первое выражение равняется определенному числу, а второе есть функцией от a и b.

Так, в высказываниях и говорится не о особенностях отдельных элементов множества M, а о особенностях самого множества M. Истинность либо ложность этих высказываний не зависит от того, как обозначена предметная переменная, входящая в них, и ее возможно заменить каждый предметной переменной, к примеру y, и взять высказывания и , имеющие тот же самый суть и те же самые значения истинности, что и исходные высказывания.

В общем случае для n-арного предиката, в случае если , операции утверждения всеобщности либо существования возможно делать k раз (порядок выбора переменных, по которым происходит навешивание квантора, возможно любым, кроме их повторение) и взять выражение

, (1)

где обозначает квантор всеобщности либо существования. Переменные в высказывательной форме (1) являются связанными, а – свободными.

Высказывательная форма (1) при замене переменных элементами множества M обращается в подлинное либо фальшивое высказывание. При k = n высказывательная форма (1) делается высказыванием. Изменение порядка следования разных кванторов изменяет суть высказывания, что может поменять его истинностное значение.

К примеру, для предиката делимости D(x,y):

высказывание читается, как “для любого x существует y, такое, что x делится на y”, и есть подлинным высказыванием, поскольку любое натуральное x делится на себя и на 1, т.е. y = x либо y =1;

высказывание читается, как “существует y, на что делится любой x ”, и кроме этого есть подлинным высказыванием, поскольку на значение y =1 делится любое натуральное x.

2. Модель. Формула алгебры предикатов сигнатуры z

Последовательность наиболее значимых понятий алгебры предикатов основывается на понятии модели.

Моделью M именуется любое множество M с заданными на нем предикатами :

M = M ; .

Множество M именуется главным множеством модели M, предикаты – главными предикатами модели M, и их комплект z = именуется сигнатурой модели M. Натуральные числа k1, ¼ , kn обозначают арности соответствующих предикатов, а их комплект t = k1, ¼ , kn именуется типом модели.

Пример.

N – множество натуральных чисел, E, S, P – определенные на множестве N предикаты равенства, умножения и сложения, т.е.

.

Модель Mа = N ; E, S, P есть математикой натуральных чисел. Ее синатура z = E, S, P и тип t = .

Любое множество моделей с одной и той же сигнатурой z именуется классом Kz моделей сигнатуры z.

Определим формулу алгебры предикатов сигнатуры z. Так же как и в алгебре высказываний, такое определение есть индуктивным.

1. В случае если и – предметные переменные, то выражение имеется формула. Такая формула именуется атомарной, в ней все вхождения предметных переменных именуются свободными.

2. В случае если U имеется формула, в которой имеются свободные вхождения переменной xi, то выражения xi (U) и $ xi (U) – формулы, в которых все вхождения xi являются связанными, а все вхождения остальных предметных переменных такие же, какими они были в формуле U. Наряду с этим формула U именуется областью действия соответствующего квантора всеобщности либо существования.

3. В случае если U имеется формула, то O U – кроме этого формула, и все свободные и связанные вхождения предметных переменных в формулу U являются соответственно свободными и связанными вхождениями в формуле O U.

4. В случае если U и V имеется формулы, то выражения (U) U (V), (U) U (V), (U) ® (V), (U) ~ (V) кроме этого являются формулами, причем все вхождения предметных переменных в этих формулах такие же, как и в формулах U и V.

5. Формулы смогут быть образованы лишь посредством правил 1 – 4.

Число скобок в формуле возможно уменьшить, в случае если условиться:

не заключать в скобки формулы и атомарные формулы, над которыми записан символ отрицания;

вместо записи , где – кое-какие кванторы, допускать запись ;

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

не заключать в скобки подформулы, обозначенные буквами;

не показывать очевидно посредством верхнего индекса местность предиката.

В случае если формула U не содержит свободных вхождений предметных переменных, то, применяя определения операций, возможно вычислить ее логическое значение. В случае если в формуле U имеется свободные вхождения предметных переменных, то она есть предикатом, именуемым формульным, зависящим от значений этих переменных. Но при каждой замене в данной формуле всех свободных вхождений предметных переменных элементами множества M она делается высказыванием, значение которого вычисляется равно как и в первом случае. К примеру, формула на модели математики натуральных чисел есть формульным предикатом от переменных x и y, т.е.

(1)

и определяет отношение . Легко проверить, что , , .

Формула именуется выполнимой на модели M, в случае если для некоей совокупности элементов модели M сигнатуры z значение формулы сигнатуры z, т.е. высказывание , есть подлинным.

Формула U сигнатуры z именуется выполнимой, в случае если существует модель сигнатуры z, на которой выполнима формула U.

В случае если высказывание есть подлинным для любой совокупности значений IM, то формула U именуется подлинной на модели M.

В случае если формула не выполнима на модели M, то она именуется фальшивой на модели M.

Так формула (1) есть выполнимой на модели N, но она не будет ни подлинной, ни фальшивой на ней. Формула

высказывает однозначность операции сложения и есть подлинной на данной модели, а формула – фальшивой.

В случае если формула U подлинна на любой модели класса Kz , то она именуется подлинной на классеKz .

Введение в логику, урок 4: кванторы и Предикаты


Также читать:

Понравилась статья? Поделиться с друзьями: