UNIT

01 Fundamentals of Logic

Names of Sub-Units

Introduction, Basic Connectives, Truth Tables, Logic Equivalence, the Laws of Logic, Logical Implication:
Rules of Inference, Quantifiers, Types of Quantifiers, Use of Quantifiers, Definitions and the Proofs of
Theorems

Overview

The Unit begins by explaining the meaning of logic and propositions with examples. Further, you will
study the basic connectives to combine two or more propositions and how to draw their truth tables.
Moving ahead, you will study the laws of logic and inferences. Also, you will acquire the knowledge
of quantifiers and their types. In addition to this, you will also grasp the knowledge of validating a
statement using the truth tables.

Learning Objectives

In this unit, you will learn to:

 Discuss the concept of logic and propositions
 Describe the different kinds of propositions and basic connectives
 Explain how to make the truth tables of logical statements
 Explain and enlist the different kinds of quantifiers
 Analyse the conclusion or inferences from the given premises
 Summarise the validate the logical inference
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

Learning Outcomes

At the end of this unit, you would:

 Understand how to combine two simple propositions by using basic connectives
 Analyse the truth tables of different logical statements
 Summarise and enlist the different types of quantifiers
 Draw conclusions or inferences from the given premises
 Validate the logical inference

Pre-Unit Preparatory Material

 https://www.geeksforgeeks.org/proposition-logic/
 https://www.cs.purdue.edu/homes/spa/courses/cs182/mod1.pdf

1.1 INTRODUCTION
One distinctive feature that differentiates human beings from other species of animals is his ability to
think and act logically in any situation of life. Humans have the ability to think critically and solve complex
problems related to life through logical reasoning. Thinking logically to solve complex life problems and
making the important decision of life is one of the most important traits of being successful. There are
hundreds of things you do every day where you make use of logic without consciously knowing that you
are making use of logic. For example, while playing ludo with your friend you think logically to decide
which ludo piece you should be moved so that the opponents piece does not land on your piece and your
piece is sent back to the start position. Similarly, when something rolls down your bed say the cap of
your bottle and you are not able to pick the thing with your hand, you think logically to decide to bring
a long stick or broom to get the thing out of your bed.
Thinking logically is the act of examining the circumstances and coming up with a rational solution.
In logical reasoning, one makes use of his reasoning skill or logic to analyse the facts or situation and
address the problem. Though the skill of thinking logically in any situation depends on person to person it
can be developed through activities such as brainstorming, participating in activities that require deep
thought and concentration such as content writing, socialising with other people as the environment
has a great role in your development and you study many things by observing, imaging the outcomes
of your decision.
Aristotle is the man who first tossed the term logic over 2000 years ago. Aristotle’s logical work is unique
and commendable especially “theory of the syllogism”. His most of the work is grouped under the title
“Organon” and still considered as the subject of interest for recent scholars.
Like in all spheres of life the logic plays a great role in computer applications too. Thinking logically is
one of the key traits for becoming successful computer professionals as one can develop any software,
application, program, game, hardware or coding language only if one has ability to think rationally.
Before moving ahead, you should understand the term proposition for solving complex problems on
logic in computer applications.

2
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

1.2 PROPOSITION
A proposition is a declarative sentence that has a truth value that is it is either true or false but not both
at the same time.
Firstly, according to this definition, the proposition is a declarative sentence. A declarative sentence is a
statement that communicates facts or information.
Secondly, a proposition has a truth value that is either they are true or false.
Consider the following sentences:
p: Window is an operating system.
q: MS window is an application software.
r: Linux is better than MS Windows.

While the first sentence is true and the second is false, you cannot say anything about the third sentence
as different people may have different views regarding which operating system is better Linux or MS
windows. Thus, the third sentence does not have any truth value as it is true of some people and for
others it is false. Hence, the third sentence cannot be considered as a proposition as it does not have
any truth value. While the first two sentences can be considered as a proposition as they are declarative
sentences and have the truth value the third sentence cannot be considered as a proposition.
Now, consider the following sentences:
p: Is window an operating system?
q: Complete the PowerPoint presentation.
r: Wow! What a great presentation it was.
Now, here the first sentence is a question, the second sentence is a command and the third sentence
is an exclamation. Thus, all these are not the proposition. Thus, no question, command, request or
exclamation can be called a proposition.
Proposition is usually represented by small letters p, q, r, etc.

