Propositional Logic

Section 1.1 Propositional Logic

Mathematical or symbolic logic is an analytical theory of the art of reasoning whose goal is to systematize and codify principles of valid reasoning. It has emerged from a study of the use of language in argument and persuasion and is based on the identification and examination of those parts of language which are essential for these purposes. It is formal in the sense that it lacks reference to meaning. Thereby it achieves versatility: it may be used to judge the correctness of a chain of reasoning (in particular, a "mathematical proof") solely on the basis of the form (and not the content) of the sequence of statements which make up the chain. There is a variety of symbolic logics. We shall be concerned only with that one which encompasses most of the deductions of the sort encountered in mathematics. Within the context of logic itself, this is "classical" symbolic logic.

🔗

Section objectives:

🔗

After completing this section, students will be able to:-

🔗

Identify the difference between proposition and sentence.
🔗

🔗
Describe the five logical connectives.
🔗

🔗
Determine the truth values of propositions using the rules of logical connectives.
🔗

🔗
Construct compound propositions using the five logical connectives.
🔗

🔗
Identify the difference between the converse and contrapositive of conditional statements.
🔗

🔗
Determine the truth values of compound propositions.
🔗

🔗
Distinguish a given compound proposition is whether tautology or contradiction.
🔗

🔗

🔗

Subsection 1.1.1 Definition and examples of propositions

Consider the following sentences.

🔗

2 is an even number.
🔗

🔗
A triangle has four sides.
🔗

🔗
Athlete Haile G/silassie weighed 45 kg when he was 20 years old.
🔗

🔗
May God bless you!
🔗

🔗
Give me that book.
🔗

🔗
What is your name?
🔗

🔗

🔗

The first three sentences are declarative sentences. The first one is true and the second one is false. The truth value of the third sentence cannot be ascertained because of lack of historical records but it is, by its very form, either true or false but not both. On the other hand, the last three sentences have no truth value. So they are not declaratives.

🔗

Now we begin by examining proposition, the building blocks of every argument. A proposition is a sentence that may be asserted or denied. Proposition in this way are different from questions, commands, and exclamations. Neither questions, which can be asked, nor exclamations, which can be uttered, can possibly be asserted or denied. Only propositions assert that something is (or is not) the case, and therefore only they can be true or false.

🔗

Definition 1.1.1.

A proposition (or statement) is a sentence which has a truth value (either True or False but not both).

🔗

The above definition does not mean that we must always know what the truth value is. For example, the sentence “The \(\text{1000}^\text{th}\) digit in the decimal expansion of \(\pi\) is 7” is a proposition, but it may be necessary to find this information in a Web site on the Internet to determine whether this statement is true. Indeed, for a sentence to be a proposition (or a statement), it is not a requirement that we are able to determine its truth value.

🔗

Every proposition has a truth value, namely true (denoted by T) or false (denoted by F).

🔗

Checkpoint 1.1.2.

Add review

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FDefinition-and-examples-of-propositions%2FDetermine-which-statements-are-true.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-definition-and-examples-of-propositions.ptx

🔗

Checkpoint 1.1.3.

Add review

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FDefinition-and-examples-of-propositions%2FPropositional-definitions.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-definition-and-examples-of-propositions.ptx

🔗

Checkpoint 1.1.4.

Add review

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FDefinition-and-examples-of-propositions%2FUsing-definition-of-statement-to-say-whether-or-not-the-sentences-are-statements.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-definition-and-examples-of-propositions.ptx

🔗

Checkpoint 1.1.5.

Add review

⁴

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FDefinition-and-examples-of-propositions%2FEvaluating-Statements-and-Truth-Values.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-definition-and-examples-of-propositions.ptx

🔗

Subsection 1.1.2 Logical connectives

In mathematical discourse and elsewhere one constantly encounters declarative sentences which have been formed by modifying a statement with the word “not” or by connecting statements with the words “and”, “or”, “if . . . then (or implies)”, and “if and only if”. These five words or combinations of words are called propositional connectives.

🔗

Note 1.1.6.

Letters such as \(p,q,r,s\) etc. are usually used to denote propositions.

🔗

Conjunction.

