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

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

Предикатов.

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

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

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

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

7.1 Основные понятия и определения алгебры логики предикатов Определение 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 Называется следствием предиката В(X1,X2,…,XN) определённом над теми же множествами, если он принимает истинные значения на всех тех наборах значений переменных, на которых истинно значение предиката А(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). Итак, требуемое тождество доказано. Отсюда следует справедливость отмеченной выше равносильности. Остальные равносильности доказываются аналогично. Теорема доказана.

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

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

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

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

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

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

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

Доказательство: Пусть = 1, тогда A(X)≡1. Отсюда A(ai)=1 для любого AiÎM. Но тогда A(a1)·A(a2)·…·A(an)=1. Пусть = 0, тогда

A(X)¹1. А это значит, что существует Ai из M, что A(Ai)=0. Но тогда A(a1)·A(a2)·…·A(an)=0. Теорема доказана.

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

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

Заметим, что к (N-1)-Местному предикату "X1 A(X1,X2, … ,Xn) зависящему от переменных Х1, X2,X3, … ,Xn можно снова применять операцию связывание квантором общности по одной из свободных переменных. В результате получится (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)=(X2<0) определен на R. Тогда X (X2<0) – ложное высказывание, которое читается: «существует действительное число, квадрат которого меньше 0».

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

Теорема 7. Пусть A(X) – одноместный предикат, определенный на конечном множестве M={A1,A2, … ,An}. Тогда X A(x)=A(a1)VA(a2) V…VA(an).

Доказательство: Пусть X A(x)=0. Тогда согласно определению 12 A(X) – тождественно ложный предикат, а значит A(Ai)=0 для любого AiÎM, но тогда A(A1)VA(A2) V…VA(An)=0.Пусть X A(X)=1. Тогда А(х) – не тождественно ложный предикат. А это значит, что найдется значение АI Из М, Что А(а I)=1. Но тогда А(а1) А(а2) …А(аN)=1. Теорема доказана.

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

Пусть, например, мы имеем двухместный предикат А(х, у)=(х>у) определённый на множестве R. Тогда Х(х>Y) задает одноместный предикат В(у), зависящий от переменной У. Данный предикат будет тождественно истинным. Действительно, пусть У0 – произвольное фиксированное действительное число. Тогда В(у0)= х(х>Y0)=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 истинно. Как видно, изменение порядков разноименных кванторов приводит к изменению смысла и, возможно, значения истинности высказывания.

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

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

1. Предикатные переменные: X, Y, Z, Xi, Yi, Zi (IÎN).

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

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

А(…), В(…), А I(…), В I(…) (IÎN)

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

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

Определение 13:

1. Каждая нульместная предикатная переменная есть формула.

2. Если А(…)-N-Местная предикатная переменная, то А(х1,х2,…,хN) есть формула, в которой все предикатные переменные Х1,х2,…,хN свободны.

3. Если F – формула, то - также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными в F).

4. Если и – формулы, если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения , , , так же являются формулами.

5. Если F – формулы и х – предметные переменные, входящие в F свободны, то выражения ХF и ХF так же являются формулами, в которых переменная Х связанная и все остальные предметные переменные, входящие в формулу F свободно или связано остаются и в новых формулах соответственно такими же.

6. Других формул логики предикатов, кроме получающихся согласно пунктам 1-5, нет.

Например, А(х,Y) B(Z) – элементарные формулы, и

Х А(х, у), (ХВ(х)) ; (Х А(х, у)), Х А(х, у) В(у) – составные формулы.

Формулы, в которых все переменные связаны, называются замкнутыми, а формулы содержащие свободные предметные переменные – открытыми.

Примерами замкнутых формул являются

ХУ А(х, у), Х В(х) У А(у).

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

Такое превращение формулы алгебры логики в высказывание называется интерпретацией этой формулы на множестве М.

Рассмотрим формулу Х А(х, у) Х А(х, у). В качестве М возьмем множество всех действительных чисел. В данную формулу вместо предикатной переменной А(х, у) подставим конкретный предикат Х+у>2 определенный на R. Получаем

Х(х+у>2) Х(х+у>2) предикат, зависящий от переменной у. Вместо у подставим любое конкретное значение У0 из F.

Получаем высказывание Х(х+у 0>2) Х(х+у 0>2), так как

Х(х+у 0>2)=0, Х(х+у 0>2)=1.

Ясно, что предикат Х(х+у >2) Х(х+у0>2) – тождественно истинный предикат.

Определение 14: Формула алгебры логики предикатов называется выполнимой на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, определенных на этом множестве, она превращается в выполнимый предикат. Другими словами, формула выполнима на М, если существует истинная ее интерпретация на М.

