CMPUT272 Lecture Notes - Lecture 2: Boolean Expression, Boolean Function, Disjunctive Normal Form

41 views4 pages
September 9 2014
ETLC E2-001
Boolean Functions
not (~) and (^) or (v)
x ~x x y x^y x y xvy
0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
'and' is conjunctive
'or' is disjunction
A boolean expression is an expression containing boolean constants (0 and 1);
boolean variables; boolean operators (^ v ~) and parenthesis.
Order of expresion
1. (, )
2. ~
3. ^, v
Parenthesis must be added to make the expression unambiguous
Evaluated like arithmetic expression
(p ^ ~q) v (~p ^ r)
p = 0, q = 1, r = 0
(0 ^ ~1) v (~0 ^ 0)
(0 ^ 0) v (1 ^ 0)
0 v 0
0
Boolean expression as a function can be represented with a truth table
(p v ~q) ^ ~(p ^ q)
p q (p v ~q) ~(p ^ q) (p v ~q) ^ ~(p ^ q)
0 0 1 1 1
0 1 0 0 0
1 0 1 1 1
1 1 1 0 0
There are infinite boolean expresions that represent the same function
(p v ~q) ^ ~(p ^ q) -- Original expression
= (p v ~q) ^ (~p v ~q) -- DeMorgan's rule
= (~q v p) ^ (~q v ~p) -- Commutative rule (x2)
= ~q v (p ^ ~p) -- Distributive rule
= ~q v 0 -- Negation rule
= ~q -- Bound rule
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

Document Summary

"or" is disjunction or (v) x y xvy. A boolean expression is an expression containing boolean constants (0 and 1); boolean variables; boolean operators (^ v ~) and parenthesis. Parenthesis must be added to make the expression unambiguous. Evaluated like arithmetic expression (p ^ ~q) v (~p ^ r) p = 0, q = 1, r = 0 (0 ^ ~1) v (~0 ^ 0) (0 ^ 0) v (1 ^ 0) Boolean expression as a function can be represented with a truth table (p v ~q) ^ ~(p ^ q) p q (p v ~q) ~(p ^ q) (p v ~q) ^ ~(p ^ q) There are infinite boolean expresions that represent the same function (p v ~q) ^ ~(p ^ q) -- original expression. = (p v ~q) ^ (~p v ~q) -- demorgan"s rule. = (~q v p) ^ (~q v ~p) -- commutative rule (x2) = ~q v (p ^ ~p) -- distributive rule.

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers