MAT1003-DMS

Module-1(Logics and Proofs) -Dr. Naraveni Rajashekar

Proposition: A proposition is a declarative sentence that is either true or false but not both.

Ex. 1) Sun rises in the East-True.

Therefore, it is a proposition.

2) Hyderabad is the capital of India- False

Therefore, it is a proposition.

3) x+3=5- Can not say whether it is true or false precisely.

Therefore, It is not a proposition.

4) Open the door- there is nothing to say whether it is true or false since it is not a declarative

Sentence. Therefore, not a proposition.

5) Sit down-not a proposition.

6) Elephant can fly- proposition.

Proposition Logic: The area of logic that deals with propositions is called the “ Proposition Calculus

or Proposition Logic”.

Logical Operators/Connectives:

AND- ∧

OR- ∨

NOT-~ or ¬

Atomic or primitive or Primary: Proposition which do not contain any of the logical operators or
connectives are called “ Atomic/Primary/Primitive Proposition”.
Compound Proposition: Many mathematical statements which can be constructed by one or more

atomic statements using connectives are called “ Compound Proposition”.

Ex.1) “It is raining today” - atomic statement, “it is cold” -atomic statement

Then “ It is raining today and It is cold” is a compound proposition. Since here we used

connective “and” and combined two atomic statements.

2) I am at home or It is raining-Compound statement

Negation: Let P be a proposition. The negation of P, denoted by “ ~P or ¬P”, is the statement

“ It is not the case that P”. The proposition ¬P is read as “not P”. The truth value of the negation

of P is the opposite of the truth value of P.

Ex. 1) P: I am playing cricket.

¬P: It is not the case that I am playing Cricket

(or) I am not playing cricket.

2)P: I am at home.

¬P: I am not at home.

Truth table for negation of a proposition: (Here T stands for true and F stands for false)

P ¬P
T F
F T

Conjunction: Let p and q be proposition. The conjunction of p and q, denoted by “p∧q”, is the

proposition “ p and q”. The conjunction p∧q is true when both p and q are true and is false

otherwise.
Ex. 1) p: I am at home. q: It is raining.
p∧q: I am at home and it is raining.
Truth table:

p q p∧q
T T T
T F F
F T F
F F F
Apart from “and” few more keywords for conjunction: and, but, although, yet, nevertheless,
moreover, in addition.
Disjunction: Let p and q be proposition. The disjunction of p and q, denoted by “p∨q”, is the

proposition “ p or q”. The disjunction p∨q is false when both p and q are false and is true

otherwise.
Ex. 1) p: I am at home. q: It is raining.
p∨q: I am at home or it is raining.

Truth table:

p q p∨q
T T T
T F T
F T T
F F F
Exclusive or: 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.
Ex. 1) Students who have taken MAT1003 or MAT1007 but not both can enroll in this class.
2) The door is open or closed
3) 𝑥 ≤ 0 𝑜𝑟 𝑥 > 0.
Truth table:

p q p⊕q
T T F
T F T
F T T
F F F

Conditional Statements:
Implication Statement: Let p and q be propositions. The implication of p and q, denoted by
p→q, is the statement “ If p, then q”. The conditional statement p→q is false when p is true and q
is false, and is true otherwise. In conditional statement p→q, p is called hypothesis and q is
called the conclusion.
Ex. 1) p: I am at home. q: It is raining
p→q: If I am at home then it is raining.
2) p: maria learns DMS q: Maria will find a good job
p→q: If Maria learns DMS then she will find a good job.
Truth Table:

p q p→q
T T T
T F F
F T T
F F T

Some other ways to express implication conditions as:

Bi-Implication: Let p and q be propositions. The bi-conditional statement of p and q, denoted by

p↔q, is the statement “p if and only if q”. The bi-conditional statement p↔q is true when p and
q have the same truth values, and is false otherwise. Bi-conditional statements are also called as
bi-implications.
Ex. 1) p: you can take the flight q: you buy a ticket
Then p↔q is the statement
“ you can take a flight if and only if you buy a ticket”.

2) An equilateral triangle has three angles of 600 , and conversely.

Some more keywords to express biconditional statements:
Truth table:

p q p↔q
T T T
T F F
F T F
F F T

Logical Operators Precedence:

Operator Precedence
¬ 1
∧ 2
∨ 3
→ 4
↔ 5

Different forms of Conditional statements: Converse, Contropositive and Inverse.

We can form some new conditional statements starting with a conditional statement p→q.

• The proposition q→p is called Converse of p→q.

