Week 6 - Propositional Logic B
2.202 Logical implication
-
Logical Implication
- Let and be propositions.
- The conditional statement, or "implication " is the Proposition "if then ".
- We call the hypothesis (or antecedent or premise)
- We call the conclusion (or consequence)
-
Example:
- Let and be the following statements:
- : "John did well in Discrete Mathematics."
- : "John will do well in the programming course."
- The conditional statement 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 - If reasoning is correct (implication is true):
- Let and be the following statements:
-
Different expressions for
- Let and be the following statements:
- : it's sunny
- : John goes to the park
- if then
- if ,
- implies
- only if
- follows from
- is sufficient for
- unless
- is necessary for
- Let and be the following statements:
- Converse, contrapositive and inverse
- Let and be propositions and the conditional statement
- The proposition is the converse of .
- The proposition is the contrapositive of
- Example 1
- Let and be the following statements:
- : It's sunny.
- : John goes to the park.
- And the statement : "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.
- Let and be the following statements:
- Example 2
- Let p and q be two propositions concerning an integer n
- : n has one digit
- : 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.
- If the integer n has one digit then it is less than 10.
- Now write its contrapositive using both symbolic logic expression and English:
- If n is greater than or equal to 10, then n has more than one digit.
- Let p and q be two propositions concerning an integer n
3.204 Logical equivalence
- Logical Equivalence
- The biconditional or equivalence statement is the proposition: and
- Equivalence properties ($\leftrightarrow$)
- Biconditional statements are also called bi-implications.
- 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.
equivalent | ||||
---|---|---|---|---|
F | F | T | T | T |
F | T | T | F | F |
T | F | F | T | F |
T | T | T | T | T |
- Equivalent propositions
- Let and be propositions
- and are logically equivalent if they always have the same truth value.
- We write
- The symbol is not a logical operator, and is not a compound proposition, but rather saying the statemnet that is always true.
- Proving equivalence
- To determine equivalence, we can use truth tables
- Examples
- Compare two propositions and
- The truth tables shows that is equivalent to as they have the same truth values.
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.
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 , and be the following propositions concerning an integer n:
- : n = 20
- : n is even
- : n is positive
- Let's express each of the following conditional statements symbolically:
- if then is positive:
- if n is even:
- only if n is even:
- Let , and be the following propositions concerning an integer n:
- Precedence of logical operations
- - 1
- - 2
- - 3
- - 4
- - 5
- Summary
- definition of equivalence
- equivalence properties
- equivalent propositions
- proving equivalence
- proving non-equivalence
- precedence of logical operations
3.206 Laws of prospositional logic
-
- Propositional logic is an algebra involving multiple laws. These are some of the laws:
Disjunction Conjunction idempotent laws commutative laws associative laws distributive laws identity laws domination laws -
Example
-
Laws of propositional logic 2
-
Equivalence Proof
- Example the equivalence between and
- - given proposition
- - De Morgan's law
- - De Morgan's law
- - double negation law
- - distributive laws
- - complement laws
Problem Sheet
Question 1
Which of the following statements are propositions?
- *$2 + 2 = 4$ - is proposition
- 2 + 2 = 5 is proposition
- - is not a proposition,as value depends on the value of x
- - 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 and be the following propositions:
- - "stocks are increasing"
- - "interest rates are steady"
- Write each of the following sentences symbolically:
- Stocks are increasing but interest rates are steady.
- Neither are stocks increasing nor are interest rates steady.
Question 3.
Let , and be the following 3 propositions:
h: it is hot. s: it is sunny. r: it is raining.
- It is not hot but it is sunny.
- It is neither hot nor sunny
- It is either hot and sunny or it is raining
- It is sunny or it is raining but not both
Question 4.
Let l denote one of the letters in the word "software". The following propositions relate to
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:
: : :
- = {f, a, e}
- = {a, e}
- = {s, o, f, t, w, r}
Question 5.
Let and be 2 propositions. Construct a truth table to show the truth value of each of the following logical statements:
p | 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 and are equivalent statements (using De Morgan's Law).
Question 6.
Let , , and be the following 3 propositions:
: it is hot : it is sunny : it is raining
-
It is sunny or it is raining but not both.
-
It is hot only if it is sunny.
-
It is hot only if it is sunny and not raining.
Question 7.
Let , be propositions. Construct a truth table to show the truth value of each of the statements:
- *$p \rightarrow q$
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 |
is the contrapositive of
Question 8.
Let p and q be the following propositions concerning a positive integer
p: n is divisible by 5. q: n is even.
- Express in words the following statements:
n is divisble by 5 or n is odd.
n is divisible by 5 and n is even.
- List the elemenst of the truth sets corresponding to each of the statements in (1).
- Express each of the following conditional statements symbolically.
if n is odd then n is divisible by 5.
n is even or n is divisible by 5 but not both.
Question 9.
Let and be two propositions. Show that is a tautology.
- -- original expression
- -- De Morgan's law
- = = T
Question 10.
Complete the following table by showing the truth value of each: , , , ,
p | 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
If it's not November 5th then we don't have fireworks.
Converse
If we have fireworks then it is November 5th
Contrapositive
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
Inverse:
If n is not divisible by 15, then it is not divisible by either 3 or 5.
Converse:
If n is divisble by either 3 or 5, then n is divisble by 15.
Contrapositive:
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:
and