Логические операции над предикатами

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

Отрицанием предиката называется новый предикат , который принимает значение “истина” при всех значениях , при которых предикат принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат принимает значение “истина”.

Из этого определения следует, что множеством истинности предиката является разность множеств и , где − множество истинности предиката , что записывается так: .

Конъюнкцией двух предикатов и называется новый предикат , который принимает значение “истина” при тех значениях , при которых оба эти предиката принимают значение “истина” и принимают значение “ложь” во всех остальных случаях.

Множеством истинности предиката является общая часть множеств истинности предикатов и , т.е. пересечение . Так, например, для предикатов − “ − четное число ” и − “ − кратно 5”, определенных на , конъюнкцией является предикат “ −четное число и −кратно 5”. Так как I_P = {2,4,6,8,10,12,14,16,18,20,…}, , то множество истинности .

Дизъюнкцией двух предикатов и называется новый предикат , который принимает значение “ложь” при тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Очевидно, что множеством истинности предиката является объединение множеств истинности предикатов и , т.е. . Так, для тех же предикатов, что и в выше приведенном примере, их дизъюнкцией будет предикат “ −четное число или кратно 5”, множество истинности которого есть .

Импликацией предикатов и называется новый предикат , который является ложным при тех значениях , при которых предикат принимает значение “истина”, а предикат − значение “ложь” и принимает значение “истина” во всех остальных случаях.

Множество истинности этой импликации определяется из следующих рассуждений: следовательно .

Так, для предикатов − “ кратно 4” и − “ – четное число”, определенных на , импликацией является предикат словесная формулировка которого будет: “если кратно 4, то – четное число. Так как , ,то т.е. все натуральные числа.

Упражнения

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

1) ;

2) при выполняется равенство ;

3) ;

4) существует такое число , что ;

5) ;

6) однозначное число кратно 3;

7)

8)

2. Выясните, какие из следующих предикатов являются тождественно истинными:

1) 2) 3)

4) 5)

3. Пусть даны предикаты “ четное число” и “ кратно 3”, определенные на множестве . Найти множества истинности предикатов:

1) ; 2) ; 3) ; 4) ;

5) .

4. Даны предикаты − “ ” и Q (x) − “ ”. Найдите множества истинности этих предикатов, если их область определения есть:

1) (действительные числа); 2) (натуральные числа).

5. На множестве заданы предикаты: − “ не делится на 5”; − “ − четное число”; − “ − простое число”; − “ кратно 3”.

Найдите множества истинности следующих предикатов:

1) ; 2) ; 3) ; 4) ;

5) ; 6) ; 7) ; 8) .

9) 10) ; 11) .

 

Кванторные операции

Кроме рассмотренных выше операций, общих как для алгебры логики, так и для логики предикатов, в последней используются логические операции, которые не применяются в алгебре логики. Эти операции превращают одноместный предикат в высказывание. Таких операций две. Они имеют собственное название и символически обозначаются с помощью так называемых кванторов (от лат. quantum − сколько) всеобщности и существования. Квантор всеобщности обозначается символом −перевернутая первая буква английского All − все, а квантор существования обозначается символом − перевернутая первая буква английского слова Exist − существует. Поскольку эти операции по смысловому содержанию квантора должны отвечать на вопрос “сколько?”, то, очевидно, должен следовать ответ “все” или “хотя бы один”, то и применяться они могут только к предикатам, являющихся по определению функцией некоторой переменной, принимающей, в общем случае, бесчисленное множество значений.

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

Рассмотрим теперь логический смысл, который придается кванторам всеобщности и существования.

Квантор всеобщности. Пусть ─ предикат, определенный на множестве . Под выражением понимают высказывание, которое является истинным, когда предикат истинен для всех элементов ,и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение будет “для всякого истинно” или “для всех x истинно”.

Переменную x в предикате называют свободной (ей можно придавать различные значения из множества M), в высказывании переменная x уже является связанной квантором .

Квантор существования. Пусть ─ предикат, определенный на множестве M. Под выражением понимают высказывание, которое является истинным, если существует элемент , для которого предикат истинен, и ложным в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение читается так: “существует , при котором истинно”.