Например, формула ХА(х)В(у) выполнима на множестве R. Действительно, подставляя в данную формулу вместо предикатных переменных конкретные предикаты (х>2),(у<3) получаем предикат Х(х>2)(у<3) зависящий от У. Данный предикат выполнимый. Действительно, пусть У=2. Ясно, что высказывание Х(х>2)(2<3) истинно.

Определение 15: Формула алгебры логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

Определение 16: Формула алгебры логики предикатов называется тавтологией (противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат.

Покажем, что формула ХА(х)ХА(х) является тавтологией. Пусть А(х) – любой конкретный предикат, определенный на любом множестве М. Покажем, что после такой подстановки в формулу мы получаем истинное высказывание.

Предположим противное ХА(х)ХА(х)=0. Тогда ХА(х)=1 и ХА(х)=0.

Отсюда следует, что А(х)≡ 1 и А(х)≡ 0 одновременно, что невозможно.

Покажем, что формула (УА(у)) является противоречием. Предположим что это не так. Тогда найдется конкретный предикат А(х) определенный на конкретном множестве М, после подстановки которого в исходную формулу мы получаем выполнимый предикат на множестве М. А это значит, что найти значение a из М, что (УА(у))=1. Но тогда =1 и УА(у)=1. Отсюда следует, что А(а)=0 и A(Y) – тождественно истинный предикат на М, одновременно. Получили противоречие.

Нахождение тавтологий является одной из важнейших задач логики предикатов. В алгебре высказываний существует алгоритм, позволяющий выяснить, является ли формула алгебры высказываний тождественно истинной или нет. Для этого нужно составить таблицу истинности формулы. Если последний столбец состоит только из единиц, то формула тождественно истинна. Аналогичная проблема о существовании такого алгоритма возникает и для формул алгебры логики предикатов. В 1936 году американским математиком А. Чёрчем было доказано, что такого алгоритма не существует. Каждая форма подлежит изучению индивидуальным методом на тождественную истинность. Тем не менее, для некоторых частных видов формул данная проблема допускает решение, в частности, для формул алгебры логики предикатов определённых на конечных множествах.

Действительно, пусть формула алгебры логики предикатов заданна на конечном множестве. Тогда вместо её предикатных переменных могут подставляться конкретные предикаты, определённые на этом множестве. Согласно теоремам 6 и 7 операции квантификации на конечном множестве сводятся к конъюнкции и дизъюнкции. Следовательно, задача о том является ли формула тавтологией, сводится к аналогичной задаче для алгебры высказываний, которая эффективно разрешима.

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

Определение 17: Две формулы и алгебры логики предикатов называются равносильными на множестве М, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определённых на множестве М, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными и обозначать =.

В следующих теоремах приводятся наиболее важные равносильные формулы алгебры логики предикатов.

Теорема 8(законы де Моргана для кванторов): Следующие формулы алгебры логики предикатов равносильны:

1) ;

2) ;

Доказательство: 1) Пусть А(х) – произвольный конкретный одноместный предикат, определённый на произвольном множестве М. Тогда и - высказывания.

Пусть =1. Тогда =0. Отсюда следует, что А(х)1. А это значит, что 0. Теперь, согласно определению 12 =1.

Пусть =0. Тогда =1. Отсюда следует, что А(х)1. А это значит, что 0. Теперь, согласно определению 12 =0.

Доказательство определения 2) приводиться аналогично.

Следствие. Следующие формулы алгебры логики предикатов равносильны:

Действительно, согласно теореме 8 и закону двойного отрицания получаем

==.

Теорема 9 (законы пронесения кванторов через конъюкцию): Следующие формулы алгебры логики предикатов равносильны :

1) X(A(X)·B(X))=( XA(X))·(XB(X));

2) X(A(X)·P)=(XA(X))·P;

Доказательство: 1) Пусть А(х),В(х) – произвольные одноместные предикаты, определённые на произвольном множестве М. ПустьX(А(х)·В(х))=1. Тогда А(х)·В(х)≡1. Согласно следствию из теоремы 2 А(х)≡1 и В(х)≡1 одновременно. Согласно определению 11 XA(X)=1 и XВ(X)=1. А это значит, что (XA(X))·( XB(X))=1.

Пусть теперь X(А(Х)·В(Х))=0. Тогда согласно определению 11 А(х)·В(х) 1. Согласно следствию из теоремы 2 либо А(х) 1, либо

В(х) 1. Но тогда согласно определению 11 либо XA(X)=0, либо XВ(X)=0. А это значит, что (XA(X))·(XB(X))=0.