When two propositions are joined with the connective “and,” the proposition formed is a logical conjunction. “and” is denoted by \(“^”\text{.}\) So, the logical conjunction of two propositions, \(p\) and \(q\text{,}\) is written:

🔗

\begin{equation*} p\text{^}q,\, \text{read as} \, \text{"p and q" or "p conjunction q".} \end{equation*}

🔗

p and q are called the components of the conjunction. \(p\text{^}q\) is true if and only if \(p\) is true and \(q\) is true.

🔗

The truth table for conjunction is given as follows:

🔗

\(p\)	\(q\)	\(p\text{^}q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)

Example 1.1.7.

Consider the following propositions:

🔗

\(p\text{:}\) 3 is an odd number. (True)

🔗

\(q\text{:}\) 27 is a prime number. (False)

🔗

\(r\text{:}\) Addis Ababa is the capital city of Ethiopia. (True)

🔗

\(p \land q\text{:}\) 3 is an odd number and 27 is a prime number. (False)
🔗

🔗
\(p \land r\text{:}\) 3 is an odd number and Addis Ababa is the capital city of Ethiopia. (True)
🔗

🔗

🔗

Disjunction.

When two propositions are joined with the connective “or,” the proposition formed is called a logical disjunction. “or” is denoted by “\(\vee\)”. So, the logical disjunction of two propositions, \(p\) and \(q\text{,}\) is written:

🔗

\(p \vee q\text{,}\) read as “\(p\) or \(q\)” or “\(p\) disjunction \(q\)”.

🔗

\(p \vee q\) is false if and only if both \(p\) and \(q\) are false.

🔗

The truth table for disjunction is given as follows:

🔗

\(p\)	\(q\)	\(p \vee q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)

Example 1.1.8.

Consider the following propositions:

🔗

\(p\text{:}\) 3 is an odd number. (True)

🔗

\(q\text{:}\) 27 is a prime number. (False)

🔗

\(s\text{:}\) Nairobi is the capital city of Ethiopia. (False)

🔗

\(p \vee q\text{:}\) 3 is an odd number or 27 is a prime number. (True)
🔗

🔗
\(p \vee s\text{:}\) 27 is an odd number or Nairobi is the capital city of Ethiopia. (False)
🔗

🔗

🔗

Note 1.1.9.

The use of “or” in propositional logic is rather different from its normal use in the English language. For example, if Solomon says, “I will go to the football match in the afternoon or I will go to the cinema in the afternoon,” he means he will do one thing or the other, but not both. Here “or” is used in the exclusive sense. But in propositional logic, “or” is used in the inclusive sense; that is, we allow Solomon the possibility of doing both things without him being inconsistent.

🔗

Implication.

When two propositions are joined with the connective “implies,” the proposition formed is called a logical implication. “implies” is denoted by “\(\rightarrow\)” So, the logical implication of two propositions, \(p\) and \(q\text{,}\) is written:

🔗

\begin{equation*} p \Longrightarrow q \text{ read as } \, \text{"}p \text{ implies } q\text{"}\text{.} \end{equation*}

🔗

The function of the connective “implies” between two propositions is the same as the use of “If … then …” Thus \(p \Longrightarrow q\) can be read as “if \(p\text{,}\) then \(q\text{.}\)”

🔗

\(p \Longrightarrow q\ \)is false if and only if \(p\) is true and \(q\) is false.

🔗

This form of a proposition is common in mathematics. The proposition \(p\) is called the hypothesis or the antecedent of the conditional proposition \(p \Longrightarrow q\) while \(q\) is called its conclusion or the consequent.

🔗

The following is the truth table for implication.

🔗

