University Discrete Mathematics — Propositional and Predicate Logic Worksheet

All 15 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1Propositions and Logical Connectives

   Decide which of the following are propositions. For each one that is, give its truth value; for each one that is not, say why.

   1. $2^{10}<1000$.
   2. $x+3=10$.
   3. Every integer greater than $1$ has a prime divisor.
   4. Is $91$ a prime number?
   5. $91$ is a prime number.
   6. Close the window before you leave.
2. Q2Propositions and Logical Connectives

   Let $p$ be “the train is late”, $q$ be “Mila takes the bus” and $r$ be “Mila arrives before 9:00”. Write each sentence in symbols.

   1. The train is late and Mila does not take the bus.
   2. Mila arrives before 9:00 only if she takes the bus.
   3. Mila takes the bus unless the train is late.
   4. Either the train is late or Mila arrives before 9:00, but not both.

   Then write $(q\wedge \neg p)\to r$ as an English sentence.

3. Q3Truth Tables

   Construct the truth table of $(p\vee q)\to (\neg p\wedge r)$ and classify the proposition as a tautology, a contradiction or a contingency.

4. Q4Conditional Statements, Converse and Contrapositive

   Consider the statement “For every integer $n$, if $n$ is divisible by $6$, then $n$ is divisible by $3$.” Write the converse, the inverse and the contrapositive of the conditional inside it (each still for every integer $n$), and decide which of the four statements are true. Give a counterexample for each false one.

5. Q5Conditional Statements, Converse and Contrapositive

   Suppose $p$ is true, $q$ is false and $r$ is true. Find the truth value of each proposition.

   1. $(p\to q)\to r$
   2. $(q\to p)\wedge (r\to q)$
   3. $\neg p\to (q\leftrightarrow r)$
6. Q6Logical Equivalences and De Morgan's Laws
   1. Use De Morgan's laws to write the negation of “The file is encrypted and the file is backed up” and of “Jonah is in the lab or Jonah is at the library”, without the words “it is not the case that”.
   2. Use De Morgan's laws and double negation to rewrite $\neg (\neg p\wedge (q\vee \neg r))$ as an equivalent proposition in which $\neg$ is applied only to single variables.
7. Q7Logical Equivalences and De Morgan's Laws

   Use a truth table to decide whether $p\to (q\to r)$ and $(p\to q)\to r$ are logically equivalent. If they are not, list every row in which they differ.

8. Q8Predicates and Quantifiers

   The domain is the climbers at a climbing gym. Let $L(x)$ be “$x$ climbs lead” and $C(x)$ be “$x$ is certified to belay”. Write each sentence in symbols.

   1. Every climber who climbs lead is certified to belay.
   2. Some climber who is certified to belay does not climb lead.
   3. No climber climbs lead.

   Then write $\exists x(L(x)\wedge \neg C(x))$ as an English sentence.

9. Q9Predicates and Quantifiers

   Let $P(x)$ be the predicate “$x^2>2x$”.

   1. Find the truth values of $P(0)$, $P(3)$, $P(-1)$ and $P(2)$.
   2. Find the truth values of $\forall x\in \mathbb{Z},P(x)$ and of $\exists x\in \mathbb{Z},P(x)$.
   3. Find the truth value of $\forall x\in D,P(x)$, where $D=\{x\in \mathbb{Z}\mid x\ge 3\}$, and justify it.
10. Q10Negating Quantified Statements

    Write the negation of each statement so that no $\neg$ stands in front of a quantifier or a bracket. Then decide whether the original or its negation is true, with a one-line reason.

    1. $\forall x\in ℝ,(x>0\to x^2>x)$
    2. $\exists n\in \mathbb{Z},n^2=n+1$
    3. $\exists x\in \mathbb{N},(x\text{ is even}\wedge x\text{ is prime})$, where $\mathbb{N}=\{0,1,2,\dots \}$
11. Q11Negating Quantified Statements

    Write the negation of each sentence in natural English, without the words “it is not the case that”.

    1. Every bus on this route arrives on time.
    2. Some password in the file is shorter than 8 characters and contains no digit.
    3. No student in the class submitted the assignment late.
12. Q12Nested Quantifiers

    The domain of every variable is $\mathbb{Z}$. Find the truth value of each statement, with a one-line reason.

    1. $\forall x\exists y,x+y=0$
    2. $\exists y\forall x,x+y=x$
    3. $\forall x\exists y,2y=x$
    4. $\exists x\forall y,x\le y$
13. Q13Rules of Inference and Valid Arguments

    For each argument, write its form in symbols and name the rule of inference it uses, or say that it is not valid.

    1. If the reactor temperature exceeds 300 degrees, the alarm sounds. The alarm did not sound. Therefore the temperature did not exceed 300 degrees.
    2. Kofi is in Toronto or Kofi is in Ottawa. Kofi is not in Toronto. Therefore Kofi is in Ottawa.
    3. If an integer is divisible by 9, it is divisible by 3. The integer 51 is divisible by 3. Therefore 51 is divisible by 9.
    4. If the meeting runs late, Inès misses the ferry. If Inès misses the ferry, she takes a taxi. Therefore, if the meeting runs late, Inès takes a taxi.
14. Q14Rules of Inference and Valid Arguments

    Decide whether the argument with premises $p\to q$, $q\vee r$, $\neg r$ and conclusion $p$ is valid. If it is not, give an assignment of truth values that shows it.

15. Q15Synthesis — drawing on several topics in this unit

    The domain is ${\mathbb{Z}}^{+}$, the positive integers. Let $P(n)$ be “$n$ is prime” and let $S$ be the statement $$\forall n\in {\mathbb{Z}}^{+},(P(n)\to P(n+2)).$$

    1. Write the negation of $S$ with no $\neg$ in front of a quantifier or a bracket.
    2. Decide which of $S$ and its negation is true, and give a witness or a counterexample.
    3. Write the contrapositive of the conditional inside $S$ as an English sentence.

The 11 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

What is a proposition, and what the connectives mean

A proposition asserts something, and it carries exactly one truth value, true or false, even if nobody present knows which. Q1 asks you to sort six sentences by that test and, for the ones that pass, to give the truth value; for the ones that fail, a reason is part of the answer, not an afterthought.

"Nobody knows the answer" is never a reason for failing the test, and "I would have to compute it" is not either. A statement about a specific number is a proposition whether or not the arithmetic has been done; the work of settling it is the answer, not the classification.

Translating English into symbols

Q2 fixes three simple propositions p, q and r and asks for four English sentences in symbols, then for one symbolic formula back in English. Translation is the skill this whole chapter is graded on, and it turns on a handful of phrases that do not mean what their word order suggests.

The last part of Q2 runs the translation the other way, turning (q ∧ ¬p) → r into a sentence. Going back to English means writing something a person would say, so replace the letters by their sentences, render ∧ with "and", ¬ by negating the clause naturally, and make the arrow an "if … then" — then read it aloud and check that it still says what the formula says.

Truth tables, built and then read

Q3 asks for the full truth table of (p ∨ q) → (¬p ∧ r) and for a classification of the result as a tautology, a contradiction or a contingency. Three variables mean 2³ = 8 rows, and the table is only as reliable as its bookkeeping.

Converse, inverse and contrapositive

Q4 takes one conditional about integers — if n is divisible by 6, then n is divisible by 3 — and asks for its converse, its inverse and its contrapositive, each still quantified over every integer n, and then for a decision about all four statements with a counterexample for each false one.

A counterexample to a statement of the form "for every integer n, if … then …" is a single specific integer that makes the hypothesis true and the conclusion false. An integer that fails the hypothesis proves nothing, because the conditional is automatically true there. Produce the number and show both halves — that it satisfies the "if" and fails the "then".

Q5 is the same connectives under a fixed assignment: p true, q false, r true, and three compound propositions to evaluate. Work strictly from the inside out, writing the value of each bracket above it before combining. A biconditional A ↔ B is true exactly when the two sides have the same truth value, which is quicker to check than to build a table for.

Logical equivalences and De Morgan's laws

De Morgan's laws say how a negation moves across a conjunction or a disjunction, and moving a negation inwards is what turns an unreadable negative sentence into a usable one.

Q6(a) does this in English on two sentences, and the instruction is strict: the phrase "it is not the case that" is banned, so the negation has to be a sentence someone would actually say. Negate each clause in plain words first — an encrypted file becomes a file that is not encrypted — then join the two with whichever of "and" or "or" the law hands you. Q6(b) does it in symbols on ¬(¬p ∧ (q ∨ ¬r)), where the requirement is that ¬ ends up in front of single variables only. Apply the law to the outer bracket first, then to whatever bracket the result exposes, and clear every double negation as it appears.

Q7 compares p → (q → r) with (p → q) → r by truth table and, if they are not equivalent, asks for every row in which they differ. Two formulas are logically equivalent exactly when their final columns agree in every row, so the comparison is a row-by-row reading and nothing else. The differing rows are the answer, so record the values of p, q and r for each one rather than just counting them.

Predicates, domains and the two quantifiers

A predicate becomes a proposition when its variable is bound. ∀x P(x) claims P holds for every member of the domain; ∃x P(x) claims at least one member satisfies it. The domain belongs to the statement itself rather than to the scenery: one and the same predicate can be universally true over one domain and false over another.

Q8 sets the domain to the climbers at a gym with two predicates, L(x) and C(x), and asks for three sentences in symbols and one formula back in English. The three sentences are the three standard shapes, and each has a pairing that has to be respected.

The last part of Q8 turns ∃x (L(x) ∧ ¬C(x)) into English. Say "there is a climber who …", and keep the domain implicit in the noun rather than adding a clause for it.

Q9 works with the predicate x² > 2x. Part (a) substitutes four specific values, so each one becomes an arithmetic comparison to be checked and reported as true or false. Part (b) quantifies over the integers, and here the two quantifiers need two different kinds of evidence. Part (c) restricts the domain to the integers that are at least 3 and demands a justification, which means an argument covering every such integer at once — rearrange the inequality into a form where the hypothesis x ≥ 3 visibly forces it, rather than testing a few values and stopping.

