1.6. Операции сравнения — логические операции с множествами

Определение. Два множества А и В называют равными, если они состоят из одних и тех же элементов. Обозначается равенство как А=В.

Если все элементы множества А принадлежат множеству В (а  А  а  В), то говорят, что А нестрого включается в В. Обозначают как А  В.

Если АВ, но АВ, то имеет место строгое включение, которое обозначают как А В.

Операции равенства нестрогого и строгого включений (=; ; ) называют операциями сравнения.

Свойства операций сравнения

1. Операции нестрогого включения и равенства обладают рефлексивностью: А  А; А = А.

2. Операции нестрогого, строгого включений и равенства обладают транзитивностью:

а) если (А  В), (В  С), то А  С;

б) если (А  В), (В  С), то А  С;

в) если (А = В), (В = С), то А = С.

3. Интуитивный принцип объемности. Если выполняется (А  В) и (В А), то справедливо: А=В.

Результатом выполнения операций сравнения является логическое значение — «истина» либо «ложь». Например, результат выражения А = А всегда истинен, выражение А  В может быть либо ложным, либо истинным — в зависимости от рассматриваемых множеств А, В. В этом заключается принципиальное отличие операций сравнения от предметных операций, результатом выполнения которых всегда является множество.

Определение. Операции со значениями истинности, обратными к операциям сравнения (= ;  ; ), назовем отрицаниями операций сравнения.

Например, операция (  ) в выражении А  В означает, что множества А и В состоят не из одинаковых элементов, операция (  ) в выражении А  В означает, что отсутствует строгое включение множества А в В.

Указанные операции можно рассматривать как сокращенную запись двухместных предикатов, где аргументами являются множества, а результат — логическое значение.

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

Правило 1. Если векторы включений у формул F₁ и F₂ совпадают, то всегда F₁ = F₂.

Правило 2. Если все элементарные пересечения формулы F₁ содержатся в элементарных пересечениях формулы F₂, то в общем случае F₁ нестрого входит в F₂ (F₁  F₂). Наличие строгого включения F₁ в F₂ либо равенство F₁ и F₂ зависит от конкретных рассматриваемых множеств.

Правило 3. Если векторы включений формул составных множеств индифферентны – не совпадают и ни один из них не входит в другой, то никаких предварительных заключений при сравнении конкретных примеров данных составных множеств по их формулам делать нельзя.

Пример 1. Сравнить составные множества, заданные в Примере 2 параграфа 1.5 на простых множествах А и В: 1) F₁ = (АВ), 2) F₂ = (АВ), 3) F₃ = АВ(АВ).

Решение. Так как векторы включений для формул F₂ и F₃ совпадают, то составные множества, задаваемые ими, всегда равны: F₂ = F₃ . Вектор включений F₁ строго входит в вектор для F₂ , поэтому в общем случае F₁  F₂ . С использованием диаграмм Венна несложно показать, что если АВ ≠Ø , то имеет место строгое включение F₁  F₂ . При АВ =Ø - равенство F₁ = F₂.

Пример 2. Рассмотрим составные множества, заданные формулами F₁ = АВ и F₂ =  А. Их векторы включений (0110) и (1100) индифферентны. Как несложно проверить, при А В  U выполняется строгое включение F₁ = В\А  F₂, поскольку пересечение А\В, соответствующее третьей компоненте векторов, в этом случае пусто. При А=U ≠ Ø получим: F₁ = АВ= В, F₂ =  А =Ø. Следовательно, в данном случае F₂ F₁.

ЗАДАЧИ

1. Сравнить пары составных множеств, заданных следующими формулами:

а) F₁ = АВ и F₂ = С(АВ),

б) F₁ = А В С и F₂ =(C\(АВ)),

в) F₁ = (А(ВС)) и F₂ = ВC.