\(p\)	\(q\)	\(p \Longrightarrow q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(T\)

Example 1.1.10.

Consider the following propositions:

🔗

\(p\text{:}\) 3 is an odd number. (True)

🔗

\(q\text{:}\) 27 is a prime number. (False)

🔗

\(r\text{:}\) Addis Ababa is the capital city of Ethiopia. (True)

🔗

\(p \Longrightarrow q\text{:}\) If 3 is an odd number, then 27 is a prime number. (False)
🔗

🔗
\(p \Longrightarrow r\text{:}\) If 3 is an odd number, then Addis Ababa is the capital city of Ethiopia. (True)
🔗

🔗

🔗

We have already mentioned that \(p \Longrightarrow q\) can be expressed as both “If \(p\text{,}\) then \(q\)” and “\(p\) implies \(q\text{.}\) ” There are various ways of expressing the proposition \(p \Longrightarrow q\text{,}\) namely:

🔗

\(\qquad \qquad \text{ If } p, \, \text{ then } \, q\text{.}\)

🔗

\(\qquad \qquad q\, \text{ if } \, p\text{.}\)

🔗

\(\qquad \qquad p \text{ implies } q\text{.}\)

🔗

\(\qquad \qquad p \text{ only if } q\text{.}\)

🔗

\(\qquad \qquad p \text{ is sufficient for } q\text{.}\)

🔗

\(\qquad \qquad q \text{ is necessary for } p\text{.}\)

🔗

Bi-Implication.

When two propositions are joined with the connective “bi-implication,” the proposition formed is called a logical bi-implication or a logical equivalence. A bi-implication is denoted by “\(\Leftrightarrow\)”. So the logical bi-implication of two propositions, \(p\) and \(q\text{,}\) is written:

🔗

\begin{equation*} p \Longleftrightarrow q\text{.} \end{equation*}

🔗

\(p \Longleftrightarrow q\) is false if and only if \(p\) and \(q\) have different truth values.

🔗

The truth table for bi-implication is given by:

🔗

\(p\)	\(q\)	\(p \Longleftrightarrow q\)
\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)

Example 1.1.11.

Let
🔗

\(p\text{:}\) 2 is greater than 3. (False)
🔗

Let \(q\text{:}\) 5 is greater than 4. (True)
🔗

Then
🔗

\(p \Longleftrightarrow q\text{:}\) 2 is greater than 3 if and only if 5 is greater than 4. (False)
🔗

🔗
Consider the following propositions:
🔗

\(p\text{:}\) 3 is an odd number. (True)
🔗

\(q\text{:}\) 2 is a prime number. (True)
🔗

\(p \Longleftrightarrow q\text{:}\) 3 is an odd number if and only if 2 is a prime number. (True)
🔗

🔗

🔗

There are various ways of stating the proposition \(p \Longleftrightarrow q\text{.}\)

🔗

\(p\) if and only if \(q\) (also written as \(p\) iff \(q\)),

🔗

\(p\) implies \(q\) and \(q\) implies \(p\text{,}\)

🔗

\(p\) is necessary and sufficient for \(q\)

🔗

\(q\) is necessary and sufficient for \(p\)

🔗

\(p\) is equivalent to \(q\)

🔗

Negation.

Given any proposition \(p\text{,}\) we can form the proposition \(\neg p\) called the negation of \(p\text{.}\) The truth value of \(\neg p\) is \(F\) if \(p\) is \(T\) and \(T\) if \(p\) is \(F\).

🔗

We can describe the relation between \(p\) and \(\neg p\) as follows.

🔗

\(p\)	\(\neg p\)
\(T\)	\(F\)
\(F\)	\(T\)

Example 1.1.12.

Let

🔗

\(p\text{:}\) Addis Ababa is the capital city of Ethiopia. (True)

🔗

\(\neg p\text{:}\) Addis Ababa is not the capital city of Ethiopia. (False)

🔗

Exercises Exercises

1.

Which of the following sentences are propositions? For those that are, indicate the truth value.

123 is a prime number.
🔗

🔗
0 is an even number.
🔗

🔗
\(x^{2} - 4 = 0\text{.}\)
🔗

🔗
Multiply \(5x + 2\) by 3.
🔗

🔗
What an impossible question!
🔗

🔗

🔗

2.

State the negation of each of the following statements.

\(\sqrt{2}\) is a rational number.
🔗

🔗
0 is not a negative integer.
🔗

🔗
111 is a prime number.
🔗

🔗

🔗

3.

Let \(p\text{:}\) 15 is an odd number.

🔗

\(q\text{:}\) 21 is a prime number.

🔗

State each of the following in words, and determine the truth value of each.

\(p \vee q\text{.}\)
🔗

🔗
\(p \land q\text{.}\)
🔗

🔗
\(\neg p \vee q\text{.}\)
🔗

