Тема 7 алгебра логики предикатов

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

7.2 Кванторные операции над предикатами.

7.3 Формулы логики предикатов.

7.4 Равносильные преобразования формул.

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

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

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