2) Пусть А(х) – произвольный конкретный одноместный предикат, определённый на множестве М, а Р – произвольное конкретное высказывание.

Пусть X(А(Х)·Р)=1. Согласно определению 12 А(х)·Р0. Отсюда нетрудно заметить, что А(х) 0 и Р=1. Тогда согласно определению 12 XА(х)=1. А это значит, что (XА(Х))·Р=1.

Пусть X(А(Х)·Р)=0. Тогда согласно определению 12 А(х)·Р≡0. Но тогда либо А(х)≡0, либо Р=0. А это значит, что либо XА(х)=0, либо Р=0. Отсюда следует, что (XA(X))·P=0.

Теорема доказана.

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

Действительно, пусть А(х) – «Х нечётное число», а В(х) – «Х чётное число» два предиката, определённые на множестве натуральных чисел. Тогда X(А(Х)Ú В(Х)) – истинное высказывание «любое натуральное число либо чётно, либо нечётно». - ложное высказывание «любое натуральное число нечётно или натуральное число чётно».

Теорема 9 (законы пронесения кванторов через дизъюнкцию): Следующие формулы алгебры логики предикатов равносильны:

1)=;

2) =;

Доказательство: Пусть А(х), В(х) – произвольные конкретные одноместные предикаты, определённые на произвольном множестве М, а Р – произвольное конкретное высказывание.

1) Пусть =1. Тогда 0. Согласно следствию из теоремы 3 либо А(х) 0, либо В(х) 0 одновременно. Согласно определению 12 либо =1, либо =1. А это значит, что =1.

Пусть теперь =0. Тогда согласно определению 12 ≡0. По следствию из теоремы 3 А(х) ≡0 и В(х) ≡0. Согласно определению 12 =0 и =0. А это значит, что =0э

2) Пусть =1. Тогда согласно определению 11 . А это значит, что либо А(х) ≡1, либо Р=1. Отсюда либо =1, либо Р=1. В любом случае =1.

Пусть теперь =0. Тогда согласно определению 11 1. Отсюда следует, что Р=0 и А(х) 1. Но тогда Р=0 и =0. Следовательно, =0. Теорема доказана.

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

Пусть А(х)=(X>2), определённый на R и В(х)=(х<2), определённый на R. Тогда =1 и =1. Следовательно, ()·()=1. Очевидно, что =0.

Теорема 10 (законы пронесения кванторов через импликацию): Следующие формулы алгебры логики предикатов равносильны :

1)=;

2)=;

3)=;

4) =;

Доказательство: Пусть А(х) – произвольный конкретный одноместный предикат, определённый на множестве М, а Р – произвольное конкретное высказывание.

1) Пусть =1. Тогда согласно определению 11 ≡1. Отсюда нетрудно показать, что либо А(х) ≡0, либо Р=1. А это значит, что либо =0, либо Р=1. В любом из этих случаев =1.

Пусть теперь =0. Тогда согласно определению 11 1. А это значит, что А(х) 1 и Р=0. Тогда =1 и Р=0. Отсюда =0.

2) Пусть =1. Тогда согласно определению 11 0. Тогда либо Р=1, либо А(х)1. В любом случае =1.

Пусть теперь =0. Тогда согласно определению 12 ≡0. А это значит, что А(х) ≡1 и Р=0. Отсюда =1 и Р=0. А это значит, что =0.

3) Пусть =1. Тогда согласно определению 11 ≡1. Отсюда либо Р=0, либо А(х) 1. Следовательно, либо Р=0, либо =1. В любом случае =1.

Пусть теперь =0. Тогда согласно определению 11 1. Тогда Р=1 и А(х) 1. Отсюда Р=1 и =0. Следовательно =0.

4) Пусть =1. Тогда согласно определению 12 0. Отсюда либо Р=0, либо А(х) 0. Следовательно, либо Р=0, либо =1. А это значит, что существует =1.

Пусть теперь =0. Тогда согласно определению 12 ≡0. Отсюда Р=1 и А(х) ≡0. Следовательно Р=1 и =0. А это значит, что =0.

Теорема доказана.

Теорема 11 (законы коммутативности для кванторов): Следующие формулы алгебры логики предикатов равносильны:

1) =;

2) ;

Доказательство непосредственно следуют из определения 11 и 12.

Пример 7. Доказать, что следующая формула является тавтологией.

Док-во: Пусть A(X) и B(X) ― произвольные конкретные предикаты, определённые на множестве M. Поставим их в исходную формулу, в результате получим высказывание. Покажем, что данное высказывание истинно.

1 способ: Предположим противное. Пусть