В предикате переменная x является свободной, а в высказывании она уже связана квантором .

Рассмотрим пример использования кванторных операций. Пусть на множестве N задан предикат “ число x делится на 3”. Используя кванторные операции всеобщности и существования из данного предиката можно получить высказывания и . Первое из них читается: “всякое натуральное число делится на 3”, а второе читается: – “ существует натуральное число, которое делится на 3”.

Очевидно, что первое из этих высказываний ложно, а второе истинно.

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

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

К этим предикатам можно применить кванторные операции по переменной y, которые приведут уже к четырем высказываниям (обратим внимание на то, что при первом применении кванторных операций по переменной к двухместному предикату мы получим предикаты, а при повторном применении кванторных операций по переменной к предикатам и мы получим высказывания следующих видов:

, , , .

Кванторные операции можно менять местами. Тогда, если поменять местами кванторы, то получим еще четыре высказывания:

, , , .

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

Рассмотрим пример конкретного предиката – “ x: y ”, определенного на множестве N. Для всех восьми возможных высказываний запишем их словесную формулировку и определим их логические значения.

1. – “для всякого и для всякого x является делителем x ”.

2. – “существует y, которое для всякого x является делителем y ”.

3. – “для всякого y существует такое x, что оно делится на y ”.

4. – “существует y и существует x такое, что оно делится на y ”.

5. – “для всякого x и для всякого y является делителем x ”.

6. – “для всякого x существует такое y, что y является делителем x ”.

7. – “существует x такое, что для всякого y x делится на y ”.

8. – “ существует x и существует y такое, что y является делителем x ”.

Анализируя приведенные высказывания, можно отметить, что высказывания 1, 5, 7 ложны, а высказывания 2, 3, 4, 6 и 8 истинны. Отсюда следует очень важный вывод, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания (когда они применяются к многоместным предикатам), а значит, и его логическое значение (примером являются высказывания 3 и 7).

Возникает естественный вопрос: связаны ли кванторные операции с какими-нибудь другими логическими операциями? Для ответа на этот вопрос рассмотрим предикат P(x), определенный на множестве . Если предикат P(x) является тождественно истинным, то истинными будут высказывания . При этом истинными будут высказывания и конъюнкция .

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

.

Нетрудно также показать, что справедлива равносильность

.

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

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

Рассмотрим два простых предложения, состоящих из одних и тех же членов, но имеющих различное местоположение. Вот эти предложения: “Они все там” и “ Там все они”. Под словами “они” и “все” мы будем полагать некоторые множества (например, людей). Очевидно, что множество “все” либо полностью включает множество “они”, либо эти множества являются совпадающими. Другими словами, множество “они” является либо частью множества “все”, либо совпадает с ним, но никак не наоборот. Тогда первое предложение следует понимать так, что в некотором месте (т.е. “там”– на собрании, конференции, в правительстве и т.д.) присутствует или находится полный состав элементов множества “все”. Второе же предложение следует понимать так, что на некотором мероприятии находятся все, но из множества “они”.

Таким образом, в соответствии с первым предложением на мероприятии находятся все элементы из множества “все”, а в соответствии со вторым предложением на мероприятии находятся все элементы из множества “они”, которое меньше или, по крайней мере, равно множеству “все”. А это не одно и то же.

Приведем еще некоторые примеры, свидетельствующие о том, что логика рассуждений и их результаты зависят от особенностей языка, на котором они осуществляются. Так, например, слова страна, девочка и др. в русском языке являются словами женского рода, а слово дом – мужского рода. Те же слова das Land, das Madchen, das Haus и др. в немецком языке являются словами среднего рода (на это указывает артикль das). И таких примеров можно приводить множество.

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

 

Упражнения

1. Даны предикаты P(x) – “ ” и – “ ”. Требуется определить, какие из высказываний истинны, и какие ложны:

1) , 2) , 3) , 4) .

2. Пусть предикат – “ x: y ” определен на множестве . Показать, что высказывания и имеют различные логические значения.

3. Установить, какие из следующих высказываний истинны, а какие ложны, если областью определения предикатов является множество всех действительных чисел R:

1) ; 2) ;

3) ; 4) ;

5) ;

6) ;

7) ;

8) ;

9) .