Logical Connectives

Another word used to combine sentences is the word "or".

Consider the sentence

i) $4^3 < 3$ ii) $5 > 3$

Combining them with the word "or" i.e. $4^3 < 3$ or $5 > 3$

The connective word "or" is called a disjunction and is symbolized by "$\vee$"

The truth value for disjunction is only false when both the components are false.

If $P$ and $Q$ are statements, then $P$ or $Q$ is symbolized as $P \vee Q$

$P \vee Q$ has a truth value false in one case when both $P$ and $Q$ are false.

Truth table for disjunction

P	Q	P ∨ Q
T	T	T
T	F	T
F	T	T
F	F	F

These are statements of the form "if……..then……"

Example. If a quadrilateral is a parallelogram then the pair of opposite sides are parallel.

The phrase "a quadrilateral is a parallelogram" is called hypothesis or antecedent.

The phrase "the pair of opposite sides are parallel" is called a conclusion or consequent.

If $P =$ hypothesis

$Q =$ conclusion

Then the statement if $P$ then $Q$ is an implication, in short we write $P \rightarrow Q$

Consider the statement

If $4^3 < 3$ then $5 > 3$ T

If $4^3 < 3$ then $5 < 3$ T If hypothesis is T and conclusion is F $4^3 > 3$ then $5 < 3$ F then the implication is T

Note: The compound statement $P \rightarrow Q$ is false only in one case $P$ is true and $Q$ is false.

Truth table for $P \rightarrow Q$

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

Propositions which carry the same meaning as if $P$ then $Q$

1. If $P$, $Q$
2. $Q$ if $P$
3. $Q$ provided that $P$
4. $P$ only if $Q$
5. $P$ is a sufficient condition for $Q$
6. $Q$ is a necessary condition for $P$

1. Determine the truth values of the following

2. If $2 < 3$ then $2 + 3 = 5$ T

3. If $3 < 2$ then $3 + 2 = 5$ T

4. If $2 + 3 = 5$ then $3 < 2$ F

5. If $2 + 1 = 2$ then $1 = 0$ T

6. Find the components of the following compound

i) If $3 < 5$ then $10 + m = 9$

1. $3 < 5$
2. $10 + m = 9$

ii) $a + b = c + d$ only if $p + q = r^2$

1. $a + b = c + d$
2. $p + q = r^2$

iii) If Galileo was born before Descartes then Newton was born before Shakespeare

1. Galileo was born before Descartes

2. Newton was born before Shakespeare

3. Write a truth table for

i) $(P \wedge Q) \vee (P \vee Q)$ ii) $(P \rightarrow Q) \wedge P$ iii) $((P \rightarrow Q) \rightarrow Q)$

Solutions

i) $(P \wedge Q) \vee (P \vee Q)$

P	Q	P ∧ Q	P ∨ Q	(P ∧ Q) ∨ (P ∨ Q)
T	T	T	T	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	F

ii) $(P \rightarrow Q) \wedge P$

P	Q	P → Q	(P → Q) ∧ P
T	T	T	T
T	F	F	F
F	T	T	F
F	F	F	F

iii) $((P \rightarrow Q) \rightarrow Q)$

P	Q	P → Q	(P → Q) → Q
T	T	T	T
T	F	F	T
F	T	T	T
F	F	T	F

Consider the truth table for $(P \rightarrow Q) \wedge (Q \rightarrow P)$

P	Q	P → Q	Q → P	(P → Q) ∧ (Q → P)
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

The statement $(P \rightarrow Q) \wedge (Q \rightarrow P)$ is known as biconditional statement and is abbreviated as $P \leftrightarrow Q$

Truth table for $P \leftrightarrow Q$

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	T

Note: $P \leftrightarrow Q$ is read $P$ if and only if $Q$

$P \leftrightarrow Q$ is true when both $P$ and $Q$ are true or when $P$ and $Q$ are false.

Example. The truth value of $4^3 > 3$ if and only if $5 < 3$ (F)

$4^3 < 3$ if and only if $3 < 5$ (F)

$4^3 < 3$ if and only if $5 < 3$ (T)

$4^3 > 3$ if and only if $5 > 3$ (T)

Given a proposition: if a quadrilateral is a parallelogram then its opposite sides are parallel, $P \rightarrow Q$

Converse: If the opposite sides are parallel, then the quadrilateral is a parallelogram i.e. $Q \rightarrow P$.

Contrapositive: If the opposite sides are not parallel, then the quadrilateral is not a parallelogram. i.e. $\sim Q \rightarrow \sim P$

Inverse: if a quadrilateral is not a parallelogram, then the opposite sides are not parallel i.e. $\sim P \rightarrow \sim Q$

Truth table for implication, converse, contrapositive, inverse

P	Q	P → Q	Q → P	~ P	~ Q	~ Q → ~P	~P → ~ Q
T	T	T	T	F	F	T	T
T	F	F	T	F	T	F	T
F	T	T	F	T	F	T	F
F	F	T	T	T	T	T	T

Column 3 has exactly truth value as column 7

i.e. $P \rightarrow Q \equiv \sim Q \rightarrow \sim P$

$Q \rightarrow P \equiv \sim P \rightarrow \sim Q$

Two propositions are logically equivalent if they have exactly the same truth values.

E.g. $P \vee Q$ and $Q \vee P$ are logically equivalent.

Solution: Draw truth for $P \vee Q$ and $Q \vee P$

P	Q	P ∨ Q	Q ∨ P
T	T	T	T
T	F	T	T
F	T	T	T
F	F	F	F

Since column 3 has exactly the same truth values as column 4 then

$P \vee Q \equiv Q \vee P$

Questions

Show whether or not the following propositions are logically equivalent

i) $P \rightarrow Q$, $\sim P \vee Q$

P	Q	P → Q	~ P	~ P ∨ Q
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

Since column 3 and 5 have exactly the same truth value therefore

$P \rightarrow Q \equiv \sim P \vee Q$

ii) $P \rightarrow (P \vee Q)$; $P \rightarrow Q$

P	Q	P ∨ Q	P → (P ∨ Q)	p → Q
T	T	T	T	T
T	F	T	T	F
F	T	T	T	T
F	F	F	T	T

Since column 4 does not have exactly same truth value as column 5 then $P \rightarrow (P \vee Q) \not\equiv P \rightarrow Q$

iii) $P \rightarrow Q$: $\sim P \rightarrow Q$

P	Q	P → Q	~ P	~ P → Q
T	T	T	F	T
T	F	F	F	T
F	T	T	T	T
F	F	T	T	F

Since column 3 does not have exactly same truth values as column 5 therefore

$P \rightarrow Q \not\equiv \sim P \rightarrow Q$

iv) $P \rightarrow Q$; $Q \rightarrow P$

P	Q	P → Q	Q → P
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

Since column 3 does not have exactly same truth values as column 4 therefore $P \rightarrow Q \not\equiv Q \rightarrow P$

v) $\sim (P \rightarrow Q)$; $P \vee \sim Q$

P	Q	~ Q	P → Q	~ (P → Q)	P ∨ ~Q
T	T	F	T	F	T
T	F	T	F	T	T
F	T	F	T	F	F
F	F	T	T	F	T

Since column 5 does not have exactly same truth value as column 6 therefore $\sim (P \rightarrow Q) \not\equiv P \vee \sim Q$

vi) $\sim (P \vee Q)$; $\sim P \wedge \sim Q$

P	Q	~ P	~ Q	P ∨ Q	~ (P ∨ Q)	~P ∧ ~Q
T	T	F	F	T	F	F
T	F	F	T	T	F	F
F	T	T	F	T	F	F
F	F	T	T	F	T	T

Since column 6 has exact same truth values as column 7 therefore $\sim (P \vee Q) \equiv \sim P \wedge \sim Q$

Compound statements with three components $P$, $Q$, $R$.

Consider the following compound statement,

Triangles have all three sides and either the area of a circular region of radius $r$ is $\pi r^2$ or it is false that the diagonals of a parallelogram do not meet.

Solution

(To symbolize the above statement)

Let $P =$ triangles have three sides

Let $Q =$ circular region of radius $r$ is $\pi r^2$

Let $R =$ diagonals of parallelogram do not meet

$P \wedge (Q \vee \sim R)$

To find the truth values of the above statement

P	Q	R	~ R	Q ∨ ~R	P ∧ (Q ∨ ~ R)
T	T	F	T	T	T

The statement has a truth value true.

A tautology is a proposition which is always true under all possible truth conditions of its component parts.

Example

Show that whether or not $\sim (P \wedge Q) \vee (\sim P \rightarrow \sim Q)$ is a tautology