🔗
\(p \land \neg q\text{.}\)
🔗

🔗
\(p \Longrightarrow q\text{.}\)
🔗

🔗
\(q \Longrightarrow p\text{.}\)
🔗

🔗
\(\neg p \Longrightarrow \neg q\text{.}\)
🔗

🔗
\(\neg q \Longrightarrow \neg p\text{.}\)
🔗

🔗

🔗

4.

Complete the following truth table.

🔗

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

🔗

Checkpoint 1.1.13.

Add review

⁵

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FLogical-connectives%2FGive-statement-forms-of-the-axioms-of-an-enigma-and-answer-to-an-enigma-.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-logical-connectives.ptx

🔗

Checkpoint 1.1.14.

Add review

⁶

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FLogical-connectives%2FTruth-Tables-and-Logical-Connectives-Interchanging-Operators-and-Analyzing-Patterns.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-logical-connectives.ptx

🔗

Checkpoint 1.1.15.

Add review

⁷

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FLogical-connectives%2FTruth-tables-for-logical-operators.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-logical-connectives.ptx

🔗

Subsection 1.1.3 Compound (or complex) propositions

So far, what we have done is simply to define the logical connectives, and express them through algebraic symbols. Now we shall learn how to form propositions involving more than one connective, and how to determine the truth values of such propositions.

🔗

Definition 1.1.16.

The proposition formed by joining two or more proposition by connective(s) is called a compound statement.

🔗

Note 1.1.17.

We must be careful to insert the brackets in proper places, just as we do in arithmetic. For example, the expression \(p \Longrightarrow q \land r\) will be meaningless unless we know which connective should apply first. It could mean \((p \Longrightarrow q) \land r\) or \(p \Longrightarrow (q \land r)\text{,}\) which are very different propositions. The truth value of such complicated propositions is determined by systematic applications of the rules for the connectives.

🔗

The possible truth values of a proposition are often listed in a table, called a truth table. If \(p\) and \(q\) are propositions, then there are four possible combinations of truth values for \(p\) and \(q\text{.}\) That is, \(TT\text{,}\) \(TF\text{,}\) \(FT\) and \(FF\text{.}\) If a third proposition \(r\) is involved, then there are eight possible combinations of truth values for \(p\text{,}\)\(q\) and \(r\text{.}\) In general, a truth table involving “\(n\)” propositions \(p_{1}\text{,}\)\(\ p_{2}\text{,}\)…,\(\ p_{n}\) contains \(2^{n}\) possible combinations of truth values. So, we use truth tables to determine the truth value of a compound proposition based on the truth value of its constituent component propositions.

🔗

Example 1.1.18.

Suppose \(p\) and \(q\) are true and \(r\) is false.
🔗
What is the truth value of \((p \land q) \Longrightarrow (r \vee s)\text{?}\)
1. Since \(p\) is true and \(q\) is false, \(p \land q\) is true.
  🔗
  
  🔗
2. Since \(r\) is true and \(s\) is false, \((r \land q)\) true.
  🔗
  
  🔗
3. Thus, by applying the rule of implication, we get that \((p \land q) \Longrightarrow (r \vee s)\) is true.
  🔗
  
  🔗
🔗
🔗
Suppose that a compound proposition is symbolized by

\begin{equation*} (p \vee q) \Longrightarrow (r \Longleftrightarrow \neg s) \end{equation*}

and that the truth values of \(p,q,r,\) and \(s\) are \(T,F,F,\) and \(T\text{,}\) respectively. Then the truth value of \(p \vee q\) is \(T\text{,}\) that of \(\neg s\) is \(F\text{,}\) that of \(r \Longleftrightarrow \neg s\) is \(T\text{.}\) So the truth value of \((p \vee q) \Longrightarrow (r \Longleftrightarrow \neg s) \) is \(T.\)

🔗

🔗

🔗

Remark 1.1.19.

When dealing with compound propositions, we shall adopt the following convention on the use of parenthesis. Whenever “ \(\vee\) ” or “\(\land\)” occur with “\(\Longrightarrow\)” or “\(\Longleftrightarrow\)”, we shall assume that “\(\vee\)” or “\(\land\)” is applied first, and then “\(\Longrightarrow\)” or “\(\Longleftrightarrow\)” is then applied. For example,

