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

• School: University of Alberta
• Department: Computing Science
• Course: CMPUT272
• Professor: Lorna Stewart

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.