Основные понятия по теме. Напомним, что под высказыванием мы понимаем предложение, о котором можно сказать одно из двух: истинно оно или ложно

Напомним, что под высказыванием мы понимаем предложение, о котором можно сказать одно из двух: истинно оно или ложно. Понятие предиката обобщает понятие высказывания. Теория предикатов представляет собой более тонкий инструмент, по сравнению с теорией высказываний. В настоящей главе рассматривается основные положения теории алгебры предикатов.

Определение 1 n- местным предикатом, определённым на множествах М₁, М₂,…,М_n, называется предложение, содержащее n переменных x₁,x₂,…,x_n превращающееся в высказывание при подстановки вместо этих переменных любых конкретных элементов из множеств М₁, М₂,…,М_n соответственно.

Обозначать n -местные предикаты будем А (x₁,x₂,…,x_n), причём переменные x₁,x₂,…,x_n называются предметными.

Всякий n- местный предикат А (x₁,x₂,…,x_n) определённый на множествах М₁, М₂,…,М_n есть функция от nаргументов, заданная на указанных множествах и принимающая значение 0(ложно) или 1(истинно).

Будем говорить, что n -местный предикат А (x₁,x₂,…,x_n ) задан на множестве М, если x₁,x₂,…,x_n принимают значения из М.

Примерами предикатов являются любые уравнения и неравенства из школьного курса математики.

Например, x+y>2, где x,y из R есть двухместный предикат заданный на множестве всех действительных чисел R.

Определение 2 Предикат А (x₁,x₂,…,x_n) заданный на множествах

М₁, М₂,…,М_n называется:

1. тождественно истинным, если при любой подстановке вместо переменных x₁,x₂,…,x_n любых конкретных значений из множеств

М₁, М₂,…,М_n он превращается в истинное высказывание.

2. тождественно ложным, если при любой подстановке вместо переменных x₁,x₂,…,x_n любых конкретных значений из множеств М₁, М₂,…,М_n соответственноон превращается в ложное высказывание.

3. выполнимым, если существует по крайней мере один набор значений переменных из М₁, М₂,…,М_n, при которых его значение истинно.

Обозначают: тождественно истинный – А (x₁,x₂,…,x_n) ≡ 1; тождественно ложный – А (x₁,x₂,…,x_n) ≡ 0.

Двухместный предикат x²+y²≥0, заданный на множестве R является тождественно истинным.

Одноместный предикат sinx>1, заданный на множестве R является тождественно ложным.

Примером выполнимого предиката заданного на множестве R является предикат x+y>z.

Определение 3 Множеством истинности предиката А (x₁,x₂,…,x_n) заданного на множествах М₁, М₂,…,М_n называется совокупность всех упорядоченных наборов (a₁,a₂,…,a_n), где a_iÎМ_i, i=1,2,…,n при которых А(a₁,a₂,…,a_n) =1.

Множество истинности предиката А (x₁,x₂,…,x_n) мы будем обозначать N_A.

Пусть A(x)=(x²+3x-4=0) – одноместный предикат, заданный на множестве R. Ясно, что N_A={1,-4}. Однако, если данный предикат задан на множестве натуральных чисел, то его множество истинности N′_A={1}.

Пусть x²+y²=4 – двухместный предикат, заданный на множестве действительных чисел R. Тогда множеством истинности его являются множества всех таких пар действительных чисел, которые являются координатами точек плоскости, лежащих на окружности с центром в начале координат и радиусом 2.

Непосредственно из определения 2 следует справедливость следующего утверждения.

Пусть А (x₁,x₂,…,x_n)n -местный предикат, заданный на множествах

М₁, М₂,…,М_n тогда справедливы следующие утверждения:

1. А (x₁,x₂,…,x_n) является тождественно истинным тогда и только тогда, когда N_A= М₁× М₂×…×М_n;

2. А (x₁,x₂,…,x_n) является тождественноложным тогда и только тогда, когда N_A=Ø;

3. А (x₁,x₂,…,x_n) является выполнимым тогда и только тогда, когда N_A≠Ø;

Определение 4 Два n -местных предиката А(x₁,x₂,…,x_n) и В(x₁,x₂,…,x_n) заданных на одних и тех же множествах М₁, М₂,…,М_n называются равносильными, если для любых наборов переменных (a₁,a₂,…,a_n), где a_iÎМ_i, i=1,2,…,n они принимают одинаковые логические значения.

Непосредственно из данного определения следует, что предикаты

А(x₁,x₂,…,x_n) и В(x₁,x₂,…,x_n) равносильны тогда и только тогда, когда их множества истинности совпадают, то есть N_A=N_В.

