Discrete Mathematics - Chapter 1 (1st Part) PDF

Discrete Mathematics Chapter 1 Propositional Logic Applications of Propositional Logic Propositional Equivalences Section 1.1  Propositions  A proposition is a declarative sentence that is either true or false but not both.  The truth-value of a proposition is "true" or "false.”  Examples...

Discrete Mathematics Chapter 1 Propositional Logic Applications of Propositional Logic Propositional Equivalences Section 1.1  Propositions  A proposition is a declarative sentence that is either true or false but not both.  The truth-value of a proposition is "true" or "false.”  Examples: Propositional Logic The following sentences are proposition.  Determine whether it is true or false. a) The Moon is made of green cheese. This makes declarative sentence , and hence is a proposition. The proposition is false (F) b) Riyadh is the capital of Saudi Arabia This makes declarative sentence , and hence is a proposition. The proposition is True (T) c) 1 + 0 = 1 This makes declarative sentence , and hence is a proposition. The proposition is True (T) Examples that are not propositions: a) Sit down! This is an imperative sentence, and not declarative sentence , and hence it is not a proposition. b) x + 1 = 2 Because this equation is true when x=1, and false for other values , it is not a proposition. c) x + y = z d) What time is it? Propositional variables (statement variables)  We use letters to denote propositional variables: : p, q, r, s, …  The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. Compound Propositions  Constructing Propositions:  Compound Propositions are formed from existing propositions using logical operators ( connectives). Negation ¬ ~ (NOT) “Unary operation” Conjunction ∧ (And) Disjunction ∨ (Or) “Binary Operation” Implication → (If) Biconditional ↔ (Iff)  1 - Negation of a proposition  DEFINITION 1: Let p be a proposition. The negation of p, denoted by ￢p (also denoted by not p), is the statement “It is not the case that p.” The proposition ￢p is read “not p” The truth value of the negation of p, ￢p, is the opposite of the truth value of p.  Example : Negation of a proposition Find the negation of the proposition “Michael’s PC runs Linux” and express this in simple English.  Solution: The negation is “It is not the case that Michael’s PC runs Linux.” This negation can be more simply expressed as “Michael’s PC does not run Linux.”  Truth tables  Truth tables are used to display the relationships between the truth-values of propositions. Number of rows determined by 𝟐𝒏, where n is the number of propositions.  “Truth table for the negation of p”. This table has a row for each of the two possible truth values of a proposition p. Each row shows the truth value of ￢p corresponding to the truth value of p for this row. p ￢p T F F T 2- Conjunction and 3- Disjunction  Definition2: Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.  Definition3: Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. Conjunction and Disjunction (Binary operations ∧, ∨)  The Truth Table for the Conjunction and Disjunction of Two Propositions. P q p∧q p∨q T T T T T F F T F T F T F F F F Note: For two propositions:, there are 𝟐𝟐 = 4 rows  Example: Conjunction and Disjunction (Binary operations ∧,∨) The Truth Table for the Conjunction and Disjunction of three Propositions. p q r p∧q p∨r T T T T T T T F T T T F T F T T F F F T F T T F T F T F F F F F T F T F F F F F Note: For 3 propositions: 𝟐𝟑 = 8 rows Corollary: Conjunction and Disjunction  A disjunction (or ) is true when at least one of the propositions is true.  ---------------------------------------------------------  A conjunction (and) is true when all of the propositions are true.  Example: Conjunction and Disjunction  Find the conjunction and disjunction of the propositions p and q where p= “Rebecca’s PC has more than 16 GB free hard disk space” q= “The processor in Rebecca’s PC runs faster than 1 GHz.” Solution  Conjunction (p ∧ q): Rebecca’s PC has more than 16 GB free hard disk space, and the processor in her PC runs faster than 1 GHz.  Disjunction (p ∨ q): Rebecca’s PC has more than 16 GB free hard disk space, or the processor in her PC runs faster than 1 GHz.  4- Exclusive or;  DEFINITION 4: Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.  The truth table for ⊕ of two propositions is: p q p ⊕q T T F T F T F T T F F F Example: Exclusive or  We are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this class.”  Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class.  Example: customers can get an exchange or a refund 5- Conditional Statements (p → q ) Definition: Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). p q p →q T T T T F F F T T F F T  Conditional Statements(implication: p →q )  Example 1: If p denotes “I am at home.” and q denotes “It is raining.” then p →q denotes “If I am at home then it is raining.”  Conditional Statements(implication )  Example: Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find a good job.”  Express the statement p → q as a statement in English. Solution :  “If Maria learns discrete mathematics, then she will find a good job.” ‫صيغ لفظية أخرى‬  “Maria will find a good job when she learns discrete mathematics.”  “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.”  “Maria will find a good job unless she does not learn discrete mathematics.” Different Ways of Expressing p →q if p, then q p implies q if p, q p only if q q unless ¬p q when p q if p q when p q whenever p p is sufficient for q q follows from p q is necessary for p a necessary condition for p is q a sufficient condition for q is p Converse, Contrapositive, and Inverse  From p →q we can form new conditional statements.  q →p is the converse of p →q  ¬q → ¬ p is the contrapositive of p →q  ¬p→¬q is the inverse of p →q Example: Find the converse, inverse, and contrapositive of “It is raining is a sufficient condition for me not going to town.” Solution: converse: If I do not go to town, then it is raining. contrapositive: If I go to town, then it is not raining. inverse: If it is not raining, then I will go to town. 6- Biconditional (p ↔q )  p ↔q , read as “p if and only if q.” The biconditional p ↔q is true when p and q have the same truth-values and is false otherwise. It denotes the proposition with this truth table: p q p ↔q T T T T F F F T F F F T  If p denotes “I am at home.” and q denotes “It is raining.” then  p ↔q denotes “I am at home if and only if it is raining.”  Expressing the Biconditional (p ↔q )  Some alternative ways “p if and only if q” is expressed in English:  p is necessary and sufficient for q  if p then q , and conversely  p iff q ****Order of operations: The logical operators in the innermost parentheses are applied first. The negation operator is applied before all other logical operators. Truth Table of 𝒑 ∨ 𝒒 → ¬𝒓  Example: Construct a truth table for 𝒑 ∨ 𝒒 → ¬𝒓 p q r r pq p  q → r T T T F T F T T F T T T T F T F T F T F F T T T F T T F T F F T F T T T F F T F F T F F F T F T  Problem  How many rows are there in a truth table with n propositional variables? Solution: 2n We will see how to do this in Chapter 6.  Note that this means that with n propositional variables, we can construct 2n distinct (i.e., not equivalent) propositions.  Logic and Bit Operations A bit has two possible values, zero (0) and one(1). A zero bit represents "false"; a one bit represents "true." There are bit operations corresponding to logical conjunction (AND), disjunction (OR), and exclusive or (XOR). A bit string is a sequence of zero or more bits. The length of the string is the number of bits in the string. The bit operations can be performed on two strings of the same length by comparing respective bits.  Logic and Bit Operations Truth Value Bit T 1 F 0 The Truth Table of 𝒙 ∨ 𝒚, 𝒙∧𝒚 and 𝒙⊕𝒚 x y 𝒙∨𝒚 𝒙∧𝒚 𝒙⊕𝒚 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 Section 1.2 Translating English Sentences  “If I go to Harry’s or to the country, I will not go shopping.”  p: I go to Harry’s  q: I go to the country.  r: I will go shopping. If p or q then not r.  Example Problem: Translate the following sentence into propositional logic: “You can access the Internet from campus only if you are a computer science major or you are not a freshman.” One Solution: Let a, c, and f represent respectively “You can access the internet from campus,” “You are a computer science major,” and “You are a freshman.” a→ (c ∨ ¬ f )  Logic Circuits  Electronic circuits; each input/output signal can be viewed as a 0 or 1.  0 represents False  1 represents True  Complicated circuits are constructed from three basic circuits called gates.  The inverter (NOT gate)takes an input bit and produces the negation of that bit.  The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits.  The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits.  More complicated digital circuits can be constructed by combining these basic circuits to produce the desired output given the input signals by building a circuit for each piece of the output expression and then combining them. For example:  Example: Logic Circuits Determine the output for the combinatorial circuit p ∧￢q (p ∧￢q)∨￢r. Solution The AND gate takes input of p and ￢q, the output is p ∧￢q. Next, we note that the OR gate takes input p ∧￢q and ￢r, the output of the inverter with input r, and produces the final output (p ∧￢q)∨￢r. The output can be found by using the truth table. Example: Logic Circuits  Build a digital circuit that produces the output (p ∨￢r) ∧ (￢p ∨ (q ∨￢r)) when given input bits p, q, and r.  Solution: To construct the desired circuit, we build separate circuits for p ∨￢r and for ￢p ∨ (q ∨￢r) and combine them using an AND gate. Section 1.3 Equivalent Propositions  Two propositions are equivalent if they always have the same truth value. The notation p ≡ q denotes that p and q are logically equivalent.  Example (++): Show using a truth table that the conditional is equivalent to the contrapositive. Solution: p →q equivalent to ¬q → ¬ p p q ¬p ¬q p →q ¬q → ¬ p T T F F T T T F F T F F F T T F T T F F T T T T  Using a Truth Table to Show Non-Equivalence Example(--): Show using truth tables that neither the converse nor inverse of an implication (conditional) are not equivalent to the implication. Solution: p q ¬p ¬q p →q ¬ p →¬ q q→p T T F F T T T T F F T F T T F T T F T F F F F T T T T T Tautologies, Contradictions, and Contingencies  A tautology is a proposition which is always true.  Example: p ∨¬p  A contradiction is a proposition which is always false.  Example: p ∧¬p  A contingency is a proposition which is neither a tautology nor a contradiction, such as p P ¬p p ∨¬p p ∧¬p T F T F F T T F Logically Equivalent  Two compound propositions p and q are logically equivalent if p↔ q is a tautology.  We write this as p⇔q or as p≡q where p and q are compound propositions.  Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree.  This truth table show ¬p ∨ q is equivalent to p → q. p q ¬p ¬p ∨ q p→ q T T F T T T F F F F F T T T T F F T T T  De Morgan’s Laws This truth table shows that De Morgan’s Second Law holds. p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Logical Equivalences p ∧ T ≡ p Identity laws p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive p∨F≡p laws -------------------------- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ T ≡ T Domination laws ------------------------------------------- p∧F≡F ￢(p ∧ q) ≡ ￢p ∨￢q De Morgan’s laws ----------------------------- ￢(p ∨ q) ≡ ￢p ∧￢q p ∨ p ≡ p Idempotent laws --------------------------------------------------- p∧p≡p p ∨ (p ∧ q) ≡ p Absorption laws --------------------------------- p ∧ (p ∨ q) ≡ p ￢(￢p) ≡ p Double negation law -------------------------------------------------- ---------------------------------------- p ∨￢p ≡ T Negation laws p ∨ q ≡ q ∨ p Commutative laws p ∧￢p ≡ F p∧q≡q∧p --------------------------------------------------------- --------------------------------------------- Associative laws (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Key Logical Equivalences (cont)  Commutative Laws: ,  Associative Laws:  Distributive Laws:  Absorption Laws: More Logical Equivalences De Morgan’s laws extend to-  ￢(p1 ∨ p2 ∨ · · · ∨ pn) ≡ (￢p1 ∧￢p2 ∧ ··· ∧ ￢pn) and  ￢(p1 ∧ p2 ∧ · · · ∧ pn) ≡ (￢p1 ∨￢p2 ∨ ··· ∨ ￢pn). Equivalence Proofs Example: Show that is logically equivalent to Solution: Example: Show that is a tautology. Solution: (p ∧ q) → (p ∨ q) ≡ ￢(p ∧ q) ∨ (p ∨ q) by Example 3 ≡ (￢p ∨￢q) ∨ (p ∨ q) by the first De Morgan law ≡ (￢p ∨ p) ∨ (￢q ∨ q) by the associative and commutative laws for disjunction ≡T∨T by Example 1 and the commutative law for disjunction ≡T by the domination law Propositional Satisfiability A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.  Example: Propositional Satisfiability Determine whether (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) is satisfiable. Solution: Instead of using truth table to solve this problem, we will reason about truth values. Note that (p ∨￢q) ∧ (q ∨￢r) ∧ (r ∨￢p) is true when the three variable p, q, and r have the same truth value. Hence, it is satisfiable as there is at least one assignment of truth values for p, q, and r that makes it true.