Unit-III

Propositional and Fuzzy Logic

Dr. Amit Kumar

Symbiosis Institute of Technology, Pune
 Propositional logic
Propositional logic is a branch
of mathematics that deals logical
relationships between propositions taken
as a whole, or connected via logical
connectives.
Logic is the basis of all mathematical
reasoning and all automated
systems/reasoning.

2
 Contents
Statements, Propositions, Connectives, Truth
tables.
Tautology, Satisfiability, Contradiction,
Logical equivalence.
Introduction to Fuzzy Sets
Membership Functions
 Operations on fuzzy sets
Proofs by Mathematical induction,
Contradiction
Stable marriage problem.
3
 Proposition
A proposition is any sentence which is having a truth value
i.e. one is able to decide that the sentence/ information is
either true (T) or false (F), we refer T (1) or F (0) as the
truth value of the statement.

Example:
May god help you Not a Proposition.
1+1=11-----------------?
X+5=6--------------------?

4
• Examples:
1. The sentence “2+2=4” is a statement.
(Now, we think about the statement for true or false)
It is observed that, the given statement is true,
so that its truth value is T (1)

2. The sentence “1=0” is also a statement.

(Here also, we think about the statement for true or false)
It is observed that, the given statement is false,
so that its truth value is F (0)

3. Do you know how to speak English?

(Note: It is a question, not a statement)

4. “3-x=5”
(It is a declarative sentence, not a statement, (The truth
values are dependent on x))

.
5
6
 Basic logical operations
 There are some key words or phrases which are used
to form new propositions from given propositions.
• Examples:
1. “and” (Conjunction)
2. “or” (Disjunction)
3. “not” (Negation)
4. “if…then” (conditional)
5. “if and only if” (bi-Conditional)

These are called logical operators/logical connectives.

 A proposition which contains some logical connectives
is called a “compound proposition/molecular statement”.

 A statement containing no logical connectives is

called
a “simple statement/atomic statement”.

7
• Examples:
1. A triangle is a plane figure and is bounded by three
lines
2. Any real number is rational or irrational
3. The next year is not a leap year
4. If you don’t maintain social distance, then you
will sick from corona
5. Ram will eat the fruit if and only if it is an apple

Basic logical operators

 Conjunction ( P  Q )
 Disjunction (P Q)
 Negation (  P or ~ P )
 Conditional ( P  Q or P  Q )
 Bi-conditional ( P  Q or P  Q )

8
 Conjunction
 A statement obtained by joining two statements by using
the operator “and” is called the conjunction of the two
statements.
It is denoted by ( P  Q ) (Read it as P and Q).

• Examples:
1. Let P: SIT is an institute
Q: No. of students in a batch is 60
Then compound statement can be written as:
( P  Q ) : SIT is an institute and no. of students in a batch is 60

Truth functional rule for

conjunction: (P Q)

 If both (P and Q) are true, then is true, otherwise

it is false
9
 Truth table for Conjunction
 Let P and Q are two statements, the truth table for the
conjunction can be formed in the following two ways:
• General representation Computer representation

P Q P Q P Q P Q
T T T 1 1 1
T F F 1 0 0
F T F 0 1 0
F F F 0 0 0

Note: The number of rows in the truth table are: 2 , where n is number of statements.
n

Ex: 1. For 1 statement, the no. of rows = 2

2. For 2 statements, the no. of rows= 4
3. For 3 statements, the no. of rows= 8
 10
 Truth table for
Conjunction
 Let P, Q and R are three statements, the truth table for the
conjunction can be formed in the following two ways:
• General representation Computer representation
P Q R P Q R P Q R P Q R
T T T T 1 1 1 1
T T F F 1 1 0 0
T F T F 1 0 1 0
T F F F 1 0 0 0
F T T F 0 1 1 0
F T F F 0 1 0 0
F F T F 0 0 1 0
F F F F 0 0 0 0
11
 Disjunction
 A statement obtained by joining two statements by using
the operator “or” is called the disjunction of the two
statements.
It is denoted by P  Q (Read it as P or Q).