Тот факт, что предикаты А(x₁,x₂,…,x_n ) и В(x₁,x₂,…,x_n ) равносильны будем обозначать так: A=B.

Определение 5 Предикат А(x₁,x₂,…,x_n) определённый на множествах М₁, М₂,…,М_n называется следствием предиката В(x ₁, x ₂,…, x _n)определённом над теми же множествами, если он принимает истинные значения на всех тех наборах значений переменных, на которых истинно значение предиката А(x₁,x₂,…,x_n).

Другими словами можно сказать, что предикат А(x₁,x₂,…,x_n) является следствием предиката В(x₁,x₂,…,x_n) тогда и только тогда, когда N_В Í N_A.

Пусть А₁(х)=х (x делится на 2) А₂(х)= х (x делится на 4) два одноместных предиката заданных на множестве натуральных чисел. Ясно, что предикат А₁ является следствием предиката А₂.

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

Определение 6 Отрицанием n-местного предиката А (x₁,x₂,…,x_n) определённого на множествах М₁, М₂,…,М_n называется n -местный предикат, определённый на тех же множествах, обозначаемый , значение которого истинно при всех тех значениях переменных, при которых значение предиката ложно.

Например, отрицанием двухместного предиката x+y>2, определённого на множестве R является предикат x+y<2, определённый на том же множестве R.

Теорема 1 Пусть - n-местный предикат, определённый на множествах М₁, М₂,…,М_n. Тогда справедливо следующее тождество:

.

Доказательство Пусть - произвольный набор переменных из . Тогда =1. Это возможно только тогда, когда =0. А это значит, что

.

Отсюда следует справедливость указанного тождества. Непосредственно из данной теоремы следует:

Следствие Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат тождественно ложен.

Определение 7 Конъюкцией n- местных предикатов и , определённых на множествах называется n-местный предикат, определённый на тех же множествах, обозначаемый · , значение которого истинно при тех и только тех наборах переменных, при которых истинно значение исходных предикатов.

Теорема 2 Пусть и два n-местных предиката определённые на множествах . Тогда справедливо следующее тождество: .

Доказательство Пусть - произвольный набор переменных из , тогда · =1. Это возможно только тогда, когда одновременно =1 и =1. А это значит, что .Теорема доказана.

Непосредственно из данной теоремы следует:

Следствие Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.

Теорема 2 используется в школьном курсе математики при решении систем уравнений и неравенств. Например, требуется решить систему неравенств , x≥3. Для этого нужно найти множество истинности предиката()· (x≥3), определённого на множестве R.Используя теорему 2 получаем:

Определение 8 Дизъюнкцией n-местных предикатов A(x₁, x₂, …, x_n) и B(x₁, x₂, …, x_n), определенных на множествах M₁, M₂, …, M_n называется n-местный предикат, определенный на этих множествах, обозначенный

A(x₁, x₂, …, x_n) V B(x₁, x₂, …, x_n), значение которого истинно при тех и только тех наборов переменных, при которых истинно значение по меньшей мере одного из исходных предикатов.

Теорема 3 Пусть A(x₁, x₂, …, x_n) и B(x₁, x₂, …, x_n) два n-местных предиката, определенные на множествах M₁,M₂, …,M_n. Тогда справедливо следующее тождество N_AVB = N_A U N_B.

Доказательство Пусть (a₁,a₂, …,a_n) – произвольный набор переменных из N_AVB. Тогда A(x₁, x₂, …, x_n) V B(x₁, x₂, …, x_n) = 1. Это возможно только тогда, когда или A(x₁, x₂, …, x_n)=1 или B(x₁, x₂, …, x_n)=1. А это значит, что (a₁ a₂, …,a_n)Î N_A U N_B. Теорема доказана.

Следствие Дизъюнкция двух предикатов тождественно ложна тогда и только тогда, когда оба данных предиката тождественно ложны.

Теорема 4 Пусть A(x₁, x₂, …, x_n), B(x₁, x₂, …, x_n) и C(x₁, x₂, …, x_n) –

n-местные предикаты, определенные на множествах M₁,M₂,…,M_n, тогда справедливы следующие равносильности:

A·B=B·A, AVB=BVA, A·(B·C)=(A·B)·C, AV(BVC)=(AVB)VC, A·(BVC)=A·BVA·C, AVB·C=(AVB)·(AVC), = V , = · .

