Question 1 Solutions:

For each of the following, write a propositional formula that accurately represents the given English statement. Use the propositions , , , and as needed, where: : “The program compiles.” : “The input is valid.” : “The output is correct.” : “The function is efficient.” : “The algorithm terminates.”

  1. “If the program compiles but the input is not valid, then the output is not correct.”

Solution

  1. Break down the components: “The program compiles”: “The input is not valid”: “The output is not correct”:
  2. Combine using logical operators: “The program compiles but the input is not valid” is “If … then …” translates to     
  1. “The function is efficient if and only if (both the algorithm terminates and the output is correct).”

Solution

or

  1. Break down the components: “The function is efficient”: “The algorithm terminates”: “The output is correct”: “Both … and …” is
  2. Combine using logical operators: “The algorithm terminates and the output is correct” is “If and only if” translates to an implication in both directions, ie.
  1. “((The program compiles and the input is valid) or the function is efficient), and the algorithm does not terminate.”

Solution

  1. Break down the components: “The program compiles”: “The input is valid”: “The function is efficient”: “The algorithm does not terminate”: “And”: , “Or”: , “But”: treated as in context.
  2. Combine using logical operators: “The program compiles and the input is valid” is “The program compiles and the input is valid, or the function is efficient” is “But the algorithm does not terminate” adds
  3. The parentheses are necessary!
  1. “If the program compiles, then ((either the input is valid and the output is correct), or the algorithm does not terminate).”

Solution

  1. Break down the components: “The program compiles”: “The input is valid”: “The output is correct”: “The algorithm does not terminate”: “Either … or …” translates to
  2. Combine using logical operators: “The input is valid and the output is correct” is “Either the input is valid and the output is correct, or the algorithm does not terminate” is “If … then …” translates to   
  1. “The function is efficient if and only if ((the program compiles and the input is valid), or (if the output is correct implies that the algorithm terminates)).”

Solution

  1. Break down the components: “The function is efficient”: “The program compiles”: “The input is valid”: “The output is correct”: “The algorithm terminates”: “If … then …” translates to    , “If and only if” translates to  .
  2. Combine using logical operators: “The program compiles and the input is valid” is “The output is correct implies that the algorithm terminates” is “The function is efficient if and only if” translates to
  3. Combine everything:

Question 2: Negating Propositional Formulae [Graded Participation]

Part A Solutions:

Draw two truth tables to verify that:

  1. is logically equivalent to .
  2. is logically equivalent to .

Hence, and are logically equivalent.

Hence, and are logically equivalent.

Part B Solutions:

To see how these equivalences may be used, let be the statement “It is raining” and let be the statement “It is cold”. Match each of the following statements with its logically equivalent; you might rewrite each statement using and to assist you.

Statements:

  1. It is not the case that it is raining or cold.
  2. It is not raining or it is not cold.
  3. It is not raining and it is not cold.
  4. It is not the case that it is both raining and cold.

Rewriting the 4 statements using and , we get:

Using De Morgan’s Laws, statements 1 and 3 and logically equivalent, and statements 2 and 4 are logically equivalent.

Question 3 Solutions:

Aiken promises Dueet that if Dueet watches anime with him, then Aiken will treat Dueet to a pizza dinner.

a. How would you write this sentence in propositional logic?

Solution

We let the proposition “Dueet watches anime with Aiken” to be and “Aiken treats Dueet to a pizza dinner” to be .

Then we can write this sentence as .

b. Determine whether the promise has been broken in each of the following cases:

  1. Dueet watches anime with Aiken, and Aiken treats Dueet to a pizza dinner.
  2. Dueet watches anime with Aiken, but Aiken does not treat Dueet to a pizza dinner.
  3. Dueet does not watch anime with Aiken, and Aiken treats Dueet to a pizza dinner.
  4. Dueet does not watch anime with Aiken, and Aiken does not treat Dueet to a pizza dinner.

Solution

In the examples we have seen truth tables where different truth values of and lead to a different truth value of . To make sense of this, we can look at this example.

Case 1 definitely doesn’t break the promise. Dueet watches anime, and Aiken keeps his promise. Case 2 breaks the promise because Dueet does his part and watches anime with Aiken, but Aiken didn’t buy pizza like he had promised. Up to now it’s all very intuitive.

Case 4 doesn’t break the promise either; since Dueet didn’t do his part, he gets no pizza. But Case 3 doesn’t break the promise either!

Why is this so? In the notes we said that in an implication, we don’t really care about what happens when the antecedent is false. An implication, or Aiken’s promise, only guarantees what happens when the antecedent is true. If we know is true, we know that will follow through. It doesn’t promise us anything about what happens when the antecedent is false!

Another example would be buying things from a store. You could pay for a soda, and get the soda (Case 1). Or don’t pay for the soda, and leave (Case 4). Or the owner might give it to you as a free gift, and you didn’t pay for the soda (Case 3). The only case that is upsetting is when you pay but you don’t get the soda (Case 2).


Question 4 Solutions:

Let:

  • be the set of circles,
  • be the set of squares,
  • be the set of triangles, and
  • be the set containing all the objects.

