- Basic Defintions
- Equivalence rules & Derivations
- Definition: The logic of compound staements built from simpler statements using boolean connectives.
- Applications
- Design of digital circuits
- Expressing conditions
- Queries
- a statement with a definite meaning, having a truth value (never both, neither or something in between).
- In probablility theory we assign degrees of certainty to propositions (For now True/False only).
- It is raining (Given a situation)
- Beijing is the capital of China (depends on the history)
- “1 + 2 = 5”
Given any instance we can decide if it’s true or false.
THE FOLLOWING ARE NOT PROPOSITIONS:
- “Who’s there?” (interog)
More on keynote.
- Negation (NOT)
- Cunjunction (AND)
- Disjunction (OR)
- Exclusive-Or (XOR)
- Implication (IF)
- Bi-conditional (IFF)
- An operator or connective combines one or more operand expressions into a larger expression. (e.g., “+” in numeric exprs.)
- Unary operators take one operator (-3) Binary take two (2 + 4)
- More in keynote.
- The unary negation operator “-|” (NOT) transforms a prop. into it’s logical negation.
If p^q we have 3 col. and 4 rows.
| p | q | p^q |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
2^2 for p^q
for p^q^r we would have 2^3 or 8 rows.
| p | q | pvq |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Symbol (+)
| p | q | p(XOR)q |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
ASSUME “OR” MEANS INCLUSIVE
- p -> q states p implies q
- It is false only in the case that p is TRUE but q is False.
e.g p = “I am elected” q = “Taxes will be lowered”
Terminology p: Hypothesis q: Conclusion
| p | q | p -> q |
|---|---|---|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
0 = 1 -> “Pigs will fly”
- Inverse of p -> q is: (NOT)p -> (NOT)q
- Converse of p -> q is: q -> p
- The contropositive of p -> q: is (NOT)q -> (NOT)p
For any p -> q the contrapositive is also true.
| p | q | not p | not q | p -> q | not q -> not p |
|---|---|---|---|---|---|
| F | F | T | T | T | T |
| F | T | F | T | T | T |
| T | F | T | F | F | F |
| T | T | F | F | T | T |
- The biconditional p <-> q states p is true if and only if (IFF) q is true.
- p <-> q is true if the two have the same truth values.
| p | q | p<->q |
|---|---|---|
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | T |
| Operator | Precedence |
|---|---|
| NOT | 1 |
| AND | 2 |
| OR | 3 |
| IF | 4 |
| IFF | 5 |
- “I just saw my old friend, and either he’s grown or I’ve shrunk.” f ^ (g v s)
- f ^ g v s - “I just saw my old friend he has grown or I have shrunk.”
NOT takes precedence over both “^” and “v” NOT s ^ f is like (NOT s) ^ f.
| name | not | and | or | xor | implies | iff |
|---|---|---|---|---|---|---|
| Propositional | - | ^ | v | (plus) | -> | <-> |
| Boolean Algebra | pbar | pq | + | (plus) | ||
| MORE IN SLIDE |
- A bit is a binary base 2 digit
- May be used to display truth values
01 1011 0110 11 0001 1101
11 1011 1111 - Bitwise OR 01 0001 0100 - Bitwise AND 10 1010 1011 - Bitwise XOR
Two syntactically different propositions could be semantically identical we call them equivilent.
Tautology - a compound proposition that is true no matter what the truth values of its atomic propositions are.
Ex. p or NOT p
| p | NOT p | p v NOT p |
|---|---|---|
| T | F | T |
| F | T | T |
Contridiction is a comp.prop that is false no matter what!
Ex. p ^ NOT p
| p | NOT P | p ^ NOT P |
| T | F | F |
| F | T | F |
Compound propositions P and ! are logically equivalent to each other IFF P and Q contain the same truth values as each other in all rows of their truth tables.
Compound proposition P is logically equivalent to the compound proposition Q, written P <=> Q, IFF the compound proposition P <-> is a tautology.
| p | q | pvq | NOT p | NOT q | NOT p ^ NOT q | NOT(NOT p ^ NOT q) |
|---|---|---|---|---|---|---|
| F | F | F | T | T | T | F |
| F | T | T | T | F | F | T |
| T | F | T | F | T | F | T |
| T | T | T | F | F | F | T |
p^T <=> p pvF <=> p
pvT <=> T p^F <=> F
pvp <=> p p^p <=> p
NOT NOT p <=> p
pvq <=> qvp p^q <=> q^p
(pvq)vr <=> pv(qvr) (p^q)^r <=> p^(q^r)