Доказательство Докажем справедливость следующей равносильности = V . Для этого нужно доказать справедливость следующего тождества N = N . Действительно, пусть (a₁,a₂,…,a_n) – произвольный набор переменных из N _. Тогда =1. Отсюда получаем, что A(a₁,a₂,…,a_n) B(a₁,a₂,…,a_n)=0. Это возможно только в том случае, когда либо A(a₁, a₂, …, a_n)=0, либо B(a₁, a₂, …, a_n)=0. А это значит, что либо , либо . Следовательно, (a₁,a₂,…,a_n) Î N _. Итак, N = N _. Отсюда = V . Аналогичным образом можно доказать справедливость других равносильностей. Теорема доказана.

Определение 9 Пусть A(x₁,x₂,…,x_n) и B(x₁,x₂,…,x_n) n- местные предикаты на множествах M₁,M₂,…,M_n. Их импликацией называется предикат, определенный на тех же множествах, обозначаемый A(x₁, x₂, …, x_n) => B(x₁, x₂, …, x_n), значение которого ложно только при тех наборах переменных, при которых значение предиката A истинно, а B – ложно. Предикат A называется посылкой и B – заключение.

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

Определение 10 Эквивалентность двух n- местных предикатов A(x₁, x₂, …, x_n) и B(x₁, x₂, …, x_n), определенных на множествах M₁, M₂, …, M_n,_, называется n- местный предикат, определенный на тех же множествах, обозначаемый A(x₁, x₂, …, x_n) <=> B(x₁, x₂, …, x_n), значение которого истинно при всех тех наборах переменных, при которых предикаты A и B принимают одинаковые логические значения.

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

В следующей теореме доказаны важные равносильности, выражающие одни логические операции над предикатами через другие.

Теорема 5 Пусть A(x₁, x₂, …, x_n) и B(x₁, x₂, …, x_n) n-местные предикаты, определенные на множествах M₁,M₂, …,M_n. Тогда справедливы следующие равносильности:

A=>B= VB, A∙B= , A<=>B=(A=>B)∙(B=>A).

Доказательство Докажем справедливость следующей равносильности A<=>B=(A=>B)∙(B=>A). Для этого нужно доказать справедливость следующего тождества N_A<=>B=N_{(A=>B)∙(B=>A)}. Пусть (a₁,a₂, …,a_n) – произвольный набор из N_A<=>B. Отсюда следует, что A(a₁,a₂, …,a_n)<=>B(a₁ a₂,… …,a_n)=1. Это возможно только в том случае, когда либо значения A(a₁,a₂,.. …,a_n) и B(a₁,a₂, …,a_n) истинны, либо ложны одновременно. Но в любом из этих случаев значение (A(a₁, a₂, …, a_n)=>B(a₁, a₂, …, a_n)) (B(a₁,a₂, …, …a_n)=>A(a₁, a₂, …, a_n))=1, т.е. (a₁, a₂, …, a_n)Î N_{(A=>B)∙(B=>A) .} Итак, требуемое тождество доказано. Отсюда следует справедливость отмеченной выше равносильности. Остальные равносильности доказываются аналогично. Теорема доказана.

Операции отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность определяются аналогично как для предикатов, так и для высказываний. Однако в теории предикатов существуют операции, для которых нет аналогов в теории высказываний. Такими операциями над предикатами являются две кванторные операции – квантор общности и квантор существования. Известно, что если в одноместном предикате зафиксировать значение переменной, то мы получим высказывание.

Имеется еще один способ. Он основан на применении к предикату операций связывания квантором общности или квантором существования. Такие операции ставят в соответствие одноместному предикату высказывание, значение которого зависит от строения исходного предиката.

Определение 11 Пусть A(x) – одноместный предикат, определенный на множестве M. Обозначим через высказывание, которое читается: «для всякого x из M справедливо A(x)», данное высказывание истинно только в том случае, когда предикат A(x) тождественно истинный.

Символ называется квантором общности по переменной x.

Например, пусть A(x)=(x² 0) определенный на множестве R. Тогда – истинное высказывание, которое читается: «квадрат любого действительно числа неотрицателен». Пусть A(x)=(x>2). Тогда – ложное высказывание, которое читается: «любое действительное число больше 2».

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

Теорема 6 Пусть A(x) – одноместный предикат, определенный на конечном множестве M={ a₁,a₂, …,a_n}, тогда = A(a₁)·A(a₂)·…·A(a_n).

Доказательство Пусть = 1, тогда A(x)≡1. Отсюда A(a_i)=1 для любого a_iÎM. Но тогда A(a₁)·A(a₂)·…·A(a_n)=1. Пусть = 0, тогда

A(x)¹1. А это значит, что существует a_i из M, что A(a_i)=0. Но тогда A(a₁)·A(a₂)·…·A(a_n)=0. Теорема доказана.

Квантор общности можно применять и к многоместным предикатам. Однократное применение квантора к одной из n переменных n-местного предиката порождает (n-1) – местный предикат.

