double arrow

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

Определение 1 n- местным предикатом, определённым на множествах М1, М2,…,Мn, называется предложение, содержащее n переменных x1,x2,…,xn превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств М1, М2,…,Мn соответственно.

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

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

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

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

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

Определение 2 Предикат А (x1,x2,…,xn), заданный на множествах

М1, М2,…,Мn называется:

1) тождественно истинным, если при любой подстановке вместо переменных x1,x2,…,xn любых конкретных значений из множеств М1, М2,…,Мn он превращается в истинное высказывание;

2) тождественно ложным, если при любой подстановке вместо переменных x1,x2,…,xn любых конкретных значений из множеств М1, М2,…,Мn соответственноон превращается в ложное высказывание;

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

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

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

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

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

Определение 3 Множеством истинности предиката А (x1,x2,…,xn) заданного на множествах М1, М2,…,Мn называется совокупность всех упорядоченных наборов (a1,a2,…,an), где ai Î Мi, i=1,2,…,n при которых А(a1,a2,…,an) =1.

Множество истинности предиката А (x1,x2,…,xn) мы будем обозначать NA.

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

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

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

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

М1, М2,…,Мn тогда справедливы следующие утверждения:

1) А (x1,x2,…,xn) является тождественно истинным тогда и только тогда, когда NA= М1× М2×…×Мn;

2) А (x1,x2,…,xn) является тождественноложным тогда и только тогда, когда NA;

3) А (x1,x2,…,xn) является выполнимым тогда и только тогда, когда NA≠Ø.

Определение 4 Два n -местных предиката А(x1,x2,…,xn) и В(x1,x2,…,xn) заданных на одних и тех же множествах М1, М2,…,Мn называются равносильными, если для любых наборов переменных (a1,a2,…,an), где aiÎМi, i=1,2,…,n они принимают одинаковые логические значения.

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

А(x1,x2,…,xn) и В(x1,x2,…,xn) равносильны тогда и только тогда, когда их множества истинности совпадают, то есть NA=NВ.

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

Определение 5 Предикат А(x1,x2,…,xn) определённый на множествах М1, М2,…,Мn называется следствием предиката В(x 1, x 2,…, x n)определённом над теми же множествами, если он принимает истинные значения на всех тех наборах значений переменных, на которых истинно значение предиката А(x1,x2,…,xn).

Другими словами можно сказать, что предикат А(x1,x2,…,xn) является следствием предиката В(x1,x2,…,xn) тогда и только тогда, когда NВ Í NA.

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

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

Определение 6 Отрицанием n-местного предиката А (x1,x2,…,xn,), определённого на множествах М1, М2,…,Мn называется n -местный предикат, определённый на тех же множествах, обозначаемый , значение которого истинно при всех тех значениях переменных, при которых значение предиката ложно.

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

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

.

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

.

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

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

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

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

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

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

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

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

Определение 8 Дизъюнкцией n-местных предикатов A(x1, x2, …, xn) и B(x1, x2, …, xn), определенных на множествах M1, M2, …, Mn называется

n-местный предикат, определенный на этих множествах, обозначенный

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

Теорема 3 Пусть A(x1, x2, …, xn) и B(x1, x2, …, xn) два n-местных предиката, определенные на множествах M1,M2, …,Mn. Тогда справедливо следующее тождество NAVB = NA U NB.

Доказательство. Пусть (a1,a2, …,an) – произвольный набор переменных из NAVB. Тогда A(x1, x2, …, xn) V B(x1, x2, …, xn) = 1. Это возможно только тогда, когда или A(x1, x2, …, xn)=1 или B(x1, x2, …, xn)=1. А это значит, что (a1 a2, …,an)Î NA U NB. Теорема доказана.

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

Теорема 4 Пусть A(x1, x2, …, xn), B(x1, x2, …, xn) и C(x1, x2, …, xn) –

n-местные предикаты, определенные на множествах M1,M2,…,Mn, тогда справедливы следующие равносильности:

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 . Действительно, пусть (a1,a2,…,an) – произвольный набор переменных из N . Тогда =1. Отсюда получаем, что A(a1,a2,…,an) B(a1,a2,…,an)=0. Это возможно только в том случае, когда либо A(a1, a2, …, an)=0, либо B(a1, a2, …, an)=0. А это значит, что либо , либо . Следовательно, (a1,a2,…,an) Î N . Итак, N = N . Отсюда = V . Аналогичным образом можно доказать справедливость других равносильностей. Теорема доказана.

Определение 9 Пусть A(x1,x2,…,xn) и B(x1,x2,…,xn) n- местные предикаты на множествах M1,M2,…,Mn. Их импликацией называется предикат, определенный на тех же множествах, обозначаемый A(x1, x2, …, xn) => B(x1, x2, …, xn), значение которого ложно только при тех наборах переменных, при которых значение предиката A истинно, а B – ложно. Предикат A называется посылкой и B – заключением.

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

Определение 10 Эквивалентность двух n- местных предикатов A(x1, x2, …, xn) и B(x1, x2, …, xn), определенных на множествах M1, M2, …, Mn,, называется n- местный предикат, определенный на тех же множествах, обозначаемый A(x1, x2, …, xn) <=> B(x1, x2, …, xn), значение которого истинно при всех тех наборах переменных, при которых предикаты A и B принимают одинаковые логические значения.

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

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

Теорема 5 Пусть A(x1, x2, …, xn) и B(x1, x2, …, xn) n-местные предикаты, определенные на множествах M1,M2, …,Mn. Тогда справедливы следующие равносильности:

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

Доказательство Докажем справедливость следующей равносильности A<=>B=(A=>B)∙(B=>A). Для этого нужно доказать справедливость следующего тождества NA<=>B=N(A=>B)∙(B=>A). Пусть (a1,a2, …,an) – произвольный набор из NA<=>B. Отсюда следует, что A(a1,a2, …,an)<=>B(a1 a2,… …,an)=1. Это возможно только в том случае, когда либо значения A(a1,a2,.. …,an) и B(a1,a2, …,an) истинны, либо ложны одновременно. Но в любом из этих случаев значение (A(a1, a2, …, an)=>B(a1, a2, …, an)) (B(a1,a2, …, …an)=>A(a1, a2, …, an))=1, т.е. (a1, a2, …, an)Î N(A=>B)∙(B=>A) . Итак, требуемое тождество доказано. Отсюда следует справедливость отмеченной выше равносильности. Остальные равносильности доказываются аналогично. Теорема доказана.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: