UNIT 3 :Logic

(Propositions, Logic Operations-Negation,

Disjunction, Conjunction, Conditional and
Bi-conditional, Truth Tables of compound
propositions, Translating English sentences in
to logical statements and vice versa, Logic
gates and circuits)

INTRODUCTION:
Logical reasoning provides the theoretical base for
many areas of mathematics and consequently
computer science. It has many practical
applications in computer science like design of
computing machines, artificial intelligence, definition
of data structures for programming languages etc.

Propositional Logic is concerned with statements

to which the truth values, “true” and “false”, can be
assigned. The purpose is to analyze these
statements either individually or in a composite
manner.
What is a Logic?
•When most people say ‘logic’, they mean
either propositional logic or first-order
predicate logic.
•However, the precise definition is quite broad,
and literally hundreds of logics have been
studied by philosophers,computer scientists
and mathematicians.
•Any ‘formal system’ can be considered a logic
if it has:
–a well-defined syntax;
–a well-defined semantics; and
–a well-defined proof-theory.
•The syntax of a logic defines the syntactically
acceptable objects of the language, which are
properly called well-formed formulae(wff). (We
shall just call them formulae.)
•The semantics of a logic associate each
formula with a meaning.
•The proof theory is concerned with
manipulating formulae according to certain
rules.

Logic is the basis of all mathematical

reasoning, and of all automated reasoning.
The rules of logic specify the meaning of
mathematical statements. These rules help us
understand and reason with statements such
as –
 such that where
Which in Simple English means “There
exists an integer that is not the sum of
two squares”.
Importance of Mathematical Logic
The rules of logic give precise meaning to
mathematical statements. These rules are
used to distinguish between valid and invalid
mathematical arguments.
Apart from its importance in understanding
mathematical reasoning, logic has numerous
applications in Computer Science, varying
from design of digital circuits, to the
construction of computer programs and
verification of correctness of programs.

Propositional Logic :
➢ A proposition is a collection of declarative
statements that has either a truth value "true”
or a truth value "false".
➢ A propositional consists of propositional
variables and connectives. We denote the
propositional variables by capital letters (A,
B, etc). The connectives connect the
propositional variables.
➢ Propositional calculus (or logic) is the study of
the logical relationship between objects called
 propositions and forms the basis of all
mathematical reasoning and all automated
reasoning.
➢ A proposition is a statement that is either true
or false, but not both (we usually denote a
proposition by letters;p,q,r,s,...)
➢ The value of a proposition is called its truth
value; denoted by T or 1 if it is true and F or 0
if it is false.
➢ Opinions, interrogative and imperative
sentences are not propositions.

Example (Propositions):
◆ Today is Monday.
◆ The derivative of sinx is cosx.
◆ Every even number has at least two factors.

Example (Not Propositions):

◆ C++is the best language.
◆ When is the pretest?
◆ Do your homework.

➢ A proposition is a statement that is,by itself,

either true or false.

Some examples of Propositions are given

below −
 • "Man is Mortal", it returns truth value
“TRUE”
• "12 + 9 = 3 – 2", it returns truth value
“FALSE”
The following is not a Proposition −
⚫ "A is less than 2". It is because unless we
give a specific value of A, we cannot say
whether the statement is true or false.
Example (Propositions?)
1. 2 + 2 = 5
2. Every integer is divisible by 12.
3. Microsoft is an excellent company
➢ Constructing Propositions : To avoid writing long
propositions we use propositional variables .A
propositional variable is typically a single letter (p,
q, r, ...). It can denote arbitrary propositions.
Examples:

1. p: it is raining
p represents the proposition “it is raining”
2. q: the streets are wet
q represents the proposition “the streets are wet”
➢ In Propositional Logic, there are two types of
sentences -- simple sentences and compound
sentences. Simple sentences express simple
facts about the world. Compound sentences
 express logical relationships between the simpler
sentences of which they are composed.

Simple sentences: Simple propositions are

declarative sentences which do not contain a
connective.Eg : 1.Grass is green.
2.the sentence:
Michael likes apples with tartar sauce.

contains the sentence "Michael likes apples"

as a part, but "with tartar sauce" does not
operate on, or modify the embedded sentence.
Rather, it modifies the non-sentence fragment,
or term, "apples." Therefore we must treat the
sentence as a simple sentence.
Compound sentences are formed from simpler
sentences and express relationships among the
constituent sentences. There are five types of
compound sentences, viz. negations, conjunctions,
dis-junctions, implications, and bi-conditionals.

In sentence "Lobsters are fierce but tasty." we

need to see that "but" means "and", and we
should rewrite the sentence as "Lobsters are
fierce and lobsters are tasty." This is a
complex sentence conjoined by "and". The two
simple sentences are "Lobsters are fierce" and
"Lobsters are tasty."

a) A negation consists of the negation operator

¬ and an arbitrary sentence, called the target.
For example, given the sentence p, we can form
the negation of p as shown below.

(¬p)
b)A conjunction is a sequence of sentences
separated by occurrences of the ∧ operator and
enclosed in parentheses, as shown below. The
constituent sentences are called conjuncts. For
example, we can form the conjunction of p and q
as follows.

(p ∧ q)
c) A disjunction is a sequence of sentences
separated by occurrences of the ∨ operator and
enclosed in parentheses. The constituent
sentences are called disjuncts. For example, we
can form the disjunction of p and q as follows.
 (p ∨ q)
d) An implication consists of a pair of sentences
separated by the ⇒ operator and enclosed in
parentheses. The sentence to the left of the
operator is called the antecedent, and the
sentence to the right is called the consequent.
The implication of p and q is shown below.

(p ⇒ q)
e) A bi-conditional is a combination of an
implication and a reverse implication. For
example, we can express the bi-conditional of p
and q as shown below.

(p ⇔ q)
Logical Operators: A logical operation
combines propositions using certain rules

Example:
•The operation denoted by “∧” means “and”
•“p ∧ q” means “it is raining and the streets are
wet”
•If both p and q are true then p ∧ q is true
•If either p or q (or both) are false then p ∧ q is
false
•“∧” is called the conjunction
(a) conjunction:“p and q”,p∧q.
(b) disjunction:“p or q”,p∨q.
(c) exclusive or :“exactly one of p or q”,
“p xor q”,p⊕q.
(d) implication:“if p then q”,p→q.
(e) bi-conditional:“p if and only if q”,p↔q.

Operations to construct compound

propositions:
•Conjunction ∧ AND
•Disjunction ∨ OR
•Negation ¬ NOT
•Implication → IF‐THEN
•Bi-conditional ↔ IFF

Truth Tables:
➢ Truth tables are used to exhibit the
relationship between the truth values of a
compound proposition and the truth values
of its component propositions.
➢ 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.

•Any proposition can be represented by a

truth table
•It shows truth values for all combinations
of its constituent variables
•Example: proposition r involving 2
variables p and q

all possible truth values of

combinations of compound
truth values of p proposition r
and q
p q r
True True
True False
False True
False False

Connectives
In propositional logic generally we use five
connectives which are −
⚫ OR (∨ )
⚫ AND (∧ )
⚫ Negation/ NOT (¬)
⚫ Implication / if-then (→)
⚫ If and only if (⇔).

1) (Disjunction) OR (∨) − The OR

operation of two propositions A and B
(written as A∨B) is true if at least any of the
propositional variable A or B is true.
Example,
The disjunction of the propositions – “Today
is Friday” and – “It is raining today”, 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.

The truth table is as follows −

 A B A∨B
True True True
True False True
False True True
False False False

2) (Conjunction) AND (∧) − The AND

operation of two propositions A and B
(written as A∧B) is true if both the
propositional variable A and B is true.
.•Conjunction is a way to combine two
propositions.
Example,
The conjunction of the propositions – “Today is
Friday” and – “It is raining today”, is “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.

The truth table is as follows −

A B A∧B
 True True True
True False False
False True False
False False False

3) Negation (¬) − The negation of a

proposition A (written as ¬A) is false when A
is true and is true when A is false.
Example,
The negation of “It is raining today”, is “It is not the
case that is raining today” or simply “It is not raining
today”.
A proposition can be negated.That is, if p is true, its
negation is false; if p is false, its negation is true.
•Some examples with natural language statements:
•e.g. in English: the negation of “John is going to
the store.” is “John is not going to the store.”
•Some are less easy to negate: “I will not go to the
store any day this week.” is negated to “I will go to
the store some day this week.”
•We'll write “¬p” for the negation of p.
•So we could say things like: “if p is the proposition
‘2+2=4’, then its negation is ¬p, ‘2+2≠4’.”
•“¬p” is itself a proposition: the “¬” takes a
proposition and makes a new one

The truth table is as follows −

A ¬A
True False
False True

4) Implication / if-then (→) − An implication

A→B is the proposition “if A, then B”. It is
false if A is true and B is false. The rest
cases are true.
In mathematics we often deal with conditional
statements like:

“if x=2,thenx2=4.
The if–then statement is called implication and it
is denoted as p→q. It is false when p is true and
q is false and true otherwise.

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 truth table is as follows −

 A B A→B
True True True
True False False
False True True
False False True

It is important to emphasize that p→q is false only

when p is true and q is false. In words, truth can not
imply a false statement, but false can imply truth.
For example, consider the following statement

if x= - 2 then x2 = 4
which is true even if the first part of this compound
statement is not true, say when x=2.

You might wonder that why is true when

is false. This is because the implication
guarantees that when and are true then the
implication is true. But the implication does not
guarantee anything when the premise is false.
There is no way of knowing whether or not the
implication is false since did not happen.
This situation is similar to the “Innocent until
proven Guilty” stance, which means that the
implication is considered true until
proven false. Since we cannot call the
implication false when 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 , some
of which are listed below.
"if , then "
" is sufficient for "
" when "
"a necessary condition for is "
" only if "
" unless "
" follows from "
Example,
“If it is Friday then it is raining today” is a
proposition which is of the form . 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.
5) If and only if (⇔) − A⇔B is bi-conditional
logical connective which is true when p and
q are same, i.e. both are false or both are
true.
For any two propositions and , the statement “ if
and only if(iff) ” is called a bi-conditional and it is
denoted by .
The statement is also called a bi-implication.
 has the same truth value as

The implication is true when and have same truth

values, and is false otherwise.

The truth table is as follows −

A B A⇔B
True True True
True False False
False True False
False False True

Example,
“It is raining today if and only if it is Friday
today.” is a proposition which is of the form
. 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.

6) Exclusive Or – For any two

propositions and , their exclusive or is
denoted by , which means “either
or but not both”. The exclusive or
is True when either or is True, and
False when both are true or both are
 false.
The truth table of is-

Example,
The exclusive or of the propositions –
“Today is Friday” and – “It is raining
today”, 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.
 Tautologies
A Tautology is a formula which is always true
for every value of its propositional variables.
Example − Prove [(A→B)∧A]→B is a
tautology

A B A → B (A → B) ∧ A [( A → B ) ∧ A] → B

True True True True True

True False False False True
False True True False True
False False True False True

The truth table is as follows −

As we can see every value of [(A→B)∧A]→B
is "True", it is a tautology.

Contradictions
A Contradiction is a formula which is always
false for every value of its propositional
variables.
Example − Prove (A∨B)∧[(¬A)∧(¬B)] is a
contradiction
The truth table is as follows −

A∨ (¬ A) ∧ (A ∨ B) ∧ [( ¬
A B ¬A ¬B
B ( ¬ B) A) ∧ (¬ B)]

True True True False False False False

True False True False True False False
False True True True False False False
False False False True True True False

As we can see every value of

(A∨B)∧[(¬A)∧(¬B)] is “False”, it is a
contradiction.

Contingency
A Contingency is a formula which has both
some true and some false values for every
value of its propositional variables.
Example − Prove (A∨B)∧(¬A) is a contingency
The truth table is as follows −
A B A ∨ B ¬ A (A ∨ B) ∧ (¬ A)
True True True False False
True False True False False
False True True True True
False False False True False
As we can see every value of (A∨B)∧(¬A)
has both “True” and “False”, it is a contingency.

Propositional Equivalences
Two statements X and Y are logically
equivalent if any of the following two
conditions hold −
⚫ The truth tables of each statement have the
same truth values.
⚫ The bi-conditional statement X⇔Y is a
tautology.
Example − Prove ¬(A∨B)and[(¬A)∧(¬B)]
are equivalent
Testing by 1st method (Matching truth table)

A∨ ¬ (A ∨ [(¬ A) ∧ (¬
A B ¬A ¬B
B B) B)]
True True True False False False False
True False True False False True False
False True True False True False False
False False False True True True True

Here, we can see the truth values of

¬(A∨B)and[(¬A)∧(¬B)] are same, hence the
statements are equivalent.

Testing by 2nd method (Bi-conditionality)

 ¬ (A ∨ [(¬ A) ∧ [¬ (A ∨ B)] ⇔
A B
B) (¬ B)] [(¬ A ) ∧ (¬ B)]
True True False False True
True False False False True
False True False False True
False False True True True
As [¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology, the
statements are equivalent.
Example: Consider the following propositions
1. ~p∨∼q and ∼(p∧q).
Are they equivalent?
Solution: Construct the truth table for both

p q ~p ~q ~p∨∼q p∧q ~(p∧q)

True True False False False True False
True False False True True False True
False True True False True False True
False False True True True False True

Conditional Statement:

❖ Implication / if-then (→) is also called a

conditional statement. It has two parts −
• Hypothesis, p
• Conclusion, q
As mentioned earlier, it is denoted as p→q
Example of Conditional Statement − “If you
do your homework, you will not be punished.”
Here, "you do your homework" is the
hypothesis, p, and "you will not be punished"
is the conclusion, q.
Let p and q are two statements then "if p then
q" is a compound statement, denoted by p→ q
and referred as a conditional statement, or
implication. The implication p→ q is false only
when p is true, and q is false; otherwise, it is
always true. In this implication, p is called the
hypothesis (or antecedent) and q is called the
conclusion (or consequent).

p q p→q
True True True
True False False
False True True
False False True

For Example: The followings are conditional

statements.
1. If a = b and b = c, then a = c.
2. If I get money, then I will purchase a
computer.
Variations in Conditional Statement
Inverse, Converse, and Contra-positive
⚫ Inverse − An inverse of the conditional
statement is the negation of both the
hypothesis and the conclusion. If the
statement is “If p, then q”, the inverse will be
“If not p, then not q”. Thus the inverse of
p→q is ¬p→¬q
Example − The inverse of “If you do your
homework, you will not be punished” is “If you
do not do your homework, you will be
punished.”
⚫ Converse − The converse of the conditional
statement is computed by interchanging the
hypothesis and the conclusion. If the
statement is “If p, then q”, the converse will
be “If q, then p”. Thus the converse of
p→q is q→p.
Example − The converse of "If you do your
homework, you will not be punished" is "If you
will not be punished, you do your homework”.
⚫ Contra-positive − The contra-positive of
the conditional is computed by
interchanging the hypothesis and the
conclusion of the inverse statement. If the
statement is “If p, then q”, the contra-
 positive will be “If not q, then not p”. The
contra-positive of p→q is ¬q→¬p.
Example − The Contra-positive of " If you do
your homework, you will not be punished” is "If
you are punished, you did not do your
homework”.

Contra-positive: The proposition ~q→~p is called contra-

positive of p →q.

Converse: The proposition q→p is called the converse of p

→q.

Inverse: The proposition ~p→~q is called the inverse of p

→q.

To summarize,

Note : It is interesting to note that the truth

value of the conditional statement is the
same as it’s contra-positive, and the truth
value of the Converse of is the same as
the truth value of its Inverse.
When two compound propositions always
have the same truth value, they are said to be
equivalent.
Therefore,
•
•

Example1: Show that p →q and its contra-

positive ~q→~p are logically equivalent.
Solution: Construct the truth table for both the
propositions:
p q ~p ~q p →q ~q→~p
True True False False True True
True False False True False False
False True True False True True
False False True True True True
As, the values in both cases are same, hence
both propositions are equivalent.
Example2: Show that proposition q→p, and
~p→~q is not equivalent to p →q.
Solution: Construct the truth table for all the
above propositions:
p q ~p ~q p →q q→p ~p→~q
True True False False True True True
True False False True False True True
False True True False True False False
False False True True True True True
As, the values of p →q in a table is not equal
to q→p and ~p→~q as in fig. So both of them
are not equal to p →q, but they are
themselves logically equivalent.
Bi- Conditional Statement
If p and q are two statements then "p if and
only if q" is a compound statement, denoted as
p ↔ q and referred as a bi-conditional
statement or an equivalence. The equivalence
p ↔ q is true only when both p and q are true
or when both p and q are false.
p q p↔q
True True True
True False False
False True False
False False True
For Example:
(i) Two lines are parallel if and only if they
have the same slope.
(ii) You will pass the exam if and only if you
will work hard.
Example: Prove that p ↔ q is equivalent to
(p →q) ∧(q→p).
Solution: Construct the truth table for both the
propositions:
p q p↔q
True True True
True False False
False True False
False False True

p q p →q q→p (p →q)∧(q→p)
True True True True True
True False False True False
False True True False False
False False True True True
Since, the truth tables are the same, hence
they are logically equivalent. Hence Proved.

Derived Connectors
1. NAND: It means negation after ANDing of
two statements. Assume p and q be two
propositions. Nanding of p and q to be a
proposition which is false when both p and q
are true, otherwise true. It is denoted by p ↑ q.
p q p↑q
True True False
True False True
False True True
False False True
2. NOR or Joint Denial: It means negation
after ORing of two statements. Assume p and
q be two propositions. NORing of p and q to
be a proposition which is true when both p and
q are false, otherwise false. It is denoted by
p ↓ q.
p q p↓q
True True False
True False False
False True False
False False True
3. XOR: Assume p and q be two propositions.
XORing of p and q is true if p is true or q is
true but not both and vice-versa. It is denoted
by p ⨁ q.
 p q p⨁q
True True False
True False True
False True True
False False False
Example1: Prove that
X ⨁ Y ≅ (X∧∼Y)∨(∼X∧Y).
Solution: Construct the truth table for both the
propositions.
(X ∧∼Y)
X Y X⨁Y ∼Y ∼X X ∧∼Y ∼X∧Y ∨
(∼X∧Y)
True True False False False False False False
True False True True False True False True
False True True False True False True True
False False False True True False False False
As the truth table for both the proposition is the
same.
X ⨁ Y ≅ (X ∧∼Y)∨(∼X∧Y).
Hence Proved.
Example2: Show that (p ⨁q) ∨(p↓q) is
equivalent to p ↑ q.
Solution: Construct the truth table for both the
propositions.
 (p⨁q)
p q p⨁q (p↓q) ∨ p↑q
(p↓q)
True True False False False False
True False True False True True
False True True False True True
False False False True True True

Precedence order of Logical

Connectives :
Logical connectives are used to construct
compound propositions by joining existing
propositions. Although parenthesis can be
used to specify the order in which the
logical operators in the compound
proposition need to be applied, there
exists a precedence order in Logical
Operators.
The precedence Order is-
Here, higher the number lower the
precedence
Translating English Sentences :
Natural Languages such as English are
ambiguous i.e. a statement may have multiple
interpretations. Therefore it is important to
convert these sentences into mathematical
expressions involving propositional variables
and logical connectives.
The above process of conversion may take
certain reasonable assumptions about the
intended meaning of the sentence. Once the
sentences are translated into logical
expressions they can be analyzed further to
determine their truth values. Rules of
Inference can then further be used to reason
about the expressions.
Example :
“You can access the Internet from campus
only if you are a computer science major or
you are not a freshman.”
The above statement could be considered as
a single proposition but it would be more
useful to break it down into simpler
propositions. That would make it easier to
analyze its meaning and to reason with it.
The above sentence could be broken down
into three propositions,
- "You can access the Internet from
campus."
- "You are a computer science major."
- "You are a freshman."
Using logical connectives we can join the above-
mentioned propositions to get a logical expression
of the given statement.
“only if” is one way to express a conditional
statement,
Therefore the logical expression would be –

Guidelines to Translation
(i).If the sentence you are translating is a
simple declarative sentence, then you’re done.
Remember, in Propositional Logic, these are
just represented as atomic propositions, e.g.,
p..
(ii). Assuming the sentence you have to
translate is a compound sentence, the first
step is to identify the simple, declarative
sentences in it. (We will ignore embedded
sentences. So for example, the sentence I
know Bob is happy is treated as a simple
declarative sentence, even though it contains
the embedded sentence Bob is happy.)
(iii). Once you’ve identified the simple,
declarative sentences, translate these into
atomic propositions. You can write each one
like this: “p = ...” or “Let p = ...”
(iv).Next you need to identify those words that
string the simple sentences together in English,
e.g., and, but, or, if...then, if and only if, just in
case, it is not the case that, unless,only if,
when, etc.
(v).Once you’ve identify these words, translate
them into the appropriate connectives in
Propositional Logic.
(vi).Lastly, you need to determine the order the
atomic propositions combine in with the
connectives. When you combine the atomic
propositions, remember that the syntactic rules
of PL(propositional logic ) must be satisfied—
so you’re not working in a vacuum. These
rules can help guide you.
(vii).Remember to use (but not abuse) the
parenthesis. They make a difference. Pay
attention to Rule (ii) to figure out where they
go.
Atomic propositions correspond to simple,
declarative sentences. So these are the
easiest to translate. To do this, we need only
equate an atomic proposition to the sentence
we want it to correspond to.

Translating Simple Declarative Sentences

a. Let p = It is raining.
b.Let q = Mary is sick.
c.Let t = Bob stayed up late last night.
d.Let r = Paris is the capital of France.
e.Let s = John is a loud-mouth.
Suppose that what we understand informally
as negation (¬) corresponds to the use of “not”
and related terms in natural language.

Translating Negation

(A) It isn’t raining (¬p)

(B) It is not the case that Mary isn’t sick(¬(¬q))
(C) Paris is not the capital of France (¬r)
(D) John is in no way a loud-mouth (¬s)
(E) Bob did not stay up late last night (¬t)

Now suppose what we understand informally

as conjunction (∧) corresponds to the use of
“and” and related terms in natural
language,like “but”. .

Translating Conjunction
(A) It is raining and Mary is sick(p ∧ q)
(B) Bob stayed up late last night and John is
a loud-mouth(t ∧ s)
(C) Paris isn’t the capital of France and It
isn’t raining(¬r ∧¬p)
(D) John is a loud-mouth but Mary isn’t sick
(s ∧¬q)
(E) It is not the case that it is raining and
Mary is sick
translation 1: It is not the case that both it is
raining and Mary is sick ¬(p ∧ q)
translation 2: Mary is sick and it is not the case
that it is raining (¬p ∧ q)

Translating Disjunction

(A) It is raining or Mary is sick (p ∨ q)

(B) Paris is the capital of France and it is
raining or John is a loud-mouth
((r ∧ p) ∨ s) or (r ∧ (p ∨ s))
(C) Mary is sick or Mary isn’t sick (q ∨¬q)
(D) John is a loud-mouth or Mary is sick or it
is raining ((s ∨ q) ∨ p) or (s ∨ (q ∨ p))
(E) It is not the case that Mary is sick or Bob
stayed up late last night ¬(q ∨ t) or (¬q ∨ t)
Whenever a compound sentence includes
conjunction and disjunction, ambiguity is quite
possible so be on guard. Once again, the
sentences are translated into distinct
propositions, one for each meaning. The
context or intonation can disambiguate which
proposition actually corresponds to the
sentence whenever it is uttered.
Suppose what we understand informally as
implication (→) corresponds to the use of “if ...
then ...”in natural language and related terms
like “when”.

Translating Implication

(A) If it is raining, then Mary is sick (p → q)

(B) It is raining, when John is a loud-mouth
(s → p)
(C) Mary is sick and it is raining implies that
Bob stayed up late last night ((q ∧ p) → t)
(D) It is not the case that if it is raining then
John isn’t a loud-mouth ¬(p →¬s)

Suppose what we know informally as

equivalence (↔) corresponds to the use of “if
and only if” in natural language and related
terms,such as “just in case” and “if ... , then ... ,
and vice versa”.
Translating Equivalence

(A) It is raining if and only if Mary is sick

(p ↔ q)
(B) If Mary is sick then it is raining, and vice
versa ((p → q) ∧ (q → p)) or (p ↔ q)
(C) It is raining is equivalent to John is a
loud-mouth (p ↔ s)
(D) It is raining is not equivalent to John is a
loud-mouth ¬(p ↔ s)
Equivalence of Propositions :Two
propositions are said to be logically equivalent if
they have exactly the same truth values under all
circumstances.The table contains the fundamental
logical equivalent expressions:

Laws of the algebra of propositions

The above Logical Equivalences used only
conjunction, disjunction and negation. Other
logical Equivalences using conditionals and bi-
conditionals are-
Example,
Show that .
Considering LHS,

Another example,
Show that .
Considering LHS,
❖ De Morgan’s Law :
In propositional logic and boolean algebra, De
Morgan’s laws are a pair of transformation
rules that are both valid rules of inference.
They are named after Augustus De Morgan, a
19th-century British mathematician. The rules
allow the expression of conjunctions and
disjunctions purely in terms of each other via
negation.
In formal language, the rules are written as –
•

Proof by Truth Table –

Duality Principle
Two formulas A1 and A2 are said to be dual of each
other if either one can be obtained from the other by
replacing ∧ (AND) by ∨ (OR) and ∨ (OR) by ∧
(AND). Also if the formula contains T (True) or F
(False), then we replace T by F and F by T to obtain
the dual.

Duality principle states that for any true

statement, the dual statement obtained by
interchanging unions into intersections (and
vice versa) and interchanging Universal set
into Null set (and vice versa) is also true. If
dual of any statement is the statement itself, it
is said self-dual statement.
Example − The dual of (A∩B)∪C is (A∪B)∩C
Note1: The two connectives ∧ and ∨ are called
dual of each other.
2. Like AND and OR, ↑ (NAND) and ↓ (NOR) are
dual of each other.
3. If any formula of the proposition is valid, then
it's dual of each other.

Normal Forms
The problem of finding whether a given
statement is tautology or contradiction or
satiable in a finite number of steps is called the
Decision Problem. For Decision Problem,
construction of truth table may not be practical
always. We consider an alternate procedure
known as the reduction to normal forms.
There are two such forms:
1. Disjunctive Normal Form (DNF)
2. Conjunctive Normal Form
Disjunctive Normal Form (DNF): If p, q are
two statements, then "p or q" is a compound
statement, denoted by p ∨ q and referred as
the disjunction of p and q. The disjunction of p
and q is true whenever at least one of the two
statements is true, and it is false only when
both p and q are false
p q p∨q
True True True
True False True
False True True
False False False
Example: - If p is "4 is a positive integer" and
q is "√5 is a rational number", then p ∨ q is true
as statement p is true, although statement q is
false.
A compound statement is in disjunctive normal
form if it is obtained by operating OR among
variables (negation of variables included)
connected with ANDs. In terms of set
operations, it is a compound statement
obtained by Union among variables connected
with Intersections.
Examples
➢ (A∧B)∨(A∧C)∨(B∧C∧D)
➢ (P∩Q)∪(Q∩R)
Conjunctive Normal Form: If p, q are two
statements, then "p and q" is a compound
statement, denoted by p ∧ q and referred as
the conjunction of p and q. The conjunction of
p and q is true only when both p and q are true,
otherwise, it is false

p q p∧q
True True True
True False False
False True False
False False False

Example: If statement p is "6<7" and

statement q is "-3>-4" then the conjunction of p
and q is true as both p and q are true
statements
A compound statement is in conjunctive
normal form if it is obtained by operating AND
among variables (negation of variables
included) connected with ORs. In terms of set
operations, it is a compound statement
obtained by Intersection among variables
connected with Unions.
Examples
➢ (A∨B)∧(A∨C)∧(B∨C∨D)
➢ (P∪Q)∩(Q∪R)

Predicate Logic
Predicate Logic deals with predicates, which
are propositions containing variables.
A predicate is an expression of one or more
variables defined on some specific domain. A
predicate with variables can be made a
proposition by either assigning a value to the
variable or by quantifying the variable.
The following are some examples of
predicates −
• Let E(x, y) denote "x = y"
• Let X(a, b, c) denote "a + b + c = 0"
• Let M(x, y) denote "x is married to y"
Well Formed Formula
Well Formed Formula (wff) is a predicate
holding any of the following −
◆ All propositional constants and propositional
variables are wffs. If x is a variable and Y is
a wff, ∀xY and ∃xY are also wff
Truth value and false values are wffs
Each atomic formula is a wff
All connectives connecting wffs are wffs

For all (∀)

There exists (∃)

Quantifiers
The variable of predicates is quantified by
quantifiers. There are two types of quantifier in
predicate logic − Universal Quantifier and
Existential Quantifier.
Universal Quantifier
Universal quantifier states that the statements
within its scope are true for every value of the
specific variable. It is denoted by the symbol
∀.∀xP(x) is read as for every value of x, P(x) is
true.
Mathematical statements sometimes assert
that a property is true for all the values of a
variable in a particular domain, called the
domain of discourse. Such a statement is
expressed using universal quantification.
The universal quantification of P(x)for a
particular domain is the proposition that
asserts that P(x) is true for all values of x in
this domain. The domain is very important
here since it decides the possible values of x.
The meaning of the universal quantification of
P(x) changes when the domain is changed.
The domain must be specified when a
universal quantification is used, as without it, it
has no meaning.
Example − "Man is mortal" can be
transformed into the propositional form ∀xP(x)
where P(x) is the predicate which denotes x is
mortal and the universe of discourse is all men.
If p(x) is a proposition over the universe U.
Then it is denoted as ∀x,p(x) and read as "For
every x∈U,p(x) is true." The quantifier ∀ is
called the Universal Quantifier.
There are several ways to write a proposition,
with a universal quantifier.
∀x∈A,p(x) or p(x), ∀x ∈A Or ∀x,
p(x) or p(x) is true for all x ∈A.

Existential Quantifier
Existential quantifier states that the statements
within its scope are true for some values of the
specific variable. It is denoted by the symbol
∃.∃xP(x) is read as for some values of x, P(x)
is true.
Some mathematical statements assert that
there is an element with a certain property.
Such statements are expressed by existential
quantification. Existential quantification can be
used to form a proposition that is true if and
only if P(x) is true for at least one value of in
the domain.

Example − "Some people are dishonest" can

be transformed into the propositional form
∃xP(x)
where P(x) is the predicate which denotes x is
dishonest and the universe of discourse is
some people.
If p(x) is a proposition over the universe U.
Then it is denoted as ∃x p(x) and read as
"There exists at least one value in the universe
of variable x such that p(x) is true. The
quantifier ∃ is called the existential quantifier.
There are several ways to write a proposition,
with an existential quantifier, i.e.,
(∃x∈A)p(x) or ∃x∈A such that p
(x) or (∃x)p(x) or p(x) is true for some x
∈A.
Example : Let P(x) be the statement “ > 5″.
What is the truth value of the statement
?
Solution: P(x) is true for all real numbers
greater than 5 and false for all real numbers
less than 5. So .
To summarise,

Negation of Quantified Propositions:

When we negate a quantified proposition, i.e.,
when a universally quantified proposition is
negated, we obtain an existentially quantified
proposition,and when an existentially
quantified proposition is negated, we obtain a
universally quantified proposition.
The two rules for negation of quantified
proposition are as follows. These are also
called DeMorgan's Law.
Example: Negate each of the following
propositions:
1.∀x p(x)∧ ∃ y q(y)
Sol: ~.∀x p(x)∧ ∃ y q(y))
≅~∀ x p(x)∨∼∃yq(y)
(∴∼(p∧q)=∼p∨∼q)
≅ ∃ x ~p(x)∨∀y∼q(y)
2. (∃x∈U) (x+6=25)
Sol: ~( ∃ x∈U) (x+6=25)
≅∀ x∈U~ (x+6)=25
≅(∀ x∈U) (x+6)≠25
3. ~( ∃ x p(x)∨∀ y q(y)
Sol: ~( ∃ x p(x)∨∀ y q(y))
≅~∃ x p(x)∧~∀ y q(y)
(∴~(p∨q)= ∼p∧∼q)
≅ ∀ x ∼ p(x)∧∃y~q(y))
Propositions with Multiple Quantifiers:
The proposition having more than one variable
can be quantified with multiple quantifiers. The
multiple universal quantifiers can be arranged
in any order without altering the meaning of
the resulting proposition. Also, the multiple
existential quantifiers can be arranged in any
order without altering the meaning of the
proposition.
The proposition which contains both universal
and existential quantifiers, the order of those
quantifiers can't be exchanged without altering
the meaning of the proposition, e.g., the
proposition ∃x ∀ y p(x,y) means "There exists
some x such that p (x, y) is true for every y."
Example: Write the negation for each of the
following. Determine whether the resulting
statement is true or false. Assume U = R.
1.∀ x ∃ m(x2<m)
Sol: Negation of ∀ x ∃ m(x2<m) is ∃ x ∀ m
(x2≥m). The meaning of ∃ x ∀ m (x2≥m) is that
there exists for some x such that x2≥m, for
every m. The statement is true as there is
some greater x such that x2≥m, for every m.
2. ∃ m∀ x(x2<m)
Sol: Negation of ∃ m ∀ x (x2<m) is ∀ m∃x
(x2≥m). The meaning of ∀ m∃x (x2≥m) is that
for every m, there exists for some x such that
x2≥m. The statement is true as for every m,
there exists for some greater x such that x2≥m.
To deduce new statements from the
statements whose truth that we already know,
Rules of Inference are used.
While the word “argument” may mean a
disagreement between two or more people, in
mathematical logic, an argument is a
sequence or list of statements called premises
or assumptions and returns a conclusion.
An argument is only valid when the conclusion,
which is the final statement of the opinion,
follows the truth of the discussion’s preceding
assertions.
Consequently, it is our goal to determine the
conclusion’s truth values based on the rules of
inference.
Definition
The rules of inference (also known as
inference rules) are a logical form or guide
consisting of premises (or hypotheses) and
draws a conclusion.
A valid argument is when the conclusion is
true whenever all the beliefs are true, and an
invalid argument is called a fallacy.
In other words, an argument is valid when the
conclusion logically follows from the truth
values of all the premises.
There are two ways to form logical arguments,
as seen in the image below. We will be
utilizing both formats in this lesson to become
familiar and comfortable with their framework.

Basic Example
Now, before we jump into the inference rules,
let’s look at a basic example to help us
understand the notion of assumptions and
conclusions.
Is this argument valid?
Without using our rules of logic, we can
determine its truth value one of two ways.
1. Surmising the fallacy of each premise,
knowing that the conclusion is valid only
when all the beliefs are valid.
2. Construct a truth table and verify a
tautology.
From the above example, if we know that both
premises “If Marcus is a poet, then he is poor”
and “Marcus is a poet” are both true, then the
conclusion “Marcus is poor” must also be true.
And using a truth table validates our claim as
well.
 What are Rules of Inference for?
Mathematical logic is often used for logical
proofs. Proofs are valid arguments that
determine the truth values of mathematical
statements.
An argument is a sequence of statements. The
last statement is the conclusion and all its
preceding statements are called premises (or
hypothesis). The symbol “∴”, (read therefore)
is placed before the conclusion. A valid
argument is one where the conclusion follows
from the truth values of the premises.
Rules of Inference provide the templates or
guidelines for constructing valid arguments
from the statements that we already have.

Table of Rules of Inference

Rule of Name Rule of
Name
Inference Inference
P P∨Q Disjunctive
Addition ¬P Syllogism
∴P∨Q ∴Q
P Hypothetical
P→Q Syllogism
Q Conjunction
Q→R
∴P∧Q ∴P→R
Simplification (P→Q)∧(R→S) Constructive
 P∧Q P∨R Dilemma

