Topic Name Mapped CO Numbers
Propositional CO1, CO2, CO3, CO4,
Logic CO5
Propositional Logic
Propositional logic is a branch of mathematics that studies the logical
relationships between propositions (or statements, sentences, assertions) taken
as a whole, and connected via logical connectives.
It focuses on how these propositions relate to each other through logical
connectives such as AND, OR, NOT, IF…THEN, etc.
Examples of Propositions
Truth
Statement Value
The sun rises in the East and sets in
True
the West.
1+1=2 True
‘b’ is a vowel. False
All of the above are propositions because each has a definite truth value.
Non-Propositions
Some sentences are not propositions because they don’t have a definite truth
value or may vary depending on context:
“What time is it?” (Question)
“Go out and play.” (Command)
“x + 1 = 2” (Open sentence — depends on the value of x)
Logical Connectives
In propositional logic, logical connectives are symbols used to build compound
propositions from atomic ones.
Types of Propositions
In propositional logic, propositions are statements that can be evaluated as true
or false. They are the building blocks of more complex logical statements. Here's
a breakdown of the two main types of propositions:
Atomic Propositions
Compound Propositions
Truth Table of Propositional Logic
Since we need to know the truth value of a proposition in all possible scenarios,
we consider all the possible combinations of the propositions which are joined
together by Logical Connectives to form the given compound proposition. This
compilation of all possible scenarios in a tabular format is called a truth table.
Most Common Logical Connectives-
1. Negation
If p is a proposition, then the negation of p is denoted by ¬p, which when
translated to simple English means- "It is not the case that p" or simply "not p".
The truth value of -p is the opposite of the truth value of p. The truth table of -
p is:
p ¬p
T F
F T
Example, Negation of "It is raining today", is "It is not the case that is raining
today" or simply "It is not raining today".
2. Conjunction
For any two propositions p and q, their conjunction is denoted by p∧q, which
means "p and q". The conjunction p∧q is True when both p and q are True,
otherwise False. The truth table of p∧q is:
p∧
p q q
T T T
T F F
F T F
F F F
Example, Conjunction of the propositions p- "Today is Friday" and q- "It is raining
today", p∧qis "Today is Friday and it is raining today". This proposition is true
only on rainy Fridays and is false on any other rainy day or on Fridays when it
does not rain.
3. Disjunction
For any two propositions p and q, their disjunction is denoted by p∨q, which
means " p or q". The disjunction p∨q is True when either p or q is True, otherwise
False. The truth table of p∨q is:
p q p∨q
T T T
T F T
F T T
F F F
Example, Disjunction of the propositions p- "Today is Friday" and q- "It is raining
today", p∨q is "Today is Friday or it is raining today". This proposition is true on
any day that is a Friday or a rainy day (including rainy Fridays) and is false on
any day other than Friday when it also does not rain.
4. Exclusive Or
For any two propositions p and q, their exclusive or is denoted by p⊕q, which
means "either p or q but not both". The exclusive or p⊕q is True when
either p or q is True, and False when both are true or both are false. The truth
table of p⊕q is:
p⊕
p q q
T T F
T F T
F T T
F F F
Example, Exclusive or of the propositions p- "Today is Friday" and q- "It is raining
today", p⊕q is "Either today is Friday or it is raining today, but not both". This
proposition is true on any day that is a Friday or a rainy day(not including rainy
Fridays) and is false on any day other than Friday when it does not rain or rainy
Fridays.
5. Implication
For any two propositions p and q, the statement "if p then q" is called an
implication and it is denoted by p→q. In the implication p→q, p is called the
hypothesis or antecedent or premise and q is called the conclusion or
consequence. The implication is p→q is also called a conditional statement. The
implication is false when p is true and q is false otherwise it is true. The truth
table of p→q is:
p→
p q q
T T T
T F F
p→
p q q
F T T
F F T
One might wonder that why is p→q true when p is false. This is because the
implication guarantees that when p and q are true then the implication is true.
But the implication does not guarantee anything when the premise p is false.
There is no way of knowing whether or not the implication is false since p did not
happen. This situation is similar to the "Innocent until proven Guilty" stance,
which means that the implication p→q is considered true until proven false. Since
we cannot call the implication p→q false when p is false, our only alternative is to
call it true.
This follows from the Explosion Principle which says: "A False statement implies
anything" Conditional statements play a very important role in mathematical
reasoning, thus a variety of terminology is used to express p → q, some of which
are listed below.
"If p, then "q"p is sufficient for q""q when p""a necessary condition for p is q""p
only if q""q unless ≠p""q follows from p"
Example, "If it is Friday then it is raining today" is a proposition which is of the
form p→q. The above proposition is true if it is not Friday (premise is false) or if it
is Friday and it is raining, and it is false when it is Friday but it is not raining.
6. Biconditional or Double Implication
For any two propositions p and q, the statement "p if and only if(iff) q " is called a
implication. p↔q has the same truth value as (p→q) ∧ (q→p). The implication is
biconditional and it is denoted by p↔q. The statement p↔q is also called a bi-
true when p and q have same truth values, and is false otherwise. The truth
table of p→q is:
p q p↔q
T T T
T F F
F T F
F F T
p q p↔q
Some other common ways of expressing p↔q are:
"p is necessary and sufficient for q""if p then q, and conversely""p if q"
Example, "It is raining today if and only if it is Friday today." is a proposition
which is of the form p↔q. The above proposition is true if it is not Friday and it is
not raining or if it is Friday and it is raining, and it is false when it is not Friday or
it is not raining.
Application of propostional Logic
Mathematics – Proving theorems and solving problems.
Computer Science – Designing algorithms, programming, and databases.
Digital Circuits – Designing and analyzing logic gates.
Artificial Intelligence – Knowledge representation and reasoning.
Decision Making – Drawing correct conclusions from facts.
Linguistics – Analyzing sentence structure and meaning.
Propositional Logic Examples
1) Consider the following statements:
P: Good mobile phones are not cheap.
Q: Cheap mobile phones are not good.
L: P implies Q
M: Q implies P
N: P is equivalent to Q
Which one of the following about L, M, and N is CORRECT?
(A) Only L is TRUE.
(B) Only M is TRUE.
(C) Only N is TRUE.
(D) L, M and N are TRUE.
Solution:
Let a and b be two proposition
a: Good Mobile phones.
b: Cheap Mobile Phones.
P and Q can be written in logic as
P: a-->~b
Q: b-->~a.
Truth Table
a b ~a ~b P Q
TTFFFF
TFFTTT
FTTFTT
FFTTTT
it clearly shows P and Q are equivalent.
so option D is Correct
2) Which one of the following is not equivalent to p <-> q
(A) ¿
(B) ¿
(C) ¿
(D) ¿
conjunction p ∧ q is True, when both p and q is True. Disjunction of p and q,
Conjunction of p and q, denoted by p∧q, is the proposition ‘p and q’. The
denoted by p∨q, is the proposition ‘p or q’. The disjunction p∨q is False when
both p and q is False.
Logical Implication - It is a type of relationship between two statements or
true and q is false, and true otherwise. i.e. p → q = ¬p ∨ q
sentence. Denoted by ‘p → q’. The conditional statement p → q is false when p is
Bi-Condition A bi-conditional statement is a compound statement formed by
combining two conditionals under “and.” Bi-conditionals are true when both
statements have the exact same truth value.
Solution:
p↔q≡(p∧q)∨(¬p∧¬q)
A biconditional is true when both propositions have the same truth value:
Option (D) matches this directly.
Option (A): (¬p∨q) ∧ (p∨¬q) is equivalent to (¬p∨q) ∧ (¬q∨p), which is p ↔ q.
Option (B): q→p is ¬q∨p, so (B) is the same as (A).
Option (C): (¬p∧q) ∨ (p∧¬q)
is true exactly when p and q have opposite truth values: p ⊕q = ¬(p↔q)
Only option which is not equivalent to p↔q is option (C). So, option (C) is correct.
∧ q) which is Option (D)
Unsolved Question on Proposition Logic
Question 1:
Given:
P: “It is raining” (r)
Q: “The ground is wet” (w)
Check if the statement ¿ is logically equivalent to ¬� ∨ � Justify with truth table
Question 2: Simplify (p∨q) ∧(¬p∨q) to an equivalent expression using logical
laws.
Question 3: Let:
P: "If I study, I will pass." (s→p)
Q: "If I do not pass, then I did not study." (¬p→¬s)
R: "If I pass, then I studied." (p→s)
Which of the following is true?
(A) P and Q are equivalent, but not R
(B) P and R are equivalent, but not Q
(C) All three are equivalent
(D) None are equivalent