## 2.202 Logical implication

• Logical Implication

• Let $p$ and $q$ be propositions.
• The conditional statement, or "implication $p \rightarrow q$" is the Proposition "if $p$ then $q$".
• We call $p$ the hypothesis (or antecedent or premise)
• We call $q$ the conclusion (or consequence)
• Example:

• Let $p$ and $q$ be the following statements:
• $p$: "John did well in Discrete Mathematics."
• $q$: "John will do well in the programming course."
• The conditional statement $p \rightarrow q$ can be written as:
• "If John did well in Discrete Maths then John will do well in programming."
• Truth table for condition statement

• If reasoning is correct (implication is true):
• If the hypothesis is true then the conclusion is true
• If reasoning is incorrect (implication is false):
• if the hypothesis is true, the conclusion is false
• it's always true that:
• from a false hypothesis any conclusion can be implied (true or false)
p q p -> q
F F T
F T T
T F F
T T T
• Different expressions for $p$

• Let $p$ and $q$ be the following statements:
• $p$: it's sunny
• $q$: John goes to the park
• $p \rightarrow q$
• if $p$ then $q$
• if $p$, $q$
• $p$ implies $q$
• $p$ only if $q$
• $p$ follows from $q$
• $p$ is sufficient for $q$
• $q$ unless $\neg p$
• $q$ is necessary for $p$
• Converse, contrapositive and inverse
• Let $p$ and $q$ be propositions and $A$ the conditional statement $p \rightarrow q$
• The proposition $q \rightarrow p$ is the converse of $A$.
• The proposition $\neg p \rightarrow \neg q$ is the contrapositive of $A$
• Example 1
• Let $p$ and $q$ be the following statements:
• $p$: It's sunny.
• $q$: John goes to the park.
• And $A$ the statement $p \rightarrow q$: "If it's sunny then John goes to the park"
• The converse of A is: If John goes to the park then it's sunny.
• The contrapositive of A is: If John doesn't go to the park, then it's not sunny.
• Example 2
• Let p and q be two propositions concerning an integer n
• $p$: n has one digit
• $q$: n is less than 10
• Writing the statement using symbolic logic expression:
• If the integer n has one digit then it is less than 10.
• $p \rightarrow q$
• Now write its contrapositive using both symbolic logic expression and English:
• $\neg q \rightarrow \neg p$
• If n is greater than or equal to 10, then n has more than one digit.

## 3.204 Logical equivalence

• Logical Equivalence
• The biconditional or equivalence statement $p \leftrightarrow q$ is the proposition: $p \rightarrow q$ and $q \rightarrow p$
• Equivalence properties ($\leftrightarrow$)
• Biconditional statements are also called bi-implications.
• $p \leftrightarrow q$ can be read as "p if and only if q"
• The biconditional statements is true when p and q have the same truth values, and is false otherwise.
$p$ $q$ $p \rightarrow q$ $q \rightarrow p$ $(p \rightarrow q \land q \rightarrow p)$ equivalent
F F T T T
F T T F F
T F F T F
T T T T T
• Equivalent propositions
• Let $p$ and $q$ be propositions
• $p$ and $q$ are logically equivalent if they always have the same truth value.
• We write $p \equiv q$
• The symbol $\equiv$ is not a logical operator, and $p \equiv q$ is not a compound proposition, but rather saying the statemnet that $p \leftrightarrow q$ is always true.
• Proving equivalence
• To determine equivalence, we can use truth tables
• Examples
• Compare two propositions $p \rightarrow q$ and $\neg p \lor q$
• The truth tables shows that $\neg p \lor q$ is equivalent to $p \rightarrow q$ as they have the same truth values.
$p$ $q$ $p \rightarrow q$ $\neg p$ $\neg p \lor q$
F F T T T
F T T T T
T F F F F
T T T F T
• Proving non-equivalence
• To determine equivalence, we can use truth tables and find at least one row where values differ.
• Example
• Let's examine whether the converse or the inverse of an implication is equivalent to the original implication.
$p$ $q$ $\neg p$ $\neg q$ $p \rightarrow q$ $\neg p \rightarrow \neg q$ $q \rightarrow p$
F F T T T T T
F T T F T F F
T F F T F T T
T T F F T T T
• Example
• Let $p$, $q$ and $r$ be the following propositions concerning an integer n:
• $p$: n = 20
• $q$: n is even
• $r$: n is positive
• Let's express each of the following conditional statements symbolically:
• if $n = 20$ then $n$ is positive: $p \rightarrow r$
• $n = 20$ if n is even: $q \rightarrow p$
• $n = 20$ only if n is even: $p \rightarrow q$
• Precedence of logical operations
• $\neg$ - 1
• $\land$ - 2
• $\lor$ - 3
• $\rightarrow$ - 4
• $\leftrightarrow$ - 5
• Summary
• definition of equivalence
• equivalence properties
• equivalent propositions
• proving equivalence
• proving non-equivalence
• precedence of logical operations