∴P ∴Q∨S
P→Q (P→Q)∧(R→S) Destructive
¬Q∨¬S Dilemma
P Modus Ponens

∴Q ∴¬P∨¬R
P→Q Modus Tollens

¬Q

∴¬P

◆ Addition
If P is a premise, we can use Addition rule
to derive P∨Q.
P

∴P∨Q
Example
Let P be the proposition, “He studies very hard”
is true
Therefore − "Either he studies very hard Or he
is a very bad student." Here Q is the
proposition “he is a very bad student”.
◆ Conjunction
If P and Q are two premises, we can use
Conjunction rule to derive P∧Q.
P
Q

∴P∧Q
Example
Let P − “He studies very hard”
Let Q − “He is the best boy in the class”
Therefore − "He studies very hard and he is
the best boy in the class"
◆ Simplification
If P∧Q is a premise, we can use Simplification
rule to derive P.
P∧Q

∴P

Example
"He studies very hard and he is the best boy in
the class", P∧Q
Therefore − "He studies very hard"
◆ Modus Ponens
If P and P→Q are two premises, we can use
Modus Ponens to derive Q.
P→Q
P

∴Q
Example
"If you have a password, then you can log on
to facebook", P→Q
"You have a password", P
Therefore − "You can log on to facebook"
◆ Modus Tollens
If P→Q and ¬Q are two premises, we can use
Modus Tollens to derive ¬P.
P→Q
¬Q
∴¬P
Example
"If you have a password, then you can log on
to facebook", P→Q
"You cannot log on to Facebook", ¬Q
Therefore − "You do not have a password "
◆ Disjunctive Syllogism
If ¬P and P∨Q are two premises, we can use
Disjunctive Syllogism to derive Q.
¬P
P∨Q