1.2.1 Type of Propositions

The two different types of prepositions are as follows:
1. Simple Proposition: A proposition is called simple if it cannot be broken down into two or more
propositions.
For example, the propositions given below are all simple propositions.
p: Unix is a multiuser operating system.
q: Google Android is a mobile operating system.
r: Chrome is an internet browser.
2. Compound Proposition: A proposition made of two or more simple propositions is called a compound
proposition.
For example, the proposition

3
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

“p: Unix and Mainframe OS are the multiuser operating system.” can be written as two simple
propositions as follows.
q: Unix is a multiuser operating system.
r: Mainframe OS is a multiuser operating system.

1.3 BASIC CONNECTIVES

The basic connectives also referred to as propositional connectives are the words that are used to
combine two or more simple propositions to form a compound proposition.
The five basic connectives are as follows:
1. Conjunctionoftwoproposition: Ifpandqaretwosimplepropositions, thenthecompoundproposition
formed by connecting these two propositions using the word “and” is called the conjunction of p and
q. The conjunction of two statements p and q is denoted by symbol  and written as p  q.
Example:
p: Norton Disk Doctor (NDD) is an antivirus software.
q: eScan is an antivirus software.
p  q: Norton Disk Doctor (NDD) and eScan are antivirus software.
2. Disjunction of two proposition: If p and q are two simple propositions, then the compound proposition
formed by connecting these two propositions using the word “or” is called the disjunction of p and q.
Disjunction of two statements p and is denoted by symbol  and written as p  q.
Example:
p: Norton Disk Doctor (NDD) is an antivirus software.
q: Norton Disk Doctor (NDD) is an internet browser.
p  q: Norton Disk Doctor (NDD) is an antivirus software or the Internet browser.
3. Negation of a proposition: Negation of the proposition is the counterstatement of a given proposition.
The negation of the proposition is formed by writing the word not in the given proposition at an
appropriate place. You can also write the negation of the given proposition by writing the words
“It is not the case” or “It is false that” before the proposition. The negation of the proposition ‘p’ is
denoted by symbol  or by symbol  and written as  p or ~p.
Example:
p: Corel Draw is a graphics program.
~p: Coral Draw is not a graphics program.
4. Conditional Proposition: If p and q are two simple propositions, then the proposition formed by
combining the two given propositions by using the words if and. Then, i.e., “if p then q” is called
conditional proposition or an implication. The conditional proposition “if p then q” is symbolically
written as p  q or p  q, where p is called hypothesis or antecedent and q is called conclusion or
consequent.
Example:
p: Keyboard is an input device.
q: Keyboard is hardware.
p  q: If the keyboard is an input device, then it is hardware.

4
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

5. Biconditional Proposition: If p and q are two simple propositions, then the proposition formed
by combining these two propositions by using the word if and only if (also written as iff) is called
Biconditional Proposition. The biconditional proposition “p if and only if q” is symbolically written
as p  q or p  q.
Example:
p: A  B and B  A
q: A=B
 p  q: If A  B and B  A if and only if A=B.

1.3.1 Components or Elements of a Propositional Logic

When two or more propositions are combined to form a compound proposition then the propositions
combined are called elements or components of the propositional logic.
Example:
p: Google apps for business is an example of productivity software.
q: Microsoft office is an example of productivity software.
r: Open Office is an example of productivity software.
p  q  r: Google apps for business, Microsoft Office and Open Office are example of productivity
software.
Here, p, q and r are the elements of propositional logic.

1.4 TRUTH TABLES

The truth table is the tabular representation of the change in the truth value of the compound proposition
with respect to the change in the truth value of its components or elements.

1.4.1 Truth Value of Conjunction of Two Propositions

Let p and q be two propositions.
 The truth value of the conjunction of two propositions, i.e., pq is true whenever both p and q have
the truth value true.
 The truth value of the conjunction of two propositions, i.e., pq is false whenever both p and q have
a false truth value or either of p or q is false.

This can be represented in tabular form as follows:

p q pq
True True True
True False False
False True False
False False False

5
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

1.4.2 Truth Value of Disjunction of Two Propositions

