Основные понятия и определения алгебры логики предикатов

Определение 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).} Итак, требуемое тождество доказано. Отсюда следует справедливость отмеченной выше равносильности. Остальные равносильности доказываются аналогично. Теорема доказана.