т. е. найти множество тех студентов, которые имеют пропуски по математике, но не имеют их по информатике. Фактически нам надо найти пересечение двух множеств: множества А (имеющих пропуски по математике) и множества ВС (не имеющих пропусков по информатике), т. е. множество A ∩ BС. Для того чтобы найти элементы этого множества, нам нужно выразить множества A ∩ BС через фундаментальные произведения. Сделать это можно с помощью искусственного приема, который позволяет вводить в любое пересечение множеств те множества, которые в нем отсутствуют, приводя его тем самым к объединению фундаментальных произведений.
Это решение, по сути дела, представляет собой действия, произведенные при решении задачи в первом случае, но выполненные в обратном порядке. Это же способ позволяет выразить любое множество через фундаментальные произведения.
1.12. Многочлены алгебры множеств
Множества с операциями пересечения, объединения и дополнения, удовлетворяющие абстрактным законам, введенным в главе 1, параграф 1.8, образуют алгебраическую систему, называемую алгеброй множеств. Эта алгебра является булевой алгеброй и поэтому часто использует идеи и терминологию булевой алгебры, однако следует отметить, что эта терминология не вполне стандартизирована, что иногда приводит к различным названиям одних и тех же понятий. Рассмотрим некоторые понятия более подробно.
Пусть имеется n переменных, каждая из которых определяет некоторое множество. Выражением алгебры множеств Е (или формулой) называется выражение, составленное из этих переменных, соединенных при помощи операций объединения, пересечения и дополнения, например
Е1 = A ∩ (BС ∩ С)С ∪ (A ∩ BС ∩ СC)С,
Е2 = A ∩ (BС ∩ С) ∪ (A ∩ BС ∩ СC),
Е3 = (A ∩ BС ∩ С) ∪ (A ∩BС ∩ СC),
Е4 = (AC ∪ BC) ∩ (AC ∪ BC ∪ С) ∩ (BC ∪ С),
Е5 = (AC ∪ B ∪ С) ∩ (A ∪ BC ∪ С) ∩ (AC ∪ BC ∪ С)
являются выражениями из трех переменных А, В и С.
Литералом называется переменная или дополнение переменной, например А, АС, ВС и т. д. Произведением называется литерал или пересечение двух или более литералов, таких что ни одна пара из них не содержит одной и той же переменной. Например, BС ∩ С, A ∩ BС ∩ СC, А, СC являются произведениями, а выражения A ∩ BС ∩ АС и A ∩ BС ∩ BС – нет. Заметим, что любое пересечение литералов всегда приводится либо к Ø, либо к произведению. Так, например A ∩ BС ∩ АС= Ø, потому что A ∩ АС= Ø (по закону дополнения), а пересечение A ∩ BС ∩ BС= A ∩ BС, потому что BС ∩ BС= BС (по закону идемпотентности).
Если при n переменных произведение состоит из n литералов, то его называют фундаментальным произведением (некоторые авторы называют любое произведение фундаментальным произведением).
Выражение, представляющее собой объединение различных произведений, если в нем нет ни одного произведения, которое включается в другое произведение, называют суммой произведений, или нормальной формой объединения пересечений, или многочленом в нормальной форме.