• Examples:
1. Let P: SIT is an institute
Q: No. of students in a batch is 100
Then compound statement can be written as:
P  Q : SIT is an institute or no. of students in a batch is 100

Truth functional rule for

disjunction: (P Q)

 If both (P and Q) are false, then is false, otherwise

it is true 12
 Truth table for disjunction
 Let P and Q are two statements, the truth table for the
disjunction can be formed in the following two ways:
• General representation Computer representation

P Q P Q P Q P Q
T T T 1 1 1
T F T 1 0 1
F T T 0 1 1
F F F 0 0 0
n
Note: The number of rows in the truth table are: 2 , where n is number of statements.
Ex: 1. For 1 statement, the no. of rows = 2
2. For 2 statements, the no. of rows= 4
3. For 3 statements, the no. of rows= 8

13
 Truth table for disjunction
 Let P, Q and R are three statements, the truth table for the
disjunction can be formed in the following two ways:
• General representation Computer representation

P Q R P Q R P Q R P Q R
T T T T 1 1 1 1
T T F T 1 1 0 1
T F T T 1 0 1 1
T F F T 1 0 0 1
F T T T 0 1 1 1
F T F T 0 1 0 1
F F T T 0 0 1 1
F F F F 0 0 0 0
14
 Negation
 A statement which has a truth value opposite to the
given statement P is called the negation of P
It is denoted by ~ P or  P (Read it as negation of P).

• Examples:
1. Let P: The number of COVID patients are more in India
Then compound statement can be written as:
 P : The number of COVID patients are not more/less in India

Truth functional rule for

P P
negation
 If P is true, then is false; if P is false, then is true

15
 Truth table for negation
 Let P is the statement, the truth table for the
negation can be formed in the following two ways:
• General representation Computer representation

P P P P
T F 1 0
F T 0 1
• Note: Negation does not mean that, exactly opposite to the statement
• Example: If the statement is “Water is cold”, the negation is
“Water is not cold”;
It does not mean that “Water is hot”

16
 Conditional
 A statement obtained by joining two statements by using
the operator “if…then…” is called the
conditional/implication statement
It is denoted by P  Q (Read it as P implies Q).

• Examples:
1. Let P: I win the game
Q: I will get the prize
Then compound statement can be written as:
P  Q : If I win the game, then I will get the prize

Truth functional rule for

conditional P Q

 If P is true and Q is false, then is false, otherwise

it is true
17
 Truth table for conditional
 Let P and Q are two statements, the truth table for the
conditional statement can be formed in the following two
ways:
• General representation Computer representation

P Q P Q P Q P Q
T T T 1 1 1
T F F 1 0 0
F T T 0 1 1
F F T 0 0 1
Note: In which, P is called hypothesis or antecedent
and Q is called the conclusion or consequent.

18
 Bi-conditional
 A statement obtained by joining two statements by using
the operator “if and only if” is called the
Biconditional/double implication statement
It is denoted by P  Q (Read it as P if and only if Q)

• Examples:
1. Let P: A number is even
Q: A number is divisible by two
Then compound statement can be written as:
P  Q : A number is even if and only if it is divisible by two

Truth functional rule for bi-

conditional PQ

 If both (P and Q) are true or false, then is true,

otherwise it is false
19
 Truth table for conditional
 Let P and Q are two statements, the truth table for the
biconditional statement can be formed in the following two
ways:
• General representation Computer representation

P Q PQ P Q PQ
T T T 1 1 1
T F F 1 0 0
F T F 0 1 0
F F T 0 0 1

20
 Truth table for
biconditional
 Let P, Q and R are three statements, the truth table for the
biconditional can be formed in the following two ways:
• General representation Computer representation
P Q R PQR P Q R PQR
T T T T 1 1 1 1
T T F F 1 1 0 0
T F T F 1 0 1 0
T F F F 1 0 0 0
F T T F 0 1 1 0
F T F F 0 1 0 0
F F T F 0 0 1 0
F F F T 0 0 0 1
21
 Q: Determine the truth values of each of the following:
(a) 4+2=5 and 6+3=9
(b) 3+2=5 or 6+1=7
(c) If 4+5=9 then 1+2=4
(d) 3+2=5 if and only if 4+7=11

Ans: (a) False

(b) True
(c) False
(d) True

22
Q. Construct the truth table for  ( P  Q )
Solution:
Whenever we encounter a complex formula like this,
we work from the inside out.
Thus, we start with the P and Q columns
Therefore, the required truth table is given as:

P Q P Q ( P  Q )
T T T F
T F F T
F T F T
F F F T

23
Q: Construct the truth table for  ( P  Q )   R
Solution:
Here, there are three variables: P, Q and R.
Thus we start with 3 initial columns showing all 8 possibilities
Therefore, the required truth table is given as:

P Q R P Q ( P  Q )  R ( P  Q )   R
T T T T F F F
T T F T F T F
T F T F T F F
T F F F T T T
F T T F T F F
F T F F T T T
F F T F T F F
F F F F T T T
24
 Q: Show the propositions ~ ( P  Q ) and ~ P ~ Q
are logically equivalent.

Ans:
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

It is observed that, the highlighted columns are identical

Therefore,
The given propositions are logically equivalent.
25
 Q: Verify the proposition P ~ ( P  Q )
is tautology.

Ans:
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

It is observed that, the truth values of the proposition are

true in the all cases.
Therefore,
The given proposition is tautology
26
 Tautology, Contradiction and
Satisfiable
 A compound statement or a proposition R(P,Q,…….) is called
Tautology Contradictio Contingency Satisfiable
n
If the truth values If the truth If the truth values If there exist at least
of R are always values of R of R are the one combination of
TRUE are always combination of input whose output
FALSE TRUE and is true.
If It is tautology,
we say that it is FALSE
Valid Statement

27
 Q: Find the converse, inverse and contrapositive arguments

Ans:

28
Propositional Equibalance
Two Propositions are said to be
logically equivalent if they have
the same truth values.
Two propositions P and Q are said
to be logically equivalent if is a
Tautology.
 e.g. is logically equivalent to

29
 Solve the following:
Q1: Construct the truth table for ~ ( P  Q )  (~ P  Q )
Q2: Check the argument P  ~ Q , R  Q , R  ~ Q is valid or
not. P, P  Q, Q  R  R
Q3: Show that is( Pvalid.
 Q ~ P )  ~ Q
Q4: Find the behaviorP  ( Qof  Rthe
) (statement:
P  Q ) ( P  R )
Q5: Prove that P  ( Q  ( P  Q ))
Q6: Construct the ( P truth
Q ) table
~ ( P  for
Q)
Q7: Prove that is a contradiction.
Q8: Show that the following statements are equivalent:
Statement_1: Good food is not cheap
Statement_2: Cheap food is not good
Q9: Check validity of the following argument:
If 7 is less than 4, then 7 is not a prime number
7 is not less than 4
---------------------------------------------------------------
7 is a prime number
30
 Stable Marriage Problem

It is a classic and well-known problem in the

field of discrete mathematics and algorithm
design. It deals with finding a stable
matching between two sets of elements with
preferences for each other.
The problem was first introduced by David
Gale and Lloyd Shapley in 1962, and it has
applications, where there are two groups of
participants with preferences for each other,
such as matching residents to hospitals,
students to schools, employees to jobs etc.
31
 Some more Application
College Admissions: In the context of college
admissions, the Stable Marriage Problem can
be used to match students to colleges or
universities based on their preferences and
admission criteria. This ensures that both the
students and the educational institutions are
satisfied with the final matching.

32
Partner Matching: The Stable Marriage Problem
can be used in online dating platforms or
matchmaking services to match potential partners
based on their preferences and compatibility. This
helps improve the chances of forming stable and
satisfying relationships.

Roommate Assignment: In situations where

multiple people need to be assigned to shared
accommodations, such as dormitories or
apartments, the Stable Marriage Problem can be
used to match individuals as roommates based on
their preferences.

33
Resource Allocation: The problem can be
adapted to allocate resources, such as project
assignments in a team or research funding, in a
way that ensures maximum satisfaction among
the participants and minimizes conflicts.

School Choice: The Stable Marriage Problem

