7. Proofs using laws of logic (logical equivalences) (OPTIONAL)

The laws of logic, given in the tables of logical equivalences, provide an alternative method for:

proving whether or not compound propositions are logically equivalent.

proving a proposition is a tautology, or a contradiction, or neither of these.

simplifying compound propositions.

We present some examples to illustrate the above.

Example 38

(i). Prove that $\sim(p \to q)$ and $p \; \wedge \sim q$ are logically equivalent.

Solution

$\sim(p \to q)$

$\equiv \;\sim(\sim p \vee q)$ ( logical equivalence )

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

$\equiv p \; \wedge \sim q$ ( double negation )

Hence, $\sim(p \to q)$ and $p \; \wedge \sim q$ are logically equivalent.

(ii). Use logical equivalences to show that $\sim q \vee ( p \to q )$ is a tautology.

Solution

$\sim q \vee(p \to q)$

$\equiv \; \sim q \vee(\sim p \vee q)$ ( logical equivalence )

$\equiv \; \sim q \vee(q \; \vee \sim p)$ ( commutativity of ∨ )

$\equiv (\sim q \vee q) \vee \sim p$ ( associativity of ∨ )

$\equiv T\; \vee \sim p$ ( negation )

$\equiv T$ ( dominance )

Hence, $\sim q \vee ( p \to q )$ is a tautology.

Exercise: Prove the above result using a truth table.

(iii). Use logical equivalences to show that $q \; \wedge \sim ( p \to q )$ is a contradiction.

Solution

$q \; \wedge \sim (p \to q)$

$\equiv q \; \wedge \sim (\sim p \vee q)$ ( logical equivalence )

$\equiv q \wedge [\, \sim (\sim p)\; \wedge \sim q\,]$ ( De Morgan’s Law )

$\equiv q \wedge (p \; \wedge \sim q)$ ( double negation )

$\equiv q \wedge (\sim q \wedge p)$ ( commutativity of $\wedge$ )

$\equiv (q \; \wedge \sim q) \wedge p$ ( associativity of $\wedge$ )

$\equiv F \wedge p$ ( negation )

$\equiv F$ ( dominance )

Hence, $q \; \wedge \sim ( p \to q )$ is a contradiction.

Exercise: Prove the above result using a truth table.

(iv). Use logical equivalences to simplify, $\sim ( \sim p \to q ) \vee ( p \; \wedge \sim q )$.

Solution

$\sim ( \sim p \to q ) \vee (p \; \wedge \sim q)$

$\equiv \; \sim (\sim \; \sim p \vee q) \vee (p \; \wedge \sim q)$ ( logical equivalence )

$\equiv \; \sim (p \vee q) \vee (p \; \wedge \sim q)$ ( double negation )

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

$\equiv (\sim q \; \wedge \sim p) \vee (\sim q \wedge p)$ ( commutativity of $\wedge$ )

$\equiv \sim q \wedge (\sim p \vee p)$ ( distributivity of $\vee$ from right to left )

$\equiv \; \sim q \wedge T$ ( negation )

$\equiv \; \sim q$ ( identity )

Hence, the compound proposition $\sim ( \sim p \to q ) \vee ( p \; \wedge \sim q )$ has been simplified to the simple proposition $\sim q$, i.e. they are logically equivalent.

Exercise: Prove the above result using a truth table.

End of Example 38

Example 39

Prove that the propositions $\sim ( p \wedge q )$ and $\sim p \; \wedge \sim q$ are not logically equivalent.

Solution

We could use a truth table to show this result but instead we will use a counterexample. It is enough to find one example for which the result does not hold to conclude that they are not logically equivalent.

Define the following propositions:

$p : 2 < 4$

$q : 4 < 2$

Now, $\sim ( p \wedge q )$ reads as, “It is not the case that both $2 < 4$ and $4 < 2$”, which is true.

On the other hand, $\sim p \; \wedge \sim q$

reads as, “$2 \not< 4$ and $4 \not< 2$”, which is false.

Hence, $\sim ( p \wedge q )$ and $\sim p \; \wedge \sim q$ are not logically equivalent.

📹 Logical equivalence without truth tables

End of Example 39

8. Arguments

A logical argument, or simply an argument, is a finite list of propositions, $p_1, p_2, \dots, p_n$ known as the premises or hypotheses of the argument followed by a single statement, $q$ , called the conclusion of the argument. In column form the structure of an argument is,

$p_1$

$p_2$

$\vdots$

