Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 7 стр.

UptoLike

Составители: 

1. Составляющими системы X
1
= {a, b}, X
2
= {b} суть {b}, , {a}, {c, d} и, следо-
вательно, данная система множеств не является независимой;
2. Составляющими системы X
1
= {a, b}, X
2
= {b, c}, суть {b}, {c}, {a}, {d}, и,
следовательно, данная система множеств независима.
Для σ {0, 1} и множества X введём обозначение X
σ
: X
σ
есть X, если σ = 1 и
X, если σ = 0.
Лемма 1.2. 1. Произвольная составляющая s S системы множеств
{X
1
, . . . , X
n
} представима в виде s =
T
n
j=1
X
σ
j
j
, где σ
j
{0, 1}, и, следова-
тельно, две составляющие либо совпадают, либо не пересекаются.
2. Независимая система из n множеств имеет 2
n
различных составляющих.
Доказательство. Доказательство п. 1) легко проводится по индукции. Утверждение 2)
следует из 1).
Из леммы следует, что получаемая в соответствии с определением совокупность со-
ставляющих некоторой системы множеств не зависит от порядка выбора этих множеств
и, таким образом, определение набора составляющих корректно.
Теорема 1.3 (Венна). Если булево равенство выполнено для некоторой независимой
системы множеств, то оно справедливо для любой системы множеств.
Доказательство. Рассмотрим множество F , представимое некоторой булевой форму-
лой над независимой системой множеств X = {X
1
, . . . , X
n
} и s составляющая этой
системы. Тогда либо s F , либо s F = . Первый случай имеет место если и только
если x s x F . Это означает, что множество F может быть представлено в ви-
де объединения F =
S
xs xF
s. Такое разложение останется справедливым и для зави-
симой системы множеств перестав, однако, быть единственным. Таким образом, если в
независимой системе множеств две булевы теоретико-множественные формулы F
1
и F
2
представляются в виде объединения одних и тех же составляющих, истинность x F
1
и x F
2
будет одинакова в любой другой системе.
Из теоремы следует, что булево равенство достаточно проверить на одной диаграмме
Эйлера-Венна для независимых систем множеств (их обычно и называют множествами
общего положения).
Заметим, что система подмножеств некоторого множества может оказаться булевой
алгеброй, не являясь при этом алгеброй множеств. Это будет, когда хотя бы одна из
операций на данной системе не совпадает с соответствующей теоретико-множественной
(ниже будут приведены подобные примеры).
1.1.3 Изоморфизмы булевых алгебр
Хотя алгебры множеств являются, как мы увидим, в определённом смысле, основными
примерами булевых алгебр, последние ими не исчерпываются.
Пример 3. 1. Рассмотрим двоичное множество истинностных значений B = { 1, 0 }
и сигнатуру σ
B
= h , , ¬, 0, 1 i, состоящую из логических операций дизъюнк-
ции, конъюнкции и отрицания, а также символов элементов B : логического нуля
7
  1. Составляющими системы X1 = {a, b}, X2 = {b} суть {b}, ∅, {a}, {c, d} и, следо-
     вательно, данная система множеств не является независимой;

  2. Составляющими системы X1 = {a, b}, X2 = {b, c}, суть {b}, {c}, {a}, {d}, и,
     следовательно, данная система множеств независима.

   Для σ ∈ {0, 1} и множества X введём обозначение X σ : X σ есть X, если σ = 1 и
X, если σ = 0.

Лемма 1.2.        1. Произвольная составляющаяT s     ∈      S системы множеств
                                               n     σj
   {X1 , . . . , Xn } представима в виде s =   j=1 Xj   , где σj ∈ {0, 1}, и, следова-
   тельно, две составляющие либо совпадают, либо не пересекаются.

  2. Независимая система из n множеств имеет 2n различных составляющих.

Доказательство. Доказательство п. 1) легко проводится по индукции. Утверждение 2)
следует из 1).
    Из леммы следует, что получаемая в соответствии с определением совокупность со-
ставляющих некоторой системы множеств не зависит от порядка выбора этих множеств
и, таким образом, определение набора составляющих корректно.

Теорема 1.3 (Венна). Если булево равенство выполнено для некоторой независимой
системы множеств, то оно справедливо для любой системы множеств.

Доказательство. Рассмотрим множество F , представимое некоторой булевой форму-
лой над независимой системой множеств X = {X1 , . . . , Xn } и s — составляющая этой
системы. Тогда либо s ⊆ F , либо s ∩ F = ∅. Первый случай имеет место если и только
если x ∈ s ⇒ x ∈ F . Это
                       S означает, что множество F может быть представлено в ви-
де объединения F =           s. Такое разложение останется справедливым и для зави-
                     x∈s ⇒ x∈F
симой системы множеств перестав, однако, быть единственным. Таким образом, если в
независимой системе множеств две булевы теоретико-множественные формулы F1 и F2
представляются в виде объединения одних и тех же составляющих, истинность x ∈ F1
и x ∈ F2 будет одинакова в любой другой системе.
   Из теоремы следует, что булево равенство достаточно проверить на одной диаграмме
Эйлера-Венна для независимых систем множеств (их обычно и называют множествами
общего положения).
   Заметим, что система подмножеств некоторого множества может оказаться булевой
алгеброй, не являясь при этом алгеброй множеств. Это будет, когда хотя бы одна из
операций на данной системе не совпадает с соответствующей теоретико-множественной
(ниже будут приведены подобные примеры).

1.1.3   Изоморфизмы булевых алгебр
Хотя алгебры множеств являются, как мы увидим, в определённом смысле, основными
примерами булевых алгебр, последние ими не исчерпываются.
Пример 3.   1. Рассмотрим двоичное множество истинностных значений B = { 1, 0 }
    и сигнатуру σB = h ∨, ∧, ¬, 0, 1 i, состоящую из логических операций дизъюнк-
    ции, конъюнкции и отрицания, а также символов элементов B : логического нуля




                                          7