Truth tables Truth table for the statement form ~ p ∧ q

Truth tables for:

p q ~p ~p∧q
~p∧q
~ p ∧ (q ∨ ~ r)
(p ∨ q) ∧ ~ (p ∧ q)

Discrete Structures
BSCS (3 Credit Hour)
Lecture # 02

Truth table for ~ p ∧ (q ∨ ~ r) Truth table for (p ∨ q) ∧ ~ (p ∧ q) Double Negative Property ~(~p) ≡ p
p q r ~r q∨~ ~p ~ p ∧ (q ∨ ~ p q p ∨ q p ∧ ~ (p∧q) (p ∨ q) ∧ ~ (p ∧ p ~p ~(~p)
r r) q q)

~ (p ∧ q) and ~p ∧ ~q are not logically

Example: equivalent DE MORGAN’S LAWS:
“It is not true that I am not happy” The negation of an and statement is logically equivalent
Prove it double negation property for the above p q ~p ~q p ∧ q ~(p∧q) ~p ∧ ~q to the or statement in which each component is negated.
statement ~ (~p) ≡ p Symbolically: ~(p ∧ q) ≡ ~p ∨ ~q.
Solution:
Let p = “I am happy” The negation of an or statement is logically equivalent to
Then ~p = “I am not happy” the and statement in which each component is negated.
and ~(~ p) = “It is not true that I am not happy” Symbolically: ~(p ∨ q) ≡ ~p ∧ ~q.
Since ~ (~p) ≡ p
Hence the given statement is equivalent to:
“I am happy”
 Application of De morgan’s Law using
Truth Table for ~(p ∨ q) ≡ ~p ∧ ~q statements: Exercise:
Give negations for each of the following Associative Law
p q ~p ~q p∨ ~(p ∨ q) ~p ∧ statements:
q ~q
The fan is slow or it is very hot. Are the statements (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)?
Akram is unfit and Saleem is injured. Are the statements (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) logically
equivalent?
Solution:
The fan is not slow and it is not very hot.
Akram is not unfit or Saleem is not injured.

TAUTOLOGY: CONTRADICTION: EXAMPLE:

A tautology is a statement form that is always true A contradiction is a statement form that is always false The statement form p ∧ ~ p is a contradiction.
regardless of the truth values of the statement variables. regardless of the truth values of the statement variables.
A tautology is represented by the symbol “T”.. A contradiction is represented by the symbol “c”. p ~p p∧~
p
EXAMPLE:
Note:
The statement form p ∨ ~ p is tautology
So if we have to prove that a given statement form is Since in the last column in the truth table we have F in all
p ~p p∨~p CONTRADICTION we will make the truth table for the entries so is a contradiction
the statement form and if in the column of the given p ∧ ~p ≡c
statement form all the entries are F ,then we say that
statement form is contradiction.
p ∨ ~p ≡ t

LOGICAL EQUIVALENCE INVOLVING

HOME Work REMARKS: TAUTOLOGY
Show that p ∧ t ≡ p

Most statements are neither tautologies nor ∧

contradictions.
(p˄q)˅(̴ p˅(P˅ ̴ q)) ≡ t The negation of a tautology is a contradiction and vice
versa.
(p˄ ̴ q)˄ (̴ P˅ q)) ≡ c Since in the above table the entries in the first and last
columns are identical so we have the corresponding
statement forms are Logically Equivalent that is
p∧t≡p
 LOGICAL EQUIVALENCE INVOLVING
CONTRADICTION EXERCISE: INEQUALITIES AND DEMORGAN’S LAWS
Show that p ∧ c ≡ c Use truth table to show that (p ∧ q) ∨ (~p ∨ (p ∧ Use De-Morgan’s Laws to write the negation of
~q)) is a tautology. -1 < x ≤ 4
∧
-1 < x ≤ 4 means x > –1 and x ≤ 4
Use truth table to show that (p ∧ ~q) ∧ (~p ∨ q) is a
contradiction. By DeMorgan’s Law, the negation is:
Same truth values in the indicated columns so p∧c ≡ c x > –1 or x ≤ 4
Which is equivalent to: x ≤ –1 or x > 4

LAWS OF LOGIC
Given any statement variables p, q and r, a tautology t and Distributive Law: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Double Negation Law: ~ (~p) ≡ p
a contradiction c, the following logical equivalences hold: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Idempotent Laws: p∧p≡p
Commutative Laws: p∧q≡q∧p Identity Laws: p∧t≡p p∨p≡p
p∨q≡q∨p p∨c≡p
De Morgan’s Laws: ~(p ∧ q) ≡ ~p ∨ ~q
Associative Laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Negation Laws: p∨~p≡t ~(p ∨ q) ≡ ~p ∧ ~q
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) p∧~p≡c

Universal Bound Law: p∨t≡t

p∧c≡c

Absorptions Laws: p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p

Negation of t and c: ~t≡c

~c≡t