\begin{equation*} p \land q \Longrightarrow r \, \, \text{means} \, \, (p \land q) \Longrightarrow r \end{equation*}

\begin{equation*} p \vee q \Longleftrightarrow r \, \, \text{means} \, \, (p \vee q)\Longleftrightarrow r \end{equation*}

\begin{equation*} \neg q \Longrightarrow \neg p \, \, \text{means} \, \, (\neg q) \Longrightarrow (\neg p) \end{equation*}

\begin{equation*} \neg q \Longrightarrow p \Longleftrightarrow r \, \, \text{means} \, \, ((\neg q) \Longrightarrow p)\Longleftrightarrow r \end{equation*}

However, it is always advisable to use brackets to indicate the order of the desired operations.

🔗

Definition 1.1.20.

Two compound propositions \(P\) and \(Q\) are said to be equivalent if they have the same truth value for all possible combinations of truth values for the component propositions occurring in both \(P\) and \(Q\text{.}\) In this case we write \(P \equiv Q\text{.}\)

🔗

Example 1.1.21.

Let P:\(p \Longrightarrow q\text{.}\)

🔗

Q:\(\neg p \Longrightarrow \neg q\text{.}\)

🔗

\(p\)	\(q\)	\(\neg p\)	\(\neg q\)	\(p \Longrightarrow q\)	\(\neg p \Longrightarrow \neg q\)
\(T\)	\(T\)	\(F\)	\(F\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)

Then, P is equivalent to Q, since columns 5 and 6 of the above table are identical.

🔗

Example 1.1.22.

Let P:\(p \Longrightarrow q\text{.}\)

🔗

Q:\(\neg p \Longrightarrow \neg q\text{.}\)

🔗

\(p\)	\(q\)	\(\neg p\)	\(\neg q\)	\(p \Longrightarrow q\)	\(\neg p \Longrightarrow \neg q\)
\(T\)	\(T\)	\(F\)	\(F\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)

Looking at columns 5 and 6 of the table we see that they are not identical. Thus \(P \not\equiv Q\text{.}\) It is useful at this point to mention the non-equivalence of certain conditional propositions. Given the conditional \(p \Longrightarrow q\text{,}\) we give the related conditional propositions:-

\begin{equation*} q \Longrightarrow p:\, \, \, \, \, \text{Converse of}\, \, p \Longrightarrow q \end{equation*}

\begin{equation*} \neg p \Longrightarrow \neg q:\, \,\, \text{Inverse of}\, \, p \Longrightarrow q \end{equation*}

\begin{equation*} \neg q \Longrightarrow \neg p:\, \, \, \, \text{Contrapositive of} \, \, p \Longrightarrow q \end{equation*}

🔗

As we observed from example 1.7, the conditional \(p \Longrightarrow q\) and its contrapositve \(\neg q \Longrightarrow \neg p\) are equivalent. On the other hand, \(p \Longrightarrow q \not\equiv q \Longrightarrow p\) and \(p \Longrightarrow q \not\equiv \neg p \Longrightarrow \neg q\text{.}\)

🔗

Do not confuse the contrapositive and the converse of the conditional proposition. Here is the difference:

🔗

Converse: The hypothesis of a converse statement is the conclusion of the conditional statement and the conclusion of the converse statement is the hypothesis of the conditional statement.

🔗

Contrapositive: The hypothesis of a contrapositive statement is the negation of conclusion of the conditional statement and the conclusion of the contrapositive statement is the negation of hypothesis of the conditional statement.

🔗

Example 1.1.23.

If Kidist lives in Ethiopia, then she lives in Addis Ababa.
🔗

Converse: If Kidist lives in Addis Ababa, then she lives in Ethiopia.
🔗

Contrapositive: If Kidist does not live in Ethiopia, then she does not live in Addis Ababa.
🔗

Inverse: If Kidist does not live in Addis Ababa, then she does not live in Ethiopia.
🔗

🔗
If it is morning, then the sun is in the east.
🔗

Converse: If the sun is in the east, then it is morning.
🔗

Contrapositive: If the sun is not in the east, then it is not morning.
🔗

