Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


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

а понятие включения множеств следующим образом:


M_1\subseteq M_2\quad \mathop{\Longleftrightarrow}\limits^{\text{def}}\quad (\forall x)(x\in M_1\leftrightarrow x\in M_2).

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


Пример 24.25. M_1=M_2\Leftrightarrow M_1\subseteq M_2\land M_2\subseteq M_1..


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


\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}

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


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


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

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


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

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




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


\overline{\bigcup\limits_{i\in I}M_i}= \bigcap\limits_{i\in I}\overline{M_i}\,.

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


\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}

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved