CMPS 257 Flashcards
Conjunction
Operator AND denoted by (^). Other words include: but, also, in addition, morever Ex: A ^ B
Disjunction
Operator OR denoted by (v) Ex: A v B
Implication
Operation IMPLICATION denoted by (–>) Ex: A, then B A, therefore B A, only if B
Tautology
A statement which is always true not matte what truth values are assigned to the letters.
This law states,”NOT (A OR B) is equivalent to NOT A AND NOT B, also NOT (A AND B) is equicalent to NOT A OR NOT B” Ex: A implies B is equal to (A’ v B)
DeMorgan’s Law
The opposite of tautology is something that is always false, this means it is a…
Contradiction
Some tautological Equivalences
A V B ↔ B V A = A^B ↔ B^A (commutative properties)
(AVB)VC↔AV(BVC) = (A^B)^C ↔ A^(B^C) (associative property)
AV(B^C) ↔ (AVB)^(AVC) = A^(BVC) ↔ (A^B)V(A^C) (distributive)
Av0 ↔ A = A^1↔ A (identity property)
AVA ↔ 1 = A ^ A ↔ 0 (compliment property)
What are propositions?
statements which can be evaluated to true or false.
Ex: If there is a storm then class is cancelled. There is a storm therefore class is cancelled. First we assign values to the statements. S = “There is a storm” C = “Class is cancelled” sometimes people may want to assign S to storm. Storm is not a statement.
WFF = (S → C)^S→ C
Equivalence Rules Commutative
P v Q = Q vP
P ^ Q = Q ^ P
Equivalence Rules Assocative
(PvQ)vR = Pv(QvR)
(P^Q)^R = P^(Q^R)
Equivalence Rules DeMorgan’s
(PvQ)’ = ‘P ^ ‘Q
(P^Q)’ = P’ v Q’
What is recursion
something which is defined using the word itself.
Union
Given that A = {2, 4, 5, 6, 8, 10} and B = {1, 2, 3, 4 ,5}
A U B = {1,2,3,4,5,6,8,10}
Intersection
Given that A = {2, 4, 5, 6, 8, 10} and B = {1, 2, 3, 4 ,5}
A upsidedown U B = {2, 4, 5}
Truth Tables
Boolean Algebra