• The proposition (¬q)→(¬p) is called Contrapositive statement of p→q.
• The proposition (¬p) →(¬q) is called the inverse of p→q.
➢ Only the contrapositive always has the same truth values as p→q.
➢ When two compound propositions always have the same truth values we call them
“equivalent”. Therefore, a conditional statement and its contrapositive are equivalent.
➢ The converse and inverse of a conditional statements are also equivalent.
Q1: What are the contrapositive, converse and inverse of the conditional statement
“ The home team wins whenever it is raining”
Sol: Because “ q whenever p” is one of the ways to express the conditional statement p→q.
The original statement can be written as “ If It is raining, then the home team wins”.
Here p: It is raining q: the home team wins
1)Then the converse is “ if home team wins, then it is raining (i.e.)q→p.
2)Contrapositive statement is “ If home team does not win, then it is not raining”. (i.e.)
(¬q)→(¬p).
3) Inverse statement is “ If it is not raining, then the home team does not win”. (i.e.) (¬p) →(¬q)

Q2. Construct the truth table of the compound proposition (p∨¬q)→(p∧q).

Sol:

p q ¬q p∨¬q p∧q (p∨¬q)→(p∧q).

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

Q3. Show using a truth table that the conditional statement is equivalent to the contrapositive.
Sol: Last two rows of below truth table shows that conditional statement and contrapositive
statements are equivalent since both have same truth values.

p q ¬p ¬q ¬q→¬p p→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

Applications of propositional logic:

Translating english to propositional logic:
•There are many reasons to translate English sentences into expressions involving
propositional variables and logical connectives. In particular, English is often ambiguous.
Translating sentences into compound statements removes the ambiguity.
• Once we translate sentences from English into logical expressions, we can analyze these
logical expression to determine their truth values, we can manipulate them, and we can use
rules of inference (which are discussed in later section) to reason about them.

Ex. 1) Translate the following sentence into logical expression

 “If I go to shankers’s house or to the sports ground then I will not go to shopping.”
Sol: Lets take propositions like
p: I go to shanker’s house
q: I go to sports ground
r: I will go to shopping
With the help of these variables notation, we can rewrite the given sentence as “If p or q
then not r.” Then the logical expression is “ (p∨q)→(¬r)”.
2) Translate the following sentence into logical expression
“you can access the internet from campus only if you are a computer science major or you are
not a freshman.”
Sol: Lets take the proposition variables(notations) as
a: you can access the internet from campus
c: you are a computer science major
f: you are a freshman
with the help of these variables, we can rewrite the sentence as “ a only if c or not f”. Then
the logical expression for this is “ a→(c∨¬f).”
3) How can this English sentence be translated into a logical expression?
“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16
years old.”
Sol: Let q, r, and s represent
q: “You can ride the roller coaster,”
r: “You are under 4 feet tall,” and
s: “You are older than 16 years old,” respectively.
Then the sentence can be translated to (r ∧ ¬s) → ¬q.

System specifications: System software engineers take requirement in English and express them
in precise specification language based on logic.
Ex. 1) Express in proposition logic “ The automated reply can not be sent when the file system is
full”.
Sol: Let p and q represents
p: The automated reply can be sent
q: the file system is full
Then the given sentence can be rewritten as “ ¬p when q”. Therefore, the logical expression
is “q→¬p”.
System specifications should be consistent, that is, they should not contain conflicting
requirements that could be used to derive a contradiction. When specifications are not
consistent, there would be no way to develop a system that satisfies all specifications.
Ex. 1) Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”
Sol: To determine whether these specifications are consistent, we first express them using
Logical expressions.
Let p :“The diagnostic message is stored in the buffer” and
q: “The diagnostic message is retransmitted.”
The specifications can then be written as (for first, second and third given statements)
p ∨ q, ¬p, and p → q.
If we take truth table for these three compound propositions and if we able to get atleast one

combination of p and q truth values such that above three compound propositions are true

then we say system is consistent or stable.

Truth Table:

p q ¬p p∨q p→q
T T F T T
T F F T F
F T T T T
F F T F T

If we see the third row for p false and q true then we get all our compound proposition are
true,(i.e.) we can able to find atleast one p and q truth values combination sothat all our
statements are true therefore the system specifications are consistent.
2) Determine whether these system specifications are consistent:
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”
“ The diagnostic message is not retransmitted”
Sol: To determine whether these specifications are consistent, we first express them using
Logical expressions.
Let p :“The diagnostic message is stored in the buffer”
q: “The diagnostic message is retransmitted.”
The specifications can then be written as (for first, second and third given statements)
 p ∨ q, ¬p, p → q and ¬q