You are also given the following predicates, which you may use freely in your answers:

  • is true when object is above object in the grid.
  • is true when object is blue.
  • is true when object is grey.
  • is true when the object is orange.
  • is true when the object is a circle
  • is true when is a square object.
  • is true when is a triangular object.

Determine whether the following statements are true or false for the picture: 5. 6. 7. 8. 9. 10.

Solution:

  1. True; let that object be the orange triangle .

  2. False; consider letting the object be the orange circle .

    • The predicate is true.
    • The predicate is false.
    • But, evaluates to false. Since is stating that: “For every object , if is a circle then is blue”, and we have found a circle that is not blue, the statement is false.
  3. True; no matter which square is picked, we can always find at least one triangle such that lies above in the grid: consider triangle , it is above all squares.

  4. True; no matter which circle and which square are picked from the sets of circles and squares, will lie above in the grid, since all the circles lie above all the squares.

  5. False; no matter which object is picked, we can always find at least circle such that does not lie above , since there is no object that lies above the circle .

  6. True; consider letting the object be the blue circle and letting the object be the grey triangle .

    • The predicate is false.
    • The predicate is false, and so is true.
    • Thus, evaluates to true.

Question 5 Solutions:

Consider the following first order logic statements:

Write the negation for each of the statements.

Part 1 Solutions:

Solution

  1. Put a negation sign outside:
  2. Using negation of an existential quantifier:
  3. Using De Morgan’s Law:

Further

Sometimes we may be confused when we see a bunch of mathematical symbols. It certainly takes time to familiarise yourselves with FOL. When it comes to negating these statements, one way to think about it is to translate it into English.

Statement 1 is an existential statement. What is means, essentially, is that there exists some in set such that both and is true. To negate it, think of the opposite.

If there exists NO in set such that and are both true, this means that for ALL in set , it either does not satisfy , or it doesn’t satisfy . There is just no that satisfies both at the same time.

And how would we then write this into FOL? We would write .

Part 2 Solutions:

Solution

  1. Put a negation sign outside:
  2. Using negation of an existential quantifier:
  3. Using De Morgan’s Law:

Further

Statement 2 is a universal statement that says: Every in set satisfies or (or both), either one of them is fine. To negate it, think of the opposite.

NOT every in set satisfies at least one of or . This means that there exists one (or more) that does not satisfy both and .

And then we write this into FOL, .

Part 3 Solutions:

Solution

  1. Put a negation sign outside:

  2. Using negation of a universal quantifier:

  3. Using negation of an existential quantifier:

  4. Using De Morgan’s Law:

Further

Statement 3 is a little more complex. What it means is that for every in set , there exists some corresponding in set , such that both and are true. To negate this, think of the opposite.

NOT every in set has some corresponding in set such that both and are true. This means that there should exist (at least one) in set where you CANNOT find any in set such that both and are true. In other words, there exists in set where for ALL in set , and are not true at the same time (ie. at least one of them is not true), so either is not true, or is not true, or both.

Now we just write this into FOL. There exists in set where for all in set , either is not true, or is not true. Thus we write .

Part 4 Solutions:

Solution

  1. Put a negative sign outside:

  2. Using negation of an existential quantifier:

  3. Using negation of a universal quantifier:

  4. Using implication law: , we replace with , thus we write: .

  5. Using De Morgan’s Law:

  6. Double negation: , thus we get .

Further

After looking at the statement 3, this one should make more sense. What this statement means is that there exists some in set where for all in set , is true. To negate this, think of the opposite.

If there exists NO in set where for every in set satisfies , it means that for every in set , there has to exist some in set that doesn’t satisfy , which means that is false.

To negate an implication, we use implication law to turn it into something we can work with. So we replace with , and then negate it, which gives us . Then we use De Morgan’s Law to further simplify into .

In other words, for every in set , there exists some in set , such that . Now we just have to translate this into FOL, and we have .


Question 6 Solutions:

Part A Solutions:

  1. (True)

Explanation

This is a practice on negating multiple quantifiers in the same statement.

  1. (Negation of universal quantifier)
  2. (Negation of existential quantifier)
  3. (Negation of equals)

Deciphering the statement: This statement says that every natural number, is equal to some integer. We know this to be intuitively true, by the definition of the sets of and .

  1. (False)

Explanation

This is a practice on negating multiple objects in the same quantifier.

  1. (Negation of universal quantifier)
  2. (Negation of equals)

Deciphering the statement: This statement says any 2 rational numbers are equal. We know this to be false.

  1. (False)

Explanation

This is a practice on applying De Morgan’s Law.

  1. (Negation of universal quantifier)
  2. (De Morgan’s Law and negation of equals)

Deciphering the statement: This statement says when you pick any 3 integers, one of the integers you picked will be equal to one of the other 2 integers.

This is false.

  1. (True)

Explanation

This is another practice on applying De Morgan’s Law, but with a little more complexity.

  1. (Negation of universal quantifier)
  2. (Negation of existential quantifier)
  3. (De Morgan’s Law and negation of equals)