Let p and q be two propositions.
 The truth value of the disjunction of two propositions, i.e., pq is true whenever both or either of p
or q have the truth value true.
 The truth value of the disjunction of two propositions, i.e., pq is false whenever the truth value of
both p and q is false.

This can be represented in tabular form as follows:

p q pq
True True True
True False True
False True True
False False False

1.4.3 Truth Value of Negation of a Proposition

Let p be any proposition.
 The truth value of negation of a proposition, i.e., ~p is false whenever the truth value of p true.
 The truth value of negation of a proposition, i.e., ~p is true whenever truth value p is false.

This can be represented in tabular form as follows:

p ~p
True False
False True

1.4.4 Truth Value of Conditional Proposition

Let p and q be two propositions.
 The conditional proposition if p then q means that p is the necessary condition for q. Therefore, the
truth value of the conditional propositions if p then q i.e. p  q will be true only when consequent q
is true whenever hypothesis p is true.
 The truth value of conditional proposition p  q is false when the consequent q is false and hypothesis
p is true.
 As p is the necessary condition for the q nothing can be said about the consequent q when hypothesis
p is false. So in that case when hypothesis p is false the conditional statement will be true in both the
condition, i.e., either consequent q is true or false.
This can be represented in tabular form as follows:

p q pq
True True True
True False False
False True True
False False True

6
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

1.4.5 Truth Value of Biconditional Proposition

Let p and q be two propositions.
The biconditional proposition p if and only if q may be considered as a conjunction of ‘if p then q’ and ‘if q
then p’. Thus, it may be regarded as p is a necessary condition for p and q is a necessary condition for q.
 Thus, the true value of the biconditional proposition p if and only if q, i.e., p  q will be true only if
both the elements of the biconditional proposition have the same truth value, i.e., either when both
are true or both are false.
 The true value of the biconditional proposition p  q is false when both elements of the biconditional
proposition have different truth values.

This can be represented in tabular form as follows:

p q pq
True True True
True False False
False True False
False False True

Example 1
Find the truth value of following compound proposition when proposition p and q are as follows:
p: Python is a programming language.
q: Firefox is a programming language.
a. p  q
b. p  q
Solution
You know that python is a programming language but firefox is an example of web browser. Therefore,
here proposition ‘p’ is true, whereas the proposition ‘q’ is false.
Thus, the truth value of given compound propositions are as follows:
a. p  q : Python and Firefox are programming languages.
p q p q
True False False
b. p  q : Python or Firefox is a programming language.
p q p q
True False True

Example 2
Draw the truth table of the following proposition:
p: Printer can print on both sides of paper.

7
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

q: Printer is the duplex printer.

a. p  q
b. p  q

Solution
a. p  q : If a printer can print on both sides of paper, then it is duplex a duplex printer.

p q pq
True True True
True False False
False True True
False False True
b. p  q : Printer can print on both sides of the paper if and only if it is duplex.

p q pq
True True True
True False False
False True False
False False True

1.5 LOGIC EQUIVALENCE

A logical statement is a statement consisting of two or more simple propositions combined using basic
connectives. If p, q and r are three simple propositions then (p  q)r, p~q, (pq)r, etc. are some
examples of logical statements.
Two logical statements are logically equivalent if they have the same truth table. We use the symbol ‘’
to denote two logical equivalent statements.
Example 3
If p and q are two proposition then prove that (pq)~p ~q.
Solution

p q pq (p  q)  p  q  p  q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

Since both  (p  q) and  pq have the same truth table, therefore, the two given logical statements
are equivalent, i.e., (pq)pq.
Example 4
If p and q are two proposition then prove that (pq)pq.

8
UNIT 01: Fundamentals of Logic JGI JAIN DEEMED-TO-BE UNI VE RSI TY

Solution

p q pq (pq) p q pq

T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

Since both (p  q) and pq have the same truth table, therefore, the two given logical statements are
equivalent, i.e., (p  q)pq.
The logical statements (p  q)pq and (p  q)pq are known as De Morgan’s law.

1.5.1 The Laws of Logic

