Introduction to logic

Unit 3 Introduction to logic

Key unit competence: Analyse statements and arguments using principles of logic in solving mathematical and real-life problems.

Key ideas

• A proposition (statement) is a sentence that is either true (T) or false (F), not both. Questions and commands are not propositions.
• Connectives: negation $\neg p$; conjunction $p\wedge q$ (true only when both are true); disjunction $p\vee q$ (false only when both are false).
• Conditional $p\Rightarrow q$ is false only when $p$ is true and $q$ is false. Biconditional $p\iff q$ is true when $p$ and $q$ have the same truth value.
• For $p\Rightarrow q$: converse $q\Rightarrow p$; inverse $\neg p\Rightarrow \neg q$; contrapositive $\neg q\Rightarrow \neg p$ (equivalent to the original).
• A tautology is always true; a contradiction is always false; a contingency is neither.
• De Morgan's laws: $\neg (p\wedge q)\equiv \neg p\vee \neg q$; $\neg (p\vee q)\equiv \neg p\wedge \neg q$. Also $p\Rightarrow q\equiv \neg p\vee q$.
• Quantifiers: universal $\forall$ ("for all"), existential $\exists$ ("there exists"). Negation: $\neg (\forall x,P(x))\equiv \exists x,\neg P(x)$ and $\neg (\exists x,P(x))\equiv \forall x,\neg P(x)$.
• A propositional function (predicate) $P(x)$ becomes a proposition when $x$ is given a value or is quantified.

Formulas to know

Common misconceptions

• "The converse of a true statement is true." Not necessarily: "If $x=2$ then $x^2=4$" is true, but its converse is false ($x=-2$).
• "$p\Rightarrow q$ is false when $p$ is false." No: a conditional with a false hypothesis is true.
• "The negation of 'all students passed' is 'no student passed'." No: it is "at least one student did not pass".

Worked examples

Practice questions

Easier and harder questions are mixed, just like in a real exam.

1. Construct the truth table for $(p\wedge q)\Rightarrow p$ and classify it.

   Show answer

   TT: T⇒T = T; TF: F⇒T = T; FT: F⇒F = T; FF: F⇒F = T. It is a tautology.

   Common mistake: Mixing up the rows for $p$ and $q$.

2. Translate into symbols with $p$: "I go to school" and $q$: "It is Saturday": "I go to school if and only if it is not Saturday."

   Show answer

   $p\iff \neg q$.

   Common mistake: Writing $p\Rightarrow \neg q$ (only one direction).

3. Write the converse, inverse and contrapositive of "If a number is divisible by 4, then it is even." Which are true?

   Show answer

   Converse: if even then divisible by 4 (false: 6). Inverse: if not divisible by 4 then not even (false: 6). Contrapositive: if not even then not divisible by 4 (true).

   Common mistake: Thinking the converse is always true.

4. Is "$x>3$" a proposition? What about "$\exists x\in \mathbb{N},x>3$"?

   Show answer

   "$x>3$" is a predicate (no truth value until $x$ is known). The quantified sentence is a true proposition.

   Common mistake: Calling the open sentence false.

5. Use De Morgan's laws to negate "Kalisa is tall and Mukamana is short."

   Show answer

   "Kalisa is not tall or Mukamana is not short."

   Common mistake: Keeping "and" in the negation.

6. Classify $(p\vee q)\iff (q\vee p)$.

   Show answer

   Tautology: $\vee$ is commutative, so both sides always match.

   Common mistake: Building only two rows of the table.

7. Show that $p\Rightarrow q$ and $\neg p\vee q$ have the same truth table.

   Show answer

   Both give T, F, T, T for TT, TF, FT, FF.

   Common mistake: Using $\neg p\wedge q$.

8. Determine the truth value of $\forall x\in \mathbb{R},x^2+1>0$ and of its negation.

   Show answer

   True ($x^2\ge 0$). Negation $\exists x\in \mathbb{R},x^2+1\le 0$ is false.

   Common mistake: Negating only the inequality.

Matching and drag-and-drop