P	Q	~ P	~ Q	P ∧ Q	~ (P ∧ Q)	~ P → ~Q	~ (P ∧ Q) ∨ (~ P → ~Q)
T	T	F	F	T	F	T	T
T	F	F	T	F	T	T	T
F	T	T	F	F	T	F	T
F	F	T	T	F	T	T	T

Since column 8 has all the truth values True (T) therefore it is TAUTOLOGY.

Since column 8 has truth value true throughout then, $\sim (P \wedge Q) \vee (\sim P \rightarrow \sim Q)$ is a tautology.

Questions

1. Show whether the given compound statements are tautology or not

i) $(P \wedge Q) \rightarrow P$

P	Q	P ∧ Q	(P ∧ Q) → P
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

Since column 4 has truth value true throughout then $(P \wedge Q) \rightarrow P$ is a tautology.

ii) $P \rightarrow (P \wedge Q)$

P	Q	P ∧ Q	P → (P ∧ Q)
T	T	T	T
T	F	F	F
F	T	F	T
F	F	F	T

Since column 4 does not have truth value true throughout then $P \rightarrow (P \wedge Q)$ is not a tautology.

iii) $P \rightarrow \sim P$

P	~ P	P → ~P
T	F	F
F	T	T

Since column 3 does not have the truth value true throughout then

$P \rightarrow \sim P$ is not a tautology.

iv) $(P \rightarrow Q) \rightarrow (\sim P \rightarrow Q)$

P	Q	P → Q	~ P	~P → Q	(P → Q) → (~ P → Q)
T	T	T	F	T	T
T	F	F	F	T	T
F	T	T	T	T	T
F	F	T	T	F	F

Since column 6 does not have the truth value true throughout then $(P \rightarrow Q) \rightarrow (\sim P \rightarrow Q)$ is not a tautology.

v) $(P \rightarrow Q) \vee (Q \rightarrow P)$

P	Q	P → Q	Q → P	(P → Q) ∨ (Q → P)
T	T	T	T	T
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

Since column 5 has all truth values true throughout then $(P \rightarrow Q) \vee (Q \rightarrow P)$ is a tautology.

2. Express the following in symbolic form and then find its truth value

i) 2 is a prime, and either 4 is even or it's not true that 5 is even

Solution

Let $P =$ 2 is a prime

Let $Q =$ 4 is even

Let $R =$ 5 is even

$P \wedge (Q \vee \sim R)$

P	Q	R	~ R	Q ∨ ~ R	P ∧ (Q ∨ ~ R)
T	T	T	F	T	T

$P \wedge (Q \vee \sim R)$ has a truth value true.

ii) 7 is odd, or either London is in France and it is false that Paris is not in Denmark

Let $P =$ 7 is odd

$Q =$ London is in France

$R =$ Paris is not in Denmark

$P \vee (Q \wedge \sim R)$

P	Q	R	~ R	Q ∧ ~R	P ∨ (Q ∧ ~ R)
T	F	T	F	F	T

$P \vee (Q \wedge \sim R)$ has a truth value True.

3. Find the truth values of $P \wedge (Q \vee \sim R)$ if

$P$, $Q$, $R$ all has truth value T

If $P$, $Q$, $R$ all have truth value of F

If $P$ is true, $Q$ is false and $R$ is false

P	Q	R	~ R	Q ∨ ~ R	P ∧ (Q ∨ ~ R)
T	T	T	F	T	T
F	F	F	T	T	F
T	F	F	T	T	T

A complete truth table for general cases

1. Only one compound $P$ — Two rows

P
T
F

2. Two components $P$ and $Q$ — Four rows

P	Q
T	T
T	F
F	T
F	F

3. Three components $P$, $Q$, $R$ — Eight rows

P	Q	R
T	T	T
T	T	F
T	F	T
T	F	F
F	T	T
F	T	F
F	F	T
F	F	F

4. Four components $P$, $Q$, $R$, $S$ — Sixteen rows

P	Q	R	S
T	T	T	T
T	T	T	F
T	T	F	T
T	T	F	F
T	F	T	T
T	F	T	F
T	F	F	T
T	F	F	F
F	T	T	T
F	T	T	F
F	T	F	T
F	T	F	F
F	F	T	T
F	F	T	F
F	F	F	T
F	F	F	F

Example constructs a truth table for the compound statement

$((P \rightarrow Q) \wedge R) \leftrightarrow Q$