soen331a1

SOEN 331: Assignment 1 Adrienne Digo(40058646) Flora Avakian(40158192) Rose Rutherford-Stone(27062516) Due: October 14, 2021 Problem 1. Question 4.1. Propositional Logic You are shown a set of four cards placed on a table, each of which has a letter on one side and a symbol on the other side. The visible faces of the cards show the letters L and A, and the symbols 2 , and 3 . Which card(s) must you turn over in order to test the truth of the proposition that “If a card has an consonant on one side, then it has the symbol 3 on the other side” Solution. Question 4.1. The proposition can be rewritten as consonant → 3 . This statement will only ever be false if the card face shows a vowel, and the other side shows a 3 . First, we should check the card L. Using modus ponens we get: consonant → 3 consonant ∴ 3 So, if we turn over a card which has a consonant (L), we should see a diamond, otherwise the proposition is false. Next, we would flip over the 2 . Using modus tollens (where ¬ consonant is vowel and ¬ 3 is 2 ): consonant → 3 2 ∴ vowel So, if we flip over a square we would expect to see a vowel. We do not need to flip over the 3 card or the A card. Flipping over the 3 card would give us no information as this would be a converse error: consonant → 3 3 ∴ consonant This is a fallacy and cannot be used as evidence to prove consonant → 3 . Flipping over the A card would also not give any information as it would be an inverse error. consonant → 3 vowel ∴ 2 This would be a fallacy and cannot be using to prove consonant → 3 . So, in summary L and 2 must be turned over, A and 3 do not need to be. Problem 2. Question 4.2 In the domain of all people, consider the predicate disclosed(a, b) that is interpreted as “a has disclosed a secret to b.” 1. How are the following two expressions translated into plain English? Are the two expressions logically equivalent? • ∀ a ∃ b disclosed(a,b). 1

• ∃ b ∀ a disclosed(a,b). 2. Can we claim that ∀ a ∃ b disclosed(a,b) → ∃ b ∀ a disclosed(a,b)? 3. Can we claim that ∃ b ∀ a disclosed(a,b) → ∀ a ∃ b disclosed(a,b)? Solution. Question 4.2 1. In plain English, the first expression reads: “Every a has disclosed a secret to at least one b ”. The second expression reads: “There is some b who has had a secret disclosed to from every a ”. The two expressions are not logically equivalent. In the first expression, b can be different for each a but in the second expression, b must work for all a . Logical equivalence occurs when p ⇐⇒ q is a tautology. This is not the case and is thus not logically equivalent. 2. No. Suppose ∀ a ∃ b disclosed(a, b) is true. This means that for all a , disclosed(a,b) is true for some b . Let G ( a ) be the set of elements b , where b ∈ disclosed(a,b). Let m be a point where m ∈ disclosed(m,b). Let G ( m ) be the set of elements b in which we are satisfying disclosed(a,b) with point m . ∀ a ∃ b disclosed(a, b) tells us that for every point m , the sets G ( m ) can result in two cases: (i) intersection is an ∅ or, (ii) at least one shared element b. In the first case, ∀ a ∃ b disclosed(a, b) holds true. It is not true however for ∃ b ∀ a disclosed(a, b). The intersection of all G ( m ) s must contain at least one shared b since there is some b in which all a has disclosed a secret to it. 3. Yes. Using the same logic as the previous answer: Suppose ∃ b ∀ a disclosed(a, b) is true. This means that for some b , disclosed(a,b) is true for all a . Let G ( a ) be the set of elements b , where b ∈ disclosed(a,b). Let m be a point where m ∈ disclosed(m,b). Let G ( m ) be the set of elements b in which we are satisfying disclosed(a,b) with point m . ∃ b ∀ a disclosed(a, b) tells us that for every point m , G ( m ) is not empty. This is also true for ∀ a ∃ b disclosed(a, b) since there is some b ∈ G ( m ) for all m . Problem 3. Question 4.3 Consider the subject “x is a person” and the predicate “x is mortal”, together with the following list of categorical propositions: • “No person is immortal.” • “All people are immortal.” • “Some people are mortal.” • “Some people are not mortal.” 1. Identify each categorical statement with its name (i.e. letter description). 2. Identify universal statements. 3. Identify particular statements. 4. Identify affirmative statements. 5. Identify negative statements. 6. Identify statements with opposite truth values. 7. Identify statements that cannot both be true, but could both be false. 8. Identify statements that cannot both be false but could both be true. 9. Identify pairs of super-subaltern statements. Solution. Question 4.3 2

Problem 5. Question 4.5 Consider the sets: • Laptop = { Apple,IBM ,Sony,HP,Acer,Dell,LG } • Favorite = { Apple,Sony,Dell } Answer the following questions: 1. How do we interpret the expression Favorite : P Laptop? 2. Is P Laptop a legitimate type? 3. What is the nature of the variable in Favorite : P Laptop? (i.e. Atomic or composite? If composite, what type?) 4. Is Apple ∈ P Laptop? Explain why or why not 5. Is { Apple } ∈ P Laptop? Explain why or why not 6. Is {{}} ∈ P Laptop? Explain why or why not 7. Is {} ∈ P Laptop? Explain why or why not 8. If we define variable Favorite : P Laptop, is {} a legitimate value for variable Favorite? Explain why or why not 9. Is Favorite ∈ P Laptop? Explain. 10. Is Favorite ⊂ P Laptop? Explain. Solution. Question 4.5 1. It is interpreted as “The variable Favorite can assume any value supported by the powerset of Laptop .” 2. Yes, the power set of Laptop is a legitimate type because it is a set that contains all subsets of Laptop including the empty set. 3. The nature of the variable in Favorite is composite and it is of type set. 4. No, Apple isn’t an element of the power set Laptop because Apple is not a subset of Laptop since it is not defined inside braces. 5. Yes, { Apple } belongs to P Laptop because a power set contains all subsets of a given set and { Apple } is a subset of Laptop. 6. No, {{}} doesn’t belong to the power set Laptop because an empty set including an empty set cannot be an element of this set. 7. Yes, {} is an element of P Laptop because an empty set is an element of all sets. 8. Yes, because the empty set is a valid set and is a subset of all sets. 9. Yes, Favorite is an element of the power set Laptop because Favorite is a set that contains elements of Laptop . 10. No, because Favorite is not a subset P Laptop . Problem 6. Question 4.6 Consider a system that assigns id’s to locations. An id may represent a vehicle in a parking lot, a train in a station, a process in an operating system etc. A location may represent a parking spot, a train station platform, a core in a hardware system etc. The requirements of the system are as follows: 4

