Определим следование предикатов, докажем связь этого понятия с импликацией и тождественной истинностью предикатов, а также с равносильностью предикатов.
***
Пусть \( \large A_1, A_2, \ldots, A_k, B \) - предикаты, которые определены на множествах \( \large M_1, M_2 , \ldots, M_n \), причём \( \large n \ge 1 \).
Определение 17.2. Предикат \( \large B \) называется
следствием предикатов \( \large A_1,A_2, \ldots, A_k \), если для любых предметных постоянных \( \large a_i \in M_i, \ i=1,2, \ldots, n \), истинность высказываний \( \large A_1(a_1,a_2, \ldots, a_n) \), \( \large A_2(a_1,a_2, \ldots, a_n) \), \( \large \ldots, A_k(a_1,a_2, \ldots, a_n) \) влечёт истинность высказывания \( \large B(a_1,a_2, \ldots, a_n) \).
Замечание 17.8. Учитывая определения множества истинности, включения и пересечения множеств, предикат \( \large B \) является
следствием предикатов \( \large A_1,A_2, \ldots, A_k \), если пересечение множеств истинности предикатов \( \large A_1, A_2, \ldots, A_k \) является подмножеством множества истинности предиката \( \large B \):
\( \large \mathcal{A_1} \cap \mathcal{A_2} \cap \ldots \cap \mathcal{A_k} \subseteq \mathcal{B} \).
Предикат \( \large B \) является следствием предиката \( \large A \), если множество истинности предиката \( \large A \) является подмножеством множества истинности предиката \( \large B \):
\( \large \mathcal{A} \subseteq \mathcal{B} \).
Замечание 17.9. Как и в случае с равносильностью, определение следования имеет смысл лишь при \( \large n \ge 1 \). Если \( \large A_1,A_2, \ldots, A_k,B \) - нульместные предикаты, то следование будем понимать так: истинность высказываний \( \large A_1,A_2, \ldots, A_k \) влечёт истинность высказывания \( \large B \).
Замечание 17.10 Из тождественно ложного предиката следует любой предикат, поскольку пустое множество (множество истинности тождественно ложного предиката) является подмножеством любого множества. Тождественно истинный предикат следует из любого предиката, так как всякое множество есть подмножество универсального множества (множества истинности тождественно истинного предиката).
Замечание 17.11. Предикат \( \large B \) не является следствием предикатов \( \large A_1,A_2, \ldots, A_k \), если найдутся такие предметные постоянные \( \large a_i \in M_i, \ i=1,2, \ldots, n \), что высказывания \( \large A_1(a_1,a_2, \ldots, a_n) \), \( \large A_2(a_1,a_2, \ldots, a_n) \), \( \large \ldots, A_k(a_1,a_2, \ldots, a_n) \) истинны, а высказывание \( \large B(a_1,a_2, \ldots, a_n) \) ложно. Нульместный предикат (высказывание) \( \large B \) не является следствием нульместных предикатов (высказываний) \( \large A_1,A_2, \ldots, A_k \), если высказывания \( \large A_1,A_2, \ldots, A_k \) истинны, а высказывание \( \large B \) ложно.
Замечание 17.12. Предикат \( \large B \) не является
следствием предикатов \( \large A_1,A_2, \ldots, A_k \), если пересечение множеств истинности предикатов \( \large A_1, A_2, \ldots, A_k \) не является подмножеством множества истинности предиката \( \large B \):
\( \large \mathcal{A_1} \cap \mathcal{A_2} \cap \ldots \cap \mathcal{A_k} \not \subseteq \mathcal{B} \).
Предикат \( \large B \) не является следствием предиката \( \large A \), если множество истинности предиката \( \large A \) не является подмножеством множества истинности предиката \( \large B \):
\( \large \mathcal{A} \not \subseteq \mathcal{B} \).
Замечание 17.13. Если предикат \( \large B \) является следствием предикатов \( \large A_1,A_2, \ldots, A_k \), то используется такое обозначение:
\( \large A_1,A_2, \ldots, A_k \Rightarrow B \).
Толстая стрелка вновь используется для того чтобы не путать следование предикатов с пропозициональной операцией - импликацией. Если предикат \( \large B \) не следует из предикатов \( \large A_1,A_2, \ldots, A_k \), то пишут
\( \large A_1,A_2, \ldots, A_k \not \Rightarrow B \).
Замечание 17.14. Чтобы показать, что предикат \( \large B \) следует из предикатов \( \large A_1,A_2, \ldots, A_k \) на множестве \( \large M \) используется обозначение
\( \large A_1,A_2, \ldots, A_k \stackrel{M}{\Rightarrow} B \).
Пример 17.2. Пусть \( \large M= \{0,1,2, \ldots, 10 \} \). Определим на этом множестве два предиката: \( \large A(x) \) означает "\( \large x \) делится на \( \large 10 \)", \( \large B(x) \) означает "\( \large x \) делится на \( \large 5 \)". Ясно, что множеством истинности первого предиката является \( \large \mathcal{A}=\{ 0,10\} \), а множеством истинности второго предиката - \( \large \mathcal{B}=\{ 0,5,10\} \). Предикат \( \large B \) следует из предиката \( \large A \), так как \( \large \mathcal{A} \subseteq \mathcal{B} \).