propositional “variable” (label): a stand-in for a factual statement which is either true or true.
Just called a proposition, for short.
propositional formula: can build up formula of propositions with logical connectives / operators.
E.g.,
| \(p\) | \(\lnot p\) | ||
| T | F | ||
| F | T |
Oh, and
| \(p\) | \(q\) | \(p\land q\) | ||
| T | T | T | ||
| T | F | F | ||
| F | T | F | ||
| F | F | F |
| \(p\) | \(q\) | \(p\lor q\) | ||
| T | T | T | ||
| T | F | T | ||
| F | T | T | ||
| F | F | F |
| \(p\) | \(q\) | \(p\rightarrow q\) | ||
| T | T | T | ||
| T | F | F | ||
| F | T | T | ||
| F | F | T |
“English” is much, much richer. Logical formula are meant to be read literally.
Some formulae are equivalent truth-wise.
\(\lnot p\lor q\) \(\equiv\) \(p\rightarrow q\)
\(\lnot q\rightarrow\lnot p\) \(\equiv\) \(p\rightarrow q\)
Called the contrapositive.
De Morgan's Laws
\(\lnot (p\lor q) \equiv (\lnot p\land\lnot q)\)
\(\lnot (p\land q) \equiv (\lnot p\lor\lnot q)\)
If two formula have the same truth table, then they are equivalent (\(“\equiv”\)).
E.g.,
| \(p\) | \(q\) | \(\lnot p\lor q\) | \(p\rightarrow q\) | ||
| T | T | T | T | ||
| T | F | F | F | ||
| F | T | T | T | ||
| F | F | T | T |
2 propostions \(2^2 = 4\)
10 propostions \(2^{10} = 1,024\)
100 propostions \(2^{100} = 1,267,650,600,\)
\(228,229,401,496,703,205,376\)
1,000 propostions \(2^{1,000} = \ldots\)
You will have to prove things like this later in the course!
If I have two formula of 20 propositions each, how to match the propositions up?
\(20! = 20\times 19\times\ldots\times 1\) \(= 2,432,902,008,176,640,000\)
Too big!
Punchline: We'll need other methods to prove equivalences.
A tautology is a propositional formula that is true for every row of its truth table.
E.g., \(p\lor\lnot p\)
A fallacy is a propositional formula that is false for every row of its truth table.
E.g., \(p\land\lnot p\)
Propositional formulae provide us with proof patterns (techniques).
E.g., I need to prove \(p\rightarrow q\).
I could prove \(\lnot q\rightarrow \lnot p\), if that turned out to be easier.
Same thing.
logical circuits
logic puzzles
e.g., knights &knaves
Note that knaves are just as valuable as knights!
The worst are humans!
Because they tell the truth sometimes, but lie other times.
What is paradox?
How does it arise?
probabilities (& probabilistic reasoning)
E.g., “It will be raining tomorrow.”
imperatives
E.g., “Go run around campus three times!”
questions (& hypotheticals)
E.g., “Is EECS-1019 a fun course?”
resolving paradoxes
E.g., “I am lying in this statement.”
variables
E.g., “\(x + 3 = 5\)”
Let us fix this last one now!