CSE2133 - Discrete Mathematics¶

Logic and Proofs¶

Term 151¶

Q1(a): Let p, q, and r be the propositions: p: You get an A on the final exam. q: You do every exercise in this book. r: You get an A in this class. Write these propositions using p, q, and r and logical connectives:
To get an A in this class, it is necessary for you to get an A on the final.
You get an A on the final, but you don't do every exercise in this book; nevertheless, you get an A in this class.
Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.
Q1(b): Let p and q be the propositions: p: The election is decided. q: The votes have been counted. Express each of these compound propositions as an English sentence: (i) \(p\to q\); (ii) \(p\leftrightarrow q\); (iii) \(p\oplus q\).
Q1(c): Show that each of these conditional statements is a tautology by using truth tables: (i) \(p\to(p\lor q)\); (ii) \(\neg p\to(p\to q)\); (iii) \((p\land q)\to(p\to q)\).
Q1(d): Define the terms with appropriate examples - "Tautology" and "Contradiction".
Q1(e): Show that \((p\to q)\) and \(\neg p\lor q\) are logically equivalent.
Q3(a): Define and distinguish between universal quantifier and existential quantifier. Briefly discuss about the negation of the quantifiers using example.
Q3(b): Explain predicates and quantifiers with necessary examples.
Q3(c): Convert the following statement into logical expression: (i) Everyone has exactly one best friend. (ii) Every student of your university has a computer or has a friend who has a computer. (iii) If somebody is female and is a parent, then this person is someone's mother.

Term 161¶

Q1(a) [3]: Consider the following propositions: p: You can send an email. q: Your inbox is full. r: New emails are stored in your inbox. Translate the following sentences into logical expressions: (i) You cannot send an email if and only if your inbox is full. (ii) New emails are stored in your inbox unless your inbox is full.
Q1(b) [3]: Consider the following propositions: p: It is raining. q: It is windy. r: The courts are open for play. s: We study today. Translate the following logical expressions into English sentences: (i) \(\neg p\land\neg q\to r\); (ii) \(\neg s\leftrightarrow r\).
Q1(c) [4]: Show that \(p\to(q\to r)\equiv(p\land q)\to r\): (i) using the truth table; (ii) developing a series of logical equivalences.
Q1(d) [4]: Translate each of these statements into logical expressions using predicates, quantifiers and logical connectives: (i) No one is perfect. (ii) Everyone is your friend and is perfect. (iii) One of your friends is perfect. (iv) All of your friends are perfect.
Q3(a) [1+4]: Name the basic methods to prove theorem. Define vacuous proof and trivial proof with example.
Q3(b) [3]: Prove the following statements: (i) If \(3n+2\) is odd, then n is odd. (ii) If n is odd, then \(n^2\) is odd.

Term 171¶

Q1(a) [1+3]: Define logical equivalence. Show that the propositions \(p\lor(q\land r)\) and \((p\lor q)\land(p\lor r)\) are logically equivalent.
Q1(b) [4]: Show that \((p\land q)\to(p\lor q)\) is a tautology.
Q1(c) [4]: Let \(A=\{1,2,3,4,5\}\). Determine the truth value of each of the following statement with explanation: (i) \((\exists x\in A)(x+3=10)\); (ii) \((\forall x\in A)(x+3<10)\); (iii) \((\exists x\in A)(x+3<5)\); (iv) \((\forall x\in A)(x+3<7)\).
Q1(d) [2]: Prove that \(\neg(p\land q)\equiv\neg p\lor\neg q\).

Term 181¶

Q1(a): Define and distinguish between universal quantifier and existential quantifier. Briefly discuss about the negation of the quantifiers using example.
Q1(b): Explain predicates and quantifiers with necessary examples.
Q1(c): Convert the following statement into logical expression: (i) Everyone has exactly one best friend. (ii) Every student of your university has a computer or has a friend who has a computer. (iii) If somebody is female and is a parent, then this person is someone's mother.
Q4(b): State the converse, contrapositive, and inverse of each of the following implications: (i) If it snows tonight, then I will stay at home. (ii) I go out today if it is a sunny summer day.

