лекции (2)

3.B (A ∩ B) = {0, 2, 3, 4, 5, 6, 7, 8};

4.A \ (B (A ∩ B)) = ;

5.A \ B = {3, 7, 8};

6.M = (A \ (B (A ∩ B))) ∩ (A \ B) = .

Способ 2. Преобразуем множество M , используя некоторые из приведенных выше свойств.

M= (A \ (B (A ∩ B))) ∩ (A \ B) =

=(A ∩ (B (A ∩ B))) ∩ (A \ B) =

=(A ∩ (B ∩ (A ∩ B))) ∩ (A \ B) =

=((A ∩ B) ∩ (A ∩ B)) ∩ (A \ B) =

=∩ (A \ B) = .

3.7Вопросы для самопроверки

1.Что понимается под множеством?

2.Сформулируйте определение подмножества.

3.Какие два множества называются равными?

4.Сформулируйте определения пустого и универсального множества.

5.Равны или нет множества и { }?

6.Какой из знаков нужно поставить между множеством {1} и множеством {{1}, {1, 2}}?

7.Что называется пересечением, объединением, разностью двух множеств?

8.Что называется дополнением множества?

9.Какими свойствами обладают операции над множествами?

10.Какими способами можно доказывать равенства множеств?

31

3.8Упражнения

1.Пусть A, B, C — множества, для которых верны равенства и A ∩ B = A ∩ C и A B = A C. Можно ли утверждать, что B = C?

2.Что можно сказать о множествах A1, A2, . . . , AN, если

A1 A2 . . . AN A1?

3.Задайте двумя способами множество точек плоскости с целочисленными координатами, принадлежащих кругу радиуса 2 с центром в начале координат.

4.Задайте с помощью характеристического свойства множество всех точек плоскости, принадлежащих первому координатному углу.

5.Изобразите графически следующие множества:

6. В каких случаях

а) A ∩ B = A, б) A B = A, в) A \ B = A, г) A B = A ∩ B?

7.Из 50 студентов 21 изучают английский, 22 – немецкий, 20 – французский, 8 – английский и немецкий, 9 – немецкий и французский, 7

–английский и французский и 3 студента изучают все три языка. Ответьте на следующие вопросы:

(a)Сколько студентов изучают только английский язык?

(b)Сколько студентов изучают только немецкий язык?

(c)Сколько студентов изучают только французский язык?

(d)Сколько студентов не изучают ни один из указанных языков?

8.Пусть U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12},

A = {1, 2, 3, 7, 8, 9, 12};

B = {4, 5, 6, 7, 8, 9};

C = {7, 8, 9, 10, 11, 12}. Найдите множество C \ A B.

9.Докажите равенства

32

(a)A \ ((A B) ∩ C) = A ∩ (B C);

(b)A \ (B ∩ C) = A ∩ (B C);

(c)(A\B) ∩ (A\C) = A ∩ (B\C);

(d)(A B)\(A ∩ C) = A (B\C).

10.Выразите через A, B, C множества, заштрихованные на следующих рисунках:

Рис. 12.

33

4Приложения

4.1Задания для контрольной работы

Для того, чтобы узнать номер своего варианта, нужно взять число, записанное двумя последними цифрами своего студенческого билета, разделить его на число 25 и найти остаток. Этот остаток и будет номером варианта. Например, номер студенческого билета такой: 287835. Последние две цифры этого номера образуют число 35. Делим 35 на число 25 и получим: 35 = 25 · 1 + 10. Остаток равен числу 10. Значит 10 и есть номер варианта. Следует решать все задания под номером 10. Остаток, равный нулю, соответствует варианту № 25.

Задание I. Алгебра высказываний.

Доказать равносильность формул с помощью таблицы истинности и с помощью преобразований.

1.p (q r) ≡ (p q) (p r);

2.(p q) r ≡ (¬p r) (q r);

3.p (q r) ≡ (p (¬q)) (p r);

4.p (q r) ≡ (q p) (¬r p);

5.¬p (q ¬r) ≡ (q ¬p) (r ¬p);

6.p (q r) ≡ (p q) (p r);

7.p (q r) ≡ (p q) (p r);