Inverse: If it is not morning, then the sun is not in the east.
🔗

🔗

🔗

Propositions, under the relation of logical equivalence, satisfy various laws or identities, which are listed below.

🔗

Idempotent Laws
1. \(p \equiv p \vee p\text{.}\)
  🔗
  
  🔗
2. \(p \equiv p \land p\text{.}\)
  🔗
  
  🔗
🔗
🔗
Commutative Laws
1. \(p\ \land \ q \equiv q \land p\text{.}\)
  🔗
  
  🔗
2. \(p\ \vee \ q \equiv q \vee p\text{.}\)
  🔗
  
  🔗
🔗
🔗
Associative Laws
1. \(p \land (q \land r) \equiv (p \land q) \land r\text{.}\)
  🔗
  
  🔗
2. \(p \vee (q \vee r) \equiv (p \vee q) \vee r\text{.}\)
  🔗
  
  🔗
🔗
🔗
Distributive Laws
1. \(p \vee (q \land r) \equiv (p \vee q) \land (p \vee r)\text{.}\)
  🔗
  
  🔗
2. \(p \land (q \vee r) \equiv (p \land q) \vee (p \land r)\text{.}\)
  🔗
  
  🔗
🔗
🔗
De Morgan’s Laws
1. \(\neg(p \land q) \equiv \neg p \vee \neg q\text{.}\)
  🔗
  
  🔗
2. \(\neg(p \vee q) \equiv \neg p \land \neg q\text{.}\)
  🔗
  
  🔗
🔗
🔗
Law of Contrapositive \(p \Longrightarrow q \equiv \neg q \Longrightarrow \neg p\)
🔗

🔗
Complement Law \(\neg(\neg p) \equiv p\text{.}\)
🔗

🔗

🔗

Checkpoint 1.1.24.

Add review

⁸

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FCompound-%28or-complex%29-propositions%2FDetermine-which-ones-of-statements-are-tautologies.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-compound-%28or-complex%29-propositions.ptx

🔗

Checkpoint 1.1.25.

Add review

⁹

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FCompound-%28or-complex%29-propositions%2FDetermine-contrapositive%2C-converse%2C-inverse%2C-negation-of-a-condition-statement.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-compound-%28or-complex%29-propositions.ptx

🔗

Subsection 1.1.4 Tautology and contradiction

Definition 1.1.26.

A compound proposition is a tautology if it is always true regardless of the truth values of its component propositions. If, on the other hand, a compound proposition is always false regardless of its component propositions, we say that such a proposition is a contradiction.

🔗

Note 1.1.27.

A proposition that is neither a tautology nor a contradiction is called a contingency.

🔗

Example 1.1.28.

Suppose \(p\) is any proposition. Consider the compound propositions \(p \vee \neg p\) and \(p \land \neg p\text{.}\)
🔗

\(p\) \(\neg p\) \(p \vee \neg p\) \(p \land \neg p\)

\(T\) \(F\) \(T\) \(F\)

\(F\) \(T\) \(T\) \(F\)

Observe that \(p \vee \neg p\) is a tautology while \(p \land \neg p\) is a contradiction.
🔗

🔗
For any propositions \(p\) and \(q\text{.}\) Consider the compound proposition \(p \Longrightarrow (q \Longrightarrow p)\text{.}\) Let us make a truth table and study the situation.
🔗

\(p\) \(q\) \(q \Longrightarrow p\) \(p \Longrightarrow (q \Longrightarrow p)\)

\(T\) \(T\) \(T\) \(T\)

\(T\) \(F\) \(T\) \(T\)

\(F\) \(T\) \(F\) \(T\)

\(F\) \(F\) \(T\) \(T\)

We have exhibited all the possibilities and we see that for all truth values of the constituent propositions, the proposition \(p \Longrightarrow (q \Longrightarrow p)\) is always true. Thus, \(p \Longrightarrow (q \Longrightarrow p)\) is a tautology.
🔗

🔗

\(p\)	\(\neg p\)	\(p \vee \neg p\)	\(p \land \neg p\)
\(T\)	\(F\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)

