Scribd
Upload
2K views2 pages

Chapter1 Cheat Sheet

The document discusses logical operators, their truth tables, and logical laws. It covers precedence of logical operators and quantifiers. It also covers De Morgan's laws, negating quantified expressions, and properties of statements with quantified variables.

Uploaded by

LuIs I. GuTi
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2K views2 pages

Chapter1 Cheat Sheet

The document discusses logical operators, their truth tables, and logical laws. It covers precedence of logical operators and quantifiers. It also covers De Morgan's laws, negating quantified expressions, and properties of statements with quantified variables.

Uploaded by

LuIs I. GuTi
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Chapter 1 cheat sheet

Logical operators, their truth tables, laws:


Precedence of Logical Operators: , ., v, , Logic and bit operations (above):
Laws:
p p
T F
F T
p
q p q
T T T
T F F
F T T
F F T
p
q
p q
T T F
T F T
F T T
F F F
p
q
p q
T T T
T F F
F T F
F F T
x y
x.y xv y xy
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0
(p v q) p . q
(p . q) p v q
De Morgan's
Laws (1)
p v p p
p . p p
Idempotent laws
(5)
( p) p
Double negation
law (2)
p v T T
p . F F
Domination laws
(6)
p . q q . p
p v q q v p
Commutative
laws (3)
p . T p
p v F p
Identity laws (7)
p v (p . q) p
p . (p v q) p
Absorption laws
(4)
p v p T
p . p F
Negation laws (8)
(p v q) v r p v (q v r)
(p . q) . r p . (q . r)
Associative laws (9)
p v (q . r) (p v q) . (p v r)
p . (q v r) (p . q) v (p . r)
Distributive laws (10)
p q p v q (11) p q (p q) . (q p) (12)
p q q p (13) p q p q (14)
p v q p q (15) p q (p . q) v (p . q) (16)
p . q (p q) (17) (p q) p q (18)
(p q) p . q (19)
(p q) . (p r) p (q . r) (20)
(p q) v (p r) p (q v r) (21)
(p r) . (q r) (p v q) r (22)
(p r) v (q r) (p . q) r (23)
p
q p q
T T T
T F T
F T T
F F F
p
q
p . q
T T T
T F F
F T F
F F F
universal quantifier - existential quantifier -! uniqueness quantifier .v
Precedence of Quantifiers and Logical Operators: , ., v, ,
-,-!
Quantifiers' precedence: from left to the right
Quantifiers with restricted domain:
x<0 (x
2
>0) can be re-written with implication x (x<0 x
2
>0)
-x>0 (x
2
=4) can be re-written with conjunction -x (x>0 . x
2
=4)
Negating Quantified expressions (De Morgan's Laws):
-xP(x) xP(x) xP(x) -xP(x)
Nested quantifiers:
p q
q p contrapositive,
q p converse,
p q inverse.
Statement When True? When False?
y x P(x,y)
x y P(x,y)
P(x,y) is true for any pair x, y there is a pair x, y for which
P(x,y) is False
x -y P(x,y)
For any x, there is a y, for
which P(x,y) s true
There is an x, for which
P(x,y) is false for any y
-x y P(x,y)
There exists an x, for which
P(x,y) is true for any y
There is no x, such that
P(x,y) is true for any y
-x -y P(x,y)
-y -x P(x,y)
There is a pair x, y for which
P(x,y) is true
P(x,y) is false for every pair
x, y

You might also like