A menu driven program which revolves around various Conjuctures ! written by me and Abdul Moeed (bscs18056@itu.edu.pk)
PART 1 Problem 1 Write a function bool isPrime(int N), to check whether a given number N is prime or not. Your program should run in such a way that it should only try 2 and then all odd numbers and to the limit of N/2. Now Compare it within the limit of SQRT(N). Test the execution time on the following number for both implementations. Write a function to check whether P(N) = n2+ n + 41 is prime or not? Write a main program for testing if the above function(c) fails for any value n? Write the code for FINDTwinPrime , and it should return two prime numbers(a pair of two consecutive odd numbers).
Problem 2 Write a proposition function which on given values a, b, c, and d compute if Euler's Conjecture a4+ b4+ c4= d4 fails? Write a program (main) which should test if there exists a 4 tuple on which the above proposition functions returns TRUE, within integer(32 bit) range?
Problem 3 Write a function which should test for a given triplet if it satisfies the Elliptic Curve Conjecture 313(a3+ b3) = c3. Write a program (main) which should test if there exists a 3 tuple(of positive integers) on which the above proposition functions returns true. How much time did it take for testing all the possibilities of integers? Goldbach Conjecture states that every even integer greater than 2 can be written as sum of two prime numbers. Write the code for Goldbach conjecture Test on random 10 big even integers such that they can be represented as a summation of two primes. Write output of the numbers in your submission. Write the code for 3n+1 conjecture and verify on 10 huge numbers and your submission should print its trail of shrinking to 1.
Problem 4 (Puzzle of Knights and Knaves) On an island, there live two types of people: KNIGHTS, who always tell the truth, and KNAVES, who always lie. You visit the island and meet two natives, who speak to you as follows: A says: B is knight B says: A and I are of opposite type. What are A and B? (they might be both of the same type or different) Describe how you reach your answer. You may use any method to solve the problem.
Problem 5 In the back of an old cupboard, you discover a note signed by a pirate, who has studied Discrete Structures and loves logical puzzles. In the note he wrote, he had hidden a treasure somewhere in this big house. He listed five TRUE statements. Based on these, find out the location of treasure. If the house is next to the lake, the treasure is not in the kitchen. If the tree in the front yard is an elm, then the treasure is in the kitchen. The house is next to the lake. The tree in the front yard is an elm or the treasure is buried under the flagpole. If the tree in the backyard is an oak, then the treasure is in the garage. Where is the treasure? Describe how have you figure out?
PART 2
Problem 6
Construct a truth table for each of these compound propositions)
p → (¬q ∨ r) ii) (p → q) ∧ (¬p → r)
Evaluate(describe with reason if the given claim is correct or not) the following propositions:
If x is divisible by 150 then it is either a multiple of 90 or 30.
If x*y=0, either x=0 or y=0.
If Islamabad is the Capital of Pakistan and Faisal Mosque is the largest mosque in the world then Capital of Pakistan has the world’s largest mosque.
Problem 7 Write negation of following statements. Hint: Try to separately write p and q: He never comes on time in summer. Amina’s favourite food is halwa puri and her least favourite drink is lassi. Jamil will come to class if he wakes up on time. x=3, y=0,z=10 implies xyz=0. If x*y=0, either x=0 or y=0.
Problem 8 Let p, q, and r be the propositions p : You get an A on the final exam. q : You do every assignment. r : You get an A in this class. Write the following propositions using p, q, and r and logical connectives (including negations). a) You get an A in this class, but you do not do every assignment. b) You get an A on the final, you do every assignment, and you get an A in this class. c) To get an A in this class, it is necessary for you to get an A on the final. d) You get an A on the final, but you don’t do every assignment; nevertheless, you get an A in this class. e) Getting an A on the final and doing every assignment is sufficient for getting an A in this class.
Problem 9 Write the inverse, converse and contrapositive of the following statements (in English). Hint: It will help to separately write p and q. It is important to note that inverse of p -> q is never equal to its contraposition Pakistan will win the match if they bat all 50 overs. Winning the match against Bangladesh is sufficient for Pakistan to qualify for semi final. It is necessary to do all the assignments in Discrete Structures to understand the material well.
Problem 10 The binary logical connectors ∧ (and), ∨(or) and → (implies) often occur in computer programs. In chip design, however, it is considerably easier to construct them out of another operation nand which is simple to represent in a circuit. Truth table for nand Is given below: p q P nand q
Represent the following expressions only using ¬ (negation) and nand and appropriately placed parentheses. Use can use p and q any number of times. p ∧ q p ∨ q