8.p (q r) ≡ (p q) (p r);

9.¬p ¬(q r) ≡ ¬(q p) ¬(q r);

10.¬p ¬(q r) ≡ (q p) (r p);

11.¬(p q) r ≡ (p q) (p r);

12.p ¬(q r) ≡ (p q) (p ¬r);

13.p ¬(q r) ≡ ¬(p r) ¬(q r);

14.p ¬(q r) ≡ (¬q p) (r p);

15.¬p ¬(q r) ≡ (¬q p) (r p);

34

16.¬(p q) ¬r ≡ (p q) (r q);

17.p (¬q r) ≡ (¬p ¬r) (p q);

18.p (¬q r) ≡ (p q) (p r);

19.¬p ¬(q r) ≡ (¬p r) (¬p ¬q);

20.¬p ¬(q r) ≡ ¬(p r) (p q);

21.p ¬(q r) ≡ (¬q ¬p) (r ¬p);

22.¬(p q) ¬r ≡ (p ¬r) (¬q ¬r);

23.p ¬(q r) ≡ ¬(p q) (p ¬r);

24.p (q r) ≡ (p ¬r) (p q);

25.p ¬(q r) ≡ (p q) (p ¬r).

Задание II. Алгебра множеств.

Дано универсальное множество

U= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

итри его подмножества A, B, C. Найти множество M .

1.

A = {1, 2, 3, 5, 8, 12, 13, 14, 15} , B = {1, 4, 7, 9, 10, 12, 13, 14} , C = {1, 2, 8, 10, 12, 14} .

M = A B\C.

2.

A = {1, 2, 3, 5, 8, 12, 13, 14, 15} , B = {1, 4, 7, 9, 10, 12, 13, 14} , C = {1, 2, 8, 10, 12, 14} .

M = A\C B\C.

3.

A = {5, 10, 11, 12, 13, 15} , B = {2, 8, 9, 10, 12} ,

C = {2, 8, 9, 11, 15} .

M =(A\C) (B\C).

35

4.

A = {5, 6, 7, 11, 12, 13, 15} , B = {2, 7, 9, 10, 12, 14} ,

C = {3, 8, 10, 11, 14} .

M =(A\C) (B\C).

5.

A = {0, 1, 5, 10, 11, 12, 13, 15} , B = {1, 8, 9, 10, 12} ,

C = {0, 1, 8, 9, 11, 15} .

M =(A B)\(A ∩ C).

6.

A = {2, 6, 10, 11, 12, 13, 15} , B = {1, 2, 7, 9, 10, 12, 14} , C = {1, 3, 8, 10, 12, 14} .

M =A\B\C.

7.

A = {1, 2, 3, 5, 8, 12, 13, 15} , B = {1, 4, 7, 9, 10, 12, 13} , C = {1, 2, 8, 11, 12, 14} .

M =(A B)\(A ∩ C).

8.

A = {6, 7, 10, 12, 15} ,

B = {6, 9, 10, 11, 13} ,

C = {6, 7, 8, 9, 11, 13} .

M = A C ∩ (A\B) .

9.

A = {3, 11, 12, 13, 15} , B = {2, 8, 9, 10, 12} , C = {2, 8, 10, 11, 15} . M =(A\C)\(B\C).

10.

A = {0, 1, 5, 6, 9, 10, 11, 12, 13, 15} , B = {1, 8, 9, 10, 12} ,

C = {0, 1, 2, 3, 6, 7, 8, 9, 11, 15} .

M =(A\B) (A\C) = A ∩ B\C.

36

11.

A = {1, 2, 3, 7, 8, 12, 13, 15} , B = {1, 4, 8, 9, 10, 12, 13} , C = {1, 2, 7, 11, 12, 14} .

M =(A\B)\(A C).

12.

A = {1, 2, 3, 7, 8, 12, 13, 15} , B = {1, 4, 8, 9, 10, 12, 13} , C = {1, 2, 7, 11, 12, 14} .

M =A\B ∩ C.

13.

A = {0, 1, 5, 6, 9, 10, 13, 15} , B = {0, 1, 6, 9, 12} ,

C = {1, 2, 3, 6, 7, 8, 9, 11, 15} . M =(A\B)\(A C).

