Discrete Mathematics :Predicate Logic Assignment

1. Let the following predicates be given. The domain is all cars. 

F(x) = “x is fast” 

S(x) = “x is a sport car” 

E(x) = “x is expensive” 

A(x, y) = “x is safer than y” 

(a) Write the following statements in predicate logic. 

• All sports cars are fast.  
• There are fast cars that aren’t sports cars.
• Every fast car is expensive. 

(b) Write the following predicate logic statement in everyday english. Do not just give a word-for-word translation. 

(c) Formally negate the statement from part (b). Simplify your negation so that no quantifier or connective lies within the scope of a negation. State which derivation rules you are using.  

(d) Give a translation of your negated statement in everyday English.  

2. Consider the following definitions. 

Definition. An integer n is alphic if n = 4k + 1 for some integer k. 

Definition. An integer n is gammic if n = 4k + 3 for some integer k. 

a) Show that 19 is gammic. 

b) Suppose that x is alphic and y is gammic. Prove that x + y is even.

c) Prove by contraposition: If x is not odd, then x is not alphic.

3. Show that the following hypotheses are inconsistent (False). 

i) If Simon misses many lectures this semester then he fails this course.

ii) If Simon fails this course then he needs to repeat this course again. 

iii) If Simon does a lot of extra exercises then he will not repeat this course again.

iv) Simon misses many lectures this semester and does a lot of extra exercises.                                                                                                              

4. A technician suspects that one or more of the processors in a distributed system is not working properly. The processors, A, B, and C, are all capable of reporting information about the status (working or not working) of the processors in the system. The technician is unsure whether a processor is really not working, or whether the problem is in the status reporting routines in one or more of the processors. After polling each processor, the technician receives the following status reports. 

(a) Processor A reports that processor B is not working and processor C is working.

(b) Processor B reports that A is working if and only if B is working. 

(c) Processor C reports that at least one of the other two processors is not working. Help the technician by answering the following questions. 

• Assuming that all of the status reports are true, which processor(s) is/are working. 
• Assuming that all of the processors are working, which status report(s) is/are false.
• Assuming that a processor’s status report is true if and only if the processor is working, what is the status of each processor.

5. Write a proof for the following assertion and justify each step. 

6. Consider the following recurrence relation: 

7. If A and B are sets, show that 

(a) showing each side is a subset of the other side.

(b) membership table.