logic of compound statements
Logic is precise rather than ambiguous like natural languages. These are clear-cut statements that are unambiguous.
Logic provides formal, structured language for writing proof strategies and statements.
Propositional logic
Various types of logic exist in math and other disciplines. * First-order logic, modal logic, temporal logic, etc.
Propositional logic is composed of:
- Atomic statements
- Compound statements
Statements/propositions
Statements and propositions are interchangeable, these are declarative sentences that can be either TRUE or FALSE. * Can't be both TRUe and FALSE
Examples:
- "1 + 1 = 3"
- "Tom is a human"
- "1 + 1" - not a statement (not making a statement for an outcome)
- "x^2 = 4" - not a statement, we don't know about "x" and the TRUE value is dependent upon it
Shorthand
Letters are typically used to denote statements:
p,q,r,sT: TrueF: False
Example:
- Let
pdenote the statement "1 + 1 = 2" - Let q denote the statement "1 + 1 = 3"
Now we know:
p is T
q is F
Compound statements
Given a set of atomic statements, we can compose new statements with logical operations.
Negation (not)
Let p be a statement. The negation of p is ~p
The ~p is pronounced "not p" and is a new statement
The truth value of ~p is the opposite of p
Example:
Let p be "Tom is a human"
If p is True then ~p is "Tom is not a human"
Conjunction (and)
The conjunction of p and q is p^q (pronounced "p and q")
p^q is true if and only if p and q are both true
Example:
Let p be "Tom is a human", q be "Tom is tall"
p^q is "Tom is human and Tom is tall"
Disjunction (or)
The disjunction of p and q is p v q (pronounced "p or q")
p v q is true if and only if p is true or q is true`
Example:
Let p be "Tom is a human", q be "Tom is tall"
p v q is "Tom is human or Tom is tall"
Statement forms
A statement form is an expression made of statement variables and local operators
Examples:
Let p be "Bob is a CS student", q be "Bob is taking DS class"
~p ^ q "Bob is not a CS student and Bob is taking DS class"
p v (~p ^ q) "Either Bob is a CS student or Bob is not a CS student and Bob is taking DS class"
~p ^ ~q "Bob is not a CS student and Bob is not taking DS class"
Note: Truth tables show determinations of truths in statement forms
Compound statements - truth tables
We can evaluate truth values of any complex statement form.
- Label columns accordingly, then fill in with steps
- Add component variables
- Add expressions in parentheses
- Any non-nested parentheses are considered left->right
- Add expressions with logical operators
- Negation
- Conjunction/disjunction
| p | ~p |
|---|---|
| T | F |
| F | T |
| p | q | p^q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| p | q | pvq |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Example:
Construct the truth table for the statement form (p v q) ^ ~(p ^ q)
Exclusive OR
Exclusive OR is denoted as (p v q) ^ ~(p ^ q).
This is often abbreviated as (p XOR q).
The statement p XOR q means p or q and not both p and q.
| p | q | pvq | p^q | ~(p^q) | (pvq) ^ ~(p^q) |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | F | F | T | F |