The following are all propositions as they can be true or false:

(i). “$3 + 1 = 4$.” It is true and its truth-value is T.

(ii). “$7$ is an even number.” It is false and its truth-value is F.

(iii). “London is in Spain.” It is false and its truth-value is F.

(iv). “Glasgow is in Scotland.” It is true and its truth-value is T.

(v). "$2 × 0 = 0$.” It is true and its truth-value is T.

(vi). "$2 × 0 = 2$.” It is false and its truth-value is F.

The following are not propositions:

(vii). “$x + y > 6$ where $x$ and $y$ are integers.” Without knowing the values of $x$ and $y$ we are unable to ascertain its truth value. The sentence will be true for some choices of $x$ and $y$, and false for other choices. For example, if $x = 3$ and $y = 4$ the sentence is true, but if $x = 3$ and $y = 2$ it is false.

(viii). “He is a computing student.” Whether it is true or false depends on the person. It will be true for some people and false for others.

(ix). “What time is it?” This is a question, not a proposition. It is neither true nor false.

(x). “Shut the door.” This is a command, not a proposition. It is neither true nor false.

(i). The proposition, $p$ : “ $4 > 9$ ” has truth value F.

The proposition, $\sim p :$ not $( p )$

not $(4 > 9)$

“$4$ is not greater than $9$”, i.e.

“$4 \le 9$ ” has truth value T.

(ii). Let $p$ represent, “Maths for Computing is easy”.

We can read $\sim p$ as:

“Maths for Computing is not easy”, or

“It is not the case that Maths for Computing is easy”, or

“It is not true that Maths for Computing is easy”.

The double negation rule says that taking a proposition, negating it and then negating the negation recovers the original proposition, i.e. $\sim (\sim p) = p $.

📹 Propositional Logic: Double Negation

Define the following simple propositions:

$p : 4 > 0$

$q : 6 > 2$

$r : 7 > 9$

$s : 8 < 3$

We then have:

$p \wedge q$ is true since $p$ is true and $q$ is true.

$p \wedge r$ is false since $p$ is true and $r$ is false

$r \wedge q$ is false since $r$ is false and $q$ is true.

$r \wedge s$ is false since $r$ is false and $s$ is false