The basic laws of logic are as follows:
1. Commutative law: The commutative law states that in conjunction and disjunction of two
propositions the order does not matter. Thus, if p and q are two propositions then:
p  q  q  p and
pqqp
Example 5:
Let p: PHP is a programming language.
q: HTML is a programming language.
Thus, “p  q: PHP and HTML are programming language.” and
“q  p: HTML and PHP are programming languages.” are logically equivalent propositions.
2. Associative law: If p, q and r are three propositions, then
(p  q)  r  p  (q  r) and (p  q)  r  p  (q  r)
3. Distributive law: If p, q and r are three propositions, then
p  (q  r)  (p  q)  (p  r) and p  (q  r)  (p  q)  (q  r)
4. Idempotent law: If p is a proposition, then
p  p  p and p  p  p
5. Inverse Law: The inverse law states that if p is a proposition then the truth value of conjunction of
p and its negation is always false and the truth value of disjunction of p and its negation is always
true. Thus, this can be written as:
p  ∼ p  f and p  ∼ p  t, where ‘f’ means false and ‘t’ means true.
Validation:
The truth table of pp is as follows:

p p pp
T F F
F T F

9
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

The truth table of pp is as follows:

p p pp
T F T
F T T
6. Domination law: Let p be any proposition. Then the domination law states that the conjunction of
p with any false proposition is always false and disjunction of p with any true proposition is always
true.
Thus, p  F  F (∵ conjunction of two proposition is true only when both of them are true and when
we know that one of them is false then the conjunction of two proposition will obviously be false.)
And p  T  T (As we know the disjunction of two propositions is true when either one or both of the
propositions are true. Here, as you know that one of the propositions is true so the disjunction of p
and True proposition will be true whether p is false or true)
7. Identity law: Let p be any proposition. This law states that the truth value of conjunction of p with
any true proposition will be equal to the truth value of p and truth value of disjunction of p with any
false proposition will be equal to the truth value of p.
Thus,
p  T  p and p  F  p
This can be shown on the truth table as below:
p T pT
T T T
F T F
Note, here truth values of p and p  T are the same.
p F pF
T F T
F F F
Note here the truth value of p and p  F are the same.
8. Absorption law: Let p and q be any two propositions then according to absorption law:
p  (p  q)  p and p  (p  q)  p
Representing p  (p  q)on the truth table, we get

p q pq p(pq)
T T T T
T F T T
F T T F
F F F F

Thus the truth value of both p and p  (p  q) are the same. Thus, p and p  (p  q) are logically equivalent
propositions.

10
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

Representing p  (p  q)on the truth table, we get

p q pq p(pq)
T T T T
T F F T
F T F F
F F F F 

Thus the truth value of both p and p  (pq) are the same. Thus, p and p  (p  q) are logically equivalent
propositions.

1.6 LOGICAL IMPLICATION: RULES OF INFERENCE

The conditional statements involving the words if-then are called logical implications. Thus, if p and q
are two propositions then the proposition “if p then q” is called a logical implication. It can be read as
p implies q. It simply means if p then q or if ∼ q then ∼ p. Thus p is a sufficient condition for q or q is a
necessary condition for p.

1.6.1 Premises and Conclusion

Premises are the propositions or assumptions on the basis of which we derive a conclusion. The
conclusion is the statement or result that we derive from the premises. A group or set of statements
consisting of both premises and conclusion is known as argument.
Example
Premise 1 All machines have a lifespan.
Premise 2 Computer is a machine.
Conclusion Computer has a lifespan.
An argument is said to be valid if premises are true then it is not possible to make conclusion false no
matter what particular statements are substituted in the premises and conclusion. IF it leads to a false
conclusion or premises then the argument is considered to be invalid.
Let

p q
p
 q

Here, p  q and p are two premises. Now, if p  q and p both are true, then obviously q must be true. So
this is a valid argument.
Now consider the argument

p q
q
 p

11
JGI JAINDEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

Here, p  q and q are two premises. Now, if p  q and q both are true, then nothing can be said about
p whether it will be true or false. As in both case whether p is true or false the premises p  q and q
will remain true. Hence, these premises do not imply that p will be true only. Thus, this is an invalid
argument.

1.6.2 Inference
The inference is the process of drawing conclusion on the basis of premises or the assumptions. Rule
of Inferences is the templates or models for constructing a valid argument. They are themselves valid
arguments and are used for constructing a more complicated valid argument.
1. Modus Ponens Rule: This states that if p  q and p are true then q will also be true. This can be
written as:

p q
p
 q or [(p  q)  p]  q

2. Modus Tollens: According to this rule if p  q and q are true then ∼ p will also be true. Now if
p  q is true therefore q has to be true when p is true. But it is given that ∼ q is true. Hence, q will be
false. Therefore, p  q will become false if p is true and q is false. Hence, p will be false and ∼ p will
be true. This can be written as:

p q
∼q
 ∼p or [(p  q)  ∼ q]  ∼ p
3. Hypothetical Syllogism: According to this rule if p  q and q  r are true then p  r will also be
true. Now, if p is true q will also be true and if q is true r will also be true so p  r will be a true
statement. This can be written as follows:

p q
q r
p r or [(p  q)  (p  q)]  (p  r)
4. Disjunctive Syllogism: According to this rule if (p  q) and ∼ p are true then q will be true. Now, p will
be true only when p is false. Therefore p is false. And p  q will be true when p or q is true. But as p is
false so q will be true. As both q and (p  q) are true, therefore, (p  q)  ∼ p will be true. This can be
shown on the truth table as follows:
p –p q p q (p  q)  ∼ p
F T T T T
F T T T T
Disjunctive syllogism can be written as
(p  q)
–p
 q (p  q)  ∼ p  q

12
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

5. Addition: According to this rule if p is true then p  q will be true. This is obvious as p  q will remain
true whether q is false or true as p is true. This can be written as follows:
p
 p q or p  p  q
6. Simplification: According to this rule if p  q is true, then p and q both are true. This is obvious. This
can be written as follows:
p q or p q
p q
OR
(p  q)  p (p  q)  q

7. Conjunction Rule: According to this rule if p is true and q is true then p  q will also be true. This can
be written as:
p
q
 p q or [(p)  (q)]  (p  q)
8. Resolution Rule: According to this rule if (p  q) and ( ∼ p  r) is true then q  r is true. This can be
proved as follows.
Case I
Consider q to be false. Then p is true as (p  q) is true and q is false. Therefore, ∼ p will be false. Hence,
r is true as ( ∼ p  r) is true.
Hence the conclusion (q  r) is true as r is true.
Case II
Consider q to be true. So in case to conclusion (q  r) will be true considering the fact whether r is
true or false.
Therefore, Resolution Rule can be written as follows:
(p  q)
(p  r)
qr or (p  q)  (p  r)qr

Example 6
Which rule of inference is used in each of these arguments?
a. Premises1: If the printer is monochrome, then it will print in black ink only.
Premises 2: HP Laserjet P1108 is a monochrome printer.
Conclusion: HP LaserJet P1108 prints in black ink only.
b. Premises 1: If the printer is duplex it can print on both sides of the paper.
Premises 2: HP Ink tank 315 colour printer cannot print on both sides of the paper.
Conclusion: HP Ink tank 315 colour printer is not the duplex printer.

13
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

c. Premises 1: If ‘n’ is a natural number then it is a whole number too.

Premises 2: If ‘n’ is a whole number then it is integer too.
Conclusion: If ‘n’ is a natural number then it is an integer too.
d. Premises 1: Either PASCAL or Abode Photoshop is a programming language.
Premises 2: Adobe Photoshop is not a programming language.
Conclusion: Pascal is a programming language.
e. Premises 1: Visual Basic is a programming language.
Premises 2: Coral Draw is a programming language.
Conclusion: Either Visual Basic or Coral Draw is a programming language.

Solution
a. It follows Modus Ponens Rule, i.e., [(p  q)  p]  q
b. It follows Modus Tollens Rule, i.e., [(p  q)  ∼ q]  ∼ p
c. It follows the Hypothetical Syllogism Rule, i.e., [(p  q)  (p  q)]  (p  r)
d. It follows Disjunctive Syllogism, i.e., (p  q)  ∼ p  q
e. As the first premise is true here and the second is false it follows the addition rule i.e. p  p  q