If we take truth table for these three compound propositions and if we able to get atleast one

combination of p and q truth values such that above three compound propositions are true

then we say system is consistent or stable.

Truth Table:

p q ¬q ¬p p∨q p→q
T T F F T T
T F T F T F
F T F T T T
F F T T F T

We are unable to find a possible combination of p and q truth values such that given four
specifications is true. Therefore the system is inconsistent.

Logic Puzzles
Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic
puzzles is an excellent way to practice working with the rules of logic. Also, computer programs
designed to carry out logical reasoning often use well-known logic puzzles to illustrate their
capabilities.
Ex. 1) An island has two kinds of inhabitants,
knights, who always tell the truth, and their opposites, knaves, who always lie.
You encounter two people A and B.
What are A and B if A says “B is a knight” and B says “The two of us are opposite types?”
Sol: Case1: If A is a Knight then he always says truth. He said B is a knight therefore B should be
Knight. In this Case A and B are Knights but B said “The two of us are opposite types”
which is not. Therefore this case is not valid.
Case 2: If A is a Knave then he always says lie therefore B must be Knight. In this case, A is
knave and B is Knight. But if we see B statement “ The two of us are opposite types”
he is telling truth which is contradiction. Therefore, this case also not valid.
Case 3: Let B is Knight, then he always tell the truth and he said that “The two of us are
opposite types” therefore A should be Knave that is he should lie. But If we see A
statement “B is a knight”, he is telling truth which is contradiction. Therefore this
case also not valid.
Case 4: Let B is Knave then he tells lie and his statement is “The two of us are opposite types”.
Since he tells lie, therefore A should be Knave that is A should also tell the lie. If we
see A statement “B is a knight” but here we consider B is Knave that is A is telling lie
as our expectation. Therefore, this case is valid and A and B should be Knaves.

Tautology: A compound proposition that is always true, no matter what the truth values of the
propositions that occur in it, is called a “ tautology”.
Ex. 1) p∨¬p is a tautology
 Verification:
p ¬p p∨¬p
T F T
F T T
2) Show that (p→q)∨(q→p) is a tautology
Proof:
p q p→q q→p (p→q)∨( q→p)
T T T T T
T F F T T
F T T F T
F F T T T

Contradiction: A Compound proposition that is always false is called a “ Contradiction”.

Ex. p∧¬p
Verification:
p ¬p p∧¬p
T F F
F T F

Contingency: A compound proposition that is neither a tautology nor a contradiction is called

“contingency”.
Ex: (¬p)∧(p∨q) is a contingency.
Logically equivalent: Two compound propositions 𝑋(𝑝1 , 𝑝2 , … 𝑝𝑛 ) and 𝑌(𝑝1 , 𝑝2 , … 𝑝𝑛 ) ,where
𝑝1 , 𝑝2 … 𝑝𝑛 are propositions, are said to be “ logically equivalent” or simply “ equivalent” if
X↔y is a tautology.

• The notation 𝑋 ≡ 𝑌 denotes that X and Y are logically equivalent.

Ex. 1) Show that p→q and ¬p˅q are logically equivalent.
Proof: Here we denote X: p→q and Y: ¬p˅q

p q ¬p X: p→q Y: ¬p˅q X↔Y

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

X↔Y is a tautology, therefore X≡Y.

Demorgan’s Laws: 1) ¬(p∧q)≡(¬p∨¬q)

2) ¬(p∨q)≡(¬p∧¬q)
Propositional Satisfiability: A compound proposition is satisfiable if there is an assignment of
truth values to its variables that make it true. When no such assignments exist, the compound
proposition is unsatisfiable.

• A compound proposition is unsatisfiable if and only if its negation is a tautology.

Ex.1 ) Determine the satisfiability of the following compound statements
a) (p∨¬q)∧(q∨¬r)∧(r∨¬p)
Sol: Truth table:

p q r ¬p ¬q ¬r (p∨¬q) (q∨¬r) (r∨¬p) (p∨¬q)∧(q∨¬r)∧(r∨¬p)

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

If we take truth values of p,q,and r as T then we are getting (p∨¬q)∧(q∨¬r)∧(r∨¬p)

Is also true therefore, it is satisfiability. One can consider the case that truth values of p,q
and r are F then also (p∨¬q)∧(q∨¬r)∧(r∨¬p) is true, therefore satisfiability.
2) Show that below compound proposition is not satisfiability