can be applied to school choice programs,
where students and schools rank each other
based on preferences, and the algorithm ensures
that each student is assigned to the best possible
school based on their preferences and available
seats.
34
 Stable Marriage Problem
Algorithm:
1. Consider 2 individual groups
2. One group is known as proposing group
3. Other group is known as accepting/rejecting group
4. One individual from the proposing group who is not already engaged will
propose to their most preferable option who has not already rejected them.
5. The person being proposed to will:
(a) Accept if this is their first offer
(b) Reject if this is worse than their current offer
(c) Accept if this is better than their current offer
6. We continue this procedure, till we get perfect match.

Note: (a) If we get perfect match, we say that the problem is stable,
otherwise, the problem is unstable
(b) We may choose any group as proposing/accepting group
(c) If proposing group is Men then we say that Women optimal solution
(d) If proposing group is Women then we say that Men optimal solution
(e) The answer should same in two ways, then only stable.
35
 Q: Four boys (A, B, C, D) married to four girls (a, b, c, d).
Find the stability of the following preferences.

Boy Preferences Girl Preferences

A c b d a a A B D C
B b a c d b C A D B
C c a d b c C B D A
D c a d b d B A C D

Ans: Consider Boy group is proposing group (Girls optimal solution)

Boy Preferences Girl Preferences

A c b d a a A B D C
B b a c d b C A D B
C c a d b c C B D A
D c a d b d B A C D
36
 Step by step explanation:
1. At starting, A has proposed to c, c has accepted A’s proposal since she has
no previous proposals.
2. Next day, B has proposed to b, b has accepted B’s proposal since she has
no previous proposals.
3. Then, C has proposed to c, c has accepted C’s proposal and immediately
rejected A’s proposal, because it is best offer as compared with A (Means
there is no relationship between A and c, again A has to search).
4. In the next morning, D has proposed c, c has directly rejected D’s offer, because
already she has best offer as compared with D (Means there is no relationship
between D and c , again D has to search).
5. Next day, A has proposed to b, b has accepted A’s proposal and immediately rejected
B’s proposal, because it is best offer as compared with B (Means there is no
relationship between B and b , again B has to search).
6. Next day, B has proposed a, a has accepted B’s proposal since she has
no previous proposals.
7. Next day, D has proposed to a, a has directly rejected D’s offer, because already she
has best offer as compared with D (Means there is no relationship between D and a ,
again D has to search).
8. Next day, D has proposed d, d has accepted D’s proposal since she has
no previous proposals.
Now, we stop the process, as per the observations, we got the perfect matches and the problem is stable.
The perfect matches are: A-b, B-a, C-c, D-d.
Note: Try to find the stable matches by considering Girls proposing group.
37
 Find the stability of the following preferences in both ways
Boy Preferences Girl Preferences
Q1:
A L J K M J A D C B
B J M L K K A B C D
C K M L J L B D C A
D M K J L M C A B D

Q2: Men Preferences Women Preferences

M1 W1 W4 W3 W2 W1 M3 M1 M2 M4
M2 W1 W2 W3 W4 W2 M1 M4 M3 M2
M3 W2 W4 W3 W1 W3 M2 M4 M3 M1
M4 W3 W1 W2 W4 W4 M4 M2 M1 M3

38
 Boy Preferences Girl Preferences
Q3: M1 W2 W4 W1 W3 W1 M2 M1 M4
M2 W3 W1 W4 W2 M4 M3 M1
M3 W2 W3 W3 M1 M4 M3 M2
M4 W4 W1 W3 W2 W4 M2 M1 M4

39
 Proof by Mathematical
Induction
 Proof by mathematical induction that P(n) is true for every
positive integer “n” consists of the following two steps:
• Basic step: P(1) is shown to be true for n=1
• Inductive step: P(n) is assumed to be true for n=k; Then,
We need to prove that P(n) is true for n=k+1

40
 n( n  1 )
Q1:Prove that 1  2  3  ...  n  2

Proof: For n=1

