What is logical equivalence in discrete structures

Discrete Mathematics Basics


1 Fundamentals of Discrete Mathematics Prof. Dr. Romana Piat WS 25/6 General information Lectures: ./ C Train D (Wed., 3rd block + Thu., 4th block, y-raster) Train E (Tue., 5th block + Thu.,. Block, y-raster) Tutors: Ms. Marjan Godini (train D) Examination: am! Mr. Sebastian Weiß (train D only one group!) Mr. Ersan Banbal (train E) PVL: Successful completion of the homework (5 sheets) + successful passing of the theoretical test (mid-January) Office hours: by arrangement Further information, e.g. Slides, transcripts etc. can be found on: Page 2 5%

2 Literature Manfred Brill Mathematics for Computer Science 2 Edition 25, Hanser Verlag Gerald Teschl, Susanne Teschl Mathematics for Computer Science Volume. 2nd edition 27, Springer Verlag page 3 Motivation page 4

3 Content of the lecture Part I: Logic IMPORTANT: e.g. general programming semester: Technical basis of computer science Part II: Basic concepts of set theory and combinatorics IMPORTANT: e.g. Development of algorithms Part III: Discrete mathematics (modular arithmetic, encryption) Part IV: Figures, Relations Part V: Recursive Consequences IMPORTANT: eg coding, encryption, development of computer architecture IMPORTANT: eg databases development and administration IMPORTANT: eg typical approaches to programming Page 5 Content of the lecture Part I: Logic. Logical Statements and Links Definitions; Negation, join, logical operators, truth table, tautology, laws of propositional logic. 2 Boolean algebra Boolean term, complexity, minimal term, minimal form. 3 Normal forms DNF and CNF. 4 Predicate logic and quantifiers Definitions, statement representation with quantifiers Summary PVL: Exercise sheet! page 6

4th Logic Logic is a doctrine of reasonable inference. LOGIC Greek: thinking art, procedure sub-area of ​​philosophy sub-area of ​​mathematics sub-area of ​​computer science - artificial formal language - strictly defined inference rules propositional logic predicate logic page 7. Logic. Logical Statements and Associations Propositional logic is a teaching of statements and their associations definition. A statement is a sentence that is either true or false. The principle of the excluded third applies: there is no third. for false and true: two constants and page 8

5. Logic Comment: Sentences with!,?, Command sentences etc. - are not statements Example: a) 3 = b) Please sit down. c) Squares are round. d) There is an even prime number. e) Hurray! false statement-> no statement false statement-> true statement-> no statement f) When it rains, the road is wet. true statement-> page 9. Logic example: a) 3 = false statement-> c) squares are round. wrong statement-> d) There is an even prime number. true statement-> f) When it rains, the road is wet. true statement-> The statements a), b), d) are elementary or atomic statements: A, B, C ,, P, Q, A, A 2, The statement f) is more complex: Two elementary statements equal to then connected! More on this! page

6th Logic By negating (or negating, NON) a statement you can change its truth value. Example the statement A: 6 is a prime number is false the negative of A: 6 is not a prime number is true. Page. Logic This one-digit logical operation of negation can easily be represented in the form of a truth table in which one compares the truth value of the negative statement A (or A) for every possible truth value of a statement A: A A page 2

7th Logic Examples of negations: A: a) 3 = b) Squares are round. c) There is an even prime number. A: 3 squares are not round. There is no such thing as an even prime. d) When it rains, the road is wet.? Page 3. Logic Definition.2 If A and B are statements, then new statements can be formulated with the help of negation and two-digit connectors. A B f f 2 f 3 f 4 f 6 or or or or For 2 statements there are = 2 4 = 6 possibilities to define a two-digit link! page 4

8th . Logic new statement symbol name (4 out of 6) A and BA or B if A, then BA if and only if BABABABAB ,,, are called joiners conjunction disjunction implication equivalence example.2 When it rains, then the road gets wet with help formulated by two atomic statements and the implication: A: It's raining ABB: The road is wet page 5. Logic truth values ​​of the two-digit links: ABABABABAB page 6

9. Logic Interpretation: A B A B A B A B A B. Disjunction (): similar to addition with the assumption that + =; either A or B or both 2. Conjunction (): similar to multiplication (AB, AB, AB) 3. Equivalence (): is similar to the condition of equality 4. Implication (): page 7. Logic Example 3: When it rains ( A), then the road is wet (B): ABA =, B =: If it doesn't rain, then the road is dry, possible !!!, ie AB is true () A =, B =: If it doesn't rain , then the street is wet, possible !!!, ie AB is true () A =, B =: If it rains, then the street is dry, impossible !!!, ie AB is false () A =, B = : If it rains, then the road is wet, possible !!!, ie AB is true () page 8

