Лекция №13

Тема: ТОЖДЕСТВЕННО ИСТИННЫЕ ПРЕДИКАТЫ

Основные вопросы, рассматриваемые на лекции:

1. Области определения и множества истинности отрицания P

2. Области определения дизъюнкции и конъюнкции P и Q

3. Множества истинности дизъюнкции и конъюнкции P и Q

4. Множества истинности импликации и эквивалентности P и Q

5. Области определения и множества истинности обощения и подтверждения

6. Тождественно истинные предикаты

Краткое содержание лекционного материала

Отрицанием предиката P (x ₁,…, x_n) называется предложение "Неверно, что P (x ₁,…, x_n)". Обозначение: Ø P (x ₁,…, x_n). Область определения предиката Ø P совпадает с множеством U = U ₁´…´ U_n – областью определения предиката P. При замене переменных x ₁,…, x_n их допустимыми значениями a ₁Î U ₁, …, a_n Î U_n отрицание предиката обращается в отрицание высказывания, истинностное значение которого определяется по условию:

Множеством истинности предиката Ø P является дополнение множества истинности предиката P до U: T _{Ø P} = U T_P.

Характеристическую функцию предиката Ø P можно выразить через характеристическую функцию предиката P: l_{Ø P} =1-l _P.

Пусть P (x ₁,…, x_m, x_{m +1},…, x_{m + n}) и Q (x_{m +1},…, x_{m + n}, x_{m + n +1},…, x_{m + n + s}) – предикаты с общими переменными x_{m +1},…, x_{m + n}. U ₁, …, U_{n + n + s} Далее мы в некоторых случаях для краткости переменные у предикатов не указываем.

Дизъюнкцией (конъюнкцией, импликацией, эквивалентностью) двух предикатов P (x ₁,…, x_m, x_{m +1},…, x_{m + n}) и Q (x_{m +1},…, x_{m + n}, x_{m + n +1},…, x_{m + n + s}) называется предложение " P или Q " (соответственно, " P и Q ", "если P, то Q ", " P тогда и только тогда, когда Q "). Обозначение: (P Ú Q)(x ₁,…, x_{m + n + s})=

= P (x ₁,…, x_m, x_{m +1},…, x_{m + n})Ú Q (x_{m +1},…, x_{m + n}, x_{m + n +1},…, x_{m + n + s}) (аналогично в остальных случаях). Пусть U ₁, …, U_{n + n + s} – множества допустимых значений переменных x ₁, …, x_{m + n + s} соответственно. Тогда U = U ₁´…´ U_{n + n + s} – область определения предиката P Ú Q.

При замене переменных x ₁,…, x_{n + n + s} их допустимыми значениями a ₁Î U ₁, …, a_{n + n + s} Î U_{n + n + s} дизъюнкция, конъюнкция, импликация, эквивалентность двух предикатов обращается соответственно в дизъюнкцию конъюнкцию, импликацию, эквивалентность двух высказываний, истинностное значение которых определяется следующим образом:

Рассмотрим для простоты предикаты P и Q с одними и теми же свободными переменными x ₁,…, x_n и с одним и тем же множеством допустимых значений U = U ₁´…´ U_n. Тогда множеством истинности дизъюнкции, конъюнкции, импликации и эквивалентности предикатов P и Q представляются через множества истинности предикатов P и Q следующим образом:

T_{P Ú Q} = T_P È T_Q, T_{P Ù Q} = T_P Ç T_Q, T_{P Þ Q} =(U T_P)È T_Q,

T_{P Û Q} =((U T_P)È T_Q)Ç(T_P È(U T_Q)).

Характеристические функции предиката дизъюнкции, конъюнкции, импликации и эквивалентности предикатов P и Q можно выразить через характеристические функции предикатов P и Q следующим образом:

l _{P Ú Q} =l _P +l _Q -l _P ×l _Q, l _{P Ù Q} =l _P ×l _Q, l _{P Þ Q} =1-l _P +l _P ×l _Q,

l _{P Û Q} =1-l _P -l _Q +2l _P ×l _Q.

В логике предикатов, кроме операций алгебры высказываний, рассматриваются операции навешивания кванторов.

Во-первых, кванторы – это символы " (все) и $ (существует).

Во-вторых, кванторы – это слова вида "Для всех x " и "Существует x, такое, что", которые обозначаются соответственно " x и $ x.

