Применение логических связок

Так как предикаты принимают значения из множества {0, 1}, то они являются высказываниями, и их можно объединять логическими связками, получая более сложные предикатные функции.

Пусть и – два п -местных предиката, определённых на некотором множестве M.

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

Дизъюнкция. – это предикат, который ложен для тех и только тех объектов из M, для которых оба предиката ложны. Таким образом, область истинности предиката равна объединению областей истинности предикатов и , т.е. .

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

Импликация. ‑ это предикат, который истинен для тех и только тех объектов из M, на которых предикат ложен или истинен. Таким образом, область истинности предиката будет: .

Эквивалентность. ‑ это предикат, который истинен для тех и только тех объектов из M, на которых предикаты и одновременно истинны или ложны. Областью истинности будет: .

Свойства отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности.

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

Пусть , и – п -местные предикаты, определённые на некотором множестве M, тогда:

1) закон двойного отрицания ;

2) законы идемпотентности , ;

3) законы коммутативности ; ; ;

4) законы ассоциативности , ;

5) законы дистрибутивности

, ;

6) законы поглощения , ;

7) законы де Моргана ; ;

8) , , , , ; ;

9) ; .

В этих утверждениях необходимо следить, какие переменные определяются одинаковыми буквами, а какие разными. Пусть имеется два предиката и , определённых на множестве M. Тогда предикат – некоторый трёхместный предикат от x, y, z. Чтобы определить для каких значений предикат принимает истинные значения, а для каких ложные, необходимо произвести унификацию переменных, то есть присвоить переменных некоторые конкретные значения из множества M.

Пусть , , где , тогда . Предикат , когда и .

Пример. (ФАМИЛИЯ = "Петров")& (ВУЗ = "МИРЭА")&(1<КУРС>4), Это сложное высказывание будет истинным для студента МИРЭА 2-го или 3-го курса с фамилией Петров. Для всех остальных студентов значения предиката будет "ложь".