10. Logic sentence Each of the 6 possible, two-digit logical connections can be traced back to a combination of disjunctions, conjunctions and negations. Example 4: We want to consider three of these 6 possibilities in detail. These are the Scheffer operator (NAND,), the Peirce operator (NOR,) and the operator (exclusive OR or XOR,). Page 9. Logic A B Scheffer-Pierce Exclusive OR A B A B A B A B = (A B) A B = (A B) A B = (A B) Exercise: Show the validity of these formulas with the help of the truth table. Page 2

11. Logic Definition (AB): = (AB) (BA) That means it is sufficient to show that the implication also leads to an expression of the three elementary logical operations: AB = ABABABAABAB = (AB) (BA) AB = (AB) = = ((AB) (BA)) page 2. Logic Let us also consider f =; f 6 = AA =: = (AA) (BB): = (AA) (BB) Thus we have proven the assertion of theorem for 9 (,,,,,,,,) of the 6 possible two-digit links and we dispense with the full proof. Page 22

12th Logic Lemma Let A and B be statements. For the NAND and NOR operation, the negation, conjunction and disjunction can be expressed as follows: Scheffer-Pierce-. Negation: A = A A = A A. 2nd conjunction: A B = (A B) (A B) = (A A) (B B). 3. Disjunction: A B = (A A) (B B) = (A B) (A B). Proof is done with the help of truth tables (homework, sheet). Truth values ​​for and see on page 2. page 23. Logic Definition.3 Let F be a logical formula (connection of several statements). There are 3 possibilities for every formula F in propositional logic: a) F is called satisfiable if there is at least one combination of the propositional variables for which formula F is true. b) F is called tautology (or generally valid) if the formula F is true for all combinations of the propositional variables. f 6 = a) F is called contradiction (contradiction) if the formula F is false for all combinations of the propositional variables. f page = 24

13th Logic example 5 a) F = AB b) F = (AB) (AB) c) F2 = (A (AB)) B Solution: with the help of the truth table, see transcript (page 6) Contradiction ABAB (AB) A F2 page 25. Logic example.5 (continued) d) F = (AB) (AC) (BC) satisfiable Solution: see transcript ABABABABAB page 26

14th Logic Laws of propositional logic Theorem 2 Let A be a statement, then the following applies: a) A =, A = A b) A = A, A = c) A = A (double negation) d) AA = e) AA = f) AA = A, AA = A Proof: with the help of the truth table on page 27. Logic sentence 3 Let A, B and C be statements, then the following applies: a) AB = BA, commutative law AB = BA, associative law b) A (BC) = (AB) CA (BC) = (AB) C c) A (BC) = (AB) (AC) A (BC) = (AB) (AC) distributive law AB = BA, A + B = B + AA (BC ) = (AB) CA + (B + C) = (A + B) + C A + (BC) = (A + B) (A + C) 3 (5 + 7) = (3 5) + (3 7 ) A (B + C) = (AB) + (AC) page 28

15th Logic sentence 3 (continued): d) (AB) = (A) (B), (AB) = (A) (B) e) AB = (B) (A) De Morgan's Laws Law of counterposition f) AB = (A) B g) AB = (AB) (BA) Proof: with the help of the truth table on page 29.Logic negation of complicated statements: (AB) replace AB with (AB) (f) -page 29) negate (AB): ( AB) Apply De Morgan's Law (AB) = A (B) AB: When it rains, the road is wet. (A B): It is raining and the road is not wet. Page 3

16. Logic Negation of complicated statements (general): replace all quantifiers with ,, (sentence 3 f) and g)) Put the negation sign in brackets: apply De Morgan's law. Simplify the formula obtained. Example (transcript): Simplify F = (A B) (B C) Answer: F = A B C Page 3. Logic Example 6 Peter wants to buy shares. He thinks: If I don't buy Siemens and Deutsche Bank shares, I'll buy SAP shares. Which stocks are eligible? Statement variables: A: B: Peter buys Siemens shares Peter buys Deutsche Bank shares C: Peter buys SAP shares Solution:) Write down formula F and simplify it 2) Use the truth table to determine whether and when formula F can be fulfilled Page 32

