Tautology
A statement that is always true
Contradiction
A statement that is always false
De Morgan's Law
~(P ^ Q) = ~P v ~Q~(P v Q) = ~P ^ ~Q
Idempotent Laws
P ^ P = PP v P = P
Distributive Laws
P ^ (Q v R) = (P ^ Q) v (P ^ R)P v (Q ^ R) = (P v Q) ^ (P v R)
Identity Laws
P ^ t = P P v C = P
Absorption Laws
P v (P ^ Q) = P P ^ (P v Q) = P
Sufficient condition
R is sufficient condition for s" means "if r, then s
If P, then Q
P is sufficient for Q
Necessary condition
R is necessary for s" means "if not r, then not s
If not P, then not Q
P is necessary for Q
If Q, then P
necessary condition
If not q, then not p
Contrapositive of "if p, then q
Not p and not q
Conditional statement ("if p, then q") expressed as or
Modus tollens
If P, then Q.Not Q.Therefore, not P.
Modus ponens (primero)
If P, then Q.P.Therefore, Q.
Converse error (affirming the consequent)
If P, then Q.Q. Therefore, P.
Inverse error (denying the antecedent)
If P, then Q. Not P.Therefore, not Q.
NAND-gate
An "and" gate followed by a "not" gate. (sheffer stroke)
NOR-gate
An "or" gate followed by a "not" gate. (pierce arrow)
Recognizer
A circuit that outputs a 1 for only one combination of input signals
Two's complement
A way to represent the negative of a binary number.
2^n - a
Form of the two's complement
Proposition (statement)
A sentence that can either be true or false
Predicate
A sentence whose truth value cannot be determined because there is a variable or missing information
Vacuously true
If p is false, then q is true. This statement is True.If p is false, then q is false. This statement is True.Every time p is false, the statement is True! What is this called?
For all x, if P(x) then Q(x).P(a) is true for a particular a.Therefore, Q(a) is true for that particular a.
Universal modus ponens
For all x, if P(x) then Q(x).Q(a) is false for a particular a.Therefore, P(a) is false for that particular a.
Universal modus tollens
For all x, if P(x) then Q(x).For all x, if Q(x) then R(x).Therefore, for all x, if P(x) then R(x).
Universal transivity
Constructive proof of evidence
Showing at least one possible x such that P(x) proves that "there exists some x such that P(x)
Direct proof
Showing that P(x) is true for any x proves that "for all x, P(x)
Zero product propert
If neither of two real numbers is zero, then their product is also not zero.
1. Write the 8-bit binary notation for a. 2. Flip the bits.3. add 1 in binary notation
How do you convert a positive integer into the two's complement?
Every integer greater than 1 is divisible by a prime number.
Divisibility by a prime number theorem states...
Any integer greater than 1 is either prime or a factor of prime numbers.
Unique factorization of integers theorem states...
An irrational number
A non-terminating real number is
10 (base 2)
1 (base 2) + 1 (base 2) =
11 (base 2)
1 (base 2) + 1 (base 2) + 1 (base 2) =