Deciphering the statement: This statement is a little tricker to unpack. It says that every integer, is 3 times of some rational number, and 5 times of another rational number.

This is true, as for any integer , and , and we know that and are rational numbers.

  1. (False)

Explanation

This is an example of when negating a statement can make it easier to understand.

  1. (Negation of existential quantifier)
  2. (Negation of universal quantifier)
  3. (Negation of equals)

Deciphering the statement: This statement is not so easy to intuitively determine if it is true just by looking at the original statement, so we will instead consider the negation.

The negation says, any 2 integers added together is equal to another integer.

We know this to be true. Therefore, the original statement must be false.

In contrast, the original says, there are 2 integers that are not equal to any integer when added together. Not that it is impossible to tell this is false, but consider how much easier negating the statement made it to digest the statement.

  1. (False)

Explanation

This is a practice on negating implication statements.

  1. (Negation of universal quantifier)
  2. (Substitute with a logically equivalent proposition)

Deciphering the statement: This statement says if the squares of 2 integers are equal, the 2 integers are also equal.

This is false as the square of a number and its negative counterpart are equal.

Important to note is the use of a commonly used logical equivalence to substitute away the implication connective, as that is the easiest way to negate them.

Part B Solutions:

  1. (True)

Explanation

This is a practice on finding the contrapositive of a simple implication statement.

  1. (Substitution of contrapositive form)

Deciphering the statement: This statement says if the squares of 2 integers are not equal, the 2 integers are also not equal.

This might be tricky to justify, so let’s consider the contrapositive.

The contrapositive says that if 2 integers are equal, the squares of the 2 integers are also equal.

Ah, this is significantly easier to justify and imagine.

The contrapositive is thus true, making the original statement true.

  1. (True)

Explanation

This is a practice on finding the contrapositive of an implication statement with connectives.

  1. (Substitution of contrapositive form)
  2. (De Morgan’s Law)

Deciphering the statement: This statement says that any integer more than 5 and less than equal to 26 must be more than equal to 0.

This statement is true.

Technique of note in this question is the use of De Morgan’s Law even when finding a contrapositive.

  1. (True)

Explanation

This is a practice on finding the contrapositive of an implication statement with quantifiers.

  1. (Substitution of contrapositive form)
  2. (Negation of universal quantifier)
  3. (Negation of equals)

Deciphering the statement: This statement says that any integer and any natural number, if the numbers are not equal, the integer is less than or equal to 5.

This statement is quite confusing to even approach from this angle, so let’s consider the contrapositive.

The contrapositive says that any integer greater than 5 has a natural number equal to it.

Again, this is significantly easier to justify and digest.

The contrapositive is thus true, making the original statement true.


Question 7 Solutions [Graded Participation]:

Prove the following statement:

Theorem

Where we define the predicate to be: , and we define the predicate to be:

Solution

Proof:

  1. Let , arbitrarily chosen.
  2. Assume for the sake of contradiction that .
  3. . [Specialisation on line 2]
  4. . [Unpacking definition of ]
  5. Let be such that . [Existential instantiation on line 2.2]
  6. . [Specialisation on line 2]
  7. . [Unpacking definition of ]
  8. Let be such that . [Existential instantiation on line 2.5]
  9. Then, we have . [Basic algebra, from lines 2.3 and 2.6]
  10. . [Basic algebra]
  11. . [Basic algebra]
  12. . [Basic algebra, from line 2.9]
  13. Since and , we have . [Basic algebra, from lines 2.3 and 2.6]
  14. . [Conjunction on lines 2.10 and 2.11]
  15. . [Contradiction rule on line 2.12]
  16. . [Proof by contradiction rule on line 2.13]
  17. . [Universal generalisation on lines 1 and 3]

Question 8:

You are tasked with building a load balancer that services clients, and has to balance them between servers. All clients will request to be serviced at the same time at the start of the day, and the load balancer must assign each client a server immediately at the start of the day.

Your boss tells you to keep costs down, that each server must service less than clients in total. Let be the number of clients that the server has to service. e.g., is the number of clients for the first server, is the number of clients for the second server, and so on. Since we have servers, we have quantities .

Question: Prove to yourself and your boss that this is impossible.

Solution:

Before we begin the proof, let’s formalise what the question wants us to prove. We need to show that the following statement is true:

Given such that , and the set (refer to Common Sets for Numbers for an explanation of this notation),

Essentially, that it is impossible (indicated by the "" symbol) for all servers to service fewer than clients. Now that we have a concrete statement down, we can continue proving it:

Solution

Proof:

  1. Let , arbitrarily chosen, be such that .
  2. Assume for the sake of contradiction that .
  3. Then, we must have that , , , . [Universal instantiation on line 2.1]
  4. . Rewriting this (for presentation’s sake), we have . [Basic algebra]
  5. In particular, . [Basic algebra]
  6. . [Conjunction on lines 1 and 2.3]
  7. . [Contradiction rule on line 2.4]
  8. . [Proof by contradiction rule on line 2.5]
  9. Therefore, [Universal generalisation on lines 1 and 3]

Thus, such a task is impossible.