Example 7
Draw the conclusion using the law of inference from the following premises if the given premises are
true.
a. Premises 1: Keshav will research about device driver or Keshav will research about programming
language.
Premises 2: Keshav will not research device drivers or Keshav will research graphic programs.
b. Premises 1: Photoshop or Thunderbird is graphic software.
Premises 2: Thunderbird is not graphic software.
Solution
a. Let p: Keshav will research about device driver.
q: Keshav will research programming language.
r: Keshav will research graphic programs.
We know both premises 1 and 2 are true, i.e., (p  q)  ( ∼ p  q) is true.
Therefore, by the resolution rule, we can conclude
Keshav will research programming language or Keshav will research graphic programs.
b. Let p : Photoshop is a graphic software.
q : Thunderbird is graphic software.
Now both the premises are true i.e. (p  q)  ∼ q is true. Therefore, by disjunction rule, you can
conclude p is true, i.e., Photoshop is a graphic program.

14
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

1.7 QUANTIFIERS
Quantifiers are the words and phrases that give details about the quantity or number of objects or
persons.

1.7.1 Types of Quantifiers

In logical reasoning, you mainly use two kinds of quantifiers. They are as follows:
1. Universal quantifier: The words or phrases such as “for all” or “for every” are called universal
quantifiers as they indicate all the objects or members of a given group satisfy the given property.
Example: For all natural numbers n, n 2≥n. The symbol ‘  ’ is used to express the quantifier “for all”
or “for every”.
2. Existential quantifier: The words or phrase “there exist” are called existential quantifiers. They
indicate that there exists at least one object or member of the group that satisfies the given property.
For example, There exists a natural number p such that it has only two factors. Here, it means that
there is at least one natural number such that it has only two factors. The symbol ‘  ’ is used to
denote the quantifier “there exists”

1.7.2 Use of Quantifiers

Quantifiers tell us about the quantity or number of the objects of a given group that satisfy the given
property without actually telling about the exact number. You can make some important inferences
from the premises involving quantifiers.
For example:
p : All printers are output devices.
q : All output devices are hardware.

From these two sentences, you can conclude that “All printers are hardware”
Rule of Inference for Quantified Statement
We make some important conclusions from the premises involving quantifiers. The rules of inferences
of the quantified statement are as follows:
1. Universal instantiation rule: If a property P(x) is true for all elements ‘x” in a group, then it must be
true for a particular element in that group.
Example:
Premise 1: All web browsers are application software.
Premise 2: Firefox is a web browser.
Conclusion: Firefox is an application software.
2. Universal generalisation: If a property p(x) is true for an element ‘c’ in a group then it must be true
for all elements of that group.
Example:
Premise 1: “A number divisible by 10 is an even number”
Conclusion: All numbers divisible by 10 are even numbers.

15
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

3. Existential instantiation: According to this law there exist some c in the given domain for which the
property p(x) is true. We use the symbol ‘ ’ for denoting the words “there exist”
Example
There exist a natural number that is even and prime.
So, according to this statement there exist at least one element in the domain N of a natural number
that is even and prime.
4. Existential generalisation: According to this rule if the property p(x) is true for any element ‘c’ in the
domain then we can conclude that there exists at least one element x in the domain for which the
property p is true.
Example:
Premise: Reema in class X has long hair.
Conclusion: Someone in class X has long hair.

Example 8
What can you conclude from the following premises:
a. Premise 1: All operating systems are system software.
Premise 2: Android is an operating system.
b. Premise 1: All word processors are application software.
Premise 2: Google Doc is a word processor.

Solution
a. By Universal Instantiation Rule we can conclude
Android is system software.
b. By Universal Instantiation Rule we can conclude
Google Doc is an application software.

1.8 DEFINITIONS AND THE PROOFS OF THEOREMS

Tautology
A proposition that is always true is called a tautology.

Example: p  ∼ p
Contradiction
A proposition that is always false is called a contradiction.

Example: p  ∼ p
Contingency
A proposition that is neither a tautology nor a contradiction is called contingency. Example: p  q

16
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

p q pq
T T T
T F T
F T T
F F F

Example 9
Validate the following statements:
a. ∼ (p  q)  ∼ p  ∼ q
b. ∼ (p  q)  [p  ( ∼ q)]

Solution
a. ∼ (p  q)  ∼ p  ∼ q
We will validate this statement by using a truth table

p q p q – (p  q) –p ∼q –p ∼q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
– (p  q) and ∼ p  ∼ q have the same truth table. Therefore,
– (p  q)  ∼ p  ∼ q
b. ∼ (p  q)  [p  ( ∼ q)]
We will validate this statement by using a truth table.

