Chapter 1: Logic, Reasoning Methods and Set Theory PDF

# Chapter 1: Logic, Reasoning Methods and Set Theory ## 1.1 Logic ### 1.1.1 Proposition (statement), truth table * **Definition:** A proposition is a sentence that is either true or false, but not both simultaneously. * **Notation:** P, Q, R... * **Example:** 1. "For all x ∈ R, we have x² ≥...

# Chapter 1: Logic, Reasoning Methods and Set Theory ## 1.1 Logic ### 1.1.1 Proposition (statement), truth table * **Definition:** A proposition is a sentence that is either true or false, but not both simultaneously. * **Notation:** P, Q, R... * **Example:** 1. "For all x ∈ R, we have x² ≥ 0". This sentence is true so it is a proposition. 2. "2 x 3 = 5". This sentence is false so it is a proposition. 3. "The integer x divides 2". This sentence is neither true nor false so it is not a proposition. * **Remark:** * If the sentence is true, we assign it the value 1 (or T). * If the sentence is false, we assign it the value 0 (or F). ### 1.1.2 Truth Table * **Definition:** The truth table gives us the different possibilities for the statement P to be true or false, and is represented as follows: | P | |---|---| | 1 | | 0 | ### 1.1.2 Predicate * **Definition:** A predicate is a logical formula that depends on a free variable. ## 1.1.3 Basic Logical Connectives * **a) Negation:** "Not P", "¬P" * **Definition:** The negation of P is the statement "Not P", "¬P", which is true if P is false and which is false if P is true (vise-versa). * **Truth Table:** | P | ¬P | |---|---| | 1 | 0 | | 0 | 1 | * **Example:** * Given the statement P: "2 × 3 = 6" * Its negation is ¬P: "2 × 3 ≠ 6". * Given the statement Q: "√2 ∈ N" * Its negation is ¬Q: "√2 ∉ N". * **b) Conjunction:** “P and Q”, “P ∧ Q” * **Definition:** The conjunction of P and Q, denoted "P∧Q" which is true if both P and Q are true and false otherwise. * **Truth Table:** | P | Q | P ∧ Q | |---|---|---| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 0 | * **Example:** * "π is not an integer and π > 2". * "f (x) is decreasing and f (x) = ex". * **c) Disjunction:** "P or Q", "P ∨ Q" * **Definition:** The disjunction is the proposition "P or Q", denoted "P ∨ Q" which is false if both P and Q are false and true otherwise. * **Truth Table:** | P | Q | P ∨ Q | |---|---|---| | 1 | 1 | 1 | | 1 | 0 | 1 | | 0 | 1 | 1 | | 0 | 0 | 0 | * **Example:** * "π≥ 2 or e > 1". * "π = 3 or e <0". * **d) Implication:** "If P then Q", "(not P) or Q", "P ⇒ Q" * **Definition:** The implication is defined as "P ⇒ Q", we say that "if P then Q" or "(not P) or Q". "P ⇒ Q" is false when P is true and Q is false. "P ⇒ Q" is true otherwise. * **Truth Table:** | P | Q | P ⇒ Q | |---|---|---| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 1 | | 0 | 0 | 1 | * **Remark** * P is sufficient for Q. * Q is necessary for P. * **Example:** * "sine = 0 ⇒ 0 = π/2". * "2<7 ⇒ 2−7<0". * **e) Equivalence:** "If and only if...”, “P ⇔ Q” * **Definition:** The equivalence is defined as "P ⇔ Q” is the sentence “P ⇒ Q” and “Q ⇒ P”. we say that “P is equivalent to Q” or “P if and only if Q”. "P ⇔ Q" is true if and only if both statements P and Q have the same truth value i.e "P⇔ Q" when P and Q are true or when P and Q are false, and "P↔ Q" is false otherwise. * **Truth Table:** | P | Q | P ⇔ Q | |---|---|---| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 1 | * **Remark** * "P ⇔ Q" means that: P is both necessary and sufficient for Q. * **Example:** * "16 is even ⇒ 16 is divisible by 2". * "7 is prime number ⇒ 7 is divisible by 5". ## 1.2 Reasoning methods ### 1.2.1 Direct proof * **Definition:** To show that the statement "P ⇒ Q" is true, we assume that P is true and we show that Q is true. ### 1.2.2 Proof by cases * **Definition:** In order to show a statement P(x), for all x ∈ E, we show P(x), for x ∈ A ⊂ E, then for all x ∈ A. ### 1.2.3 Proof by contrapositive * **Definition:** To show that the statement “P ⇒ Q" is true, we show that its contrapositive "Q → P" is true. ### 1.2.4 Proof by contradiction * **Definition:** To show that the statement "P ⇒ Q”, we assume that P is true and Q is false (i.e is true) and we obtain a contradiction. Thus if P is true then Q is true, and “P ⇒ Q" is true. ### 1.2.5 Proof by counter example * **Definition:** In order to show a statement “∀x ∈ E: P(x)" is false, its suffices to get x ∈ E such that P(x) is false ### 1.2.6 Proof by induction * **Definition:** Let P(n) be a proposition depending on an integer n (n∈N). To show that P(n) is true for all n ∈ N, we follow the next steps: * **Step 1:** We prove that P(no) is true (with no is the initial value of n). * **Step 2:** We assume that P(n) is true for all n∈ N, and we prove that P(n + 1) is true. ## 1.3 Sets ### 1.3.1 Basic Concepts * **Definition:** A set is a collection of distinct objects. These are called the elements of E and are denoted by x ∈ E. * **Special Set:** The empty set denoted Ø contains no elements. * **Cardinality:** The number of elements of E is called the cardinal of E, denoted card(E). * **Example:** 1. The set of natural numbers N = {0, 1, 2, 3, ...}. 2. E = {red, black}, card(E) = 2. 3. A = {x ∈ R/ 0 ≤ x ≤ 1} = [0,1], x = 0.5 is an element of A. 4. E = 0 ⇒ card(E) = 0. ### 1.3.2 Relationships Between Sets * **a) Inclusion:** * **Definition:** We say that F is included in E, or that E contains F, or that F is a part of E : If every element of F is an element of E. * F ⊂ E ⇔ [∀x(x ∈ F ⇒ x ∈ E)]. * **Remark:** If F ⊂ E, then F is called a subset of E. * **Example:** * Let A, B be two sets such that: * A = {x ∈ R : |x| ≤ 4} = [-4,4], * B = {x ∈ R: |x| ≤ 2} = [-2,2], * Therefore, B ⊆ A. * **b) Equality of two sets:** * **Definition:** E and F are equal and are denoted by E = F if and only if (E⊆ F) and (F⊆ E). ### 1.3.3 Set and operations * **a) Intersection:** * **Definition:** The intersection of A and B is a part of E defined by: * A ∩ B = {x ∈ E/ x ∈ A and x ∈ B}. * **b) Union** * **Definition:** The union of A and B is the set defined by: * AUB = {x ∈ E/x ∈ A or x ∈ B}. * **c) Complement:** * **Definition:** The complement of A with respect to E, is the set denoted Ā (and sometimes also CɛA or Aº) and defined by: * Ā = {x ∈ E : x ∉ A}. * **d) Difference:** * **Definition:** The difference of A and B is the set noted (A - B) or (A \ B) and defined by: * A − B = {x ∈ E/ x ∈ A and x ∉ B}. * **e) Symmetric difference:** * **Definition:** The symmetric difference of A and B is denoted A∆B and defined by: * A∆B = {x ∈ E/ (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A)}, * = (A - B) U (B – A). ### 1.3.3 Set of parts (Power set) * **Definition:** Let E be a set, and the subsets of E form a set called the set of parts of E, denoted by: P(E). * **Proposition:** Let E be a set such that card(E) = n, then card(P(E)) = 2card(E) = 2^n. ### 1.3.5 Partition * **Definition:** Let E be a set and E1, E2, ..., En be parts of E. We say that (E1, E2, ..., En) form a partition of E if the following conditions are satisfied: * **1:** Each of these sets are non-empty. * **2:** They are two by two disjoint. * **3:** Their union is equal to E.