∴Q
Example
"The ice cream is not vanilla flavored", ¬P
"The ice cream is either vanilla flavored or
chocolate flavored", P∨Q
Therefore − "The ice cream is chocolate
flavored”
◆ Hypothetical Syllogism
If P→Q and Q→R are two premises, we can
use Hypothetical Syllogism to derive P→R
P→Q
Q→R

∴P→R
Example
"If it rains, I shall not go to school”, P→Q
"If I don't go to school, I won't need to do
homework", Q→R
Therefore − "If it rains, I won't need to do
homework"
◆ Constructive Dilemma
If (P→Q)∧(R→S) and P∨R are two premises,
we can use constructive dilemma to derive
Q∨S.
(P→Q)∧(R→S)
P∨R

∴Q∨S
Example
“If it rains, I will take a leave”, (P→Q)
“If it is hot outside, I will go for a shower”,
(R→S)
“Either it will rain or it is hot outside”, P∨R
Therefore − "I will take a leave or I will go for a
shower"

◆ Destructive Dilemma
If (P→Q)∧(R→S) and ¬Q∨¬S are two
premises, we can use destructive dilemma to
derive ¬P∨¬R.
(P→Q)∧(R→S)
¬Q∨¬S

∴¬P∨¬R
Example
“If it rains, I will take a leave”, (P→Q)
“If it is hot outside, I will go for a shower”,
(R→S)
“Either I will not take a leave or I will not go for
a shower”, ¬Q∨¬S
Therefore − "Either it does not rain or it is not
hot outside"

