Introduction
Logic is the study of reasoning. It is specifically concerned with whether the reasoning is correct. Logic focuses on the relationship among propositions. Consider, for example, the following statement:
All ICT students read variables.
Anyone who read variables is an algebraist.
Therefore, all ICT students are algebraists.
Technically, logic does not help to determine whether any of these propositions is true; however, if the first two propositions are true, logic assures that the third proposition will be true,
i.e., All ICT students are algebraists, is true.
The rules of logic give precise meaning to mathematical propositions. The rules can be used to distinguish valid and invalid mathematical arguments. Therefore, logic is also essential in reading and developing proofs. Besides the importance of logic in understanding mathematical reasoning, and proofs, logic has numerous applications in computer science. These rules are used to design computer circuits, computer programs, and in many other ways. So, we will discuss these applications of logic in this unit.
Example
Consider the interpersonal relations of a small group. There are just four girls – A, B, C, D. Some of the girls like each other, but some do not. The following figure shows one set of possibilities. The figure below shows one possible world. In this world, every girl likes exactly two other girls, and every girl is liked by just two girls.
| A | B | C | D | |
| A | 👧 | 👧 | ||
| B | 👧 | 👧 | ||
| C | 👧 | 👧 | ||
| D | 👧 | 👧 |
There are 216 (65,536) possible combinations of these true-false possibilities, so there are 216 possible worlds. This is where Logic comes in. By writing logical sentences, each informant can express exactly what he or she knows - no more, no less. For our part, we can use the sentences we have been told to draw conclusions that are logically entailed by those sentences. And we can use logical proofs to explain our conclusions to others. Let's consider each of these elements in turn.
Logic भनेको तर्क को अध्ययन हो। यसले विशेष गरी तर्क सही छ वा छैन भनेर अध्ययन गर्छ। Logic ले proposition हरू बीचको सम्बन्धमा अध्ययनलाई केन्द्रित गर्दछ। उदाहरणका लागि, निम्न कथनलाई विचार गर्नुहोस्:
सबै ICT विद्यार्थीहरूले variables (चर) पढ्छन्।
जसले चर पढ्छ उ एक बीजगणितज्ञ हो।
त्यसकारण, सबै ICT विद्यार्थीहरू बीजगणितज्ञ हुन्।
प्राविधिक रूपमा, माथिको उदाहरणमा, Logicले दिएका प्रस्तावहरू मध्ये कुनै पनि सत्य हो कि होइन भनेर निर्धारण गर्दैन। यद्पि, यदि पहिलो दुई प्रस्तावहरू साँचो छन् भने, Logic ले तेस्रो प्रस्ताव सत्य हुनेछ भनेर निर्धारण गर्दछ।
अर्थात्, यदि
सबै ICT विद्यार्थीहरूले variables (चर) पढ्छन्।
जसले चर पढ्छ उ एक बीजगणितज्ञ हो।
सत्य हो भने
सबै ICT विद्यार्थीहरू बीजगणितज्ञ हुन्,
यो पनि सत्य हो।
Logic का नियमहरूले गणितीय प्रस्तावहरूलाई सटीक अर्थ दिन्छ। यस्ता नियमहरूले वैध र अवैध गणितीय तर्कहरू छुट्याउन मद्दत गर्छ। तसर्थ, Theorem हरु पढ्न र विकास गर्न पनि Logic आवश्यक छ। साथै कम्प्युटर विज्ञानमा पनि Logic का धेरै प्रयोगहरू छन्। यसबाट कम्प्युटर सर्किटहरू, कम्प्युटर प्रोग्रामहरू, र अन्य कुराहरु डिजाइन गर्न सकिन्छ। त्यसैले, हामी यस इकाईमा Logic का प्रयोगहरूको बारेमा छलफल गर्नेछौं।
Proposition and Truth function
In English literature, sentences are classified as declarative, exclamatory, interrogative, or imperative. In this unit, we confine our attention to those declarative sentences which has only one truth value either ‘true’ or ‘false’. We call such sentences propositions. It is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. The main importance is that propositions are basic building blocks of logic. We start the concept of a proposition with a few examples.
Example
- The sentence ‘Kathmandu is in Nepal; is true. So it is a statement.
- The sentence “Every rectangle is a square” is false. So it is a statement.
- The sentence “Close the door” can not be assigned true or false. So it is NOT a statement.
- The sentence “How old are you?” can not be assigned true or false. So it is NOT a statement.
- The truth or falsity of the sentence “x is a natural number” depends on the value of x. So it is NOT a statement. However, in some books, it is called an open statement.
- KTM is the capital city of Nepal
- 1 + 1 = 2
- 2 + 2 = 3
- x+2=5
The propositions are denoted by small English letters, for example; a,b,c,d,... For example,
- p: KTM is the capital city of Nepal.
- q: 1 + 1 = 2.
- r: 2 + 2 = 3.
The true value of a proposition is denoted by T, and the false value is denoted by F.
Propositional Logic
The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago. Many mathematical propositions are constructed
by combining one or more propositions.
There are two types of propositions.
- Simple proposition
- Compound proposition
Simple proposition
Simple proposition are single proposition whose truth value does not depend on other proposition. For example,
- p: 2+2=5
- q: 3>1
Compound proposition
Compound proposition is a new propositions formed from existing propositions using logical operators. It is multiple propositions. It is composition of simple propositions whose truth value depends on anchor (connective) proposition. For example,
- p: 2+2=5 and q: 3>1
- q: If battery is low then the light is dim.
Logical Connectives
In logic, compound propositions are formed by connecting two or more simple propositions. To connect the simple proposition, logic utilize connectives. These connectives are also called logical connectives. The common logical connectives are given below.
| SN | Name | Symbol | Word | Meaning |
| 1 | Conjunction |
˄ |
AND | Intersection |
| 2 | Disjunction |
˅ |
OR | Union |
| 3 | Negation | ~ | NOT | Negation |
| 4 | Conditional | → | If,…, Then… | If |
| 5 | Bi-conditional | ↔ | If and only if | Equivalent |
Logical Connectives: Negation
Let p is a simple proposition, then the negation of p is a compound proposition, denoted by ~p and defined by
~p is true if p is false and vice-versa.
The negation of p is the statement “It is not the case that p.” The proposition ~p is read “not p.” The truth value of ~p is the opposite of the truth value of p. This is given below.
Let us consider a proposition p¸ then
| p | ~p |
| T | F |
| F | T |
Negation in Venn-diagram
Negation of words
Let us see an example. We know that "some" means "at least one," therefore, the logical opposite of "some" will be "none." Therefore, the negation of "some" is "none." Now, let's look at other statements.
| Some | None |
| All | NOT All |
| Most | Not more than half (which means half or less, 0-50) |
| Exactly X | NOT Exactly X |
| Never | Sometimes |
Example 1
- Find the negation of a proposition “Gita’s PC runs Linux”
- Find negation of a proposition “Ram’s smartphone has 32GB of memory”
In expressions involving some or all of the operators ~, ∧, and ∨, in the absence of parentheses, we first evaluate ~, then ∧, and then ∨. We call such a convention operator precedence. In algebra, operator precedence tells us to evaluate BODMAS. In logic, it is NCD.
Example 2
Given that proposition p is false, proposition q is true, and proposition r is false, then determine the value of proposition ~p ∨ q ∧ r
Logical Connectives: Conjunction
Let p and q be two simple propositions, then the conjunction of p and q is a compound proposition, denoted by p∧q and defined by
p∧q is true if p is true and q is true.
otherwise, p∧q is false.
In logic “but” can be used instead of “and” in conjunction. For example,
- The sun is shining, but it is raining
- The sun is shining and it is raining
- Here, both propositions are the same.
(In natural language, there is a subtle difference in meaning between “and” and “but”; however, logic will not care about this nuance here.)
The validity of conjunction is described in a table. This table is called the truth table. This is given below.
Let us consider two propositions, p, and q¸then
| p | q | p∧q |
| T | T | |
| T | F | |
| F | T | |
| F | F |
Venn-diagram of Conjunction
Example 1.
Find the conjunction of the propositions p and q where p is “Rita’s PC has more than 16 GB free hard disk space” and q is “The processor in Rita’s PC runs faster than 1 GHz.”
Solution
Let
p =Rita’s PC has more than 16 GB of free hard disk space
q =The processor in Rita’s PC runs faster than 1 GHz
Now,
Conjunction= p˄q
or Conjunction= p and q
Conjunction= “Rita’s PC has more than 16 GB free hard disk space” and “The processor in Rita’s PC runs faster than 1 GHz”
Conjunction= Rita’s PC has more than 16 GB free hard disk space and the processor in her PC runs faster than 1 GHz
The truth table of p∧q is
| p | q | p∧q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Example 2
Ram has a pen and a pencil. Construct a truth table for this proposition.
Solution.
Let
p: Ram has a pen.
q: Ram has a pencil.
Now, the corresponding truth table for the proposition “Ram has a pen and a pencil” is given below.
| p | q | p∧q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Logical Connectives: Disjunction
Let p and q are two simple propositions, then disjunction of p and q is a compound proposition, denoted by p∨q and defined by
p∨q is true if p is true or q is true.
otherwise p∨q is false.
The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the two propositions is true. For instance, the inclusive or is being
used in the statement
“Students who have taken calculus or computer science can take class.”
Here, we mean that students who have taken both calculus and computer science can take the class, as well as the students who have taken
only one of the two subjects.
On the other hand, we are using the exclusive or when we say
“Students who have taken calculus or computer science, but not both, can enroll in class.”
Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class. Similarly, when a menu at a restaurant states, “Soup or salad comes with an entrée,” the restaurant almost always means that customers can have either soup or salad, but not both. Hence, this is an exclusive, rather than an inclusive or.
The validity of disjunction is describe by a table. This table is called truth table. This is given as below.
Let us consider two propositions, p and q¸then
| p | q | p∨q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Venn-diagram of Disjunction
Example 1
Find the disjunction of the propositions p and q where p is the proposition “Rita’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rita’s PC runs faster than 1 GHz.”
Example 2
Ram has a pen or a pencil or a book. Construct a truth table for this proposition.
Solution.
Let
p: Ram has a pen.
q: Ram has a pencil.
r: Ram has a book.
Now, the corresponding truth table for the proposition “Ram has a pen or a pencil or a book” is given as below.
| p | q | r | p∨q∨r |
| T | T | T | T |
| T | T | F | T |
| T | F | T | T |
| T | F | F | T |
| F | T | T | T |
| F | T | F | T |
| F | F | T | T |
| F | F | F | F |
Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.
Logical Connectives: Conditional
Let p and q be two simple propositions, then the conditional of p and q is a compound proposition, denoted by p→q and defined by
p→q is false if p is true and q is false.
otherwise, p→q is true.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). A conditional statement is also called an implication.
A useful way to understand the truth value of a conditional statement is to think of an obligation or a contract. For example, a politician says when asking for a vote is that “If I am elected, then I will make the road pitch.”
In this case,
- If the politician is elected, and he made the road pitch, it is all right.
- If the politician is not elected, and he made the road pitch, it is all right.
- If the politician is not elected, and he does not make the road pitch, it is all right.
- If the politician is elected, and he does not make the road pitch, it is NOT right.
Thus, it is only when the politician is elected but does not pitch the road that voters can say that the politician has broken the assurance. This last scenario corresponds to the case when p is true but q is false in p → q.
The validity of the conditional is described in a table. This table is called the truth table. This is given below.
Let us consider two propositions, p and, then
| p | q | p→q | |
| T | T | T | It is logically true |
| T | F | F | |
| F | T | T | It is vacuously true. (The proposition is true because hypothesis p is false. When a hypothesis is false, the conditional proposition is true regardless of whether the conclusion is true or false.) |
Venn-diagram of Conditional (implication)
Example 1
Let p be the statement “Mira learns discrete mathematics” and q the statement “Mira will find a good job.” Express the statement p → q in the English language.
Solution
p=Mira learns discrete mathematics
q=Mira will find a good job
Now,
p → q:
If p then q
If Mira learns discrete mathematics then Mira will find a good job
If Mira learns discrete mathematics then she will find a good job
Example 2
If you study hard, then you will pass the exam. Construct a truth table for this proposition.
Solution.
Let
p: you study hard.
q: you will pass the exam.
Now, the corresponding truth table for the proposition “If you study hard, then you will pass the exam” is given as below.
| p | q | p→q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
“If Kiran has a smartphone, then 2 + 3 = 5” is true from the definition of a conditional statement, because its conclusion is true. (The truth value of the hypothesis does not matter then.) The conditional statement “If Kiran has a smartphone, then 2 + 3 = 6” is true if Kiran does not have a smartphone, even though 2 + 3 = 6 is false.
Therefore, we would not use conditional statements in natural language, because there is no relationship between the hypothesis and the conclusion in either statement. In mathematical reasoning, the mathematical concept of a conditional statement is independent of a cause-and-effect relationship between the hypothesis and the conclusion. Our definition of a conditional statement specifies its truth values; it is not based on English usage. Propositional language is an artificial language; we only parallel English usage to make it easy to use and remember.
Logical Consequence
ImplicationLet p and q are two simple propositions, and p→q is its conditional proposition, then various other conditional propositions can be formed. These are as follows.
- Converse:
The converse of the conditional proposition
“if p then q” [or p→ q] is “if q then p” [or q → p] - Inverse:
The inverse of the conditional proposition
“if p then q” [or p→ q] is “if ~p then ~ q” [or ~p → ~ q] - Contrapositive:
The contrapositive of the conditional proposition
“if p then q” [or p→ q] is “if ~ q then ~ p” [or ~ q → ~ p]
| Implication p→q If p then q |
Converse q→p If q then p |
| Inverse ~p→~q If ~p then ~q |
Contrapositive ~q→~p If ~q then ~p |
Example 1
“If you study hard, then you will pass the exam”. Construct all possible conditional propositions.
Solution.
Given conditional proposition is
“If you study hard, then you will pass the exam”.
So, let
p: you study hard.
q: you will pass the exam.
Now, all possible conditional propositions are given below.
- Conditional
p → q
If p then q
If… then…
If you study hard then you will pass the exam. - Converse
q → p
If q then p
If…then…
If you will pass the exam then you study hard. - Inverse
~p → ~q
If ~p then ~q
If… then…
If you do not study hard then you will not pass the exam. - Contrapositive
~q → ~p
If ~ q then ~p
If… then…
If you will not pass the exam then you do not study hard.
Validity of Logical Consequences of a conditional proposition
- If conditional proposition p → q is true then contrapositive ~q→ ~p is true and vice-versa. A separate truth table is not necessary.
- If convers proposition q → p is true then inverse ~p→~ q is true and vice-versa. A separate truth table is not necessary.
- If conditional proposition p → q is true then converse q → p (or inverse ~p→~ q) may be true or may be false. So, a separate truth table is necessary.
Example 2.
“If it is a square, then it is a rectangle”. Construct all possible conditional propositions. Also, inspect the validity.
let
p: it is a square.
q: it is a rectangle.
- Conditional
p → q
If p then q
If… then…
If it is a square then it is a rectangle. (T) - Converse
q → p
If q then p
If…then…
If it is a rectangle then it is a square. (F) - Inverse
~p → ~q
If ~p then ~q
If… then…
If it is not square then it is not a rectangle. (F) - Contrapositive
~q → ~p
If ~ q then ~p
If… then…
If it is not a rectangle then it is not square. (T)
Example 3
|
Implication p →q If the quadrilateral is square then the opposite sides are equal. (T) |
Converse q →p If the opposite sides are equal, then the quadrilateral is square. (F) |
| Inverse ~p→~q If the quadrilateral is not square then the opposite sides are not equal. (F) |
Contrapositive ~q→~p If the opposite sides are not equal, then the quadrilateral is not square. (T) |
Example 4
|
Implication: p →q If the triangles are similar triangle then the corresponding angles are proportional (T) |
Converse: q →p If the corresponding angles are proportional, then the triangles are similar (T) |
|
Inverse: ~p→~ q If the triangles are not similar triangle then the corresponding angles are not proportional (T) |
Contrapositive: ~q→~p If the corresponding angles are not proportional, then the triangles are not similar (T) |
Logical Connectives: Bi-conditional
Let p and q are two simple propositions, then bi-conditional of p and q is a compound proposition, denoted by p↔q and defined by
p↔q is true if p and q have same truth value.
otherwise, p↔q is false.
Venn-diagram of Bi-Conditional
The alternate form of p↔q are- (¬p∧¬q)∨(p∧q)
- (p→q)∧(q→p)
- ¬(p∨q)∨(p∧q)
Logical Properties
Order of logical connectives
- ¬
- ∧
- ∨
- → (or ⇒)
- ↔ (or ⇔)
- ¬ has higher precedence than ∧
- ∧ has higher precedence than ∨
- ∨ has higher precedence than ⇒
- ⇒ has higher precedence than ⇔
Expressing propositions in Logic
The propositions in logic are expressed using a propositional function. A propositional function is a function whose variables are propositions. It is mapped by {T, F}→{T, F}n where n is a number of propositions.
Tautology and Contradiction
A compound proposition that is always true is called a tautology. Also, a compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.
Tautology
A proposition is called tautology if it has all truth (T) possibilities in its truth table.
Contradiction
A proposition is called a contradiction if it has all false (F) possibilities in its truth table.
Logical equivalence
Two propositions that have identical truth values in their truth table are called logically equivalent. Two propositions p and q are called logically equivalent if p↔q is a tautology, and it is denoted by p ≡ q.
Logically equivalent statements are “the same” in the sense that logically equivalent
statements can be freely substituted for each other without changing the meaning of a
compound statement.
For example,
- A conditional and its contrapositive are equivalent: p→q≡ ~q→ ~p.
- The converse and inverse are equivalent: q→ p≡ ~p→~q.
Example 1
- ((p→ q)˄p)→ q is a tautology.
- (p˅q)˄(~p˄~q) is a contradiction.
Example 2
Show that p→ q≡ ~q→ ~p.
Solution.
The equivalence of propositions is justified by the truth table. In this case, the truth table is given below.
| p | q | p→ q | ~q | ~p | ~q→ ~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 |
Here,
The truth table of p→ q and ~q→ ~p are identical.
Therefore,
p→ q≡ ~q→ ~p.
Basic Laws of Logic
| Equivalence | Name |
| p∨¬p≡T p∧¬p≡F |
Laws of the excluded middle |
| p∨F≡p p∧T≡p |
Identity laws |
| p∨T≡T p∧F≡F |
Domination laws |
| p∨p≡p p∧p≡p |
Idempotent Laws |
| ~ (~p)≡p | Double negation Laws Involution |
| p∨q≡ q∨p p∧q≡ q∧p |
Commutative Laws |
| (p∨q)∨r≡ p∨(q∨r) (p∧q)∧r≡ p∧(q∧r) |
Associative Laws |
| p∧(q∨r)≡ (p∧q)∨(p∧r) p∨(q∧r)≡ (p∨q)∧(p∨r) |
Distributive Laws |
| ~(p∨q)≡~p∧~q ~(p∧q)≡~p∨~q |
De-Morgan’s Laws |
| p∧(p∨q)≡p p∨(p∧q)≡p |
Absorption Laws |
| p→q≡~p∨q | Law of Implication |
| p→q≡~q→~p | Law of Contrapositive |
Basic Rule of Inference of Logic
| Rule | Tautology | Name | Example |
| p p → q ∴ q |
(p∧(p→ q))→q | Modus ponens (Direct) | |
| ~q p → q ∴ ~p |
(~q∧(p→q))→~p | Modus Tollens (Indirect) | |
| p → q q → r ∴ p → r |
((p→q)∧(q→r))→(p→r) |
Hypothetical syllogism (Transitive) |
|
| p∨ q ~p ∴ q |
((p∨ q)∧~p)→q | Disjunctive syllogism | |
| p ∴ p∨ q |
p→(p∨ q) q→ (p∨ q) |
Addition | |
| p∧ q ∴ p |
(p∧ q) →p (p∧ q)→q |
Simplification | |
| p q ∴ p∧ q |
((p)∧ (q))→(p∧ q) | Conjunction | |
| p∨ q ~p∨ r ∴ q∨ r |
((p∨ q)∧ (~p∨ r))→(q∨ r) | Resolution |
Solved Examples
Example 1
Use De Morgan’s laws to express the negations
- “Mohan has a cellphone and he has a laptop computer”
- “Hari will go to the concert or Sita will go to the concert.”
-
Let p be “Mohan has a cellphone” and q be “Mohan has a laptop computer.” Then
“Mohan has a cellphone and he has a laptop computer” can be represented by
p∧q.
By the first of De Morgan’s laws, it is
~(p∧q) is equivalent to ~p∨~q.
Consequently, we can express the negation of our original statement as
“Mohan does not have a cellphone or he does not have a laptop computer.” -
Let r be “Hari will go to the concert” and s be “Sita will go to the concert.” Then
“Heather will go to the concert or Sita will go to the concert” can be represented by
r∨s.
By the second of De Morgan’s laws,
~(r∨s) is equivalent to ~r∧~s.
Consequently, we can express the negation of our original statement as
“Hari will not go to the concert and Sita will not go to the concert.”
Example 2
-
Prove that ~(p→q) ≡p∧~q
~(p→q)=~(~p∨q) Implication
Solution
or~(p→q)=p∧~q De Morgan’s -
Prove that ~(p ∨ (~p ∧ q)) ≡~p ∧~q
~(p∨(~p∧q)) =~p∧~(~p∧ q) De Morgan’s
Solution
or~(p∨(~p∧q)) =~p∧(p∨~q) De Morgan’s
or~(p∨(~p∧q)) = (~p∧p)∨(~p ∧~q)Distributive
or~(p∨(~p∧q)) =F∨(~p∧~q)Contradiction
or~(p∨(~p∧q)) =~p∧~q Identity -
Prove that (p ∧ q) → (p ∨ q) ≡~p ∧~q
(p∧q) → (p∨q) = (~p ∨~q) ∨ (p ∨ q)Implication and De Morgan’s
Solution
or(p∧q) → (p∨q) = (~p ∨ p) ∨ (~q ∨ q)
or(p∧q) → (p∨q) = T ∨ T Tautology
or(p∧q) → (p∨q) = T -
Prove that ~(~p∧q)˄(p∧q) ≡p
~(~p∧q)˄(p∧q) =(p˅~q)˄(p∧q)De Morgan’s
Solution
or~(~p∧q)˄(p∧q) =p˅(~q∧q)Distributive
or~(~p∧q)˄(p∧q) =p˅FContradiction
or~(~p∧q)˄(p∧q) =pIdentity - Prove that q∨¬(¬p∧q) is a Tautology
Solution
q∨¬(¬p∧q)= q∨ ¬(¬p∧q) orq∨¬(¬p∧q)= q∨ (p∨¬q) De-Morgan’s Law
orq∨¬(¬p∧q)= q∨(p∨¬q)
orq∨¬(¬p∧q)= (p∨¬q)∨q Associative Law
orq∨¬(¬p∧q)= (p∨¬q)∨q
orq∨¬(¬p∧q)= p∨(¬q∨q) Associative Law
orq∨¬(¬p∧q)= p∨T
orq∨¬(¬p∧q)= T Domination law