## 3.206 Laws of prospositional logic

• Laws of Propositional Logic

• Propositional logic is an algebra involving multiple laws. These are some of the laws:
Disjunction Conjunction
idempotent laws $p \lor p \equiv p$ $p \land p \equiv p$
commutative laws $p \lor q \equiv q \lor p$ $p \land q \equiv q \land p$
associative laws $(p \lor q) \land r \equiv p \lor (q \lor r)$ $(p \land q) \land r \equiv p \land ( q \land r)$
distributive laws $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ $p \lor (q \lor r) \equiv (p \land q) \lor (p \land r)$
identity laws $p \lor \mathbf{F} \equiv p$ $p \land \mathbf{T} \equiv p$
domination laws $p \lor \mathbf{T} \equiv \mathbf{T}$ $p \land \mathbf{F} \equiv \mathbf{F}$
• Example

• Laws of propositional logic 2

• Equivalence Proof

• Example the equivalence between $\neg (p \land (\neg p \lor q))$ and $(\neg p \lor \neg q)$
• $\neg (p \land (\neg p \lor q))$ - given proposition
• $\neg p \lor \neg (\neg p \lor q)$ - De Morgan's law
• $\neg p \lor ((\neg \neg p) \land \neg q)$ - De Morgan's law
• $\neg p \lor (p \land \neg q)$ - double negation law
• $(\neg p \lor p) \land (\neg p \lor \neg q)$ - distributive laws
• $T \land (\neg p \lor \neg q)$ - complement laws

## Problem Sheet

### Question 1

Which of the following statements are propositions?

• *$2 + 2 = 4$ - is proposition
• 2 + 2 = 5 is proposition
• $w^2 + 2 = 11$ - is not a proposition,as value depends on the value of x
• $x + y > 0$ - is not a proposition, as value depends on x and y.
• "This coffee is strong" - is not a proposition. It is subjective, not true or false.

Question 2. Let $s$ and $i$ be the following propositions:

• $s$ - "stocks are increasing"
• $i$ - "interest rates are steady"
• Write each of the following sentences symbolically:
• Stocks are increasing but interest rates are steady. $s \land i$
• Neither are stocks increasing nor are interest rates steady.

$\neg s \land \neg i = \neg (s \land i)$

Question 3.

Let $h$, $s$ and $r$ be the following 3 propositions:

h: it is hot. s: it is sunny. r: it is raining.

1. It is not hot but it is sunny.

$\neg h \land s$

1. It is neither hot nor sunny

$\neg (h \lor s)$

1. It is either hot and sunny or it is raining

$(h \land s) \lor r$

1. It is sunny or it is raining but not both

$s \oplus r$

Question 4.

Let l denote one of the letters in the word "software". The following propositions relate to $l$

p: "l is a vowel". q: "l comes after the letter k in the alphabet".

Use the listing method to specify the truth sets corresponding to each of the following statements:

$p$: $\{o, a, e\}$ $q$: $\{s, o, t, w, r\}$ $\neg p$: $\{s, f, t, w, r, o\}$

• $\neg q$ = {f, a, e}
• $p \land \neg q$ = {a, e}
• $\neg p \lor q$ = {s, o, f, t, w, r}