p q p q – (p  q) –q [p  ( ∼ q)]
T T T F F F
T F F T T T
F T T F F F
F F T F T F

– (p  q) and [p  ( ∼ q)] have the same truth table.

Therefore, ∼ (p  q)  [p  ( ∼ q)]

Conclusion 1.9 CONCLUSION

 Thinking logically to solve complex life problems and making the important decision of life is one of
the most important traits of being successful.
 Thinking logically is the act of examining the circumstances and coming up with a rational solution.

17
JGI JAINDEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

 Aristotle is the man who first tossed the term logic over 2000 years ago. Aristotle’s logical work
is unique and commendable especially “theory of the syllogism”. His most of the work is grouped
under the title “Organon” and still considered as the subject of interest for recent scholars.
 Laws of logic
 Commutative law: If p and q are two propositions, then:
p  q  q  p and
p q q p
 Associative law: If p, q and r are three propositions, then
(p  q)  r  p  (q  r) and (p  q)  r  p  (q  r)
 Distributive law: If p, q and r are three propositions, then
p  (q  r)  (p  q)  (p  r) and p  (q  r)  (p  q)  (q  r)
 Idempotent law: If p is a proposition, then
p  p  p and p  p  p
 Inverse law: The inverse law states that if p is a proposition then p  ∼ p  f and p  ∼ p  t where
‘f’ means false and ‘t’ means true.
 Domination law: Let p be any proposition.
Then p  F  Fand p  T  T
 Identity law: Let p be any proposition. Then,
p  T  p and p  F  p
 Absorption law: Let p and q be any two propositions then according to absorption law:
p  (p  q)  p and p  (p  q)  p
 Quantifiers are the words and phrases that give details about the quantity or number of objects or
persons. The two types of quantifiers are as follows:
 Universal quantifier
 Existential quantifier
 You can make some important inferences from the premises involving quantifiers.

1.10 GLOSSARY

 Proposition: A proposition is a declarative sentence that has a truth value that is it is either true or
false but not both at the same time.
 Simple proposition: A proposition is called simple if it cannot be broken down into two or more
propositions.
 Compound proposition: A proposition made of two or more simple propositions is called a compound
proposition.
 Basic Connectives: The basic connectives also referred to as propositional connectives are the words
that are used to combine two or more simple propositions to form a compound proposition.
 Components or elements of a propositional logic: When two or more propositions are combined to
form a compound proposition then the propositions combined are called elements or components
of the propositional logic.

18
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

 Truth table: Truth table is the tabular representation of the change in truth value of the compound
proposition with respect to the change in the truth value of its components or elements.
 Logical statement: A logical statement is a statement consisting of two or more simple propositions
combined using basic connectives.
 Logic equivalence: Two logical statements are logically equivalent if they have the same truth table.
We use the symbol ‘  ’ to denote two logical equivalent statements.
 Logical implication: The conditional statements involving the words if-then are called logical
implications.
 Premises and conclusion: Premises are the propositions or assumptions on the basis of which we
derive a conclusion.
 Argument: A group or set of statements consisting of both premises and conclusion is known as an
argument.
 Inference: Inference is the process of drawing conclusion on the basis of premises or the assumptions.
 Tautology: A proposition that is always true is called a tautology.
Example: p  ∼ p
 Contradiction: A proposition that is always false is called a contradiction.
Example: p  ∼ p
 Contingency: A proposition that is neither a tautology nor a contradiction is called contingency.
Example p  q

1.11 SELF-ASSESSMENT QUESTIONS

A. Essay Type Questions

1. Write the conjunction and disjunction of the following statements:
a. p: Mother Board is a hardware.
q: Keyboard is the hardware.
b. p: Lotus word pro is a word processor.
q: Notepad is a word processor.

c. p: Antivirus is a utility software.

q: File Management System is a utility software.
d. p: MS Excel is a spreadsheet.
q: Visual Basic is a spreadsheet.
2. Which of the following is a proposition? Justify your answer.
a. Will it rain today?
b. Wow! What a decent mobile.
c. VLC is a movie player.
d. Chetan Bhagat is the most famous writer in the world.
e. The mouse is software.