1. Matching

   Match each item in column A with the correct answer in column B. Write the letter next to each number.

   Column A	Column B
   1. $p$ is true, $q$ is true and $r$ is false. Find the truth value of $(p\wedge q)\Rightarrow r$.	a. $p\wedge \neg q$
   2. $\neg (\neg p\vee q)$ is equivalent to:	b. False
   3. The statement $p\Rightarrow (q\Rightarrow p)$ is:	c. True
   4. Is "If $3>5$, then $2+2=5$" true or false?	d. a tautology

   Show answer

   1 → b (False) · 2 → a ($p\wedge \neg q$) · 3 → d (a tautology) · 4 → c (True)

   • Step 1. $p\wedge q$ is T.
     Step 2. T $\Rightarrow$ F is F.
   • Step 1. De Morgan: $\neg (\neg p)\wedge \neg q$.
     Step 2. $\neg \neg p\equiv p$: result $p\wedge \neg q$.
   • Step 1. It is false only if $p$ is T and $(q\Rightarrow p)$ is F.
     Step 2. But $q\Rightarrow p$ is F only when $p$ is F. Contradiction, so it is always true.
   • Step 1. The hypothesis $3>5$ is false.
     Step 2. F $\Rightarrow$ F is T.

2. Drag and drop

   Choose the correct word or phrase from the box for each gap. One word in the box is not needed.

   $p\Rightarrow q$  ·  $\exists x\in \mathbb{R},x^2+1\le 0$  ·  affirming the consequent (invalid)  ·  modus tollens (valid)
   1. The argument "$p\Rightarrow q$, $\neg q$, therefore $\neg p$" is called .
   2. "$p$ only if $q$" means .
   3. The negation of "$\forall x\in \mathbb{R},x^2+1>0$" is .
   Show answer

   1: modus tollens (valid) · 2: $p\Rightarrow q$ · 3: $\exists x\in \mathbb{R},x^2+1\le 0$

   • Step 1. It uses the contrapositive $\neg q\Rightarrow \neg p$.
     Step 2. This valid form is called modus tollens.
   • Step 1. "$p$ only if $q$": $p$ cannot be true unless $q$ is true.
     Step 2. That is $p\Rightarrow q$ ($q$ is a necessary condition).
   • Step 1. $\forall$ becomes $\exists$.
     Step 2. $>$ becomes $\le$.

3. Matching

   Match each item in column A with the correct answer in column B. Write the letter next to each number.

   Column A	Column B
   1. Simplify $\neg (p\Rightarrow \neg q)$.	a. $x=2$ and $x=3$
   2. $P(x)$: "$x^2-5x+6=0$" with $x\in \mathbb{N}$. For which $x$ is $P(x)$ true?	b. $p\wedge q$
   3. $p$ is false and $q$ is true. Find the truth value of $(\neg p\vee q)\iff (p\Rightarrow q)$.	c. True
   4. Find the truth value of the converse of "If $n$ is divisible by 6, then $n$ is even".	d. False

   Show answer

   1 → b ($p\wedge q$) · 2 → a ($x=2$ and $x=3$) · 3 → c (True) · 4 → d (False)

   • Step 1. $p\Rightarrow \neg q\equiv \neg p\vee \neg q$.
     Step 2. Negate with De Morgan: $p\wedge q$.
   • Step 1. $x^2-5x+6=(x-2)(x-3)$.
     Step 2. It is 0 for $x=2$ and $x=3$, both natural numbers.
   • Step 1. $\neg p\vee q$: T $\vee$ T $=$ T.
     Step 2. $p\Rightarrow q$: F $\Rightarrow$ T $=$ T.
     Step 3. T $\iff$ T is T.
   • Step 1. Converse: "If $n$ is even, then $n$ is divisible by 6".
     Step 2. Counter-example: $n=4$ is even but not divisible by 6.

4. Drag and drop

   Choose the correct word or phrase from the box for each gap. One word in the box is not needed.

   if $x^2=4$, then $x\ne 2$  ·  $\neg p\vee q$  ·  if $x\ne 2$, then $x^2\ne 4$  ·  invalid (affirming the consequent)
   1. $\neg (p\wedge \neg q)$ is equivalent to .
   2. "If I study, I pass. I passed. Therefore I studied." This argument is .
   3. The contrapositive of "If $x^2=4$, then $x=2$" is .
   Show answer

   1: $\neg p\vee q$ · 2: invalid (affirming the consequent) · 3: if $x\ne 2$, then $x^2\ne 4$

   • Step 1. De Morgan: $\neg (p\wedge \neg q)\equiv \neg p\vee \neg \neg q$.
     Step 2. $\neg \neg q\equiv q$: result $\neg p\vee q$ (which is also $p\Rightarrow q$).
   • Step 1. Form: $p\Rightarrow q$, $q$, so $p$.
     Step 2. The row $p$ F, $q$ T makes both premises true and the conclusion false: invalid.
   • Step 1. The contrapositive of $p\Rightarrow q$ is $\neg q\Rightarrow \neg p$.
     Step 2. $\neg q$: $x\ne 2$; $\neg p$: $x^2\ne 4$. (Both the statement and its contrapositive are false: try $x=-2$.)

Take the Unit 3 quiz → · Back to contents