Пусть, например, мы имеем двухместный предикат A(x,y)=(x>y), определенный на множестве R. Тогда " x (x>y) задает одноместный предикат B(y), зависящий от переменной y. Определим тип этого предиката. Возьмем произвольное действительное число y₀. Ясно B(y₀)= " x(x>y₀)=0. Следовательно, B(y) – тождественно ложный предикат.

Заметим, что к (n-1)- местному предикату " x₁ A(x₁,x₂, …,x_n) зависящему от переменных х₁, x₂,x₃, …,x_n можно снова применять операцию связывание квантором общности по одной из свободных переменных. В результате получится (n-2)- местный предикат и т.д.

Пусть, например, мы имеем двухместный предикат A(x,y)=(x+y>2), определенный на R. Тогда x " y (x+y>2) – ложное высказывание, которое читается: «сумма любых двух действительных чисел больше двух».

Определение 12 Пусть A(x) – одноместный предикат, определенный на множестве M. Обозначим x A(x) – высказывание, которое читается: «существует x из M, что справедливо A(x)», данное высказывание ложно только в том случае, когда предикат A(x) тождественно ложный.

Символ x называют квантором существования по переменной x.

Например, пусть A(x)=(x²<0) определен на R. Тогда x (x²<0) – ложное высказывание, которое читается: «существует действительное число, квадрат которого меньше 0».

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

Теорема 7 Пусть A(x) – одноместный предикат, определенный на конечном множестве M={a₁,a₂, …,a_n}. Тогда x A(x)=A(a₁)VA(a₂) V…VA(a_n).

Доказательство Пусть x A(x)=0. Тогда согласно определению 12 A(x) – тождественно ложный предикат, а значит A(a_i)=0 для любого a_iÎM, но тогда A(a₁)VA(a₂) V…VA(a_n)=0. Пусть x A(x)=1. Тогда А(х) – не тождественно ложный предикат. А это значит, что найдется значение а_i из М,что А(а _i)=1. Но тогда А(а₁) А(а₂) … А(а_n)=1. Теорема доказана.

Квантор существования можно применять к многомерным предикатам. Однократное применение квантора к одной из n переменных а- мерного предиката порождает (n-1)- мерный предикат.

Пусть, например, мы имеем двухместный предикат А(х,у)=(х>у) определённый на множестве R. Тогда х(х>y) задает одноместный предикат В(у), зависящий от переменной у. Данный предикат будет тождественно истинным. Действительно, пусть у₀ – произвольное фиксированное действительное число. Тогда В(у₀)= х(х>y₀)=1.

Заметим, что если в многомерном предикате все переменные связаны кванторами, то он будет высказыванием.

Пусть А(х,у)=(х+у>1) двухместный предикат определённый на множестве R.

Тогда из него связыванием переменных х и у можно получить восемь высказываний:

1. х у(х+у>2) – “Для всяких действительных чисел х и у их сумма больше двух”.

2. у х(х+у>2) – “Для всяких действительных чисел у и х их сумма больше двух”.

3. х у(х+у>2) – “Существуют действительные числа х и у, сумма которых больше двух”.

4. у х(х+у>2) – “Существуют действительные числа у и х, сумма которых больше двух”.

5. х у(х+у>2) – “Для всякого действительного числа х существует действительное число у, что их сумма больше двух”.

6. у х(х+у>2) – “Для всякого действительного числа у существует

действительное число х, что их сумма больше двух”.

7. х у (х+у>2) – “Существует действительное число х, что для всякого действительного числа у их сумма больше двух ”.

8. х (х+у>2) – “Существует действительное число у, что для всякого

действительного числа х их сумма больше двух ”.

Нужно заметить, что высказывания 1 и 2 оба ложны и имеют один и тот же смысл; высказывания 3 и 4 оба истины и имеют один и тот же смысл. Как видно, изменение порядка одноименных кванторов не влияет на смысл и значение истинности высказывания. Высказывание 5 истинно, а высказывание 8 ложно.

Высказывание 7 ложно, а высказывание 6 истинно. Как видно, изменение порядков разноименных кванторов приводит к изменению смысла и, возможно, значения истинности высказывания.

Понятие формулы алгебры логики предикатов определим индуктивно.

Вначале задается алфавит символов, из которых будут составляться формулы.

1. Предикатные переменные: x, y, z, x_i, y_i, z_i (iÎN).

2. Нульместные предикатные переменные: А,В,С,А_i,В_i,С_i (iÎN).

3. n- мерные (n>=1) предикатные переменные:

А(…), В(…), А _i(…), В _i(…) (iÎN)

4. Символы логических операций: , , , ,

5. Кванторы: ,