1. ID’s are unique. 2. An id is assigned to a single location (and maybe reassigned subsequently). 3. No multiple id’s may be assigned to the same location The model of the system is captured by a relation assignment, which is represented as a set as shown below: assignment = { 001 7→ A , 002 7→ B , 003 7→ C , } 1. Define the precondition to operation add, that assigns a new id to a location. 2. Provide two alternative definitions for the main functionality of the operation. 3. What would be the result of calling the operation with id? = 001, and location? = D? 4. Let us get rid of the precondition. What would be the result of calling add with id? = 004, and location? = C? Would you accept or reject the call? If accepted then the pair should be added to the relation. If rejected, it should not be added to the relation. 5. Assume that in the absence of a precondition, we attempted to call operation add with some input parameters id? and location?. Under what conditions, if any, would this be acceptable? 6. Consider operation reassign that modifies the location of an existing id. Define the precondition to operation reassign. 7. Define the body of operation reassign. Solution. Question 4.6 1. id? : id location? : location id ? / ∈ dom assignment location ? ∈ ran assignment 2. The two definitions for the main functionality of the operation are the following : assignment 0 = assignemnt ⊕ { id ? 7→ location ? } assignment 0 = assignemnt ∪ { id ? 7→ location ? } 3. The result would lead to a violation of requirements since no multiple id’s may be assigned to the same location. It is no longer a proper function since two unique ids are mapped to two elements in the co domain. We thus reject and will not be added. 4. For basic specification, it may ignore the incorrect input or may break down. But, we can define a schema that describes the errors, its condition for which the error occurs, and an appropriate error message. For example, in this case, we can create a schema IDExists which specifies that the id already exists in the domain and can display a message such as ” ID already exists! ”. 5

4. Given the following expression { mate 10 pro , iPhoneSE , galaxyJ 2 Core } - C cellphones (a) What is the meaning of the operator - C ? (b) What is the value of the expression? (c) Where would deploy such operator in the context of a database management system? 5. Given the following expression cellphones - B { apple , xiaomi } (a) What is the meaning of the operator - B ? (b) What is the value of the expression? (c) Where would deploy such operator in the context of a database management system? 6. Consider the following expression: cellphones ⊕ { galaxyA 51 7→ samsung , mate 9 7→ huawei } (a) What is the meaning of the operator ⊕ ? (b) What is the value of the expression? (c) Where would deploy such operator in the context of a database management system? (d) Does the result of the expression have a permanent effect on the database (relation)? If not, describe in detail how would you ensure that such operation would have a permanent effect. Solution. Question 4.7 1. (a) The domain is defined as : dom cellphones = { galaxyA 21 s , mate 10 , mate 10 pro , galaxyA 01 , iPhone 12 ProMax , iPhoneSE , galaxyJ 2 Core , redmi 6 A , redmi 8 } (b) The range is defined as: ran cellephones = { samsung , huawei , apple , xiaomi } . 2. (a) Domain restriction selects pairs based on their first element. (b) The value of this expression will be { galaxyA 01 , galaxyJ 2 Core , redmi 8 } cellphones = { galaxyA 01 7→ samsungl , galaxyJ 2 Core 7→ samung , redmi 8 7→ xiaomi , } (c) The operator is deployed to model database queries. 7

3. (a) Range restriction selects pairs based on their second element. (b) The value of this expression will be cellphones { samsung , xiaomi } = { galaxyA 21 s 7→ samsung , galaxyA 01 7→ samsung , galaxyJ 2 Core 7→ samsung , redmi 6 A 7→ xiaomi , redmi 8 7→ xiaomi , } (c) The operator is deployed to model database queries. 4. (a) Domain subtraction removes elements from the domain of the relation. (b) The value of this expression will be { mate 10 pro , iPhoneSE , galaxyJ 2 Core } - C cellphones = { galaxyA 21 s 7→ samsung , mate 10 7→ huawei , galaxyA 01 7→ samsung , IPhone 12 ProMax 7→ apple , redmi 6 A 7→ xiaomi redmi 8 7→ xiaomi } (c) The operator is deployed to model deletion of records. 5. (a) Range subtraction removes elements from the codomain of the relation. (b) The value of this expression will be cellphones - B { apple , xiaomi } = { galaxyA 21 s 7→ samsung , mate 10 7→ huawei , mate 10 pro 7→ huawei , galaxyA 01 7→ samsung , galaxyJ 2 Core 7→ samsung , } (c) The operator is deployed to model database updates (deletion of records). 6. (a) Relational overriding can model database updates (addition of records). (b) The result is 8