L.H.S=1, R.H.S=1;
Therefore, it is true for n=1.
Let us consider the statement is true for n=k.
k( k  1 )
i.e., 1  2  3  ...  k 
2
The we need to show that, it is true for n=k+1
k( k  1 )
i.e., 1  2  3  ...  k  ( k  1 )  ( k 1)
2
k ( k  1 )  2( k  1 )

2
( k  1 )( k  2 )

2
( k  1 )(( k  1 )  1 )

2
We have reached the solution that is true for n=k+1; Hence proved.
41
 Q2: Prove that sum of the first n odd positive integers is n 2

Proof: As per the statement, we need to prove that: 1  3  5  ...  ( 2 n  1 ) n 2

For n=1
L.H.S=1, R.H.S=1;
Therefore, it is true for n=1.
Let us consider the statement is true for n=k.
i.e., 1  3  5  ...  ( 2 k  1 ) k 2

The we need to show that, it is true for n=k+1

i.e., 1  3  5  ...  ( 2 k  1 )  ( 2( k  1 )  1 ) k 2  ( 2( k  1 )  1 )
k 2  2 k  1
( k  1 )2

We have reached the solution that is true for n=k+1; Hence proved.

42
 Q3: Prove that n 3 - n is divisibleby 3, whenever n is a positiveinteger.

Proof: For n=1, 13 - 1 0

Means 0 is divisible by 3.
Therefore, it is true for n=1.
Let us consider the statement is true for n=k.
i .e., k 3 - k is divisibleby 3
The we need to show that, it is true for n=k+1
i .e., ( k  1 )3 - ( k  1 ) k 3  3k 2  3k  1  k  1
( k 3  k )  3( k 2  k )

As we know that, ( k 3  k ) is divisible by 3 and3( k 2  k ) is also divisible

by
3.
Both are divisible by 3, therefore the sum of those is also divisible by 3.

We have reached the solution that is true for n=k+1; Hence proved.
43
 Q4: Prove that 2 n  n! for every integer n with n 4.

Proof: For n=4

L.H.S=16, R.H.S=24;
Therefore, it is true for n=4.
Let us consider the statement is true for n=k.
i .e., 2 k  k!
The we need to show that, it is true for n=k+1
i .e., 2 k 1 2 k * 2
 2 * k ! ( By the statement )
 ( k  1 )* k ! k 4  ( k  1 )  4  ( k  1 )  2

 ( k  1 )! i .e ., 2  ( k  1 )

We have reached the solution that is true for n=k+1; Hence proved.

44
 Proof by contradiction
 Let us consider P is any statement.
In this method, we assume that P is false.
Then, by logical argument, we arrive at situation,
which is a contradiction.
This can happen only when ~P is false, which implies that P
must be true.

45
 2
Q1: There is no solution to the equation x  3x  1
x
x 3
2
Proof: Let there is a solution for the equation: x  3 x  1 x
x 3
Let p is the solution for the equation
Then, it satisfies
p2  3 p  1
 p  p 2  3 p  1  p 2  3 p  1 0
p 3
It is not possible
Therefore, our assumption is wrong
Therefore, there is no solution for the equation. (Hence
proved)

46
 Q2: Show that 2 is an irrational number

Proof: Assume that, 2 is a rational number.

x x2
2   2  2  x 2 2 y 2 (x and y have no common factor)
y y
Here x 2 is an even number, therefore x is an even number
Let x 2 k; k  Ζ
 x 2 4 k 2 2 * 2 k 2
Now, 2 y 2  x 2  2 y 2 2 * 2 k 2  y 2 2 k 2
Here y 2 is an even number, therefore y is an even number
Since x and y are both even numbers,
Thererefore, they have common factor.
Therefore, our assumptionis wrong.
Hence 2 is an irrational number.

47
Introduction Fuzzy Set

48
 Fuzzy Set
Fuzzy set is a concept in mathematical logic and set
theory introduced by Lotfi Zadeh in 1965.
It is an extension/generalization of classical/crisp
sets. The major property of the Fuzzy set is that it
allows the partial membership.
Unlike classical sets, where an element either
belongs to the set or does not, a fuzzy set is
concerned about the degrees of membership of that
particular element.
Elements belong to a Fuzzy set with a varying
degrees between zero and one, as per the strength of
their membership in the set. 49
 Some Applications of

