Chapter 3 Introduction to Logic
3.1 Statement (Proposition)
- A statement is a declarative sentence which is either true or false but not both
- A proposition is a collection of declarative statements that has either a truth value “true” or a truth value “false”.
- The truth value True and False are denoted by the symbols T and F, respectively.
- Sometimes it is also denoted by 1 (stands for true) and 0 (stands for false).
- Since it depends on only two possible truth values, it is known as two-values logic of bi-values logic.
Example 1
Consider the following sentences and select the statements
- Man is Mortal
- 12 plus 9 is equal to 1
- Moon rises in the east
- 3 is less than four
- Please sit down
- \(y\) is a cat
- 14 is a composite number
- Chaddy is a nice dog.
3.2 Propositional Variables
- Every statement in propositional logic consists of propositional variables combined via propositional connectives.
- Propositional variables are usually denoted by capital English letters, such as P, Q, R etc.
- Each variable can take one of two values: T or F.
3.3 Logical Connectives
- We use logical connectives to connect the propositional variables (several statements into a single statement).
- The most basic and fundamental connectives are Negation, Conjunction and Disjunction.
3.3.1 Negation
- Negation is the simplest common example of a truth-functional operation.
- The negation of a statement is also a statement.
- We use the connective Not for negation.
- If \(P\) be a statement, then the negation of \(P\) is denoted by \(\neg P\).
- \(P\) and \(\neg P\) has opposite truth values.
- The relationship between the truth values of \(P\) and \(\neg P\) can be made explicit by a diagram called a truth table
Truth Table (Negation)
| \(P\) | \(\neg P\) |
|---|---|
| \(T\) | \(F\) |
| \(F\) | \(T\) |
3.3.2 Conjunction
- The conjunction of two statements, \(P\) and \(Q\) is also a statement.
- We use the connective And (\(\land\)) for conjunction.
- It is denoted by \(P \land Q\)
Truth Table (Conjunction)
| \(P\) | \(Q\) | \((P \land Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) |
Rule: \((P \land Q)\) is true if both \(P\) and \(Q\) are true, otherwise false.
- In order to make \((P \land Q)\) true, \(P\) and \(Q\) have to be simultaneously true
3.3.3 Disjunction
- The disjunction of two statements, \(P\) and \(Q\) is also a statement.
- We use the connective Or (\(\lor\)) for disjunction
- It is denoted by \(P \lor Q\)
Truth Table (Disjunction)
| \(P\) | \(Q\) | \((P \lor Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
Rule: \((P \lor Q)\) is true if either \(P\) or \(Q\) is true and it is false when both \(P\) and \(Q\) are false.
- \((P \lor Q)\) shall stand for “\(P\) or \(Q\) or both”.
3.4 Conditional
- In mathematics, expressions of the form “IF \(P\) then \(Q\)” occur so often.
- This can be expressed in any one of the following forms.
- If \(P\), then \(Q\)
- \(P\) only if \(Q\)
- \(P\) implies \(Q\)
- \(Q\) if \(P\)
- Therefore, it is important to understand the corresponding truth-functional operation.
- Let \(P\) and \(Q\) be any two statements.
- Then the statement \(P \rightarrow Q\) is called a conditional statement.
- In an implication \(P \rightarrow Q\), \(P\) is called the antecedent (hypothesis) and \(Q\) is called the consequent (conclusion).
Truth Table (Conditional)
| \(P\) | \(Q\) | \((P \rightarrow Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
Rule: An implication (conditional) \((P \rightarrow Q)\) is False only when the hypothesis (\(P\)) is true and conclusion (\(Q\)) is false, otherwise True.
3.5 Bi-Conditional
- Let \(P\) and \(Q\) be any two statements.
- Then the statement \(P \leftrightarrow Q\) is called a bi-conditional statement.
- This can be expressed in any one of the following forms.
- \(P\) if and only if \(Q\)
- \(P\) is necessary and sufficient of \(Q\)
- \(P\) is necessary and sufficient for \(Q\)
- \(P\) implies \(Q\) and \(P\) is implied by \(Q\)
- The bi-conditional (double implication) \(P \leftrightarrow Q\) can be defined as
\[P \leftrightarrow Q: (P \rightarrow Q) \land (Q \rightarrow P)\]
Truth Table (Bi-Conditional)
| \(P\) | \(Q\) | \((P \rightarrow Q)\) | \((Q \rightarrow P)\) | \((P \leftrightarrow Q)\) |
|---|---|---|---|---|
| \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
Rule: \((P \leftrightarrow Q)\) is True only when both \(P\) and \(Q\) have identical truth values, otherwise false.
3.6 Converse
- Let \(P\) and \(Q\) be any two statements.
- The converse statement of the conditional \(P \rightarrow Q\) is given as \(Q \rightarrow P\)
3.7 Inverse
- Let \(P\) and \(Q\) be any two statements.
- The inverse statement of the conditional \((P \rightarrow Q)\) is given as \((\lnot P \rightarrow \lnot Q)\)
3.8 Contra Positive
- Let \(P\) and \(Q\) be any two statements.
- The contra positive statement of the conditional \((P \rightarrow Q)\) is given as \((\lnot Q \rightarrow \lnot P)\)
Truth Table (Contra Positive)
| \(P\) | \(Q\) | \(P \rightarrow Q\) | \(\lnot Q\) | \(\lnot P\) | \((\lnot Q \rightarrow \lnot P)\) |
|---|---|---|---|---|---|
| \(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(T\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
- From the truth table it can be seen that both conditional \(P \rightarrow Q\) and contra positive \((\lnot Q \rightarrow \lnot P)\) have same truth values.
3.9 Exclusive OR
- Let \(P\) and \(Q\) be any two statements.
- The exclusive OR of two statements \(P\) and \(Q\) is denoted by \((P \overline{\lor} Q)\).
- We use the connective XOR for exclusive OR
- The exclusive OR \((P \overline{\lor} Q)\) is true if either \(P\) or \(Q\) is True but not both.
- The exclusive OR is also known as exclusive disjunction.
the conditional \((P \rightarrow Q)\) is given as \((\lnot Q \rightarrow \lnot P)\)
Truth Table (Exclusive OR)
| \(P\) | \(Q\) | \((P \overline{\lor}Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(F\) |
Rule: \((P \overline{\lor}Q)\) is true if either \(P\) or \(Q\) is True but not both, otherwise false.
3.10 NAND
- The word NAND stands for NOT and AND.
- The connective NAND is denoted by the symbol \(\uparrow\).
- Let \(P\) and \(Q\) be any two statements.
- The NAND of \(P\) and \(Q\) is denoted by \((P \uparrow Q)\).
- The NAND, \((P \uparrow Q)\) can be defined as
\[(P\uparrow Q)\equiv\lnot(P \land Q)\]
Truth Table (NAND)
| \(P\) | \(Q\) | \((P \uparrow Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(T\) |
| \(F\) | \(T\) | \(T\) |
| \(F\) | \(F\) | \(T\) |
Rule: \((P \uparrow Q)\) is True if either \(P\) or \(Q\) is false, otherwise False
3.11 NOR
- The word NOR stands for NOT and OR.
- The connective NOR is denoted by the symbol \(\downarrow\).
- Let \(P\) and \(Q\) be any two statements.
- The NOR of \(P\) and \(Q\) is denoted by \((P \downarrow Q)\).
- The NOR, \((P \downarrow Q)\) can be defined as
\[(P\downarrow Q)\equiv\lnot(P \lor Q)\]
Truth Table (NOR)
| \(P\) | \(Q\) | \((P \downarrow Q)\) |
|---|---|---|
| \(T\) | \(T\) | \(F\) |
| \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(T\) |
Rule: \((P \downarrow Q)\) is True only when both \(P\) or \(Q\) are false, otherwise False
3.12 Tautology
- If the truth values of a composite statement are always true, irrespective of the truth values of the atomic (individual) statements, then it is a tautology.
Example
- The composite statement \((P\land (P \rightarrow Q)) \rightarrow Q\) is a tautology.
- Verify this using a truth table with composite statement as \((P\land (P \rightarrow Q)) \rightarrow Q\)
3.13 Contradiction
- If the truth values of a composite statement are always false, irrespective of the truth values of the atomic (individual) statements, then it is a contradiction or unsatisfiable.
Example
- The composite statement \(\lnot(P\rightarrow(Q\rightarrow(P\land Q)))\) is a contradiction.
- Verify this using a truth table with composite statement as \(\lnot(P\rightarrow(Q\rightarrow(P\land Q)))\)
3.14 Satisfiable
- If the truth values of a composite statement are sometimes true and sometimes false, irrespective of the truth values of the atomic statements, then it is called a satisfiable.
Example
- The composite statement \((P \rightarrow Q) \rightarrow (Q \rightarrow P)\) is satisfiable.
- Verify this using a truth table of \((P \rightarrow Q) \rightarrow (Q \rightarrow P)\)
3.15 Duality Law
- Two formulae \(P\) and \(p^*\)are said to be duals of each other if either one can be obtained from the other by interchanging \(\land\) by \(\lor\) and \(\lor\) by \(\land\).
- The two connectives \(\lor\) and \(\land\) are called dual to each other.
Example
The formulae \(P \equiv (P \lor Q)\land R\) and \(P^* \equiv (P \land Q)\lor R\) are dual to each other.
3.16 Algebra of Propositions
- If \(P, Q\) and \(R\) be three statements, then the following laws hold.
| Algebra of Propositions | |
|---|---|
| Commutative Laws | \(P\land Q\equiv Q \land P\) and \(P\lor Q\equiv Q \lor P\) |
| Associative Laws | \(P\land (Q \land R)\equiv (P\land Q) \land R\) and \(P\lor (Q \lor R)\equiv (P\lor Q) \lor R\) |
| Distributive Laws | \(P\land (Q \lor R)\equiv (P\land Q) \lor (P\land R)\) and \(P\lor (Q \land R)\equiv (P\lor Q) \land (P\lor R)\) |
| Idempotent Laws | \(P\land P\equiv P\) and \(P\lor P\equiv P\) |
| Absorption Laws | \(P\lor (P \land Q)\equiv P\) and \(P\land (P \lor Q)\equiv P\) |
| De Morgan’s Laws | \(\lnot (P\land Q) \Leftrightarrow (\lnot P) \lor(\lnot Q)\) and \(\lnot (P\lor Q) \Leftrightarrow (\lnot P) \land (\lnot Q)\) |
3.17 Logical Implication and Equivalence
3.18 Necessary and Sufficient Conditions
3.18.1 Necessary Condition
3.18.2 Sufficient Condition
3.18.3 Necessary and Sufficient Condition
References
Acharjya, D. P. (2009). Fundamental approach to discrete mathematics. New Age International.
Mendelson, E. (1970). Boolean algebra and switching circuits. McGraw-Hill Edition 2004.
Tutorial
- Reduce the following sentences to statement forms
A necessary condition for \(x\) to be prime is that \(x\) is odd or \(x=2\).
A sufficient condition for \(f\) to be continuous is that \(f\) is differentiable.
A necessary and sufficient condition for Mr. Perera to be elected is that Mr. Perera wins 75 votes.
Calathea plant will stay healthy only if enough moisture is available.
It is raining but the sun is still shining.
She will die today unless medical aid is obtained.
If taxes are increased or government spending decreases, then inflation will not occur this year.
- Show that the composite statement \((P \land (P \rightarrow Q)) \rightarrow Q\) is a tautology using a truth table
- Show that the composite statement \(\lnot (P \rightarrow( Q \rightarrow (P \land Q)))\) is a contradiction using a truth table
- Show that \((A \rightarrow B) \rightarrow A\) logically implies \(A\)
- Show that \((A \leftrightarrow B)\) is logically equivalent to \((A \rightarrow B) \land (B \rightarrow A)\)
- Find the negation of \(A\rightarrow B\)
- Construct the truth table for \(A \rightarrow ( B\leftrightarrow A \land B).\)
- Find the negation of the following statement “He is rich but unhappy”
- Prove by constructing truth table \[P \rightarrow(Q \lor R) \equiv (P \rightarrow Q) \lor (P \rightarrow R)\]
Find the negation of \(P \leftrightarrow Q.\)
With the help of the truth table prove that \(\lnot (P \land Q) \equiv \lnot P\lor \lnot Q\)
Show that \((P \rightarrow Q) \leftrightarrow (\lnot P \lor Q)\) is a tautology
Show that the following stamens are equivalent.
Statement 1: Good food is not cheap
Statement 2: Cheap food is not good
Express \(P\rightarrow Q\) only using \(\downarrow\) and \(\uparrow\).
Prove that \((P \land Q) \land \lnot (P \lor Q)\) is a contradiction.
Express \(P \leftrightarrow Q\) only using \(\downarrow\) and \(\uparrow\).
Show by truth table the following statement are equivalent
Statement 1: Rich men are unhappy
Statement 2: Men are unhappy or poor
- A constructor promises a client “We will fix it on Monday if it is not raining”. When the constructor would be deemed to have broken his promise. Explain with the help of truth table.
- Eliminate as many parentheses as possible from
- \(\{[(A \lor B)\rightarrow (\lnot C)] \lor [(((\lnot B)\land C)\land B)]\}\)
- \(\{[A \land (\lnot (\lnot B))]\leftrightarrow [B \leftrightarrow (C \lor B)]\}\)
- \([(B\leftrightarrow (C \lor B)) \leftrightarrow (A \land (\lnot (\lnot B)))]\)
20 Show the following are tautologies without using truth tables.
- \(((A \rightarrow B) \rightarrow C) \rightarrow ((C \rightarrow A) \rightarrow(D \rightarrow A )).\)
- \((A \rightarrow B)\rightarrow ((B \rightarrow C) \rightarrow (A \rightarrow C)).\)