Пусть A = P (x ₁,…, x_n) – предикат с областью определения U = U ₁´…´ U_n. Обобщением (подтверждением) P (x ₁,…, x_n) по переменной x называется предложение вида "Для всех x верно, что A " (соответственно, "Существует x, такое, что A "). Эти предикат обозначается " xA ($ xA). Предикаты " xA и $ xA содержат n -1 свободных переменных, если x Î{ x ₁,…, x_n } (переменная x = x_i, где i =1, …, n, становится связанной), и содержат n свободных переменных x ₁,…, x_n, если x Ï{ x ₁,…, x_n }.

Если x Ï{ x ₁,…, x_n }, то при замене переменных x ₁,…, x_n их допустимыми значениями a ₁Î U ₁, …, a_n Î U_n предикаты " xA, $ xA и A обращаются в высказывания, истинностные значения которых равны:

P (a ₁,…, a_n)=" xP (a ₁,…, a_n)=$ xP (a ₁,…, a_n).

Если x = x_i, где i =1, …, n, то истинностные значения " xA и $ xA при замене переменных x ₁,…, x_{i -1}, x_{i +1},…, x_n их допустимыми значениями a ₁Î U ₁, …, a_{i -1}Î U_{i -1}, a_{i +1}Î U_{i +1}, …, a_n Î U_n обращаются в высказывания, истинностные значения которых определяется следующим образом:

Терм t допустим для подстановки в формулу A вместо переменной x, если в A нет подформул вида " yB для всех переменных y из t, отличных от x.

Пусть P (x ₁,…, x_n) – предикат с областью определения U = U ₁´…´ U_n. Говорят, что:

P (x ₁,…, x_n) – тождественно истинный (или истинный) на множестве U предикат, если P (a ₁,…, a_n)=1 для всех a ₁Î U ₁, …, a_n Î U_n;

P (x ₁,…, x_n) – тождественно ложный (или ложный) на множестве U предикат, если P (a ₁,…, a_n)=0 для всех a ₁Î U ₁, …, a_n Î U_n;

P (x ₁,…, x_n) – выполнимый на множестве U предикат, если P (a ₁,…, a_n)=1 для некоторых a ₁Î U ₁, …, a_n Î U_n;

P (x ₁,…, x_n) – опровержимый на множестве U предикат, если P (a ₁,…, a_n)=0 для некоторых a ₁Î U ₁, …, a_n Î U_n.

Высказывание " xP (x) истинно (ложно), если P (x) – тождественно истинный (опровержимый) предикат. Высказывание $ xP (x) истинно (ложно), если P (x) – выполнимый (тождественно ложный) предикат.

Пример 1. Равенство xy = yx является тождественно истинным предикатом на множестве U = U ₁´ U ₂, если U ₁= U ₂= R – поле действительных чисел, но является опровержимым предикатом, если за U ₁, U ₂ – множества всех квадратных матриц порядка 2 над полем R.

Пример 2. Свойство линейности порядка тождественно истинный предикат на множестве U = R ´ R, где отношение есть <, и опровержимый предикат на множестве U =2 ^M ´2 ^M, где 2 ^M – множество всех подмножеств некоторого множества M, где отношение есть Ì.

Примеры 1 и 2 показывают, что свойство тождественной истинности предиката на множестве U существенно зависит от структуры операций и отношений, определенных на множестве U.

Пример 3. Предложение " x $ y x = y является тождественно истинным предикатом на любом множестве вида U = U ₁´ U ₂. Предложение $ x " y x = y является тождественно истинным предикатом на любом множестве вида U ={ a }´{ b } и является опровержимым предикатомна любом множестве вида U = U ₁´ U ₂, если U ₁È U ₂ содержит не менее двух элементов.

Пример 4. Импликация (" x P (x)Ú" x Q (x))Þ" x (P (x)Ú Q (x)) является тождественно истинным предикатом на любом множестве U для любых предикатов P (x) и Q (x). Импликация (" x P (x)Ú" x Q (x))Þ" x (P (x)Ú Q (x)) является опровержимым предикатом, например, на множестве U = R, если P (x) есть x <100 и Q (x) есть x >90.

Примеры 3 и 4 показывают, что свойство тождественной истинности предиката существенно зависит от формы построения предиката при помощи логических связок и кванторов.