Значение формулы логики предикатов

    О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество \(M\), на котором определены входящие в эту формулу предикаты.
    Логическое значение формулы логики предикатов зависит от значений трех видов переменных:
    1) значений входящих в формулу переменных высказываний;
    2) значений свободных предметных переменных из множества \(M\);
    3) значений предикатных переменных.
    При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение.
    В качестве примера рассмотрим формулу (обозначим (1)):

\(\exists y\)\(\forall z\)\((P(x,y) \rightarrow P (y,z))\).

в которой двухместный предикат \(P(x,y)\) определен на множестве \(M \times M\), где \(M = \begin{Bmatrix} 0, 1,2, ..., n, ... \end{Bmatrix}\).
    В формулу (1) входит переменный предикат \(P(x,y)\), предметные переменные \(x, y,z\), две из которых \( y\) и \(z\) – связанные кванторами, а \(x\) – свободная.
    Возьмем за конкретное значение предиката \(P(x,y)\) фиксированный предикат \(P^{0} (x,y)\): "\(x\prec y\)", а свободной переменной \(x\) придадим значение \(x ^{0} = 5 \epsilon M\). Тогда при значениях \(y\), меньших \(x^{0} = 5\) предикат \(P^{0} (x^{0}, y)\) принимает значение ложь, а импликация \(P (x,y) \rightarrow P (y,z)\) при всех \(z \epsilon M\) принимает значение истина, то есть высказывание \(\exists y\)\(\forall z\)\((P^{0}(x,y) \rightarrow P ^{0} (y, z))\) имеет значение истина.
    Пример 1. Дана формула \(\forall x\)\(( P(x) \wedge Q(x) \rightarrow R (x))\), где \(P(x)\), \(Q(x)\) и \(R(x)\) определены на множестве \(N\). Найти ее значение, если
    1) \(P (x)\): "число \(x\) делится на 3", \(Q(x)\): "число \(x\) делится на 4", \(R(x)\): "число \(x\) делится на 2";
    2) \(P (x)\): "число \(x\) делится на 3", \(Q(x)\): "число \(x\) делится на 4", \(R(x)\): "число \(x\) делится на 5".
    Решение. В обоих случаях конъюнкция \(P(x) \wedge Q (x)\) есть утверждение, что число \(x\) делится на 12. Но тогда при всех \(x\), если число \(x\) делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.
    Так как из делимости числа \(x\) на 12 не при всех \(x\) следует делимость числа \(x\) на 5, то в случае 2) формула ложна.
    Пример 2. Вычислить значение формулы \(\forall x\)\(\exists y\)\(P(x,y) \rightarrow\)\(\exists x\)\(\forall y\)\(P(x,y)\), если предикат \(P(x,y)\) имеет значение \(P^{0}(x,y)\) - "число \(x\) меньше числа \(y\) и определен на множестве \(M = N\times N\).
    Решение. Так как при указанном значении предиката \(P(x,y)\) высказывание \(\forall x\)\(\exists y\)\(P(x,y)\) означает утверждение, что для любоro натуральноrо числа \(x\) найдется натуральное число \(y\), большее числа \(x\), то это высказывание истинно. В то же время высказывание \(\exists x\)\(\forall y\)\(P(x,y)\) означает утверждение, что существует натуральное число \(x\), которое меньше любоro натуральноrо числа \(y\), которое ложно. При этом исходная формула, очевидно, ложна.


2012-11-08 • Просмотров [ 1635 ]