Fuzzy Set
Control Systems: Fuzzy logic is employed
in control systems to deal with imprecise
input data and complex systems where
precise mathematical modeling is difficult.
Pattern Recognition: Fuzzy sets can be
used to classify patterns or objects that do
not have clearly defined boundaries.
Decision Making: Fuzzy logic allows for
reasoning under uncertainty, enabling
decision-making in situations where precise
information is lacking. 50
Natural Language Processing: Fuzzy sets are
used to model linguistic variables and deal with the
inherent vagueness in human language.
Medicine: Fuzzy sets are utilized in medical
diagnosis and decision support systems where the
boundaries between different disease states may
not be well-defined.
Reliability theory: Fuzzy techniques are applied to
optimize system reliability considering various
conflicting objectives and constraints. Fuzzy
reliability optimization models can handle
uncertainties in input parameters and preferences
of decision-makers, leading to robust and
adaptable designs.
51
Decision Making under Uncertainty: Fuzzy logic
is used in decision-making processes related to
reliability engineering, where decisions need to be
made in the presence of uncertain or imprecise
information.

Fault Diagnosis: Fuzzy logic is employed in fault

diagnosis systems to handle uncertain or incomplete
information about the state of components in a
system. By utilizing fuzzy inference techniques,
these systems can make decisions about the health or
condition of components based on fuzzy rules and
fuzzy membership functions.
52
Definition

53
 Membership Function
 It represents the degree (intensity) that a particular
input (element) belong to the set A.
 It represents the degree of membership of x with
respect to set A.
 It represents the degree of truthiness.
 A membership value “1” represent the completely
belongingness of x in the Fuzzy set A.
 A membership value “0” represent the completely not
belongingness of x in the Fuzzy set A.
 A membership value “between 0 an d 1” represent the
partial belongingness of x in the Fuzzy set A.
54
55
56
57
58
59
Operations on Fuzzy Sets

60
61
62
Problems

63
Q. The following Table show the annual salary of the
employs of a company.
[Link]. Name Age Net_Pay
1 Keven Norman 25 850000
2 Kristin Werner 26 470000
3 Avery Barber 24 930000
4 Boris Gibson 26 480000
5 Leif Mack 29 170000
6 Fredric Peters 32 680000
7 Sherry 27 470000
Bowman
8 Donte Richard 24 490000
9 Bobby Horton 24 1100000
10 Kenya Montoya 24 1000000

Find the following Fuzzy set

A = (All employs having high salary)
B = (All employ having low salary)
 Note: Consider that the employ whose salary is > or equal
to 1000000 is in high salary range.
 Consider that the employ whose salary is < or equal to
500000 is in low salary range.
64
Sol: The Membership function for Fuzzy
set A and B can be written as

Now by using the above membership

function one can draw the Fuzzy set A and
B.
65
Fuzzy Proposition
The fundamental difference
between classical propositions
and fuzzy propositions is in the
range of their truth values.
While each classical proposition
is required to be either true or
false, the truth or falsity of fuzzy
propositions is a matter of
degree.

66
Fuzzy quantifier

In traditional logic, quantifiers like "all" and

"some" are used to express the extent to which a
statement applies.

However, in fuzzy logic, where degrees of truth

are considered, fuzzy quantifiers allow for a
more refined expression of quantity.

67
Fuzzy quantifiers modify the truth value of a
statement based on a degree of membership in a set.
 For example, instead of saying "all students are
intelligent," which implies a binary truth value (true
or false), a fuzzy quantifier might say "most
students are intelligent," where "most" is a fuzzy
quantifier indicating a high degree of membership
in the set of intelligent students but not necessarily
all.
Common fuzzy quantifiers include "most,"
"many," "few," "almost all," "almost none," etc.
These quantifiers allow for a more flexible and
nuanced representation of uncertainty and
imprecision in natural language statements.
68
 Predicate and Quantifier
In logic and mathematics, a
predicate is a statement that may
be true or false depending on the
values of its variables.
It's is a function that returns a
truth value (true or false) when its
variables are assigned specific
values.

69
Any Questions ???

70