Math 1 - CH 01 Logic and Proofs PDF

Math 1 CH 01: Logic and Proofs  Content The Foundations: Logic and Proofs Propositional Logic Applications of Propositional Logic Propositional Equivalences Predicates and Quantifiers Nested Quantifiers Rules of Inference Introduction to Proofs Proof Methods and Str...

Math 1 CH 01: Logic and Proofs  Content The Foundations: Logic and Proofs Propositional Logic Applications of Propositional Logic Propositional Equivalences Predicates and Quantifiers Nested Quantifiers Rules of Inference Introduction to Proofs Proof Methods and Strategy  Propositional Logic Logic rules are used to distinguish between valid and invalid mathematical arguments. A proposition is a declarative sentence (a sentence that declares a fact) that is either true or false, but not both. o Propositions are the basic building blocks of logic.  Propositional Logic EXAMPLE 1: All the following declarative sentences are propositions. Proposition T/F Washington, D.C., is the capital of the United States of True America Qena is the capital of Canada False 1+1=2 True 2+2=3 False  Propositional Logic EXAMPLE 2: Some sentences that are not propositions. Proposition What time is it? not declarative sentence Read this carefully. not declarative sentence x + 1 = 2. neither true nor false x + y = z. neither true nor false  Propositional Logic Logical Operations Negation (¬𝑝) Conjunction (𝑝 ∧ 𝑞) Disjunction (𝑝 ∨ 𝑞) Exclusive (𝑝 ⊕ 𝑞) Conditional (𝑝 → 𝑞) p q 𝑝∧𝑞 p q 𝑝∨𝑞 p q 𝑝⊕𝑞 p q 𝑝 →𝑞 p ¬𝑝 T T T T T T T T F T T T T F T F F T F T T F T T F F F T F T F F T T F T T F T T F F F F F F F F F F F T  Propositional Logic EXAMPLE 7: Let 𝑝 be the statement “Maria learns discrete mathematics” and 𝑞 the statement “Maria will find a good job.” Express the statement 𝑝 → 𝑞 as a statement in English. Solution 7: “If Maria learns discrete mathematics, then she will find a good job.”  Propositional Logic EXAMPLE 8: What is the value of the variable 𝑥 after the statement 𝑖𝑓 2 + 2 = 4 𝑡ℎ𝑒𝑛 𝑥 ∶= 𝑥 + 1 if 𝑥 = 0 before this statement is encountered? Solution 8: Because 2 + 2 = 4 is true, the assignment statement 𝑥 ∶= 𝑥 + 1 is executed. Hence, 𝑥 has the value 0 + 1 = 1 after this statement is encountered.  Propositional Logic Related conditional statements 𝑝 → 𝑞 CONVERSE CONTRAPOSITIVE INVERSE 𝑞 → 𝑝 ¬𝑞 → ¬𝑝 ¬𝑝 → ¬𝑞 Only the contrapositive always has the same truth value as 𝑝 → 𝑞.  Propositional Logic The biconditional statement 𝑝 ↔ 𝑞 is the proposition “p if and only if q.” o The biconditional statement 𝑝 ↔ 𝑞 is true when 𝑝 and 𝑞 have the same truth values and is false otherwise. Example 10: “You can take the flight if and only if you buy a ticket.”  Propositional Logic EXAMPLE 11: Construct the truth table of the compound proposition (𝑝 ∨ ¬𝑞) → (𝑝 ∧ 𝑞).  Propositional Logic Precedence of Logical Operators  Exercises 1. Which of these sentences are propositions? What are the truth values of those that are propositions? Sentence 2+3=5 5 + 7 = 10 x + 2 = 11. Answer this question  Exercises 1. Which of these sentences are propositions? What are the truth values of those that are propositions? Sentence Answer 2+3=5 true proposition 5 + 7 = 10 false proposition x + 2 = 11. not a proposition Answer this question not a proposition  Exercises 8. Suppose that Smartphone A has 256MB RAM and 32GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions. Sentence Smartphone B has the most RAM of these three smartphones. Smartphone C has more ROM or a higher resolution camera than Smartphone B. Smartphone B has more RAM, more ROM, and a higher resolution camera than Smartphone A. If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera. Smartphone A has more RAM than Smartphone B if and only if Smartphone B has more RAM than Smartphone A.  Exercises 8. Suppose that Smartphone A has 256MB RAM and 32GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions. Sentence Answer Smartphone B has the most RAM of these three smartphones. True Smartphone C has more ROM or a higher resolution camera than Smartphone B. True Smartphone B has more RAM, more ROM, and a higher resolution camera than False Smartphone A. If Smartphone B has more RAM and more ROM than Smartphone C, then it also has False a higher resolution camera. Smartphone A has more RAM than Smartphone B if and only if Smartphone B has False more RAM than Smartphone A.  Exercises 14. Let 𝑝, 𝑞, and 𝑟 be the propositions 𝑝 :You have the flu; 𝑞 :You miss the final examination; 𝑟 :You pass the course. Express each of these propositions as an English sentence. Sentence 𝑝 → 𝑞 ¬𝑞 ↔ 𝑟 𝑞 → ¬𝑟 𝑝 ∨ 𝑞 ∨ 𝑟 (𝑝 → ¬𝑟) ∨ (𝑞 → ¬𝑟) (𝑝 ∧ 𝑞) ∨ (¬𝑞 ∧ 𝑟)  Exercises 14. Let 𝑝, 𝑞, and 𝑟 be the propositions 𝑝 :You have the flu; 𝑞 :You miss the final examination; 𝑟 :You pass the course. Express each of these propositions as an English sentence. Sentence Answer 𝑝 → 𝑞 If you have the flu, then you miss the final exam. ¬𝑞 ↔ 𝑟 You do not miss the final exam if and only if you pass the course. 𝑞 → ¬𝑟 If you miss the final exam, then you do not pass the course. 𝑝 ∨ 𝑞 ∨ 𝑟 You have the flu, or miss the final exam, or pass the course. (𝑝 → ¬𝑟) ∨ (𝑞 → ¬𝑟) if you have the flu, then you do not pass the course or if you miss the final exam then you do not pass the course. (𝑝 ∧ 𝑞) ∨ (¬𝑞 ∧ 𝑟) You have the flu and miss the final exam, or you do not miss the final exam and do pass the course.  Exercises 18. Determine whether these biconditionals are true or false. Sentence 1 + 1 = 3 if and only if monkeys can fly 0 > 1 if and only if 2 > 1.  Exercises 18. Determine whether these biconditionals are true or false. Sentence Answer 1 + 1 = 3 if and only if monkeys can fly This is 𝐹 ↔ 𝐹, which is true. 0 > 1 if and only if 2 > 1. This is 𝐹 ↔ 𝑇, which is false.  Exercises 19. Determine whether each of these conditional statements is true or false. Sentence If 1 + 1 = 2, then 2 + 2 = 5. If 1 + 1 = 3, then 2 + 2 = 4.  Exercises 19. Determine whether each of these conditional statements is true or false. Sentence Answer If 1 + 1 = 2, then 2 + 2 = 5. 𝑇 → 𝐹, False If 1 + 1 = 3, then 2 + 2 = 4. 𝐹 → 𝑇, True  Exercises 30. State the converse, contrapositive, and inverse of each of these conditional statements. a) If it snows tonight, then I will stay at home. b) I go to the beach whenever it is a sunny summer day. c) When I stay up late, it is necessary that I sleep until noon.  Exercises 30. State the converse, contrapositive, and inverse of each of these conditional statements. a) If it snows tonight, then I will stay at home. b) I go to the beach whenever it is a sunny summer day. c) When I stay up late, it is necessary that I sleep until noon. Converse Contrapositive Inverse If I stay home, then it will snow If I do not stay at home, then it If it does not snow tonight, then I tonight will not snow tonight. will not stay home. Whenever it is a sunny summer Whenever it is not a sunny I do not go to the beach. day, I go to the beach summer day, I do not go to the Whenever it is not a sunny day, beach. If I sleep until noon, then I stayed If I do not sleep until noon, then I If I don’t stay up late, then I don’t up late. do not stay up late. sleep until noon.  Exercises 31. How many rows appear in a truth table for each of these compound propositions? proposition 𝑝 → ¬𝑝 (𝑝 ∨ ¬𝑟) ∧ (𝑞 ∨ ¬𝑠) 𝑞 ∨ 𝑝 ∨ ¬𝑠 ∨ ¬𝑟 ∨ ¬𝑡 ∨ 𝑢 (𝑝 ∧ 𝑟 ∧ 𝑡) ↔ (𝑞 ∧ 𝑡)  Exercises 31. How many rows appear in a truth table for each of these compound propositions? proposition Answer 𝑝 → ¬𝑝 2' = 2 (𝑝 ∨ ¬𝑟) ∧ (𝑞 ∨ ¬𝑠) 2( = 16 𝑞 ∨ 𝑝 ∨ ¬𝑠 ∨ ¬𝑟 ∨ ¬𝑡 ∨ 𝑢 2) = 64 (𝑝 ∧ 𝑟 ∧ 𝑡) ↔ (𝑞 ∧ 𝑡) 2( = 16  Exercises 33. Construct a truth table for each of these compound propositions. a) 𝑝 ∧ ¬𝑝 b) 𝑝 ∨ ¬𝑝 c) 𝑝 ∨ ¬𝑞 → 𝑞 d) (𝑝 ∨ 𝑞) → (𝑝 ∧ 𝑞) e) (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝) f) (𝑝 → 𝑞) → (𝑞 → 𝑝)  Exercises 33. Construct a truth table for each of these compound propositions. a) 𝑝 ∧ ¬𝑝 b) 𝑝 ∨ ¬𝑝 𝑝 ¬𝑝 𝑝 ∧ ¬𝑝 𝑝 ∨ ¬𝑝 T F F T F T F T  Exercises 33. Construct a truth table for each of these compound propositions. a) 𝑝 ∨ ¬𝑞 → 𝑞 𝒑 𝒒 ¬𝒒 𝒑 ∨ ¬𝒒 (𝒑 ∨ ¬𝒒) → 𝒒 T T F T T T F T T F F T F F T F F T T F  Exercises 33. Construct a truth table for each of these compound propositions. a) (𝑝 ∨ 𝑞) → (𝑝 ∧ 𝑞) 𝒑 𝒒 𝑝 ∨ 𝑞 𝑝 ∧ 𝑞 (𝑝 ∨ 𝑞) → (𝑝 ∧ 𝑞) T T T T T T F T F F F T T F F F F F F T  Exercises 33. Construct a truth table for each of these compound propositions. a) (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝) 𝒑 𝒒 𝑝 → 𝑞 ¬𝑞 → ¬𝑝 (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝) T T T T T T F F F T F T T T T F F T T T  Exercises 33. Construct a truth table for each of these compound propositions. a) (𝑝 → 𝑞) → (𝑞 → 𝑝) 𝒑 𝒒 𝑝 → 𝑞 𝑞 → 𝑝 (𝑝 → 𝑞) → (𝑞 → 𝑝) T T T T T T F F T T F T T F F F F T T T  Exercises 41. Construct a truth table for (𝑝 ↔ 𝑞) ↔ (𝑟 ↔ 𝑠).  Exercises 41. Construct a truth table for (𝑝 ↔ 𝑞) ↔ (𝑟 ↔ 𝑠).  Exercises 42. Explain, without using a truth table, why (𝑝 ∨ ¬𝑞) ∧ (𝑞 ∨ ¬𝑟) ∧ (𝑟 ∨ ¬𝑝) is true when 𝑝, 𝑞, and 𝑟 have the same truth value and it is false otherwise.  Exercises 42. Explain, without using a truth table, why (𝑝 ∨ ¬𝑞) ∧ (𝑞 ∨ ¬𝑟) ∧ (𝑟 ∨ ¬𝑝) is true when 𝑝, 𝑞, and 𝑟 have the same truth value and it is false otherwise. This statement is true if and only if all three clauses, 𝑝 ∨ ¬𝑞, 𝑞 ∨ ¬𝑟, and 𝑟 ∨ ¬𝑝 are true. Suppose 𝑝, 𝑞 , and 𝑟 are all true. Because each clause has an unnegated variable, each clause is true. Similarly, if 𝑝, 𝑞 , and 𝑟 are all false, then because each clause has a negated variable, each clause is true. On the other hand, if one of the variables is true and the other two false, then the clause containing the negation of that variable will be false, making the entire conjunction false; and similarly, if one of the variables is false and the other two true, then the clause containing that variable unnegated will be false, again making the entire conjunction false.  Exercises 46. What is the value of 𝑥 after each of these statements is encountered in a computer program, if 𝑥 = 1 before the statement is reached? if x + 2 = 3 then x := x + 1 if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1  Exercises 46. What is the value of 𝑥 after each of these statements is encountered in a computer program, if 𝑥 = 1 before the statement is reached? if x + 2 = 3 then x := x + 1 The condition is true, the statement is executed, so x is incremented and now has the value 2. if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1 The condition is false, the statement is not executed, so x is not incremented and now still has the value 1.  Exercises In fuzzy logic, a proposition has a truth value that is a number between 0 and 1, inclusive. A proposition with a truth value of 0 is false and one with a truth value of 1 is true. Truth values that are between 0 and 1 indicate varying degrees of truth. o For instance, the truth value 0.8 can be assigned to the statement “Fred is happy,” because Fred is happy most of the time. o The truth value 0.4 can be assigned to the statement “John is happy,” because John is happy slightly less than half the time.  Exercises 49. The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition. What are the truth values of the statements “Fred is not happy” and “John is not happy?”  Exercises 49. The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition. What are the truth values of the statements “Fred is not happy” and “John is not happy?” For "Fred is not happy," the truth value is 1 - 0.8 = 0.2. For "John is not happy,'' the truth value is 1- 0.4 = 0.6.  Exercises 50. The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions. What are the truth values of the statements “Fred and John are happy” and “Neither Fred nor John is happy”?  Exercises 50. The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions. What are the truth values of the statements “Fred and John are happy” and “Neither Fred nor John is happy”? For "Fred and John are happy," à min(0.8; 0.4) = 0.4 For "Neither Fred nor John is happy" à min(0.2; 0.6) = 0.2  Tasks Section 1 2 5 Section 1 9 46 (c, d, e) 13 47 18 (a, b) 51 fuzzy logic 19 (c, d) 29 32 34 40 43  Content The Foundations: Logic and Proofs Propositional Logic Applications of Propositional Logic Propositional Equivalences Predicates and Quantifiers Nested Quantifiers Rules of Inference Introduction to Proofs Proof Methods and Strategy Applications of Propositional Logic Translating English Sentences System Specifications Boolean Searches Logic Puzzles Logic Circuits  Applications of Propositional Logic Translating EXAMPLE 1: English Sentences How can this English sentence be translated into a logical expression? System “You can access the Internet from campus only if you are a computer Specifications science major or you are not a freshman.” Boolean Searches Solution: Logic 𝑎 = “You can access the Internet from campus,” Puzzles 𝑏 = “𝑌𝑜𝑢 𝑎𝑟𝑒 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝑟 𝑠𝑐𝑖𝑒𝑛𝑐𝑒 𝑚𝑎𝑗𝑜𝑟, ” 𝑐 = “𝑌𝑜𝑢 𝑎𝑟𝑒 𝑎 𝑓𝑟𝑒𝑠ℎ𝑚𝑎𝑛, ” Logic “𝑜𝑛𝑙𝑦 𝑖𝑓” 𝑖𝑠 𝑜𝑛𝑒 𝑤𝑎𝑦 𝑎 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 Circuits 𝑎 → (𝑏 ∨ ¬𝑐 ).  Applications of Propositional Logic Translating EXAMPLE 3: English Sentences Express the specification using logical connectives. System “The automated reply cannot be sent when the file system is full” Specifications Boolean Solution: Searches 𝑝 = “The automated reply can be sent” Logic 𝑞 = “𝑇ℎ𝑒 𝑓𝑖𝑙𝑒 𝑠𝑦𝑠𝑡𝑒𝑚 𝑖𝑠 𝑓𝑢𝑙𝑙. ” Puzzles 𝑞 → ¬𝑝. Logic Circuits  Applications of Propositional Logic Translating Check the consistency of the system specification (no conflictions). English Sentences We have to prove that all the specifications be true. System Specifications Boolean Searches Logic Puzzles Logic Circuits  Applications of Propositional Logic Example 4: Determine if these system specifications are consistent: o“The diagnostic message is stored in the buffer or it is retransmitted.” o“The diagnostic message is not stored in the buffer.” o“If the diagnostic message is stored in the buffer, then it is retransmitted.” Solution: let op = “The diagnostic message is stored in the buffer” oq = “The diagnostic message is retransmitted.”  Applications of Propositional Logic The specification can be written as: o 𝑝 ⋁ 𝑞 = “The diagnostic message is stored in the buffer or it is retransmitted.” o ¬𝑝 = “The diagnostic message is not stored in the buffer.” o 𝑝 → 𝑞 = “If the diagnostic message is stored in the buffer, then it is retransmitted.” 1. To make ¬𝑝 true, 𝑝 must be false. 2. To make 𝑝 ⋁ 𝑞 true, we have 𝑝 is false, then we set 𝑞 to be true. 3. To make 𝑝 → 𝑞 true, we have 𝑝 is false and 𝑞 is true. So, false → true = true. From 1, 2, and 3, we conclude that the specification is consistent.  Applications of Propositional Logic Translating EXAMPLE 6: Web Page Searching, Information retrieval and Databases English Sentences Using Boolean searching to find Web pages about universities in New System Mexico, we can look for pages matching Specifications 𝑁𝐸𝑊 𝐴𝑁𝐷 𝑀𝐸𝑋𝐼𝐶𝑂 𝐴𝑁𝐷 𝑈𝑁𝐼𝑉𝐸𝑅𝑆𝐼𝑇𝐼𝐸𝑆. Boolean Searches To find pages that deal with universities in New Mexico or Arizona, we Logic can search for pages matching Puzzles (𝑁𝐸𝑊 𝐴𝑁𝐷 𝑀𝐸𝑋𝐼𝐶𝑂 𝑂𝑅 𝐴𝑅𝐼𝑍𝑂𝑁𝐴) 𝐴𝑁𝐷 𝑈𝑁𝐼𝑉𝐸𝑅𝑆𝐼𝑇𝐼𝐸𝑆. Logic What are Google Search Operators? Circuits  Applications of Propositional Logic Translating EXAMPLE 7: English Sentences An island that has two kinds of inhabitants, knights, who always tell System the truth, and their opposites, knaves, who always lie. You encounter Specifications two people A and B. What are A and B if A says “B is a knight” and B says “The two of us are opposite types?” Boolean Searches Logic Solution: …TASK Puzzles Logic Example 8: TASK … read and comprehend Circuits  Applications of Propositional Logic Translating EXAMPLE 9: English Sentences Determine the output for the combinatorial circuit in Figure 2. System Specifications Boolean Searches Logic Puzzles Logic Circuits  Exercises Translate the given statement into propositional logic using the propositions provided. 1. You cannot edit a protected Wikipedia entry unless you are an administrator. Express your answer in terms of 𝑒: “𝑌𝑜𝑢 𝑐𝑎𝑛 𝑒𝑑𝑖𝑡 𝑎 𝑝𝑟𝑜𝑡𝑒𝑐𝑡𝑒𝑑 𝑊𝑖𝑘𝑖𝑝𝑒𝑑𝑖𝑎 𝑒𝑛𝑡𝑟𝑦” and 𝑎: “𝑌𝑜𝑢 𝑎𝑟𝑒 𝑎𝑛 𝑎𝑑𝑚𝑖𝑛𝑖𝑠𝑡𝑟𝑎𝑡𝑜𝑟. ”  Exercises 1. You cannot edit a protected Wikipedia entry unless you are an administrator. Express your answer in terms of 𝑒: “𝑌𝑜𝑢 𝑐𝑎𝑛 𝑒𝑑𝑖𝑡 𝑎 𝑝𝑟𝑜𝑡𝑒𝑐𝑡𝑒𝑑 𝑊𝑖𝑘𝑖𝑝𝑒𝑑𝑖𝑎 𝑒𝑛𝑡𝑟𝑦” and 𝑎: “𝑌𝑜𝑢 𝑎𝑟𝑒 𝑎𝑛 𝑎𝑑𝑚𝑖𝑛𝑖𝑠𝑡𝑟𝑎𝑡𝑜𝑟. ” e → 𝑎 (You can edit a protected Wikipedia entry, then you are an admin) or ¬𝑎 → ¬𝑒 (if you are not an admin, you cannot edit a Wikipedia entry)  Exercises 3. You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of 𝑔: “𝑌𝑜𝑢 𝑐𝑎𝑛 𝑔𝑟𝑎𝑑𝑢𝑎𝑡𝑒, ” 𝑚: “𝑌𝑜𝑢 𝑜𝑤𝑒 𝑚𝑜𝑛𝑒𝑦 𝑡𝑜 𝑡ℎ𝑒 𝑢𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦, ” 𝑟: “𝑌𝑜𝑢 ℎ𝑎𝑣𝑒 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝑑 𝑡ℎ𝑒 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 𝑜𝑓 𝑦𝑜𝑢𝑟 𝑚𝑎𝑗𝑜𝑟, ” and 𝑏: “𝑌𝑜𝑢 ℎ𝑎𝑣𝑒 𝑎𝑛 𝑜𝑣𝑒𝑟𝑑𝑢𝑒 𝑙𝑖𝑏𝑟𝑎𝑟𝑦 𝑏𝑜𝑜𝑘. ”  Exercises 3. You can graduate only if you have completed the requirements of your major and you do not owe money to the university and you do not have an overdue library book. Express your answer in terms of 𝑔: “𝑌𝑜𝑢 𝑐𝑎𝑛 𝑔𝑟𝑎𝑑𝑢𝑎𝑡𝑒, ” 𝑚: “𝑌𝑜𝑢 𝑜𝑤𝑒 𝑚𝑜𝑛𝑒𝑦 𝑡𝑜 𝑡ℎ𝑒 𝑢𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦, ” 𝑟: “𝑌𝑜𝑢 ℎ𝑎𝑣𝑒 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝑑 𝑡ℎ𝑒 𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 𝑜𝑓 𝑦𝑜𝑢𝑟 𝑚𝑎𝑗𝑜𝑟, ” and 𝑏: “𝑌𝑜𝑢 ℎ𝑎𝑣𝑒 𝑎𝑛 𝑜𝑣𝑒𝑟𝑑𝑢𝑒 𝑙𝑖𝑏𝑟𝑎𝑟𝑦 𝑏𝑜𝑜𝑘. ” 𝑔 → (𝑟 ∧ (¬𝑚) ∧ (¬𝑏)).  Exercises 8. Express these system specifications using the propositions 𝑝 “𝑇ℎ𝑒 𝑢𝑠𝑒𝑟 𝑒𝑛𝑡𝑒𝑟𝑠 𝑎 𝑣𝑎𝑙𝑖𝑑 𝑝𝑎𝑠𝑠𝑤𝑜𝑟𝑑, ” 𝑞 “𝐴𝑐𝑐𝑒𝑠𝑠 𝑖𝑠 𝑔𝑟𝑎𝑛𝑡𝑒𝑑, ” and 𝑟 “𝑇ℎ𝑒 𝑢𝑠𝑒𝑟 ℎ𝑎𝑠 𝑝𝑎𝑖𝑑 𝑡ℎ𝑒 𝑠𝑢𝑏𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 𝑓𝑒𝑒” and logical connectives (including negations). Sentence Proposition “The user has paid the subscription fee, but does not enter a valid password.” “Access is granted whenever the user has paid the subscription fee and enters a valid password.” “Access is denied if the user has not paid the subscription fee.” “If the user has not entered a valid password but has paid the subscription fee, then access is granted.”  Exercises 8. Express these system specifications using the propositions 𝑝 “𝑇ℎ𝑒 𝑢𝑠𝑒𝑟 𝑒𝑛𝑡𝑒𝑟𝑠 𝑎 𝑣𝑎𝑙𝑖𝑑 𝑝𝑎𝑠𝑠𝑤𝑜𝑟𝑑, ” 𝑞 “𝐴𝑐𝑐𝑒𝑠𝑠 𝑖𝑠 𝑔𝑟𝑎𝑛𝑡𝑒𝑑, ” and 𝑟 “𝑇ℎ𝑒 𝑢𝑠𝑒𝑟 ℎ𝑎𝑠 𝑝𝑎𝑖𝑑 𝑡ℎ𝑒 𝑠𝑢𝑏𝑠𝑐𝑟𝑖𝑝𝑡𝑖𝑜𝑛 𝑓𝑒𝑒” and logical connectives (including negations). Sentence Proposition “The user has paid the subscription fee, but does not enter “𝑏ut” means “and”: r ∧ ¬p. a valid password.” “Access is granted whenever the user has paid the “𝑤ℎ𝑒𝑛𝑒𝑣𝑒𝑟” 𝑚𝑒𝑎𝑛𝑠 “𝑖𝑓”: 𝑟 ∧ p →q. subscription fee and enters a valid password.” “Access is denied if the user has not paid the subscription 𝑡ℎ𝑒 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑞 , 𝑠𝑜 𝑤𝑒 ℎ𝑎𝑣𝑒 ∶ ¬𝑟 → ¬𝑞. fee.” “If the user has not entered a valid password but has paid ¬𝑝 ∧ 𝑟 → 𝑞. the subscription fee, then access is granted.”  Exercises 9. Are these system specifications consistent? “The system is in multiuser state if and only if it is operating normally. If the system is operating normally, the kernel is functioning. The kernel is not functioning or the system is in interrupt mode. If the system is not in multiuser state, then it is in interrupt mode. The system is not in interrupt mode.”  Exercises 9. Are these system specifications consistent? “The system is in multiuser state if and only if it is operating normally. If the system is operating normally, the kernel is functioning. The kernel is not functioning or the system is in interrupt mode. If the system is not in multiuser state, then it is in interrupt mode. The system is not in interrupt mode.” The system is in multiuser state p it is operating normally q the kernel is functioning r the system is in interrupt mode s  Exercises 1. The system is in multiuser state if and only if it is operating normally. o𝑝↔𝑞 Both 𝑝 and 𝑞 be 𝑡𝑟𝑢𝑒, or both be 𝑓𝑎𝑙𝑠𝑒. 2. If the system is operating normally, the kernel is functioning. o𝑞→𝑟 Anything except 𝑞 = 𝑡𝑟𝑢𝑒 and 𝑟 = 𝑓𝑎𝑙𝑠𝑒. 3. The kernel is not functioning or the system is in interrupt mode. o ¬𝑟 ∨ 𝑠 𝑟 = 𝑓𝑎𝑙𝑠𝑒, or 𝑠 = 𝑡𝑟𝑢𝑒. 4. If the system is not in multiuser state, then it is in interrupt mode. o ¬p → 𝑠 Anything except 𝑝 = 𝑓𝑎𝑙𝑠𝑒 and 𝑠 = 𝑓𝑎𝑙𝑠𝑒 5. The system is not in interrupt mode. The system is in multiuser state p o ¬𝑠 𝑠 must be 𝑓𝑎𝑙𝑠𝑒 it is operating normally q the kernel is functioning r the system is in interrupt mode s  Exercises [In step 5 and 4] If we set 𝑠 = 𝑓𝑎𝑙𝑠𝑒, then we set 𝑝 = 𝑡𝑟𝑢𝑒. [In step 4 and 3] Since we have 𝑠 = 𝑓𝑎𝑙𝑠𝑒, then we set 𝑟 = 𝑓𝑎𝑙𝑠𝑒. [In step 3 and 2] Since we have 𝑟 = 𝑓𝑎𝑙𝑠𝑒, then we set 𝑞 = 𝑓𝑎𝑙𝑠𝑒. [In step 2, 1, and 4] We have 𝑞 = 𝑓𝑎𝑙𝑠𝑒, but we have 𝑝 = 𝑡𝑟𝑢𝑒 So, these specifications are not consistent  Exercises 44. Find the output of each of these combinatorial circuits.  Exercises 44. Find the output of each of these combinatorial circuits. (¬𝑝) ∨ (¬𝑞). ¬(𝑝 ∨ ((¬𝑝) ∧ 𝑞)))  Exercises 47. Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output ((¬𝑝 ∨ ¬𝑟) ∧ ¬𝑞) ∨ (¬𝑝 ∧ (𝑞 ∨ 𝑟)) from input bits 𝑝, 𝑞, and 𝑟.  Exercises 47. Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output ((¬𝑝 ∨ ¬𝑟) ∧ ¬𝑞) ∨ (¬𝑝 ∧ (𝑞 ∨ 𝑟)) from input bits 𝑝, 𝑞, and 𝑟. TASKS Section 2 2 4 45 46