\(p\)	\(q\)	\(q \Longrightarrow p\)	\(p \Longrightarrow (q \Longrightarrow p)\)
\(T\)	\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(T\)	\(T\)
\(F\)	\(T\)	\(F\)	\(T\)
\(F\)	\(F\)	\(T\)	\(T\)

The truth table for the compound proposition \(\left( p \Longrightarrow q \right) \Longleftrightarrow (p \land \neg q)\text{.}\)

🔗

\(p\)	\(q\)	\(\neg q\)	\(p \land \neg q\)	\(p \Longrightarrow q\)	\(\left( p \Longrightarrow q \right) \Longleftrightarrow (p \land \neg q)\)
\(T\)	\(T\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(F\)

🔗

In example 1.10(c), the given compound proposition has a truth value \(F\) for every possible combination of assignments of truth values for the component propositions \(p\) and \(q\text{.}\) Thus \(\left( p \Longrightarrow q \right) \Longleftrightarrow (p \land \neg q)\) is a contradiction.

🔗

Remark 1.1.29.

In truth table, if a proposition is a tautology, then every line in its column has \(T\) as its entry; if a proposition is a contradiction, every line in its column has \(F\) as its entry.
🔗

🔗
Two compound propositions \(P\) and \(Q\) are equivalent if and only if "\(P\mathbf{\Longleftrightarrow}Q\)" is a tautology.
🔗

🔗

🔗

Exercises Exercises

1.

For statements \(p\text{,}\) \(q\text{,}\) and \(r\text{,}\) use a truth table to show that each of the following pairs of statements are logically equivalent.

\((p \land q) \Longleftrightarrow p\) and \(p \Longrightarrow q\text{.}\)
🔗

🔗
\(p \Longrightarrow (q \vee r)\) and \(\neg q \Longrightarrow (\neg p \vee r)\text{.}\)
🔗

🔗
\((p \vee q) \Longrightarrow r\) and \(\left( p \Longrightarrow q \right) \land (q \Longrightarrow r)\text{.}\)
🔗

🔗
\(p \Longrightarrow (q \vee r)\) and \((\neg r) \Longrightarrow (p \Longrightarrow q)\text{.}\)
🔗

🔗
\(p \Longrightarrow (q \vee r)\) and \(((\neg r) \land p) \Longrightarrow q\text{.}\)
🔗

🔗

🔗

2.

For statements \(p\text{,}\) \(q\text{,}\) and \(r\text{,}\) show that the following compound statements are tautology.

\(p \Longrightarrow (p \vee q)\text{.}\)
🔗

🔗
\((p \land \left( p \Longrightarrow q \right)) \Longrightarrow q\text{.}\)
🔗

🔗
\(\left( \left( p \Longrightarrow q \right) \land \left( q \Longrightarrow r \right) \right) \Longrightarrow (p \Longrightarrow r)\text{.}\)
🔗

🔗

🔗

3.

For statements \(p\) and \(q\text{,}\) show that \(\left( p \land \neg q \right) \land (p \land q)\) is a contradiction.

🔗

4.

Write the contrapositive and the converse of the following conditional statements.

If it is cold, then the lake is frozen.
🔗

🔗
If Solomon is healthy, then he is happy.
🔗

🔗
If it rains, Tigist does not take a walk.
🔗

🔗

🔗

5.

Let \(p\) and \(q\) be statements. Which of the following implies that \(p \vee q\) is false?

\(\neg p \vee \neg q\) is false.
🔗

🔗
\(\neg p \vee q\) is true.
🔗

🔗
\(\neg p \land \neg q\) is true.
🔗

🔗
\(p \Longrightarrow q\) is true.
🔗

🔗
\(p \land q\) is false.
🔗

🔗

🔗

6.

Suppose that the statements \(p,q,r,\) and \(s\) are assigned the truth values \(T,F,F,\) and \(T\text{,}\) respectively. Find the truth value of each of the following statements.

\((p \vee q) \vee r\text{.}\)
🔗

🔗
\(p \vee (q \vee r)\text{.}\)
🔗

🔗
\(r \Longrightarrow (s \land p)\text{.}\)
🔗

🔗
\(p \Longrightarrow (r \Longrightarrow s)\text{.}\)
🔗

🔗
\(p \Longrightarrow (r \vee s)\text{.}\)
🔗

🔗
\((p \vee r) \Leftrightarrow (r \vee \neg s)\text{.}\)
🔗

🔗
\((s \Leftrightarrow q) \Longrightarrow (\neg p \vee s)\text{.}\)
🔗

🔗
\(\displaystyle (q \land \neg s) \Longrightarrow (p \Leftrightarrow s)\)
🔗

🔗
\(\displaystyle (r \land s) \Longrightarrow (p \Longrightarrow (\neg q \vee a)) \)
🔗

🔗
\(\displaystyle (p \vee \neg q) \vee r \Longrightarrow (s \land \neg s) \)
🔗

🔗

🔗

7.

Suppose the value of \(p \rightarrow q\) is \(T\text{;}\) what can be said about the value of \(\neg p \land q \Leftrightarrow p \vee q\text{?}\)

🔗

8.

Suppose the value of \(p \Leftrightarrow q\) is \(T\text{;}\) what can be said about the value of \(p \Leftrightarrow \neg q \) and \(\neg p \Leftrightarrow q\text{?}\)
🔗

🔗
Suppose the value of \(p \Leftrightarrow q\) is \(F\text{;}\) what can be said about the value of \(p \Leftrightarrow \neg q\) and \(\neg p \Leftrightarrow q\text{?}\)
🔗

🔗

🔗

9.

Construct the truth table for each of the following statements.

\(\displaystyle p \Longrightarrow (p \Longrightarrow q) \)
🔗

🔗
\(\displaystyle (p \vee q) \Leftrightarrow (q \vee p) \)
🔗

🔗
\(\displaystyle p \Longrightarrow \neg (q \land r) \)
🔗

🔗
\(\displaystyle (p \Longrightarrow q) \Leftrightarrow (q \vee p) \)
🔗

🔗
\(\displaystyle (p \Longleftrightarrow (q \land r)) \vee (\neg p \land q) \)
🔗

🔗
\(\displaystyle (p \land q) \Longrightarrow ((q \land \neg q) \Longrightarrow (r \land q)) \)
🔗

🔗

🔗

10.

For each of the following determine whether the information given is sufficient to decide the truth value of the statement. If the information is enough, state the truth value. If it is insufficient, show that both truth values are possible.

\((p \Longrightarrow q) \Longrightarrow r\text{,}\) where \(r = T\text{.}\)
🔗

🔗
\(p \land (q \Longrightarrow r)\text{,}\) where \(q \Longrightarrow r = T\text{.}\)
🔗

🔗
\(p \vee (q \Longrightarrow r)\text{,}\) where \(q \Longrightarrow r = T\text{.}\)
🔗

🔗
\(\neg ( p \vee q ) \Longleftrightarrow (\neg p \land \neg q)\text{,}\) where \(p \vee q = T\text{.}\)
🔗

🔗
\(\left( p \Longrightarrow q \right) \Longrightarrow (\neg q \Longrightarrow \neg p)\text{,}\) where \(q = T\text{.}\)
🔗

🔗
\(\left( p \land q \right) \Longrightarrow (p \vee s)\text{,}\) where \(p = T\) and \(s = F\text{.}\)
🔗

🔗

🔗

Checkpoint 1.1.30.

Add review

¹⁰

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FTautology-and-contradiction%2FDetermine-which-ones-of-statements-are-tautologies.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-tautology-and-contradiction.ptx

🔗

Checkpoint 1.1.31.

Add review

¹¹

docs.google.com/forms/d/e/1FAIpQLSfSNI6CXkmgeSZJh6v0WKkeD9MJ9g4pEQ9r0JaowD4ovNxj5w/viewform?usp=pp_url&entry.699375810=questions%2Ftop%2FMathematics-for-NS-%26-SS-23-24-Question-Bank%2FPropositional-Logic-and-Set-Theory-%28NS-and-SS%29%2FTautology-and-contradiction%2FDetermine-contrapositive%2C-converse%2C-inverse%2C-negation-of-a-condition-statement.xml&entry.2077830997=source%2Fpropositional-logic-and-set-theory%2Fsections%2Fsubsections%2Fsec-propositional-logic%2Fsubsec-tautology-and-contradiction.ptx

🔗

Prev Top Next