$\underline{p_n}$

$\therefore q$

which we read as “ $p_1, p_2, \dots, p_n$ therefore $q$ ”. The three dots $(\therefore)$ represent the word “therefore”. Note that the ordering of the premises does not matter.

Alternative notation takes the form

$p_1, p_2, \dots, p_n \vdash q$.

An argument is valid if the conclusion $(q)$ is true whenever all the premises $( p_1, p_2, \dots, p_n )$ are true.

If an argument is not valid it is said to be invalid or a fallacy.

Given an argument

$p_1$

$p_2$

$\vdots$

$\underline{p_n}$

$\therefore q$

a truth table can be constructed to include the truth values of the premises and the conclusion. A row in the table in which all the premises are true is called a critical row. If the conclusion in every critical row is true then the argument is valid. It is possible however, for an argument to have true premises and a false conclusion, in which case the argument is invalid.

Alternatively, an argument is valid if and only if the conditional proposition

$( p_1 \wedge p_2 \wedge \dots \wedge p_n ) \to q$

is a tautology. If the final column of the corresponding truth table contains all T’s then it is a tautology and the argument is valid.

In this section we consider some of the most common types of valid arguments, or rules of inference, and the main fallacies that occur in practice.

The four types of valid arguments we will investigate are:: modus ponens (law of detachment).; modus tollens (law of contraposition); hypothetical syllogism (transitive reasoning).; disjunctive syllogism.

It is worth noting here that if we are able to write an argument in one of these forms then it is guaranteed to be valid and so we do not actually need to construct a truth table to confirm this. However, this is a skill that takes time to develop and for completeness we will therefore include truth tables where appropriate.

The compound proposition, $p \to q$ , will feature prominently in our discussions and so we should recall that $p$ is known as the antecedent of the implication while $q$ is referred to as its consequent.

In the following paragraphs when refering to rows of a truth table we discount the header row and start numbering from the first row containing truth values.

Modus ponens

If an argument has two premises an implication $( p \to q )$ and the antecedent $( p )$ of the implication, which are both true, then the consequent $( q )$ must be true. Note here that $p$ and $q$ can be simple or compound propositions. In symbolic form the inference rule modus ponens, or law of detachment, is written,

$p \to q$

$\underline{p \;\;\;\;\;\;\;}$

$\therefore q$

with corresponding tautology, $[ ( p \to q ) \wedge p ] \to q$.

Example 40

Show that the following argument is valid:

If the sun is shining, then I go for a walk.

The sun is shining

$\therefore \;$ I go for a walk

Solution

Define

$p :$ “The sun is shining”

$q :$ “I go for a walk”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \to q \\ \underline{p \;\;\;\;\;\;\;}\\ \therefore q$
Proposition:	$[(p \to q) \wedge p ] \to q$

Construct the truth table with the premises in Columns 3 and 4 and the conclusion in Column 5:

$p$	$q$	$p \to q$	$p$	$q$
T	T	T	T	T
T	F	F	T	F
F	T	T	F	T
F	F	T	F	F

Row 1 is the only critical row, it has a true conclusion and so the argument is valid.

Hence, from knowledge that the premises $p$ and $p \to q$ are both true we were able to establish that the conclusion $q$ is true. This is because for $( p \to q ) \wedge p$ to be true we need both $p \to q$ and $p$ to be true. Now, if $p$ is true then for $p \to q$ to be true we must have that $q$ is true and the result follows.

Note that as we were able to write the argument in the form of modus ponens we knew it was valid and did not actually need the truth table.

