8.12 Propositional logic
1.Proposition
It's a statement can be true or false and be definite
2.Negation
Given a proposition, we define the negation denoted by \(\neg p\)
3.Conjunction
Let \(p\) and \(q\) be propositions, we define \(p \wedge q\) (we read "\(p\text{ and }q\)") by the values of the Truth Table
| \(p\) | \(q\) | \(p \wedge q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Conclusion
\(p \wedge q\) is True only when \(p\text{ and }q\) are both True. If not, then False.
4.Disjunction
Let \(p\) and \(q\) be propositions, we define \(p \vee q\) (we read "\(p\text{ or }q\)") by the values of the Truth Table
| \(p\) | \(q\) | \(p \vee q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Conclusion
\(p \vee q\) is True, if either \(p\text{ or }q\) is True. If not, then False.
5.De Morgan's Laws
| \(p\) | \(q\) | \(p \wedge q\) | \(\neg (p \wedge q)\) | \(\neg p\) | \(\neg q\) | \(\neg p \wedge \neg q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Conclusion
Comment
Similarly
6.Implication
Let \(p\) and \(q\) be two propositions.
We define \(p \Rightarrow q~\) (we read as "\(p\text{ implies }q\)" or " \(q\text{ is a consequence of }p\)" or "\(\text{if } p \text{ is true then } q \text{ has to be true}\)")
| \(p\) | \(q\) | \(p \Rightarrow q \quad\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Moreover
| \(p\) | \(q\) | \(p \Rightarrow q \quad\) | \(\neg p\) | \(\neg q\) | \(\neg q \Rightarrow \neg p\) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Conclusion
e.g.: \(p:\text{it's raining}\) \(q:\text{the streets are wet}\)
Example
Q: \(p(m)=" m^{2}\text{ is even}\)\("m \in N\), \(q(m)=" m\text{ is even}\)\("m \in N\). Prove that \(p(m)\Rightarrow q(m)\)
A: m being odd implies \(m^{2}\) is odd, due to \(\neg q \Rightarrow \neg p\)
And Hypothesis: \(m\) is odd, meaning that \(m=2 k+1\) is odd
Then \(m^{2}=(2k+1)^{2}=4k^{2}+4k+1=2\left(2k^{2}+2k\right)+1\) is odd
==Trick:== use \(p \Rightarrow q \equiv \neg q \Rightarrow \neg p\)
7.Equivalence
Definition
Let \(p, q\) be propositions, we define \((p \Leftrightarrow q)\) by \((p \Rightarrow q) \cap(q \Rightarrow p)\)
| \(p\) | \(q\) | \(p \Rightarrow q \quad\) | \(q \Rightarrow p \quad\) | \(p\Leftrightarrow q\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Example
Q: \(p(m)= "m\text{ is multiple of }\)\(6"\), \(q(m)="m\text{ is multiple of }\)\(3 "\)， \(r(m)="m\text{ is multiple of }\)\(2 "\)
Prove that: \(p(m) \Leftrightarrow(q(m) \cap r(m))\)
A: deal with the two implications:
\(p(m) \Rightarrow(q(m) \cap r(m))\), Let \(m\) be multiple of \(6, m=6 k=3 \times 2 k\)
\((q(m) \cap r(m)) \Rightarrow p(m)\), Since \(m\) is multiple of 3 , we have that \(m=3 \times k\)
Now, \(m\) is also multiple of \(2\) . Then \(m=2 \times 3 k, k \in N\)
Thinking
False