17th Logic example 6 (solution) F = (AB) C Simplification: (AB) C = ((AB)) C = ABC (AB) C SAP DB and SAP Siemens and SAP Siemens and DB All three stocks = (AB) C Page 33. Logic.2 Boolean Algebra-> Switching Algebra Image sources: de.freepik.co, lp.uni-goettingen.de Georg Boole, page 34 Image source: de.wikipedia.org

18th Logic Let us consider the following elementary circuit diagrams: Series connection: AND Parallel connection: OR The construction of such circuits is described with the help of so-called Boolean variables, and. Page 35. Logic Spelling of the links: Complement (negation): a = a Conjunction: ab = ab Disjunction: ab = a + b E.g. second Demorgan's law: a + b = ab (AB) = (A) (B) All laws from sentences 2 and 3 also apply to the Boolean variables (with changed notation) !!! Page 36

19th Logic Definition.4 Every elementary statement or Boolean variable is a Boolean term. An n-digit Boolean term p (x, x 2, xn) consists of the values, or the Boolean variables x, x 2, xn, and all of them with the introduced links (+ ,,) constructed expressions. Page 37. Logic Definition.5 Two n-place Boolean terms p and q are equivalent if for all (x, x 2, xn) with xn {,}, j = {,, n}, the following applies: p (x , x 2, xn) = q (x, x 2, xn). Definition.6 The complexity of a Boolean term can be defined as the number of binary operations + and used in it. Page 38

20th Logic example. 7 () The Boolean term p (x, y, z): = xyz + xyz + xyz + xyz + xyz contains binary multiplications and 4 binary additions, so it has a complexity of 4. (2) In contrast, the Boolean Term q (x, y, z): = x + yz only a complexity of 2: a binary multiplication and a binary addition. Complexity? (A + B) (B + A) 3 page 39. Logic Definition.7 A Boolean term with minimal complexity is called the minimal term of the Boolean term. Example 7 (continued) According to Theorem 2f): a + a = a, so we can expand the term p with the help of the equation xyz + xyz = xyz: aaap (x, y, z): = xyz + xyz + xyz + xyz + xyz + xyz = more notes x + yz = q (x, y, z) So q is the minimal form of p Another example of minimal form is the final formula in the stock example How can we be sure that q is a minimal form? page 4

21. Logic.3 Normal forms DNF, KNF disjunctive or conjunctive normal form Definition.8 () A literal x is a Boolean term that consists either of a single Boolean variable x or its complement x. (2) An n-place Boolean term of the form z z 2 z n is called a conjunctive minterm if z j = x j or z j = x j for j = {,, n}, i.e. the term is the product of the n literals of x j. Page 4. Logic Definition.8 (continued) (3) An n-place Boolean term of the form z + zzn is called a disjunctive minterm if zj = xj or zj = xj for j = {,, n}, i.e. the term die Is the sum of the n literals of xj. (4) A Boolean term is in DNF if it is all about disjunctions of conjunctive minterms. p (x, y) = (x y) + (x y) sum of the products disjunction conjunction page 42

22nd Logic Definition.8 (continued) (5) A Boolean term is in CNF if it is all about conjunctions of disjunctive minterms. q (x, y) = (x + y) (x + y) Example 8 DNF: p (x, y, z) = (xyz) + (xyz) conjunction product of the sum disjunction CNF: q (x, y , z) = (x + y + z) (x + y + z) (x + y + z) no DNF: xyz + xz + yz How do you get the DNF or CNF from a given Boolean term? Page 43. Logic) By expanding and / or multiplying: p (a, b) = (a + b) a = * expand * = (a + b) (a + b) (a + b) = = *. and 3rd class are equal * = (a + b) (a + b) CNF p (a, b) = (a + b) a = * multiply * = (aa) + (ab) = a + (ab ) = = (down) + (down) + (down) = = (down) + (down) DNF page 44

23 Logic 2) Using the truth table: (a + b) aabb (a + b) F = (a + b) a Minterme KNF KNF DNF DNF a + ba + babab DNF: (ab) + (ab) KNF: (a + b) (a + b) Exercise: DNF and KNF for ab + bc (both methods) transcript on page 45.Logic algorithm for creating the DNF or KNF of p (x, x 2, xn) with the help of the truth table: DNF: abb (a + b) F = (a + b) a Minterme. Select lines with p = 2. Number of minterms = number of lines with abp =, connect the minterms with + ab 3. Describe if the minterms are fulfilled: DNF: (ab) + (ab) for x = write x for x = write x page 46

24 Logic algorithm for creating the DNF or CNF of p (x, x 2, xn) with the help of the truth table: abb (a + b) F = (a + b) a Minterme a + ba + b CNF: (a + b) (a + b) KNF :. Choose lines with p = 2. Number of minterms = number of lines with p =, connect the minterms with 3. Describe, if the minterms are not fulfilled: for x = write x, for x = write x page 47. Logic algorithm for creation the DNF or CNF of p (x, x 2, xn) using the truth table: DNF :. Select lines with p = 2. Number of minterms = number of lines with p =, connect the minterms with + 3. Describe, if the minterms are fulfilled: for x = write x for x = write x CNF :. Choose lines with p = 2. Number of minterms = number of lines with p =, connect the minterms with 3. Describe, if the minterms are not fulfilled: for x = write x, for x = write x page 48

25th Logic sentence 4 Every Boolean term can be represented equivalently in DNF or CNF (exception: tautology only DNF contradiction only CNF) abp (a, b) Minterme ab from DNF: from + from + from + from abab Exercise: CNF for contradiction CNF: (a + b) (a + b) (a + b) (a + b) page 49. Logic example 9: Three switches control a lamp. The lamp burns exactly when an even number of switches are closed. (a) Give the truth table for the associated Boolean function f (x, y, z). (b) Set up the DNF. Note: is an even number. Solution: Take notes Answer: xyz + xyz + xyz + xyz page 5

26. Logic.4 Predicate logic and quantifiers During programming, queries of the form if (n) often occur, which, depending on the value of the variable n, result in a subsequent statement being executed or not. A value (mostly from a certain basic set G, e.g. integer numbers) is used for the free variable n and the resulting statement is examined for its truth value. Page 5. Logic.4 Predicate logic and quantifiers C ++: if (x>) {x ++; } Pascal: if (x>) then x: = x +; Page 52

27 Logic Definition.9 A predicate is a sentence (or formula) A (x) that contains one or more variables: A (x, x 2, xn), the one (or those) after the replacement the variable becomes a statement through concrete objects. Example: A (x) = x is a prime number x = 2 true statements x = 4 false statements (x>) x = 3 x = 2 true statements false statements page 53. Logic definition. With the help of quantifiers (,,!) New statements can be formed from predicates: Statement Quantifier Name for all x, A (x) x: A (x) universal quantifier x: A (x)! X: A (x) exists at least one x, for A (x) there is exactly one x, for A (x) there is existential quantifier - // - Page 54

28. Logic example. Let us consider the sentence (Euclid): There are infinitely many prime numbers. A (x) = x is a prime number there is no quantifier there are infinitely many! Rephrase the equivalent: for every number x (natural number) there is a larger prime number p. Formalization: x: (p: A (p) (p> x)) page 55. Logic negation: This year it rains every day. B (x) = it rains on day x Formalization: xϵ [, 365]: B (x) Negation: (xϵ [, 365]: B (x)) xϵ [, 365]: (B (x)) Exercise: What is the original sentence that leads to the following negation: xϵ [, 365]: (B (x)) (xϵ [, 365]: B (x)) Page 56

29 Logic Theorem 5 Let A (x), B (x), A (x, y) be predicates, then: x: (A (x) and B (x)) x: A (x) and x: B (x ) x: (A (x) or B (x)) x: A (x) or x: B (x) x, y: A (x, y) y, x: A (x, y) x, y : A (x, y) y, x: A (x, y) page 57.Logic Attention: and as a rule must not be interchanged Example 2 x: (p: A (p) (p> x)) true statement p: (x: A (p) (p> x)) false statement, da it means: There is a prime number p which is larger than all natural numbers (x). Page 58

30th Logic exercise The predicates are given: q (x): xx 3 r (y): yy 4 p (x, y): x + y 4 t (x, y) = q (x) r (y) p (x , y) Which statements are true? xϵn, y ϵ Z: p (x, y); true x ϵ N: q (x); x ϵ N: q (x); false true xϵn, y ϵ N: p (x, y); false t (2,3); t (, 2); t (3.3); t (2.2); false true false true page 59.Logic summary: Definitions: statement, junction, quantifier, minterm, DNF, KNF, tautology, contradiction, satisfiability Tasks: word problems, simplifications, truth tables, DNF, KNF page 6