19
JGI JAIN
DEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application
3. Write the negation of the following proposition.
a. p: Discord is a communication app.
b. p: MySQL is a database management system.
4. Draw the truth table for the following logical statements.
a. (p  q)  q
b. p  ∼ q
5. Prove p  ∼ (p  q) is a tautology.
6. Show ∼ [p  ∼ (p  q)] is a contradiction.
7. Prove ∼ (p  ( ∼ pq))  ∼ p  ∼ q .
8. Draw the conclusion using the law of inference from the following premises if the given premises are
true.
a. Premises 1: Keshav will play football or Keshav play basketball.
Premises 2: Keshav will not play football or Keshav will play cricket.
b. Premises 1: RAM or mouse is an internal hardware.
Premises 2: Mouse is not an internal hardware.
a. Let p: Keshav will play football.
q: Keshav will play basketball.
r: Keshav will play cricket.
We know both premises 1 & 2 are true i.e. (p  q)  ( ∼ p  q) is true.
Therefore, by the resolution rule, you can conclude
Keshav will basket ball or Keshav will play cricket.
b. Let p : RAM is an internal hardware.
q :Mouse is an internal hardware.
Now, both the premises are true i.e. (p  q)  ∼ q is true. Therefore, by disjunction rule, you can
conclude p is true i.e. RAM is an internal hardware.

1.12 ANSWERS AND HINTS FOR SELF-ASSESSMENT QUESTIONS

A. Hints for Essay Type Questions

1. The conjunction and disjunction of the statements are:

a. p  q: Mother board or keyboard is a hardware.
b. p  q: Lotus word pro or Notepad is a word processor.
c. p  q: Antivirus or File Management System is a utility software.
d. p  q: MS Excel or Visual Basic is a spreadsheet.
2. The answers of the statements are as follows:
a. This is not a proposition as it is a question and not a declarative sentence.
b. This is not a proposition as it an exclamation and not a declarative statement.

20
UNIT 01: Fundamentals of Logic JGI JAIN
DEEMED-TO-BE UNI VE RSI TY

c. This is the proposition as is a declarative proposition and has a truth value.

d. This is not a proposition as it does not have the truth value and different people may have a
different opinion about this statement.
e. This is the proposition as is a declarative proposition and has a truth value.

3. The negation of the following proposition are as follows:

a. ∼ p: Discord is not a communication app.
b. ∼ p: MySQL is not a database management system.
4. The truth table for the following logical statements is as follows:
a. (p  q)  q
p q (p  q) (p  q)  q
T T T T
T F F F
F T T T
F F T T
b. p  ∼ q

p q∼q p∼q
T T F F
T F T T
F T F F
F F T F
5. p  ∼ (p  q)
p q pq – (p  q) p  ∼ (p  q)
T T T F T
T F F T T
F T F T T
F F F T T
Since in all cases Truth value of p  ∼ (p  q) is true, therefore it is a tautology.
6. The answer is as follows:
p q p q – (p  q) p  ∼ (p  q) ∼ [p  ∼ (p  q)]
T T T F T F
T F F T T F
F T F T T F
F F F T T F

Since in all cases the truth value of ∼ [p  ∼ (p  q)] is false it is a contradiction.

7. The answer is as follows:
p q∼p –q – p  q p  ( ∼ pq) ∼ (p  ( ∼ pq)) –p  ∼q

21
JGI JAINDEEMED-TO-BE UNI VE RSI TY
Mathematical Foundation for Computer Application

T T F F F T F F
T F F T F T F F
F T T F T T F F
F F T T F F T T

Since ∼ (p  ( ∼ pq)) and ∼ p  ∼ q have same truth table they are logically equivalent.
8. The conclusion is as follows:.
a. Premises 1: Keshav will play football or Keshav play basket ball.
Premises 2: Keshav will not play football or Keshav will play cricket.
b. Premises 1: RAM or mouse is an internal hardware.
Premises 2: Mouse is not an internal hardware.

@ 1.13 POST-UNIT READING MATERIAL

 https://math.libretexts.org/Courses/Monroe_Community_College/MATH_220_Discrete_
Math/2%3A_Logic/2.5%3A_Logical_Equivalences
 https://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html

1.14 TOPICS FOR DISCUSSION FORUMS

 Discuss the differences between quantifiers and qualifiers.

22