Introduction to Computer Science PDF Fall 2024

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Logical Values...

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 Logical Values 45 Section 4 Logical Values The goal of this section is to lay the foundation for the conditional execution of code. In order to conditionally execute code, we need a condition, i.e. a boolean expression. Code 4.1 provides an example of where we want to go. int a; std::cin >> a; if (a % 2 == 0) std::cout = 3); // b = false int a = 4; bool b = (a % 3 == 1); // b = true int a = 1; bool b = (a != 2*a-1); // b = false Subsection 4.2 Boolean Functions and Logical Operators Boolean Functions in Mathematics Booleans can be combined and the canonical op- erators are the conjunction (logical AND) of two propositional symbols x and y is denoted x ∧ y and is true if and only if x and y are both true. the disjunction (logical OR) of two propositional symbols x and y is denoted A ∨ B and is true if and only if A or B (or both) are true. the negation (logical NOT) of a propositional symbol A is denoted ¬A and is true if and only if A is false. The conjunction and disjunction are binary functions {0, 1}2 → {0, 1}. The negation is an unary function {0, 1} → {0, 1}. Any boolean function can be defined in terms of a truth table. We define the three functions from above with the following tables. AND OR x y x∧y x y x∨y NOT 0 0 0 0 0 0 x ¬x 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 Boolean functions in C++ The logical operators AND, OR and NOT are provided with the logical operators &&, || and ! in C++. x && y logical AND x ∧ y x || y logical OR x ∨ y !x logical NOT ¬x Logical Values 47 The binary, left associative operators conjunction and disjunction take two expressions of type bool and return an R-value of type bool. The unary, right associative negation oper- ator takes an expression of type bool and returns an R-value of type bool. Example 4.3 (Examples of logical operators in C++) int n = -1; int p = 3; bool b = (n < 0) && (0 < p); // b = true int n = 1; int p = 0; bool b = (n < 0) || (0 < p); // b = false int n = 1; bool b = !(n < 0); // b = true Subsection 4.3 Precedences Like discussed in Section 3.2, the evaluation of a boolean expression is determined by the precedencs and associativities of the involved operators. The precedence of the unary negation operator is stronger than that of the binary logical operators: !b && a ⇕ (!b) && a The precedence of the binary conjunction operator is stronger than that of the binary disjunction: a && b || c && d ⇕ (a && b) || (c && d) Don’t be fooled by misleading layout: a || b && c || d ⇕ a || (b && c) || d In order to correctly parenthesize a more complex expression involving arithmetic, relational and logical, you need to know about the precedences involved. Again, that can be read out from the table on cppreference. But here is a short characterisation: Logical Values 48 Binding of Operators The unary logical operator ! binds more strongly than binary arithmetic operators. These bind more strongly than relational operators, and these bind more strongly than binary logical operators. Example 4.4 (Parenthesisation of a complex expression) 7 + x < y && y != 3 * z || ! b is correctly put into parenthesis lie this: ((7 + x) < y) && (y != (3 * z)) || (!b) Subsection 4.4 Completeness C++ offers the three canonical operators conjunction, disjunction and negation. A natural question to ask is if this is enough? Can any other binary boolean function be expressed in terms of these operators? It turns out the answer is yes. Let us start with the example of the exclusive or (XOR): x ⊕ y is true if and only if either of x or y is true, but not both. Here is the truth table: x y x⊕y 0 0 0 0 1 1 1 0 1 1 1 0 It turns out that x ⊕ y can be written as (x ∨ y) ∧ ¬(x ∧ y). How can we see this? We can certainly informally understand it from the English explanation of XOR (one of the argument needs to be true but not both) More formally, we can try it out with the truth table: x y x∨y ¬(x ∧ y) (x ∨ y) ∧ ¬(x ∧ y) 0 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 Here is the general result: Logical Values 49 Theorem 4.1. Any binary logical operator can be expressed in terms of the three canonical operators ∧, ∨ and ¬. Proof. We identify each boolean function with its characteristic four dimensional vector that contains at index i the value of the operation in the ith row of the truth table. The characteristic vector v of x ⊕ y, for example, is v = [0, 1, 1, 0], written in short as 0110. The corresponding function we denote by fv. For example for XOR this is f0110 and it holds that f0110 (0, 0) = 0, f0110 (0, 1) = 1, f0110 (1, 0) = 1 and f0110 (1, 1) = 0. In order to prove that we can generate any function from the canonical functions, we first generate the fundamental functions f0001 (x, y) = x ∧ y f0010 (x, y) = x ∧ ¬y f0100 (x, y) = ¬x ∧ y f1000 (x, y) = ¬x ∧ ¬y Now we can generate any binary logical function that contains at least one true answer, i.e. any characteristic vector containing at least one 1-entry, by applying the logical OR of all corresponding fundamental functions, i.e. those that provide a 1 at all 1-indices of the given function.23 For example f1101 (x, y) = f1000 (x, y) ∨ f0100 (x, y) ∨ f0001 (x, y) Finally, the function f0000 can be generated as f0000 (x, y) = x ∧ ¬x. Remark 4.1. The identity x ∨ y = ¬(¬x ∧ ¬y) implies that already two functions, e.g. conjunction and negation, suffice to generate all binary logical functions. Subsection 4.5 Conversion In the discussion of int and unsigned int in Section 3.6.3 we have learned that some values can be converted from one type to another in C++. This, unfortunately, is also true for types the do not seem to be compatible in the first place. Indeed bool can be used whenever int is expected – and vice versa. Many existing programs use int instead of bool. We consider using int instead of bool a bad idea, originating from the language C. 23 This vector-wise OR for the characteristic vector works because, for a given x and y, the combination f (x, y) ∨ g(x, y) of two logical functions f and g yields true if and only if f (x, y) ∨ g(x, y) is true, i.e. the 1 positions of the characteristic vectors (corresponding to a unique pair of values of x and y) can be ORed. The analog statement holds for AND. Logical Values 50 The conversion works like displayed in the following tables bool → int int → bool true → 1 ̸=0 → true false → 0 0 → false Example 4.5 (Bool-int conversion) int a = true; // a = 1 bool b = 3; // b=true bool c = 0; // c=false Subsection 4.6 The Rules of De Morgan It holds that !(a && b) == (!a || !b), corresponding to ¬(a ∧ b) = (¬a ∨ ¬b) !(a || b) == (!a && !b), corresponding to ¬(a ∨ b) = (¬a ∧ ¬b) Not (sunny and hot) = cloudy or cold. Not (sunny or hot) = cloudy and cold. These universal rules can be used in order to get a different view point on logical formulas and sometimes to simplify or better understand logical problems. Example 4.6 (Different views on equivalent formulas) (x || y) && !(x && y) x or y, and not both (x || y) && (!x || !y) x or y, and one of them not !(!x && !y) && !(x && y) not none and not both !(!x && !y || x && y) not: both or none Subsection 4.7 Short circuit Evaluation For logical expressions, C++ uses so called short circuit evaluation: Logical operators && and || evaluate the left operand first. If the result is then known, the right operand will not be evaluated. Short circuit evaluation can lead to a faster execution of code (because less work needs to be done). But, much more importantly, short circuit evaluation also gives guarantees and Logical Values 51 can be extremely handy when expressions implicitly depend on conditions that need to be established before evaluating them. Example 4.7 (Short circuit evaluation) Consider the following piece of code int x, y, z;... bool b = (x != 0) && z / x > y; If x has value 6, say, the result corresponds to xz > y. If x has value 0, the result is false and the second expression is not evaluated. No division by zero takes place! Control Statements 52 Section 5 Control Statements Subsection 5.1 Selection Statements In programs we have discussed up to this point, all statements were executed statement by statement from top to bottom. But actually, almost all interesting programs use branches and jumps. ‘Recall the Euclidean algorithm, for instance. In this paragraph we discuss selection statements that implement branches. We will first discuss the if-statement and the if-else statement. if-statement The if-statement has the form if ( condition ) statement where condition is an expression that can be converted to bool and statement is an arbitrary statement called the body of the if-statement. It provides the following semantics: if and only if condition is true, then statement will be executed. Example 5.1 (if-statement) int a; std::cin >> a; Outputs even if and only if the entered if (a % 2 == 0) number is even. std::cout > a; if (a % 2 == 0) Outputs even if and the entered num- std::cout a; if (a % 2 == 0) std::cout