Законы и тождества алгебры предикатов

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 6

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

1. Замена связанной переменной:

;

.

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

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

Пример 1

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

∎

Пример 2

.

В данном примере осуществлена замена переменной . ∎

2. Коммутативные свойства:

,

.

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

,

.

Пример 3

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

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

∎

3. Дистрибутивные свойства кванторов:

:

;

:

;

:

,

где – формула алгебры предикатов, которая не содержит переменную . Но:

;

.

Для преодоления этих ограничений дистрибутивности следует заменить связанные переменные:

;

.

4. Законы де Моргана для кванторов:

;

.

Пример 4

Пусть предикат : « – простое число». Тогда:

1. интерпретируется як «не все являются простыми числами», : «существуют , которые являются непростыми числами». Оба высказывания истинны, а значить, первый закон де Моргана справедлив и в этом случае.

2. : «Нет ни одного , которое было бы простым числом, – все являются простыми числами». Оба высказывания являются ложными, а значить, в этом случае справедлив и второй закон де Моргана. ∎

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии