Простейшие логические операции над предикатами.

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

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

Если A(x_1­,…,x_n) определен на множествах M₁,...,M_n, то его отрицанием является предикат ùA(x_1­,…,x_n), причем для набора < α_1­,…,α_n > высказывание ùA(α_1­,…,α_n) истинно тогда и только тогда, когда A(α_1­,…,α_n) ложно.

Пример. A(x)=(x>0), ùA(x)= ù(x>0)≡(x≤0)

Конъюнкцией n–местного предиката A(x_1­,…,x_n), определенного на множествах M₁,...,M_n, и B(y_1­,…,y_m), определенного на множествах N₁,...,N_m, является (n+m)-местный предикат. A(x_1­,…,x_n)ÙB(y_1­,…,y_n), определенный на множествах M₁,...,M_n,N₁,...,N_m, и принимающий значение «истина» для тех и только тех последовательностей <α₁,…,α_n,β₁,…,β_m>, для которых оба высказывания A(α₁,…,α_n) и B(β₁,…,β_m) - истинны. Аналогично определяются операции Ú, .

Примеры. Предикат (x>y)Ù(z²-4z+3=0) принимает значение 1 для набора значений переменных <-4,-5,1> и 0 для набора <0,1,3>. Предикат «х – простое число» «у – грек», (х – определено на множестве натуральных чисел, у – на множестве людей) принимает значение 1 для наборов <7,Сократ>, <8, Наполеон> и др., 0- для набора <3, Наполеон>, <5, Пушкин> и др. Предикат “х делится на у”Ú(z>t), принимает значение 1 для набора <7,2,3,1>, так как «7 делится на 2» - ложно. 3>1 – истинно, а дизъюнкция истинна в том случае, когда хотя бы один член дизъюнкции имеет значение 1.

Мы более подробно обсудили последний пример. Обоснование предыдущих выводов проводится аналогично.

Может случиться, что предикаты, над которыми выполняются операции Ú,Ù, , содержат общие переменные. Речь идет, конечно, не только о совпадении символа переменной, но и о совпадении области определения переменной. Обращаем внимание на то, что при определении местности результата выполнения операций над предикатами общая переменная считается только один раз. Например, предикат (x>y) Ù (y>z)имеет местность 3, предикат (u+t=0)Ú(ut=0) имеет местность 2.

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

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

Уже отмечалось, что для n-местного предиката A(x_1­,…,x_n), определенного на множествах M₁,...,M_n (или же на декартовом произведении M₁˟... ˟M_n), множество истинности является некоторым отношением ρÍM₁˟... ˟M_n.

Из определения операций над предикатами немедленно следует, что {<x₁,…,x_n| ùA(x₁,…,x_n)}= . Если предикат B(x₁,…,x_n) определен на тех же множествах, и его множество истинности равно σ, то множество истинности конъюнкции этих предикатов равно ρÇσ, дизъюнкции - ρÈσ. Таким образом, теоретико-множественным операциям дополнение, пересечение, объединение соответствуют логические операции ù, Ù, Ú. Указанные связи имеют более глубокий характер, чем может показаться на первый взгляд.

Контрольные вопросы и упражнения

1. Какие из следующих выражений можно рассматривать как предикаты при конкретном выборе области определения входящих в них переменных?

а) ; г) ;

б) х – истинно; д) ;

в) х включается в у; е) .

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

а) ; в) ;

б) ; г) .

3. Привести по три примера предикатов равной местности на множестве действительных чисел на каждый из трех типов, причем выполнимый предикат не должен быть тождественно истинным.

4. Привести по два примера пар:

а) равносильных предикатов;

б) один из предикатов является следствием другого.

5. Дать определение операциям над предикатами.

6. Даны два одноместных предиката: и , определенные на множестве действительных чисел. Для каких действительных чисел истина:

а) конъюнкция; в) импликация;

б) дизъюнкция; г) эквиваленция

данных предикатов? Ту же задачу решить для предикатов и ; и .

7. Доказать для n -местных предикатов, определенных на одних и тех же множествах:

а) конъюнкция тождественно истинного предиката с любым другим равносильна последнему;

б) конъюнкция тождественно ложного предиката с другим есть тождественно ложный предикат;

в) дизъюнкция тождественно истинного предиката с любым другим есть тождественно истинный предикат;

г) дизъюнкция тождественно ложного предиката с любым другим равносильна последнему;

д) импликация двух предикатов тождественно истинна, если ее посылка тождественно ложна или заключение тождественно истинно;

е) импликация двух предикатов с тождественно истинной посылкой равносильна заключению;

ж) импликация двух предикатов с тождественно ложным заключением равносильна отрицанию посылки;

з) эквиваленция двух предикатов равносильна одному из ее членов тогда и только тогда, когда другой ее член тождественно истинен;

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

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

а) ; в) ;

б) ; г) .

9. Каким условиям удовлетворяют множества истинности предикатов и , определенных на множестве М, если:

а) конъюнкция их тождественно истинна;

б) конъюнкция их тождественно ложна;

в) конъюнкция их удовлетворяется всем элементам из множества истинности предиката ;

г) дизъюнкция их тождественно истинна;

д) импликация тождественно ложна;

е) эквиваленция их тождественно ложна;

ж) эквиваленция их удовлетворяется всеми элементами, принадлежащими множеству истинности предиката , и только такими элементами.

10.Выразить множество истинности предиката через множества истинности элементарных предикатов:

а) ;

б) ;

в) ;

г) .

11.Сколько существует различных k -местных предикатов, в которых переменные определены на n -элементном множестве М?

Дата добавления: 2015-11-14