18.04.2024 / Множества и логика

Знания о множествах

• U – универсальное множество

• A – дополнение A до универсального множества

• A·B – пересечение (A ∩ B)

• A+B – объединение (A ∪ B)

• Множество задаётся логической функцией.

Логические функции множеств

• A(x) = 1

• A(x) = 1 ⇔ x ∉ A ⇔ x ∈ A'

• A(x)B(x) = 1 ⇔ x ∈ A·B

• A(x) + B(x) = 1 ⇔ x ∈ A+B

Задача дополнения

1. Для A+B = U:

   • A(x) + B(x) = 1 для всех x

   • Решение: A = B (условие: B(x) = 1)

   • Есть ли другие решения? A включает B (A⊆B)

   • Amin = Bmin

2. Для A+B = U:

   • Решение: A = B (условие: B(x) = 1)

   • Есть ли другие решения? A включает B (A⊆B)

   • Amax = Bmax

Общий подход к решению

1. Сведение задачи к базовым задачам.

2. Использование готовых решений:

   • Задача 1: Amin = B

   • Задача 2: Amax = B

Задачи с отрезками

• Даны отрезки P = [37; 60] и Q = [40; 77].

• Наименьшая длина отрезка A, чтобы (x∈P) → (((x∈Q) ^ ¬(x∈A)) → ¬(x∈P)):

  • Утверждения: P = (x∈P), Q = (x∈Q), A = (x∈A)

  • Условие: P→(QA→P)

  • Упрощение: P+(QA→P)

  • Решение: P+QA+P = P+Q+A

  • Amin = B = P∩Q = [40; 60] (длина 20)

Дополнительная задача

• Элементы множеств: P = {2, 4, 6, 8, 10, 12}, Q = {4, 8, 12, 116}.

• Наименьшая сумма элементов множества A, чтобы (x∈P) → (((x∈Q) ^ ¬(x∈A)) → ¬(x∈P)).