Rules Of Inference Examples

Let’s look at an example for each of these
rules to help us make sense of things.
Let p be “It is raining,” and q be “I will make
tea,” and r be “I will read a book.”
Example — Modus Ponens

Example — Modus Tollens

Example — Hypothetical Syllogism

Example — Disjunctive Syllogism

Example — Addition

Example — Simplification

Example - Resolution

Valid Vs Invalid Argument

Test the validity of the argument:
• If it snows, Paul will miss class.
• Paul did not miss class.
• Therefore, it did not snow.
First, we will translate the argument into
symbolic form and then determine if it matches
one of our rules.

Because the argument matches one of our

known logic rules, we can confidently state
that the conclusion is valid.
Let’s look at another example.
Test the validity of the argument:
• If it snows, Paul will miss class. (P→Q )
• It did not snow. (¬ P)
• Therefore, Paul did not miss class.( ∴ ¬Q)
So, now we will translate the argument into symbolic form
and then determine if it matches one of our rules for
inference.Because the argument does not match one of
our known rules, we determine that the conclusion is
invalid.

LOGIC GATES AND CIRCUITS :

Logic gates are the basic building blocks of

any digital system. It is an electronic circuit
having one or more than one input and only
one output. The relationship between the input
and the output is based on a certain logic.
Based on this, logic gates are named as AND
gate, OR gate, NOT gate etc.
⚫ AND Gate
A circuit which performs an AND operation is
shown in figure. It has n input (n ≥ 2) and one
output.

Logic diagram
Truth Table

0 = FALSE
1 = TRUE

⚫ OR Gate
A circuit which performs an OR operation is
shown in figure. It has n input (n ≥ 2) and one
output.

Logic diagram
Truth Table

⚫ NOT Gate
NOT gate is also known as Inverter. It has
one input A and one output Y.

Logic diagram
Truth Table

⚫ NAND Gate
A NOT-AND operation is known as NAND
operation. It has n input (n ≥ 2) and one output.

Logic diagram
Truth Table

⚫ NOR Gate
A NOT-OR operation is known as NOR
operation. It has n input (n ≥ 2) and one output.

Logic diagram
Truth Table

⚫ XOR Gate
XOR or Ex-OR gate is a special type of gate. It
can be used in the half adder, full adder and
subtractor. The exclusive-OR gate is
abbreviated as EX-OR gate or sometime as
X-OR gate. It has n input (n ≥2) and one
output.
Logic diagram

Truth Table

⚫ XNOR Gate
XNOR gate is a special type of gate. It can be
used in the half adder, full adder and
subtractor. The exclusive-NOR gate is
abbreviated as EX-NOR gate or sometime as
X-NOR gate. It has n input (n ≥ 2) and one
output.
Logic diagram

Truth Table