📹 Logic 101 (#27): Modus Ponens

End of Example 40

Modus tollens

If an argument has two premises, an implication $( p \to q )$ and a negation of the consequent $(\sim q )$ which are both true then the negation of the antecedent $( \sim p )$ must be true. Note here that $p$ and $q$ can be simple or compound propositions. In symbolic form the inference rule modus tollens, or law of contraposition, is written,

$p \to q$

$\underline{ \sim q \;\;\;\;\;}$

$\therefore\; \sim p$

with corresponding tautology, $[ ( p \to q )\; \wedge \sim q ] \to \; \sim p $.

Example 41

Show that the following argument is valid:

If the sun is shining, then I go for a walk.

I do not go for a walk.

$\therefore \;$ The sun is not shining.

Solution

Define

$p :$ “The sun is shining”

$q :$ “I go for a walk”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \to q \\ \underline{ \sim q \;\;\;\;}\\ \therefore \; \sim p$
Proposition:	$[(p \to q) \; \wedge \sim q ] \to \; \sim p$.

Construct the truth table with the premises in Columns 3 and 4 and the conclusion in Column 5:

$p$	$q$	$p \to q$	$\sim q$	$\sim p$
T	T	T	F	F
T	F	F	T	F
F	T	T	F	T
F	F	T	T	T

Row 4 is the only critical row, it has a true conclusion and so the argument is valid.

📹 Logic 101 (#28): Modus Tollens

End of Example 41

Hypothetical syllogism (transitive reasoning)

If an argument has two premises which are both implications, i.e. $p \to q$ and $q \to r$ , and both are true, then $p \to r$ must be true. Note here that $p, q$ and $r$ can be simple or compound propositions.

In symbolic form we have

$p \to q$

$\underline{q \to r \;\;\;\;}$

$\therefore p \to r$

with corresponding tautology, $[ ( p \to q ) \wedge ( q \to r ) ] \to ( p \to r )$.

A point to note here is that it is possible to construct arguments with any number of “if . . . then” premises provided the antecedent of the latest premise in the list agrees with the consequent of the previous premise. For example, look at the role of “$q$” in the two premises above.

Example 42

Let $n$ be any integer. Show that the following argument is valid:

If $n$ is divisible by 48, then $n$ is divisible by 12.

If $n$ is divisible by 12 then $n$ is divisible by 3.

$\therefore \;$ If $n$ is divisible by 48, then $n$ is divisble by 3

Solution

Define

$p :$ “$n$ is divisible by 48”

$q :$ “$n$ is divisible by 12”

$r :$ “$n$ is divisible by 3”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \to q \\ \underline{ q \to r \;\;\;\;\;}\\ \therefore \; p \to r$
Proposition:	$[ ( p \to q ) \wedge ( q \to r ) ] \to ( p \to r )$.

Construct the truth table with the premises in Columns 4 and 5 and the conclusion in Column 6:

$p$	$q$	$r$	$p \to q$	$q \to r$	$p \to r$
T	T	T	T	T	T
T	T	F	T	F	F
T	F	T	F	T	T
T	F	F	F	T	F
F	T	T	T	T	T
F	T	F	T	F	T
F	F	T	T	T	T
F	F	F	T	T	T

There are four critical rows (Rows 1, 5, 7 and 8), all have a true conclusion and so that the argument is valid.

📹 Logic 101 (#30): Hypothetical Syllogism

End of Example 42

Disjunctive syllogism

If an argument has two premises, a disjunction $p \vee q$ and a negation $\sim p$, and both are true then $q$ must be true. Note here that $p$ and $q$ can be simple or compound propositions.

In symbolic form we have

$p \vee q$

$\underline{\sim p \;\;\;}$

$\therefore q$

with corresponding tautology, $[ ( p \vee q )\; \wedge \sim p ] \to q$.

Example 43

Show that the following argument is valid:

Either Real Madrid or Barcelona will win La Liga.

Real Madrid will not win La Liga

$\therefore \;$ Barcelona will win La Liga.

Solution

Define

$p :$ “Real Madrid will win La Liga”

$q :$ “Barcelona will win La Liga”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \vee q \\ \underline{ \sim p \;\;\;\;\;}\\ \therefore \; q $
Proposition:	$[ ( p \vee q )\; \wedge \sim p ] \to q$.

Construct the truth table with the premises in Columns 3 and 4 and the conclusion in Column 5:

$p$	$q$	$p \vee q$	$\sim p$	$q$
T	T	T	F	T
T	F	T	F	F
F	T	T	T	T
F	F	F	T	F

Row 3 is the only critical row, it has a true conclusion and so the argument is valid.

This result is actually very straightforward as the disjunction tells us that at least one of the cases must be true. Either Real Madrid will win La Liga, or Barcelona will win La Liga or (very unlikely) both will win La Liga, i.e. a dead heat! Now, if we know that one of the teams (Real Madrid) will not win then it must be the case that the other team (Barcelona) will win.

📹 Logic 101 (#29): Disjunctive Syllogism

End of Example 43

Other rules of inference that occur in propositional logic include:

📹 Conjunction

📹 Simplification

📹 Biconditional

📹 Addition (disjunction)

Before moving on to look at examples of invalid arguments we present a valid argument that involves three premises, as opposed to two in the previous cases. Although we now have more terms the process of proving validity is essentially the same.

Example 44

Show that the following argument is valid:

David is playing football.

If David is playing football, then he is not studying.

If David is not studying, then his mother will not buy him a new phone

$\therefore \;$ David’s mother will not buy him a new phone.

Solution

Define $p :$ “David is playing football.”

$q :$ “David is studying.”

$r :$ “David’s mother will buy him a new phone.”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \\ p \to \; \sim q \\ \underline{\sim q \to \; \sim r \;\;\;\;\;}\\ \therefore \; \sim r$
Proposition:	$[\; p \wedge ( p \to \; \sim q ) \wedge (\sim q \to \; \sim r )\; ] \to \; \sim r $.

Construct the truth table with the premises in Columns 6, 7 and 8 and the conclusion in Column 9:

$p$	$q$	$r$	$\sim q$	$\sim r$	$p$	$p \to \; \sim q$	$\sim q \to \; \sim r$	$\sim r$
T	T	T	F	F	T	F	T	F
T	T	F	F	T	T	F	T	T
T	F	T	T	F	T	T	F	F
T	F	F	T	T	T	T	T	T
F	T	T	F	F	F	T	T	F
F	T	F	F	T	F	T	T	T
F	F	T	T	F	F	T	F	F
F	F	F	T	T	F	T	T	T

Row 4 is the only critical row, it has a true conclusion and so the argument is valid.

End of Example 44

Logical Fallacies

Of course not every argument is valid and in this section we take a brief look at types of invalid argument, also called fallacies.

Fallacy of the converse

Recall that the rule of inference called modus ponens is given in symbolic as

$ p \to q \\ \underline{p \;\;\;\;\;\;\;}\\ \therefore q$

We have seen that this is a valid argument and that the corresponding proposition, $[ ( p \to q ) \wedge p ] \to q$ is a tautology.

Now suppose that we make one seemingly “small” change and write

$ p \to q \\ \underline{q \;\;\;\;\;\;\;}\\ \therefore p$

where the roles of the second premise and the conclusion have been swapped. We illustrate with an example that this is a logical fallacy known as the, “fallacy of the converse” or “affirming the consequent”. It may be helpful to think of this argument as the invalid version of modus ponens.

Example 45

Test the validity of the following argument.

If the sun is shining, then I go for a walk.

I go for a walk

$\therefore \;$ The sun is shining

Solution

Define

$p :$ “The sun is shining.”

$q :$ “I go for a walk.”

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \to q \\ \underline{ q \;\;\;\;\;\;\;\;}\\ \therefore \; p$
Proposition:	$[\; ( p \to q ) \wedge q \;] \to p $.

Construct the truth table with the premises in Columns 3 and 4 and the conclusion in Column 5:

$p$	$q$	$p \to q$	$q$	$p$
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	F	F

Rows 1 and 3 are critical rows. Row 3 has a false conclusion and so the argument is invalid.

The premises tell us that $p \to q$ and $q$ are both true but this information is not sufficient for us to conclude anything about $p$ as it may be true or false.

📹 Logic 101 (#48): Fallacy of the Converse

End of Example 45

Fallacy of the inverse

Recall the rule of inference called modus tollens which in symbolic form was represented by,

$ p \to q \\ \underline{\sim q \;\;\;\;\;\;}\\ \therefore \; \sim p$

We have seen that this is a valid argument and that the corresponding proposition, $[ ( p \to q )\; \wedge \sim q ] \to \; \sim p$ is a tautology.

Now suppose that we make one seemingly “small” change and write

$ p \to q \\ \underline{\sim p \;\;\;\;\;\;}\\ \therefore \; \sim q$

where the roles of $\sim q$ and $\sim p$ have been swapped. We illustrate with an example that this is a logical fallacy known as the “fallacy of the inverse” or “denying the antecedent”. It may be helpful to think of this argument as the invalid version of modus tollens.

Example 46

Test the validity of the following argument to show that it is a fallacy.

If the sun is shining, then I go for a walk

The sun is not shining

$\therefore \;$ I do not go for a walk

Solution

Define $p :$ “The sun is shining.”

$q :$ “I go for a walk.”

Write the argument in symbolic form, construct the corresponding proposition and check its validity using a truth table.

Argument:	$p \to q \\ \underline{\sim p \;\;\;\;\;}\\ \therefore \; \sim q$
Proposition:	$[\; ( p \to q )\; \wedge \sim p \;] \to \; \sim q $.

Construct the truth table with the premises in Columns 3 and 4 and the conclusion in Column 5:

$p$	$q$	$p \to q$	$\sim p$	$\sim q$
T	T	T	F	F
T	F	F	F	T
F	T	T	T	F
F	F	T	T	T

Rows 3 and 4 are critical rows. Row 3 has a false conclusion and so the argument is invalid.

The premises tell us that $p \to q$ is true and $p$ is false and we conclude that $q$ is true. However, this is incorrect as knowing $p$ is false there is no way we can determine whether $q$ is true or false.

📹 Logic 101 (#49): Fallacy of the Inverse

End of Example 46

Fallacy of the false chain

Previously we encountered the type of valid argument called hypothetical syllogism which is based on transitive reasoning. We noted how, if the antecedent of the latest premise in the list agrees with the consequent of the previous premise, forming a chain, then the argument will be valid. Here we look at so-called false chains that result in invalid arguments.

Example 47

Show that the following argument is invalid:

If you are a fish, then you live in water.

If you are a fish, then you have gills.

$\therefore \;$ If you live in water, then you have gills.

Solution

Define $p :$ “You are a fish”

$q :$ “You live in water”

$r :$ “You have gills”.

Write the argument in symbolic form, construct the corresponding proposition, and check its validity using a truth table.

Argument:	$p \to q \\ \underline{p \to r \;\;}\\ \therefore \; q \to r$
Proposition:	$[\; ( p \to q )\; \wedge (p \to r)\;] \to (q \to r) $.

Construct the truth table with the premises in Columns 4 and 5 and the conclusion in Column 6:

$p$	$q$	$r$	$p \to q$	$p \to r$	$q \to r$
T	T	T	T	T	T
T	T	F	T	F	F
T	F	T	F	T	T
T	F	F	F	F	T
F	T	T	T	T	T
F	T	F	T	T	F
F	F	T	T	T	T
F	F	F	T	T	T

Rows 1, 5, 6, 7 and 8 are critical rows. Row 6 has a false conclusion and so the argument is invalid.

For example, whales and dolphins live in water but do not have gills.

End of Example 47

You should now attempt the exercises at this link 🔗 http://www.math.fsu.edu/~wooland/argumentor/argumentorIE.html#A

The table below summarises the types of argument discussed above.

Argument	Format
Modus ponens (Law of detachment)	$p \to q \\ \underline{p \;\;\;\;\;\;\;}\\ \therefore \; q$
Modus tollens (Law of contraposition)	$p \to q \\ \underline{\sim q \;\;\;\;\;}\\ \therefore \; \sim p$
Hypothetical syllogism (Transitive reasoning)	$p \to q \\ \underline{q \to r \;\;\;\;}\\ \therefore \; p \to r$
Disjunctive syllogism	$p \vee q \\ \underline{\sim p \;\;\;\;}\\ \therefore \; q$
Fallacy of the converse (Affirming the consequent)	$p \to q \\ \underline{q \;\;\;\;\;\;\;}\\ \therefore \; p$
Fallacy of the inverse (Denying the antecedent)	$p \to q \\ \underline{\sim p \;\;\;\;\;}\\ \therefore \; \sim q$
Fallacy of the false chain	$p \to q \\ \underline{p \to r \;\;\;\;\;}\\ \therefore \; q \to r$

9. Applications of laws of logic in computing

The laws of logic, included in our tables of logical equivalences, are often used in computer programming to simplify more complicated expressions. In Java programming, for example, we can utilise De Morgan’s laws to simplify expressions involving connectives such as “NOT”, “OR” and “AND”.

9.1. Logic in programming

We note the following representation of operators in Java:

&& means AND,

$\mid \mid$ means OR,

! means NOT.

Example 48

Simplify the following Java code by applying the laws of logic.

(i). Answer = $x \mid \mid \;!( y\; \& \& \; x )$.

(ii). $!( x < 4 \; \&\& \; y > 3 )$.

Solution

(i). Answer $= x \mid \mid \;! (y \; \& \& \; x) $

$= x \mid \mid (!y) \mid \mid \;(!x)$ (De Morgan's Law)

$= x \mid \mid (!x) \mid \mid (!y)$ ( Associative Law )

$= T \mid \mid (! y )$ ( Negation Law )

$= T$ ( Domination Law )

Hence, this code evaluates to “true” regardless of what the inputs $x$ and $y$ are.

(ii). $! ( x < 4 \; \&\& \; y > 3 )$( De Morgan’s Law )

$=\; !(x < 4) \mid \mid \; ! (y > 3)$

$=\; ( x \geqslant 4 ) \mid \mid ( y \leqslant 3 )$

End of Example 48

9.2. System specifications

In computing, software and system engineers will take requirements that are given in English and using the language of logic express these requirements in a more formal and precise manner.

Example 49

Express the following symbolically using propositional logic:

(i). “If the recipient’s mailbox is full, then emails will not be delivered”.

(ii). “64 bit software can only be installed on a 64 bit OS whereas 32 bit software can be installed on a 32 bit or a 64 bit OS".

Solution

(i). Define $p$ and $q$ as follows:

$p:$ “The email has been delivered”

$q:$ “The recipient’s mailbox is full”.

Symbolically the statement is, $q \to \; \sim p$ .

(ii). Define $p, q$ and $r$ as follows:

$p:$ “64-bit software can be installed on a 64-bit OS"

$q:$ “32-bit software can be installed on a 32-bit OS”

$r:$ “32-bit software can be installed on a 64-bit OS”.

Symbolically the statement is, $p \wedge ( q \vee r )$ .

End of Example 49

9.3. Inequalities and De Morgan’s Laws

We close this section with a look at how the laws of logic can be used to obtain the negation of intervals, a topic which relates to the programming examples in section 9.1.

Example 50

(i). Write the following inequality

$-3 \le x < 8$

as a statement involving two inequalities and an appropriate logical operator.

(ii). Determine the negation of $- 3 \le x < 8$ using De Morgan’s laws.

Solution

(i). The expression is equivalent to

$-3 \le x$ and $x < 8$

shown in red in the diagram below.

(ii). The negation of the statement is

$\sim (- 3 \le x$ and $x < 8 )$

which by De Morgan’s laws is equivalent to

$\sim ( - 3 \le x)$ or $\sim (x < 8)$.

To simplify this expression we note that $\sim( - 3 \le x )$ can be written as $x < - 3$ and $\sim( x < 8 )$ can be expressed as $x \ge 8$ .

Hence, the negation of $\sim 3 \le x < 8$ is

$x < - 3$ or $x \ge 8$

which is shown in blue in the following diagram.

Note the similarities between the above and the calculation of the complement of intervals in Section 10 of the unit on set theory.

End of Example 50

Example 51

Use the appropriate De Morgan’s law to determine the negation of the following:

(i). $x \le - 6$ or $x > 4$.

(ii). $4 \ge x$ and $x > -3$ .

Solution

(i). In symbolic form we have

$(x \le - 6 ) \vee ( x > 4)$.

Negating gives

$\sim [\;(x \le - 6 ) \vee ( x > 4)\;]$.

Applying De Morgan’s Law

$\sim(x \leqslant - 6)\; \wedge \sim( x > 4)$.

Simplifying we have

$ (x > - 6) ∧ ( x \le 4)$

or

$( x > - 6 )$ and $( x \le 4 )$.

In interval notation we have

$- 6 < x \le 4.$

(ii). Rewrite the expression as

$ ( 4 \ge x ) \wedge ( x > -3 )$.

Negating gives

$\sim [\;(4 \ge x ) \wedge ( x > -3)\;]$.

Applying De Morgan’s Law

$\sim ( 4 \ge x )\; \vee \; \sim ( x > -3 )$.

Simplifying we have

$( 4 < x ) \vee ( x \le -3 )$.

which gives

$x > 4$ or $x \le - 3. $

End of Example 51
Summary

In this unit we have introduced the concept propositional logic and you should now be able to:

identify whether or not an expression is a proposition/statement.

use standard logical connectives including not, and, or, biconditional and exclusive or.

use implication and its converse, inverse and contrapositive.

translate English expressions into logical statements in symbolic form.

translate logical statements in symbolic form into English.

use truth tables to prove logical equivalence.

use truth tables to identify tautologies and contradictions.

identify standard forms of valid and invalid argument.

appreciate the applications of logic in computing.

You should now attempt the tutorial questions and Maple questions on GCU Learn

The next unit provides an introduction to number systems and discusses how numbers are represented by computers.

7. Proofs using laws of logic (logical equivalences) (OPTIONAL)

8. Arguments

Modus ponens

Modus tollens

Hypothetical syllogism (transitive reasoning)

Disjunctive syllogism

Logical Fallacies

Fallacy of the converse

Fallacy of the inverse

Fallacy of the false chain

9. Applications of laws of logic in computing

9.1. Logic in programming

9.2. System specifications

9.3. Inequalities and De Morgan’s Laws

Summary