14.

A = {6, 7, 11, 12, 13, 15} , B = {2, 7, 9, 10, 12} ,

C = {3, 8, 10, 11, 14} .

M =A\B ∩ C.

15.

A = {0, 1, 5, 6, 9, 10, 13, 15} , B = {0, 5, 6, 9, 12} ,

C = {1, 3, 4, 6, 7, 8, 9, 11, 15} . M =(A\B) (A\C).

16.

A = {1, 2, 3, 7, 8, 12, 13, 15} , B = {1, 4, 8, 9, 10, 12, 13} , C = {1, 2, 7, 11, 12, 14} .

M =(A B)\(A ∩ C).

17.

A = {1, 3, 5, 6, 9, 11} ,

B = {2, 5, 9, 10, 11} ,

C = {1, 3, 5, 7, 8, 9, 10, 11, 13} .

M = (A\C) ∩ A ∩ B .

37

18.

A= {4, 5, 6, 7, 12, 15} ,

B= {4, 5, 6, 9, 11} ,

C= {3, 4, 5, 7, 8, 9, 11, 13} .

M = A ∩ C \ (A ∩ B) .

19.

A = {2, 6, 10, 11, 12, 13, 15} , B = {1, 2, 7, 9, 10, 12, 14} , C = {1, 3, 8, 10, 12, 14} .

M =(B\A) ∩ (C\A).

20.

A = {2, 3, 5, 7, 10, 15} , B = {2, 5, 6, 10, 11} ,

C = {1, 4, 6, 7, 8, 9, 10, 11, 15} .

M = (A C) \ A ∩ B .

21.

A = {6, 7, 11, 12, 13, 15} , B = {2, 7, 9, 10, 12} ,

C = {3, 8, 10, 11, 14} .

M =(B\A) (C\A).

22.

A = {2, 3, 7, 8, 12, 13, 15} ,

B = {1, 4, 8, 9, 10, 12, 13} , C = {1, 2, 7, 11, 12, 14} .

M =(C\A) (C\B).

23.

A = {0, 1, 5, 6, 9, 10, 13, 15} , B = {0, 5, 6, 9, 12} ,

C = {1, 3, 4, 6, 7, 8, 9, 11, 15} . M =(A\B) ∩ (A\C).

24.

A = {2, 3, 7, 8, 12, 13, 15} ,

B = {1, 4, 8, 9, 10, 12, 13} , C = {1, 2, 7, 11, 12, 14} .

M =A\B\C.

38

25.

A = {1, 5, 6, 9, 12, 15} , B = {0, 5, 7, 9, 12} ,

C = {1, 3, 4, 5, 7, 8, 9, 11, 13} .

M=(A\B) (A\C).

4.2Пример решения варианта контрольной работы

Задание I. Доказать равносильность

p¬(q r) ≡ (p ¬q) (p ¬r)

спомощью таблицы истинности и с помощью преобразований.

Решение. 1. Сначала составим таблицу истинности для формул A = p

¬(q r) и B = (p ¬q) (p ¬r).

Сравнивая построчно истинностные значения формул A и B, убеждаемся в том, что эти формулы равносильны.

2. Теперь преобразуем формулу B к формуле A с помощью свойств логических операций:

(p ¬q) (p ¬r) ≡ (¬p ¬q) (¬p ¬r) ≡

¬p (¬q ¬p) ¬r ≡ ¬p (¬p ¬q) ¬r ≡ (¬p ¬p) (¬q ¬r) ≡ ¬p (¬q ¬r) ≡ ¬p ¬(q r) ≡ p ¬(q r).

Задание II. Дано универсальное множество

U= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

итри его подмножества

A = {2, 4, 5, 6, 7, 8} ,

B = {3, 5, 9, 10, 11} ,

C = {1, 3, 5, 7, 8, 9, 15} .

39

Найти множество

(A\C) A B .

Решение. Выполним указанные действия:

1.A \ C = {2, 4, 6};

2.A = {1, 3, 9, 10, 11, 12, 13, 14, 15};

3.A B = {1, 3, 5, 9, 10, 11, 12, 13, 14, 15};

4.(A\C) A B = {1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15}.

40