Knowledgebase
Set Theory
Basic concepts
The notion of a set is one of the initial notions of mathematics that cannot be defined quite formally. Synonyms of the term “set” are: a collection, a group, a class, etc. Approximately, one may say that a set is a collection of objects or ideas called elements of the set.
Sets are usually denoted by Latin capital letters and their elements – by corresponding small letters:
A = {a, b, c, d}, B = {b, d}, C = {a, b, c, d}.
If set B contains only elements that belong to set A then B is said to be a subset of A:
B ⊂ A (proper subset, not all elements of A are in B), C ⊆ A (C may have all elements of A or may not).
For any set A the following is true: Ø ⊆ A, A ⊆ A.
Two sets A and B are equal (denoted by A = B) if they consist of the same elements. This is equivalent to the condition that, for arbitrary x, if it is contained in A then it follows that x is in set B as well, and vice versa.
The number of elements in a set A is called the cardinality of A and is denoted |A|. If A = {a, b, c, d} then |A|= 4.
Set P(A) is a power set of A. P(A) contains all possible subsets of set A.
Ex.: A = {a, b}. P(A) = {Ø, {a}, {b}, {a, b}}. Elements of a power set are sets themselves.
Sets A and B (finite or infinite) are called equivalent (A ≈ B) if they have the same cardinality.
Ex.: A = {1, 7, 10, 15}, B = {a, b, c, d}. |A| = |B| ⇨ A ≈ B.
Operations on sets
Union of sets A and B is a set C that contains only elements belonging to A or B.
C = A ∪ B. A ∪ B = {x | x ∈ A or x ∈ B or both}.
Ex.: A = {a, b}, B = {b, c, d}. C = A ∪ B = {a, b} ∪ {b, c, d} = {a, b, c, d}.
Intersection of sets A and B is a set C which contains elements that belong both to A and B.
C = A ∩ B. C = A ∩ B. C = {x | x ∈ A and x ∈ B}.
Ex.: A = {a, b, c, d}, B = {b, d, f, h}. C = A ∩ B = {a, b, c, d} ∩ {b, d, f, h} = {b, d}.
Compliment of a set A is a set B that contains all the elements of the universal set that does not belong to A.
C = A. C = {x | x ∈ U and x ∉ A}.
Ex.: U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {0, 2, 4, 6, 8}. C = A = {1, 3, 5, 7, 9}.
Difference of sets A and B is a set C that consists of the elements that belong to A and don’t belong to B.
C = A – B. C = {x │ x A ∈ and x ∉ B}.
Ex.: A = {0, 1, 2, 3, 4}, B = {0, 2, 4, 6}. C = A - B = {0, 1, 2, 3, 4} - {0, 2, 4, 6} = {1, 3}.
Algebra Of Sets
Algebra of sets
Definition: Set algebra is a set of all subsets of U plus {∪, /, ‾ }.
An algebra is a set of elements of an arbitrary nature together with a number of operations defined on the elements of the given set. The nature of the set elements, the number and the properties of the operations determine the specific type of an algebra.
Laws of algebra of sets:
In our application there is no functionality for simplifying equations, but for manual calculations the following laws will be very useful
1. Laws of simplification:
a) A ∪ A = A;
b) A ∩ A = A;
2. Commutative laws:
a) A ∪ B = B ∪ A;
b) A ∩ B = B ∩ A;
3. Associative laws:
a) A ∪ (B ∪ C) = (A ∪ B) ∪ C;
b) A ∩ (B ∩ C) = (A ∩ B) ∩ C;
4. Distributive laws:
a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
5. Elimination laws:
a) A ∪ (A ∩ B) = A;
b) A ∩ (A ∪ B) = A;
6. Laws for constants:
a) A ∪ U = U; A ∩ Ø = Ø;
b) A ∪ Ø = A; A ∩ U = A;
7. The law of double complement:
A̿ = A;
8. The law of the excluded middle:
A ∪ A = U;
9. The law of contradiction:
A ∩ A = Ø;
10. De Morgan's laws:
a) (A ∪ B) = A ∩ B;
a) (A ∩ B) = A ∪ B;
All these variables A, B, C, ... represent not just individual sets but arbitrary formulas of the algebra of sets. All these laws can be used for equivalent transformations of the formulas of the set algebra usually in order to simplify them.
Example: simplify the formula.
A ∪ B ∩ (A ∩ B) = A ∪ B ∩ (A ∪ B) = A ∪ (B ∩ A ∪ B ∩ B) = A ∪ (B ∩ A) = (A ∪ B) ∩ (A ∪ A) = A ∪ B
Boolean Functions
Boolean functions
A function y = f(x1, x2, ..., xn) where y, x1, x2, ..., xn ∈ {0;1} is called an n-place Boolean function. Any Boolean function can be presented by a formula (an expression consisting of Boolean functions and their compositions).
It is possible to construct a truth table for a boolean function by its number and the number of arguments n.
Ex.: Truth Tabel for: f(x1, x2) = x1 ^ x2
Algebra of 2-valued Boolean functions
Algebra of 2-valued Boolean functions
Reminder: 2-element Boolean algebra = {0,1} + {^, ∨, ‾ }.
Priority of Boolean functions in formulas: ( ), ‾, ^, ∨.
Laws of 2-element Boolean algebra:
In our application there is no functionality for simplifying equations, but for manual calculations the following laws will be very useful
1. Commutative laws:
a) a ∨ b = b ∨ b;
b) a ^ b = a ^ b;
2. Associative laws:
a) a ∨ (b ∪ c) = (a ∨ b) ∨ c;
b) a ^ (b ^ c) = (a ^ b) ^ c;
3. Distributive laws:
a) a ∨ (b ∨ c) = (a ∨ b) ^ (a ∨ c)
b) a ^ (b ∨ c) = a ^ b ∨ a ^ c;
4. Elimination laws:
a) a ∨ a ^ b = a;
b) a ^ (a ∨ b) = a;
5. Laws for constants:
a) a ∨ 0 = a; a ∨ 1 = 1;
b) a ^ 0 = 0; a ^ 1 = a;
6. Double negation law:
a̿ = a;
7. Idempotent laws:
a) a ∨ a = a;
a) a ^ a = a;
8. Negations laws:
a) a ∨ a = 1 (excluded middle);
a) a ^ a = 0;
9. De Morgan’s laws:
a) (a ∨ b) = a ^ b;
a) (a ^ b) = a ∨ b;
Perfect Disjunctive Normal Form (PDNF)
Definition: A formula of a Boolean function which is a disjunction of its minterms is called its Perfect Disjunctive Normal Form (PDNF). In technical papers such a formula is called a Complete Sum of Products Form (CSPF).
Minterm is a product of all the literals (with or without complement).
Building a formula by a truth table. A method based on 1-values of a Boolean function (Method for building PDNF):
Given: a 2-values Boolean function:
x̅^y̅^z̅ ∨ x̅^y^z ∨ x̅^y̅^z = x̅y̅z̅ ∨ x̅yz ∨ x̅y̅z - PDNF
Perfect Conjunctive Normal Form (PCNF)
Definition: A formula which is a conjunction of maxterms is called the Perfect Conjunctive Normal Form (PCNF). or, more frequently, Complete Product-of-Sums Form (CPSF).
Maxterm is a product of all the literals (with or without complement).
Building a formula by a truth table. A method based on 1-values of a Boolean function (Method for building PCNF):
Given: a 2-values Boolean function:
(x∨y∨z) ^ (x∨y̅∨z) ^ (x̅∨y∨z̅) ^ (x̅∨y̅∨z) ^ (x̅∨y̅∨z̅) - PCNF