Negating a quantified statement

Negation is mechanical once you know the two rules, and Q10 asks for negations in which no ¬ is left standing in front of a quantifier or a bracket — so the negation has to be pushed all the way in.

Push from the outside in, one step at a time: swap each quantifier as the negation passes it, then use De Morgan on any ∧ or ∨ and the implication rule on any arrow, then simplify negated comparisons — the negation of > is ≤, and the negation of = is ≠. Note that the negation of an implication is a conjunction with no arrow left in it at all, which is what makes negated conditionals feel so different from their originals.

Q10 then asks you to decide whether the original or the negation is true, with a one-line reason. Exactly one of the two is true, so the decision is really the choice of which one you can support: a witness for whichever of the pair is existential, or a short general argument for whichever is universal. The domain differs from part to part — the reals, the integers, the natural numbers starting at 0 — and the answer can turn on it, so read it each time.

Q11 is the same operation in natural English, again without "it is not the case that". Identify the quantifier hiding in the sentence — "every", "some", "no" — swap it, and negate the property. "Every bus arrives on time" becomes a claim about at least one bus; "no student did X" becomes a claim about at least one student; and where the property itself is a conjunction, De Morgan turns it into an "or" inside the new sentence.

Nested quantifiers, where order is the whole question

Q12 works over the integers and asks for the truth value of four statements, each with a one-line reason. Two of them are ∀ followed by ∃ and two are ∃ followed by ∀, and the difference between those two patterns is the point of the sheet.

A one-line reason should be the recipe or the counterexample, not a verdict. "For any x, take y equal to …" is a reason; so is "take x equal to …, which defeats it". Where the statement involves a divisibility or a solvability condition, check that the y your recipe produces is actually in the domain — an integer domain will not accept a y that comes out as a fraction, and that is often exactly where one of these four turns.

Rules of inference and valid arguments

An argument is valid when the conclusion is true in every situation that makes all the premises true. Validity is about form alone: whether the sentences are about reactors, cities or integers makes no difference.

Q13 gives four arguments in words and asks for the form in symbols and the name of the rule, or a statement that the argument is not valid. Do the symbols first: assign a letter to each simple proposition, write the premises and conclusion one per line, and only then compare the shape with the list. A conclusion that happens to be true does not make an argument valid — one of these parts is built to make exactly that point, and the honest answer there is about the form, not about the arithmetic in it.

Q14 is the same decision without the English, for the premises p → q, q ∨ r and ¬r with conclusion p. A short truth table over p, q and r settles it: look only at the rows where all three premises are true, and check whether the conclusion is true in every one of them. If some row has true premises and a false conclusion, that row is the assignment the question asks for, so write out the values of p, q and r rather than describing the row.

The synthesis question

Q15 puts three of these sheets into one statement: over the positive integers, with P(n) meaning that n is prime, the statement S says that for every n, if n is prime then n + 2 is prime. Part (a) is the negation with no ¬ in front of a quantifier or a bracket, which needs the quantifier rule and the rule for negating an implication in sequence, so the result is an existential with a conjunction inside it.

Part (b) asks which of S and its negation is true, with a witness or a counterexample. The shape of the negation tells you what kind of object to hunt for — read your own answer to part (a) and it names the two conditions the object has to satisfy at once. Whichever you produce, check both conditions explicitly, since a single number that meets only one of them proves nothing.

Part (c) is Q4's operation applied inside a quantified statement: the contrapositive of the inner conditional, written as an English sentence. Negate both halves and swap them, then say it the way a person would — a statement about an integer that fails to be prime, and what that forces about another integer.

Preview all 8 pages

Click any page to open the full PDF.

Getting the most out of it

Symbolise first, decide second

Almost every question here rewards writing the letters down before thinking about truth. Q13 and Q15 are explicitly two-stage, and Q2, Q8 and Q10 become mechanical once the symbols are on the page. A decision made from the English sentence and then dressed in symbols afterwards is where the mistakes come from.

Give the evidence the quantifier asks for

An existential claim is settled by one worked witness; a universal claim is settled by a general argument, and refuted by one worked counterexample. Before writing a reason, ask which of those four jobs you are doing. Q9, Q10, Q12 and Q15 all mark that choice.

Keep a column per subformula

In Q3, Q7 and Q14, build the table one connective at a time and label each column with the subformula it holds. It costs a little width and it makes an error findable — a wrong column is visible, a wrong final answer is not.

Say it in English at the end

Q2, Q6, Q8, Q11 and Q15 all ask for a sentence, and the written work in this course is marked on expression. Read your sentence aloud: if it needs "it is not the case that" or a bracket to be understood, push the negation further in and try again.

Use the equivalences as a check, not just a tool

A conditional and its contrapositive must agree; a negation and its original must disagree in every row; the two forms of "no A is B" must match. Whenever a question produces several related answers, those relations are a free check on all of them at once.

Common questions