Question 5.

Let $p$ and $q$ be 2 propositions. Construct a truth table to show the truth value of each of the following logical statements:

p q $p \lor q$ $\neg p$ $\neg q$ $\neg p \lor \neg q$ $p \land q$ $\neg (p \land q)$
T F T F T T F T
T T T F F F T F
F T T T F T F T
F F F T T T F T

We can see that $\neg p \lor \neg q$ and $\neg (p \land q)$ are equivalent statements (using De Morgan's Law).

Question 6.

Let $h$, $s$, and $p$ be the following 3 propositions:

$h$: it is hot $s$: it is sunny $r$: it is raining

1. It is sunny or it is raining but not both.

$h \oplus r$

2. It is hot only if it is sunny.

$h \rightarrow s$

3. It is hot only if it is sunny and not raining.

$h \rightarrow (s \land \neg r)$

Question 7.

Let $p$, $q$ be propositions. Construct a truth table to show the truth value of each of the statements:

• *$p \rightarrow q$
• $\neg p \land q$
• $\neg q \rightarrow \neg p$
p q not p not q if p then q not p or q if not q then not p
T F F T F F F
T T F F T T T
F T T F T T T
F F T T T T T

$p \rightarrow q = \neg p \lor q = \neg q \rightarrow \neg p$

$\neg q \rightarrow \neg p$ is the contrapositive of $p \rightarrow q$

Question 8.

Let p and q be the following propositions concerning a positive integer $n$

p: n is divisible by 5. q: n is even.

1. Express in words the following statements:

$p \lor \neg q$

n is divisble by 5 or n is odd.

$p \land q$

n is divisible by 5 and n is even.

1. List the elemenst of the truth sets corresponding to each of the statements in (1).

$\{1, 3, 5, 7, 9, 10, 11, 13 ...\}$ $\{10, 20, 30, ...\}$

1. Express each of the following conditional statements symbolically.

if n is odd then n is divisible by 5.

$\neg q \rightarrow p$

n is even or n is divisible by 5 but not both.

$q \oplus p$

Question 9.

Let $p$ and $q$ be two propositions. Show that $p \lor \neg (p \land q)$ is a tautology.

• $p \lor \neg (p \land q)$ -- original expression
• $p \lor \neg p \lor \neg q$ -- De Morgan's law
• $p \lor \neg p = T$ = $T \land \neg q$ = T

Question 10.

Complete the following table by showing the truth value of each: $p$, $q$, $p \rightarrow q$, $q \rightarrow p$, $p \leftrightarrow q$

p q $p \rightarrow q$ $q \rightarrow p$ $p \leftrightarrow q$
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 1 1 1

Question 11.

What is the inverse, the converse and the contraposition of the following statement:

If it is November 5th then we have fireworks.

p: is it November 5th q: we have fireworks

Inverse

$\neg p \rightarrow \neg q$

If it's not November 5th then we don't have fireworks.

Converse

$q \rightarrow p$

If we have fireworks then it is November 5th

Contrapositive

$\neg q \rightarrow \neg p$

If we don't have fireworks then it's not November 5th.

Question 12.

Let p denote the following statement about integers n:

If n is divisible by 15, then it is divisible by 3 or divisible by 5.

Write the inverse, the converse and the contrapositive of p.

p: if n is divisible by 15, then it is divisble by 3 or divisible by 5.

s: divisible by 15 q: divisible by 3 r: divisble by 5

$s \rightarrow (q \lor r)$

Inverse:

$\neg s \rightarrow \neg (q \lor r)$

If n is not divisible by 15, then it is not divisible by either 3 or 5.

Converse:

$(q \lor r) \rightarrow s$

If n is divisble by either 3 or 5, then n is divisble by 15.

Contrapositive:

$\neg (q \lor r) \rightarrow \neg s$

If n is not divisble by either 3 or 5 then n is not divisible by 15.

Question 13.

Let p and q be two propositions. Show by constructing the truth table or otherwise that the following statements are equivalent:

$p \lor q$ and $\neg$