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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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

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

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

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


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


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


[math]\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}[/math]

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


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


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

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


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

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




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


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

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


[math]\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}[/math]

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


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


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


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

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