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

Ранее была показана связь алгебры высказываний с теорией множеств. Логика предикатов усиливает эти связи, так как позволяет дать четкое толкование и обоснование известным теоретико-множественным понятиям и концепциям, а также ввести ряд новых. Например, понятие равенства двух множеств (принцип равнообъемности) на языке логики предикатов выражается так:

[cbm]M_1=M_2\quad \mathop{\Longleftrightarrow}\limits^{\text{def}}\quad (\forall x)(x\in M_1\leftrightarrow x\in M_2),[/cbm]

а понятие включения множеств следующим образом:
[cbm]M_1\subseteq M_2\quad \mathop{\Longleftrightarrow}\limits^{\text{def}}\quad (\forall x)(x\in M_1\leftrightarrow x\in M_2).[/cbm]

Тогда законы логики предикатов позволяют строго обосновать утверждение.

Пример 24.25. [cbm]M_1=M_2\Leftrightarrow M_1\subseteq M_2\land M_2\subseteq M_1.[/cbm] .

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

[cbm]\begin{aligned}M_1=M_2& ~\Longleftrightarrow~ (\forall x)(x\in M_1\leftrightarrow x\in M_2) ~\Longleftrightarrow\\ &~\Longleftrightarrow~ (\forall x)\bigl[(x\in M_1\to x\in M_2)\land (x\in M_2\to x\in M_1)\bigr] ~\Longleftrightarrow\\ &~\Longleftrightarrow~ (\forall x)(x\in M_1\to x\in M_2)\land (\forall x) (x\in M_2\to x\in M_1) ~\Longleftrightarrow\\ &~\Longleftrightarrow~ M_1 \subseteq M_2\land M_2 \subseteq M_1.\end{aligned}[/cbm]

Далее, тавтологии логики высказываний позволяют обосновывать свойства теоретико-множественных операций: дополнения, пересечения, объединения множеств. При этом каждое множество [cbm]M[/cbm] мыслится как множество истинности одноместного предиката " [cbm]x\in M[/cbm] ".

Логика предикатов позволяет ввести новые теоретико-множественные понятия. Покажем, в частности, как обобщаются теоретико-множественные операции объединения и пересечения множеств на случай бесконечного числа множеств. Пусть имеется некоторое семейство [cbm](M_i)_{i\in I}[/cbm] подмножеств множества [cbm]M[/cbm] . (Это означает, что каждому элементу [cbm]i\in I[/cbm] взаимно-однозначно сопоставлено подмножество [cbm]M_i[/cbm] множества [cbm]M[/cbm] . Множество /называется множеством индексов семейства [cbm](M_i)_{i\in I}[/cbm] , а само семейство называется индексированным.) Объединением данного семейства называется множество, обозначаемое [cbm]\mathop{\cup}\limits_{i\in I}M_i[/cbm] , состоящее из всех таких элементов множества [cbm]M[/cbm] , которые принадлежат по меньшей мере одному из подмножеств семейства:

[cbm]\bigcup\limits_{i\in I}M_i=\bigl\{x\in M\colon\, (\exists i\in I)(x\in M_i)\bigr\}.[/cbm]

Пересечением данного семейства называется множество, обозначаемое [cbm]\mathop{\cap}\limits_{i\in I}M_i[/cbm] состоящее из всех таких элементов множества [cbm]M[/cbm] , которые принадлежат каждому из подмножеств семейства:

[cbm]\bigcap\limits_{i\in I}M_i=\bigl\{x\in M\colon\, (\forall i\in I)(x\in M_i)\bigr\}.[/cbm]

Логика предикатов позволяет установить свойства этих теоретико-множественных операций: они в некотором смысле аналогичны соответствующим свойствам объединения и пересечения.


Пример 24.26. Проверим, например, один из законов де Моргана:

[cbm]\overline{\bigcup\limits_{i\in I}M_i}= \bigcap\limits_{i\in I}\overline{M_i}\,.[/cbm]

Используя закон де Моргана для кванторов (теорема 21.9, б), получаем

[cbm]\begin{aligned}\overline{\bigcup\limits_{i\in I}M_i}&= \Bigl\{x\colon\,\lnot \Bigl(\,\bigcup\limits_{i\in I}M_i\,\Bigr)\Bigr\}= \bigl\{x\colon\,\lnot (\exists i\in I)(x\in M_i)\bigr\}=\\[2pt] &=\bigl\{x\colon\, (\forall i\in I)( \lnot(x\in M_i))\bigr\}= \bigl\{x\colon\,\lnot (\forall i\in I)(x\in \overline{M_i})\bigr\}=\\[2pt] &=\bigcap\limits_{i\in I}\overline{M_i}\,.\end{aligned}[/cbm]

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: