Direct proof We suppose, that all assumptions of a theorem are true ( p is true), and then we infer, that the conclusion is true ( q is true). Example: Prove the theorem: ”If m and n are odd, then m · n is odd.” Proof: m, n - odd, so: m = 2 ...
Proof of the equivalence To prove the equivalence p ⇔ q we have to prove both implications: p ⇒ q and q ⇒ p . Proof by mathematical induction We use this method in proving theorems concerning natural numbers, it means statements of the form: ∀ n ∈ N p ( n ), where p ( n ) is a logic sentence. ...
Equivalence relation Definition Let A be a nonempty set. A binary relation E on A that is reflexive, symmetric and transitive is called an equiva- lence relation on A . If a E b we say, that a is equivalent to b (in sense of relation E ). Examples: 1. The equality relation on a set A is an equivale...
Function Definition A function f : X → Y is an assignment (a rule) f , such that ∀ x ∈ X ∃ ! y ∈ Y y = f ( x ) . X is called the domain and Y the codomain of f . The element x is called the argument (input, independent variable) and y is the value of the function f (output, dependent variable). The...
EQUALITY Two sets A and B are equal , if they contain exactly the same elements: A = B ⇔ ∀ a ( a ∈ A ⇔ a ∈ B ) . Two sets A an B are equal, if each one is a subset of the other: A = B ⇔ ( A ⊂ B ∧ B ⊂ A ) . ...
Venn diagrams The concepts of union, intersection, relative complement and complement can be presented by using certain pictures, called Venn diagrams (named after the English mathematician John Venn (1834-1923)). The Venn diagram for (A ∩ B) ∩ C. ...
...Wariacja z powtórzeniami. k-elementowa wariacja z powtórzeniami ze zbioru n-elementowego nazywamy liczbe mozliwych wyborów k elementów z n-elementowego zbioru, przy czym wybierane elementy moga sie powtarzac, a ich kolejnosc ma znaczenie Kombinacja z powtórzeniami. k-elementowa kombinacj...
Partially ordered set Definition Let P be a nonempty set. A binary relation R on P that is reflexive, antisymmetric and transitive is called a partial order . We will denote partial order with the sign _ . If a set P has a partial order defined on it, P is called a partially ordered set , and we sa...
Imię i Nazwisko Nr indeksu 16 VI 2008 Ćwiczenia prowadzi Matematyka Dyskretna – Elektronika Kolokwium nr 2. Grupa C Część I. Zadania 1–12 są za 1pkt. W celu ich rozwiązania proszę podać jedynie odpowiedź, którą należy umieścić bezpośrednio pod zadaniem. 1. Ile rozwiązań w liczbach całkow...
THE TRANSITIVE CLOSURE R t The transitive closure R t of a relation R is the smallest relation, that contains R and is transitive. We form R t by adding to R only as many ordered pairs as is necessary to make the relation transitive. If R itself is transitive, then it is its own transitive closure:...
