Propositional Logic
A statement is a declarative sentence that can be True (1) or False (0).
Examples:
- Milk is white. – T
- The cardinality of an empty set is 0.
|∅| = 0– T - Humans are just fish with legs. – F
We cannot express things like questions, as questions cannot be true or false.
We also cannot express with imperatives or commands, as those cannot be true nor false.
When we talk about propositional logic, we’re talking about statements that can be true or false.
A syntax is a propositional logic.
Syntax
Propositions are denoted with capital letters P, Q, R,…
P = I cheated.
Q = I wrote an exam.
Lowercase letters p, q, r,… are used for general propositions that have no meaning, and we will use them for general proofs.
Connectives
Connectives are used to propositions to change their meaning, or combine their meaning together.
- a proposition on its own is a well-formed formula or wff
- ¬p = not p/ negation
- p ∧ q = p and q
- p ∨ q = p or q
- p → q = if p, then q
Example:
- P = I cheat.
- Q = I will get caught.
- R = I will write an exam.
- S = I will fail.
Translate the following into English:
(R\;\wedge P)\;\to\;(Q\;\wedge\;S)
If I write an exam and I cheat, then I will get caught and I will fail.
Translate into propositional logic:
If James does not die then Mary will not get any money and James’ family will be happy.
- P = James dies
- Q = Mary will get money
- R = James’ family will be happy
\neg P\;\to\;(\neg Q\;\wedge\;R)
Sample Exercises:
Translate the following sentences, given the following statements:
- p = I finish writing my computer program before lunch.
- q = I shall play tennis in the afternoon.
- r = The sun is shining.
- s = The humidity is low.
1 – If the sun is shining, I shall play tennis this afternoon.
r\;\to\;q
2 – Finishing the writing of my computer program before lunch is necessary for my playing tennis this afternoon.
p\;is\;necessary\;for\;q\\q\to p
3 – Low humidity and sunshine are sufficient for me to play tennis this afternoon.
s\;and\;r\;are\;sufficient\;for\;q\\(s\;\wedge\;r)\;\to\;q
Latex:
- ∧ = and = \wedge
- ∨ = or = \vee
- → = if, then = \to
- ¬ = not = \neg