Term 191¶

Q1(a) [2+2]: Define Discrete mathematics. List out the problems that can be solved using Discrete Mathematics.
Q1(b) [5]: What is proposition? Let p be the statement "Maria learns discrete mathematics." and q the statement "Maria will find a good job." (i) Express \(p\to q\) as a statement in English. (ii) Express \(p\leftrightarrow q\) as a statement in English. (iii) Show the truth table of \(p\to q\) and \(p\leftrightarrow q\).
Q1(c) [3+2]: Define tautology, contradiction and contingency. Show that \(\neg p\lor q\) and \(p\to q\) are logically equivalent.
Q2(b) [3]: Define basic logic operations with example.
Q2(c) [5]: Translate the following English statements into Logical Expressions using predicates and quantifiers: (i) "Some students in the class has visited Cairo". (ii) "Every student in the class has visited either Aswan or Cairo".
Q3(a) [6]: Prove that the argument (in context of tautology) \(p\to q, q\to r\vdash p\to r\) is valid.
Q3(b) [8]: Let \(A=\{1,2,3,4,5\}\). Determine the truth value of each of the following statement with explanation: (i) \((\exists x\in A)(x+3=10)\); (ii) \((\forall x\in A)(x+3<10)\); (iii) \((\exists x\in A)(x+3<5)\); (iv) \((\forall x\in A)(x+3\le7)\).
Q6(b) [4]: Translate these statements into English, where C(x) is "x is a comedian" and F(x) is "x is funny" and the domain consists of all people: (i) \(\forall x(C(x)\land F(x))\); (ii) \(\exists x(C(x)\land F(x))\).

Term 201¶

Q1(a) [5]: Define Proposition and propositional logic. Using truth table show that the propositions \(\neg(p\land q)\) and \(\neg p\lor\neg q\) are logically equivalent.
Q1(c) [4]: Find the converse, contrapositive and inverse of the implication: "If it is holiday, then there are crowd in the shopping mall".
Q3(b) [4]: Let \(A=\{1,2,3,4,5\}\). Determine the truth value of each of the following statement with explanation: (i) \((\exists x\in A)(x+3=10)\); (ii) \((\forall x\in A)(x+3<10)\); (iii) \((\exists x\in A)(x+3<5)\); (iv) \((\forall x\in A)(x+3<7)\).

Term 211¶

Q1(a) [1+2]: Define discrete mathematics. List out the problems that can be solved using discrete mathematics.
Q1(b) [5]: Let p be "It is cold" and let q be "It is raining". Give a simple verbal sentence which describes each of the following propositions: (i) \(\neg p\), (ii) \(p\land q\), (iii) \(p\lor q\), (iv) \(p\to q\), (v) \(p\leftrightarrow q\).
Q1(c) [4+6]: Let p be "Ram reads the Newsweek", let q be "Ram reads the Times", and let r be "Ram reads the Sun". Write each of the following in symbolic form: (i) Ram reads Newsweek or the Sun, but not Times. (ii) Ram reads Newsweek and the Times, or he does not read Newsweek and the Sun. (iii) It is not true that Ram reads Newsweek but not Times.
Q2(a) [1+4]: Define tautology. Verify that the proposition \(p\lor\neg(p\land q)\) is tautology.
Q2(b) [6]: Determine the converse, inverse and contrapositive of the following statement: "If Ram is a poet, then he is poor."
Q2(c) [3]: Write the negation of the statement as simple as possible: If she works, she will earn money.
Q4(a) [6]: Let \(A=\{1,2,3,4,5\}\). Determine the truth value of each of the following statement and explain why: (i) \((\exists x\in A)(x+3=10)\); (ii) \((\forall x\in A)(x+3<10)\); (iii) \((\exists x\in A)(x+3<5)\).