📹 Logic 101 (#33): Conjunction

Consider the compound propositions:

“John passed the maths exam, but he failed the physics exam”,

“John passed the maths exam, however he failed the physics exam”,

“John passed the maths exam, yet he failed the physics exam”,

“Although John passed the maths exam, he failed the physics exam”.

All of these appear to suggest that it is perhaps surprising that John failed the physics exam, given that he passed the maths exam.

However, they all have the same logical meaning as:

“John passed the maths exam and he failed the physics exam”.

Define the following simple propositions:

$p : 4 > 0$

$q : 6 > 2$

$r : 7 > 9$

$s : 8 < 3$

We then have:

$p \vee q$ is true since both $p$ and $q$ are true

$p \vee r$ is true since $p$ is true.

$r \vee q$ is true since $q$ is true.

$r \vee s$ is false since both $r$ and $s$ are false.

📹 Logic 101 (#35): Disjunction

Suppose your lecturer tells you that:

“If you complete the Maple exercises, then you will pass the exam.”

We shall consider this to be a promise on the part of the lecturer. Let us now investigate the four possible outcomes.

Suppose you complete the Maple exercises and you pass the exam then the promise has been kept and the lecturer’s statement is true.

Suppose you complete the Maple exercises and you do not pass the exam then the promise has been broken and the lecturer’s statement is false.

Suppose you do not complete the Maple exercises. Note that the lecturer did not say what will happen if you do not complete the Maple exercises. His/Her statement only refers to the outcome if you complete the exercises. Whether or not you pass the exam the lecturer has not broken his/her promise. There are two cases:

If you do not pass the exam, the promise has not been broken.

If you pass the exam, the promise has not been broken.

So, the lecturer’s statement will be true in all but one case, i.e. when you complete the Maple exercises and you do NOT pass the exam.

📹 Conditionals Explained

Identify the hypothesis and the conclusion in the following propositions:

(i). “If a number is prime, then it has no positive integer divisors other than $1$ and itself”, $p \to q$.

Hypothesis: “a number is prime”, $(p)$.

Conclusion: “it has no positive integer divisors other than $1$ and itself”, $(q)$.

(ii). “If two lines intersect at right angles, then the lines are perpendicular”, $p \to q$.

Hypothesis: “two lines intersect at right angles”, $(p)$.

Conclusion: “the lines are perpendicular”, $(q)$.

Define the following simple propositions:

$p : 4 > 0$

$q : 3 = 3$

$r : 7 > 9$

$s : 8 < 3$.

We then have:

$p \to q$   (“If $4 > 0$, then $3 = 3$”)   is true since both $p$ and $q$ are true.

$p \to r$   (“If $4 > 0$, then $7 > 9$”)   is false since $p$ is true and $r$ is false.

$r \to q$   (“If $7 > 9$, then $3 = 3$”)   is true since $r$ is false and $q$ is true.

$r \to s$   (“If $7 > 9$, then $8 < 3$”)   is true since $r$ is false and $s$ is false.

As noted earlier there are different ways in which we can express an implication. Here we look at the use of the word “unless” as it appears in conditional statements.

Consider the conditional proposition,

“If it is not raining, then I will go walking.”

In symbolic form define,

$p$ : “I will go walking”

$q$ : “It is raining”.

The conditional proposition becomes, $\sim q \to p$.

This statement is equivalent to,

$p$ unless $q$.

which translates to give,

“I will go walking unless it is raining.”

Hence, “$p$ unless $q$” is equivalent to “if not $q$ then $p$”.

📹 Propositional Logic: A unless B

“If Angela does not go to the football match, then John does not go to the football match.”

can be written as

“John will not go to the football match unless Angela goes to the football match.”

For each of the following write down the conditional proposition $p \to q$, and its converse $q \to p$. Determine the truth value of each compound proposition.

(i). Define the following propositions:

$p : x = 6$.

$q : x^2 = 36$.

CONDITIONAL: If $x = 6$, then $x^2 = 36$, $p → q$, TRUE

CONVERSE:If $x^2 = 36$, then $x = 6, q \to p$, FALSE as we could have $x = -6$.

(ii). Define the following propositions:

$p$ : Ann is from Glasgow.

$q$ : Ann is from Scotland.

CONDITIONAL: If Ann is from Glasgow, then Ann is from Scotland, $p \to q$. TRUE

CONVERSE:If Ann is from Scotland, then Ann is from Glasgow, $q \to p$.

FALSE as Ann could be from Scotland but not from Glasgow. She may be from Edinburgh.

(iii). Define the following propositions:

$p$ : a polygon has exactly three sides.

$q$ : a polygon is a triangle.

CONDITIONAL: If a polygon has exactly three sides, then it is a triangle, $p \to q$, TRUE.

CONVERSE:If a polygon is a triangle, then it has exactly three sides, $q \to p$, TRUE.

These examples have shown that the truth of an implication does not imply the truth of its converse.

📹 Truth Table for the Converse (watch between 4:00 and 5:05) )

For each of the following write down the conditional proposition $p \to q$, and its inverse $(\sim p) \to (\sim q)$ . Determine the truth value of each compound proposition.

(i). Define the following propositions:

$p : x = 6$

$q : x^2 = 36$.

CONDITIONAL: If $x = 6$, then $x^2 = 36,\;\; p \to q$. TRUE

INVERSE: If $x \neq 6$ then $x^2 \neq 36$, $(\sim p) \to (\sim q)$, FALSE as we could have $x = -6$.

(ii). Define the following propositions:

$p$ : Ann is from Glasgow.

$q$ : Ann is from Scotland.

CONDITIONAL: If Ann is from Glasgow, then Ann is from Scotland, $p \to q$. TRUE

INVERSE: If Ann is not from Glasgow, then Ann is not from Scotland, $(\sim p) \to (\sim q)$.

FALSE as it is possible that Ann is not from Glasgow but she is still from Scotland. She may be from Edinburgh.

(iii). Define the following propositions:

$p$ : a polygon has exactly three sides.

$q$ : a polygon is a triangle.

CONDITIONAL: If a polygon has exactly three sides, then it is a triangle, $p \to q$, TRUE.

INVERSE: If a polygon does not have exactly three sides, then it is not a triangle, $(\sim p) \to (\sim q)$, TRUE.

These examples have shown that the truth of an implication does not imply the truth of its inverse.

📹 Truth Table for the Inverse (watch between 2:42 and 4:00)

For each of the following write down the conditional proposition $p \to q$, and its contrapositive $(\sim q) \to (\sim p)$. Determine the truth value of each compound proposition.

(i). Define the following propositions:

$p : x = 6$

$q : x^2 = 36$.

CONDITIONAL: If $x = 6$, then $x^2 = 36, p \to q$. TRUE

CONTRAPOSITIVE: If $x^2 \neq 36$, then $x \neq 6, (\sim q) \to (\sim p)$, TRUE.

(ii). Define the following propositions:

$p$ : Ann is from Glasgow.

$q$ : Ann is from Scotland.

CONDITIONAL: If Ann is from Glasgow, then Ann is from Scotland, $p \to q$. TRUE

CONTRAPOSITIVE: If Ann is not from Scotland, then Ann is not from Glasgow, $(\sim q) \to (\sim p)$. TRUE

(iii). Define the following propositions:

$p$ : “a polygon has exactly three sides.”

$q$ : “a polygon is a triangle.”

CONDITIONAL: If a polygon has exactly three sides, then it is a triangle, $p \to q$, TRUE.

CONTRAPOSITIVE: If a polygon is not a triangle, then it does not have exactly three sides, $(\sim q) \to (\sim p)$, TRUE.

These examples have shown that the truth of an implication does imply the truth of its contrapositive.

📹 Truth Table for the Contrapositive (watch from 5:05 onwards)

📹 Logic 101 (#18): Contrapositive

CONDITIONAL: If a polygon has exactly three sides, then it is a triangle, $p \to q$, TRUE

CONVERSE: If a polygon is a triangle, then it has exactly three sides, $q \to p$, TRUE

BICONDITIONAL: A polygon is a triangle if and only if it has exactly three sides, $p \leftrightarrow q$, equivalently $(p \to q) \wedge (q \to p)$, TRUE.

CONDITIONAL: If two lines intersect at right angles, then the lines are perpendicular, $p \to q$, TRUE

CONVERSE: If two lines are perpendicular, then the lines intersect at right angles, $q \to p$, TRUE

BICONDITIONAL: Two lines are perpendicular if and only if they intersect at right angles, $p \leftrightarrow q$, equivalently $(p \to q) \wedge (q \to p)$, TRUE.

CONDITIONAL: If a number is prime, then it has no positive integer divisors other than 1 and itself, $p \to q$, TRUE

CONVERSE: If a number has no positive integer divisors other than $1$ and itself, then it is prime, $q \to p$, TRUE

BICONDITIONAL: A number is prime if and only if it has no positive integer divisors other than $1$ and itself, $p \leftrightarrow q$, equivalently $(p \to q) \wedge (q \to p)$, TRUE.

(i). Consider the propositions,

$p : 4 < 0$

$q : 5 < 2$

The implications $p \to q$ and $q \to p$ are both true because $p$ and $q$ are both false. Hence, $(p \to q) \wedge (q \to p)$ is true so that $p \leftrightarrow q$ is true.

(ii). Consider the propositions,

$p : 4 > 0$

$q : 5 > 2$

The implications $p \to q$ and $q \to p$ are both true because $p$ and $q$ are both true. Hence, $(p \to q) \wedge (q \to p)$ is true so that $p \leftrightarrow q$ is true.

📹 Logic 101 (#10): Biconditional (IF AND ONLY IF)

📹 Propositional Logic: A if and only if B

We shall prove later, using truth tables, that $p \oplus q$ and $(p\; \wedge \sim q) \vee (\sim p \wedge q)$ are logically equivalent. In the meantime consider the following.

$p$ : I shall play golf.

$q$ : I shall play tennis.

$p \oplus q$ :Either I shall play golf or I shall play tennis, but not both.

$(p \;\wedge \sim q) \vee (\sim p \wedge q)$ : I shall play golf and I shall not play tennis or I shalll play tennis and I shall not play golf.

These two statements mean the same.

Define the following simple propositions:

$p : 4 > 0$

$q : 6 > 2$

$r : 7 > 9$

$s : 8 < 3$.

We then have the following:

$p \oplus q$ is false since $p$ is true and $q$ is true.

$p \oplus r$ is true since $p$ is true and $r$ is false.

$r \oplus q$ is true since $r$ is false and $q$ is true.

$r \oplus s$ is false since $r$ is false and $s$ is false.

📹 Logic 101 (#14): Exclusive OR

Write the following proposition using parentheses, $p\; \wedge \sim q \vee r \to s$.

Solution

The operator with the highest precedence is negation, $\sim$, and so we group it with its operand and write $(\sim q)$.

The next highest precedence is $\wedge$ and we write, $p \wedge (\sim q)$ .

The next highest precedence is $\vee$ and we write, $(p \wedge (\sim q)) \vee r$.

The next highest precedence is $\to$ and we write, $((p \wedge (\sim q)) \vee r) \to s$ .

Define the proposition $p$ and its negation as follows:

$p$ : it is raining

$\sim p$ : it is not raining.

The truth table for $p \vee (\sim p)$ is

Since there are all T’s in the final column $p \vee (\sim p)$ is a tautology.

This result should be obvious as at any given time it is either raining or it is not raining.

Define the proposition $p$ as in the previous example.

The truth table for $p \wedge (\sim p)$ is

Since there are all F’s in the final column $p \wedge (\sim p)$ is a contradiction.

Once again the result should be obvious as it cannot be raining and not raining at the same time.

Consider the following propositions:

$p$ : “Jim goes for a swim”

$q$ : “The sun is shining”

$r$ : “It is cold”.

Translate the following expressions to symbolic form:

(i). “Jim goes for a swim and the sun is shining. ”

(ii). “The sun is shining but Jim does not go for a swim.”

(iii). “Jim goes for a swim if and only if it is not cold and the sun is shining.”

(iv). “If the sun is shining and it is not cold, then Jim goes for a swim.”

(v). “It is not the case that Jim goes for a swim if and only if it is cold or the sun is shining.”

(vi). “If Jim does not go for a swim, then the sun is not shining and it is cold.”

(vii). “If Jim goes for a swim, then the sun is shining but if Jim does not go for a swim then the sun is not shining.”

Solution

(i). This compound proposition is the conjunction of, “Jim goes for a swim” $( p )$ and “the sun is shining” $( q )$ .

Hence, in symbolic form we have, $p \wedge q$.

(ii). This compound proposition is the conjunction of, “the sun is shining” $( q )$ and the negation of “Jim goes for a swim” $(\sim p )$ .

Hence, in symbolic form we have, $q \wedge ( \sim p )$.

(iii). This compound proposition involves “if and only if”, so we have a biconditional.

The first proposition is “Jim goes for a swim” $( p )$.

The proposition “it is not cold and the sun is shining” is a conjunction of the negation of “it is cold” $(\sim r )$ and “the sun is shining” $( q )$, which gives $(\sim r ) \wedge q$.

Combining these we obtain, $p \leftrightarrow (\sim r \wedge q )$.

(iv). The compound proposition is an implication.

The hypothesis follows “if” and the conclusion follows “then”.

The hypothesis is a compound proposition, involving the conjunction of, “The sun is shining” $( q )$ and the negation of “It is cold”, $(\sim r )$ giving $q \wedge ( \sim r )$.

The conclusion is, “Jim goes for a swim” $( p )$.

Hence, in symbolic form we have, $[ q \wedge ( \sim r ) ] \to p$.

(v). The use of “not” negates all that follows.

The connective “if and only if” indicates a biconditional.

The first proposition is “Jim goes for a swim” $( p )$.

The compound proposition, “it is cold or the sun is shining” is the disjunction of “it is cold”, $( r )$ and “the sun is shining” $( q )$. In symbols, $r \vee q$.

Combining the above, while remembering to negate, we obtain, $\sim [ p \leftrightarrow ( r \vee q ) ]$.

(vi). The compound proposition is an implication.

The hypothesis follows “if” and the conclusion follows “then”.

The hypothesis is, “Jim does not go for a swim”, $( \sim p )$ .

The conclusion is the compound proposition, “the sun is not shining and it is cold.” which is the conjunction of “the sun is not shining”, $( \sim q )$ and “it is cold” $( r )$. In symbols, $\sim q \wedge r$.

Combining the above we obtain, $\sim p \to (\sim q \wedge r )$.

(vii). The compound proposition is the conjunction (note the use of “but”) of two conditionals. In symbols,

“If Jim goes go for a swim, then the sun is shining” is, $p \to q$ and

“If Jim does not go for a swim then the sun is not shining” is, $\sim p \to \; \sim q$.

Hence, we have $( p \to q ) \wedge ( \sim p \to \; \sim q )$.

Define the following propositions:

$p$ : “The referee has blown the final whistle”

$q$ : “We know the result of the match”.

Express the following propositions in the form of English sentences:

(i). $\sim p$ (ii). $\sim q$ (iii). $p \wedge q$ (iv). $p \vee q$

(v). $p \to q$ (vi). $q \to p$ (vii). $q \leftrightarrow p$ (viii). $\sim p \wedge q$.

Solution

(i). “The referee has not blown the final whistle.”

(ii). “We do not know the result of the match.”

(iii). “The referee has blown the final whistle and we know the result of the match.”

(iv). “The referee has blown the final whistle or we know the result of the match.”

(v). “If the referee has blown the final whistle, then we know the result of the match.”

(vi). “If we know the result of the match, then the referee has blown the final whistle.”

(vii). “We know the result of the match if and only if the referee has blown the final whistle.”

(viii). “We know the result of the match but the referee has not blown the final whistle.”

Here we use “but” instead of “and” as it is surely surprising to know the result before the match has ended.

Of course we could equally well have used “and”.

Write the following proposition in symbolic form:

(i). “Tom is good at maths and he is good at physics and computing”

(ii). “Tom is good at maths, or he is good at physics, or he is good at computing”

(iii). “Tom is good at maths but it is not true that Tom is good at physics or Tom is good at computing”.

Solution

Define the following propositions:

$p$ : “Tom is good at maths”

$q$ : “Tom is good at physics”

$r$ : “Tom is good at computing”.

(i). The compound proposition, “Tom is good at maths and he is good at physics and computing” is the conjunction of the three simple propositions $p, q$ and $r$. Hence, in symbols we have $p \wedge q \wedge r$, where the associativity of disjunction enables us to omit parentheses. We note here that,

$p \wedge q \wedge r \equiv ( p \wedge q ) \wedge r \equiv p \wedge ( q \wedge r )$.

As we shall see later logical equivalences can be proved using truth tables.

(ii). The compound proposition, “Tom is good at maths, or he is good at physics, or he is good at computing” is the disjunction of the three simple propositions $p, q$ and $r$. Hence, in symbols we have $p \vee q \vee r$ , where the associativity of disjunction enables us to omit parentheses. We note here that,

$p \vee q \vee r \equiv ( p \vee q ) \vee r \equiv p \vee ( q \vee r )$.

As we shall see later logical equivalences can be proved using truth tables.

(iii). We can write,

“Tom is good at physics or Tom is good at computing” symbolically as $q \vee r$.

This expression is negated by the use of the word, “not” and so we write

“It is not true that Tom is good at physics or Tom is good at computing” as $\sim( q \vee r )$.

Recall that “but” can be used as an alternative to “and”.

We can therefore write the original proposition symbolically as, $p\; \wedge [\sim (q\; \vee r)]$.

Define the following propositions

$p$ : “Mary is happy”,

$q$ : “Mary sings a song”,

$r$ : “Richard is happy”.

Express the following propositions in the form of English sentences:

(i). $\sim p$

(ii). $p \to q$

(iii). $( p \vee r ) \to q$

(iv). $( p \wedge q ) \to ( \sim r )$

(v). $p \vee ( \sim p \to r )$.

(vi). $\sim r \to ( \sim p \; \wedge \sim q )$.

Solution

(i). Negate the simple proposition $p$ to give, “Mary is not happy”.

(ii). This compound proposition is an implication.

The hypothesis is, “Mary is happy”.

The conclusion is, “Mary sings a song”.

Combining these we obtain, “If Mary is happy, then she sings a song.”

(iii). This compound proposition is an implication.

The hypothesis is the disjunction, $p \vee r$, “Mary is happy or Richard is happy”.

The conclusion is $q$, “Mary sings a song”.

Hence, $( p \vee r ) \to q$ translates as,

“If Mary is happy or Richard is happy, then Mary sings a song”.

(iv). Similar to part (iii) except that the hypothesis involves a conjunction $( p \wedge q )$ and the conclusion is the negation of the simple proposition $r$. Hence, $( p \wedge q ) \to ( \sim r )$ translates as, “If Mary is happy and she sings a song, then Richard is unhappy. ”

(v). This compound proposition is a disjunction where the left disjunct is the simple proposition, “Mary is happy”.

The right disjunct is the implication, “If Mary is not happy, then Richard is happy”

Hence, $p \vee ( \sim p \to r )$ translates as,

“Either Mary is happy or if Mary is not happy then Richard is happy”

(vi). This compound proposition is an implication.

The hypothesis is, “Richard is unhappy”.

The conclusion is a conjunction where the conjuncts are both negations, i.e.

“Mary is unhappy and she does not sing a song”.

Hence, $\sim r \to ( \sim p \; \wedge \sim q )$ translates as,

“If Richard is unhappy, then Mary is unhappy and she does not sing a song”.

Define the following propositions

$p$ : “Swimming is safe in the sea”,

$q$ : “Tuna are plentiful in the sea”,

$r$ : “Sharks have been seen in the area”.

Express the following propositions in the form of English sentences.

(i). $q \; \wedge \sim r $ (ii). $r \wedge q$

(iii). $r \to \; \sim p$ (iv). $\sim r \to p$

(v). $q \to ( p \leftrightarrow \; \sim r )$ (vi). $( r ∧ q ) \to \; \sim p$

(vii). $\sim r \wedge ( p \; \wedge \sim q )$ (viii). $\sim p \wedge ( \sim r \wedge q )$.

Solution

(i). “Tuna are plentiful in the sea and sharks have not been seen in the area.”

(ii). “Sharks have been seen in the area but tuna are plentiful in the sea.”

(iii). “If sharks have been seen in the area, then it is not safe to swim in the sea.”

(iv). “If sharks have not been seen in the area, then swimming in the sea is safe.”

Alternatively, note that $\sim r \to p$ is equivalent to, $p$ unless $r$ to obtain:

“Swimming in the sea is safe unless sharks have been seen in the area.”

(v). “If tuna are plentiful in the sea, then swimming is safe if and only if sharks have not been seen in the area.”

(vi). “If sharks have been seen in the area and tuna are plentiful in the sea, then swimming in the sea is not safe.”

Alternatively, note that $( r \wedge q ) \to \; \sim p$ is equivalent to,

$\sim p$ whenever $( r \wedge q )$ to obtain:

“Swimming is not safe in the sea whenever sharks have been seen in the area and tuna are plentiful in the sea.”

(vii). “Sharks have not been seen in the area and swimming in the sea is safe but tuna are not plentiful in the sea.”

(viii). “It is not safe to swim in the sea but sharks have not been seen in the area and tuna are plentiful in the sea.”

Determine the negation of the following proposition:

“If it is Friday, then I am going on holiday”.

Solution

This compound proposition involves two simple propositions:

$p$ : “It is Friday”

$q$ : “I am going on holiday”.

The proposition is of the form: $p \to q$ .

The negation of the proposition is: $\sim( p \to q )$.

Note that $\sim( p \to q )$ and $p \; \wedge \sim q$ are logically equivalent, ( see logical equivalence tables).

Hence, the negation of the original proposition is, $p \; \wedge \; \sim q$ which translates to,

“It is Friday and I am not going on holiday.”

Use De Morgan’s laws to determine the negation of the following propositions:

(i). “John is old and wise”

(ii). “Jane is old or wise”

(iii). “It is wet and windy”.

Solution

(i). Define

$p$ : “John is old”

$q$ : “John is wise”

Proposition: $p \wedge q$.

Negating:$\sim( p \wedge q )$.

Translating:“John is not both old and wise.”

De Morgan’s Law: $\sim( p \wedge q ) \equiv \; \sim p \; \vee \sim q$.

Translating:“John is either not old or not wise.”

(ii). Define

$p$ : “Jane is old”

$q$ : “Jane is wise”.

Proposition: $p \vee q$.

Negating:$\sim( p \vee q )$.

Translating:“It is not the case that Jane is either old or wise.”

De Morgan’s Law: $\sim( p \vee q ) \equiv \; \sim p \; \wedge \sim q$.

Translating:“Jane is not old and not wise.”

(iii). Define

$p$ : “It is wet”

$q$ : “It is windy”.

Proposition: $p \wedge q$.

Negating:$\sim( p \wedge q )$.

Translating:“It is not both wet and windy.”

De Morgan’s Law: $\sim( p \wedge q ) \equiv \; \sim p \; \vee \sim q$.

Translating:“It is either not wet or not windy.”

Determine the negation of the following:

“$x$ is even and $y$ is odd”.

Solution

Define the following:

$p : “ x$ is even ”

$q : “ y$ is odd”.

Proposition: $p \wedge q$

Negating:$\sim( p \wedge q )$

Translating:“It is not true that $x$ is even and $y$ is odd”

De Morgan’s Law: $\sim( p \wedge q ) \equiv \; \sim p \; \vee \sim q$

Translating:“$x$ is not even or $y$ is not odd”

Alternatively we can write "$x$ is odd or $y$ is even".

Let $x, y$ and $z$ be real numbers. Determine the negation of,

“ $x$ is negative and $y$ and $z$ are positive”.

Solution

Define the following:

$p :$ “ $x$ is negative ”

$q : $“ $y$ is positive ”

$r :$ “ $z$ is positive ”.

Then write “$x$ is negative and $y$ and $z$ are positive” in symbolic form as, $p \wedge ( q \wedge r )$.

Negating gives, $\sim[ p \wedge ( q \wedge r ) ]$

De Morgan’s Law yields, $\sim p\; \vee \sim ( q \wedge r )$

De Morgan’s Law again, $\sim p \; \vee \sim q \; \vee \sim r$

Translating: “$x$ is not negative or $y$ is not positive or $z$ is not positive”

Alternatively, we can write “ $x \geqslant 0 \;\,\text{or}\;\, y \leqslant 0 \;\, \text{or}\;\, z \leqslant 0 $ ”.

Prove that $p \to q$ and $\sim p \vee q$ are logically equivalent by means of a truth table.

Solution

Write the propositional variables $p$ and $q$ as headers for the first two columns. Complete the first row of the table by writing: $\sim p, \; p \to q$ and $\sim p \vee q$ as headers for the remaining columns.

The first column, headed $p$, will consist of two T’s followed by two F’s.

In the second column, headed $q$, alternate T’s and F’s.

Complete the other three columns using the rules given earlier for negation, implication and disjunction.

The final two columns of the table give the truth values for $p \to q$ and $\sim p \vee q$.

The entries in these columns are identical so that the two propositions are logically equivalent, i.e. $p \to q \equiv \; \sim p \vee q$.

An implication can therefore be written using negation and disjunction.

Note: The following propositions are all logically equivalent to $p \to q$.

$\sim p \vee q$ ( shown above ),

$\sim q \to \; \sim p$ ( Can you show this using truth tables? )

$\sim( p \; \wedge \sim q )$ ( Can you show this using truth tables? ).

Show that $p \oplus q \equiv ( p\; \wedge \sim q ) \vee ( \sim p \wedge q )$ using a truth table.

Solution

From earlier we know that the truth table for $p \oplus q$ is,

The table for $( p \; \wedge \sim q ) \vee ( \sim p \wedge q )$ is obtained as follows:

Write the variables $p, q, \sim p$ and $\sim q$, and the compound propositions $p \; \wedge \sim q$ and $\sim p \wedge q$ in the top row of the table.

In the column between $p \; \wedge \sim q$ and $\sim p \wedge q$ enter the operator $\vee$ as this will be the final column and will record the truth values for the original proposition, $( p \; \wedge \sim q ) \vee ( \sim p \wedge q )$.

Complete the columns for $p$ and $q$ at Step 1.

Complete the columns for $\sim p$ and $\sim q$ at Step 2.

Complete the columns for the two conjunctions at Step 3.

Complete the column for the disjunction at Step 4, using the columns from Step 3.

The highlighted columns in the two truth tables are identical and so $p \oplus q$ and $( p \; \wedge \sim q ) \vee ( \sim p \wedge q )$ are logically equivalent, i.e. $p \oplus q \equiv ( p \; \wedge \sim q ) \vee ( \sim p \wedge q )$.

Note that to save on space the final column only contains the operator $\vee$ but we could equally well have set up a column on the right-hand-side for $( p \; \wedge \sim q ) \vee ( \sim p \wedge q )$ instead.

Exercise

Construct truth tables to show that $p \oplus q$ and $( p \; \vee q )\; \wedge \sim ( p \wedge q )$ are logically equivalent.

Determine the truth tables for the compound propositions:

(i). $( p \to q ) \wedge ( p \to r )$

(ii). $p \to ( q \wedge r )$

(iii). Comment on your answers to parts (i) and (ii).

Solution

(i). In this case there are three proposition variables $p,\, q$ and $r$ and so the table will have $2^3 = 8$ rows to account for all possible combinations of T and F.

Write the propositional variables $p,\, q$ and $r$ as well as the compound propositions, $p \to q, p \to r$ and $( p \to q ) \wedge ( p \to r )$ in the top row of the table

The first column, headed $p$, will contain four consecutive T’s followed by four consecutive F’s.

The second column, headed $q$, will alternate pairs of T’s and pairs of F’s.

The third column, headed $r$, will alternate T’s and F’s.

Complete the columns for $p \to q$ and $p \to r$ using the rules for implication.

Combine the two columns from the previous step using conjunction and write the result in the highlighted (rightmost) column to obtain the truth values for the original proposition.

The numbers in the final row indicate at which step the corresponding column was completed. For example, the columns for $p, q$ and $r$ are labelled with a “1” indicating they were generated at Step 1. The columns for the two implications are labelled “2” and were completed at Step 2. The final column, labelled “3”, was created at Step 3, using the two columns from Step 2.

(ii). Following a similar procedure to that described in part (i) we now complete the truth table for $p \to ( q \wedge r )$.

(iii). The truth values in the highlighted columns in the tables in parts (i) and (ii) are identical and so the propositions $( p \to q ) \wedge ( p \to r )$ and $p \to ( q \wedge r )$ are logically equivalent, i.e. $( p \to q ) \wedge ( p \to r ) \equiv p \to ( q \wedge r )$.

Show that the proposition $( p \to q ) \leftrightarrow ( \sim p \vee q )$ is a tautology.

The highlighted column is obtained by combining the columns to its left and right using the biconditional operator. As it consists of all T’s the proposition is a tautology.

Note: In Example 32 we showed that $p \to q$ and $\sim p \vee q$ are logically equivalent and we have now shown that $( p \to q ) \leftrightarrow ( \sim p \vee q )$ is a tautology.

In general, if two logically equivalent propositions are joined by a biconditional $( \leftrightarrow )$ the resulting proposition will be a tautology.

Show that the proposition $\sim ( p \wedge q ) \leftrightarrow ( q \wedge p )$ is a contradiction.

The highlighted column is obtained by combining the columns to its left and right using the biconditional operator. As it consists of all F’s the proposition is a contradiction.

Determine whether or not $( p \wedge q ) \vee r$ and $p \wedge ( q \vee r )$ are logically equivalent.

Solution

We construct the truth tables for each proposition and compare the final columns. Firstly, the table for $( p \wedge q ) \vee r:$

Now construct the truth table for $p \; \wedge ( q \vee r ):$

Comparing the highlighted column in each table shows that the truth values are different and so the propositions are not logically equivalent.

This example emphasises the importance of brackets as visually the only difference between the two propositions, $( p \wedge q ) \vee r$ and $p \wedge ( q \vee r )$, is the positioning of the brackets. They are however, not the same.