Propositional Logic Connectives
Before we learn about propositional logic we must first understand the meaning of certain symbols which we will call connectives. We will use these connectives with statements. These statements will be denoted with the letters $P$, $Q$, and $R$, and they will state the following:
- $P$: Bob went to the store.
- $Q$: Mary walked her dog.
- $R$: Jack had cereal for breakfast.
The three statements above are purely arbitrary and the examples based off of them below need not make sense.
| Connective | Name | English Meaning | Example |
|---|---|---|---|
| $\neg$ | Negation | "Not" | $\neg P$: Bob did NOT go to the store |
| $\wedge$ | Conjunction | "And" | $P \wedge Q$: Bob went to the store AND Mary walked her dog. |
| $\vee$ | Disjunction | "Or" | $P \vee Q$: Bob went to the store OR Mary walked her dog. |
| $\rightarrow$ | Conditional | "If - then" | $P \rightarrow Q$: IF Bob went to the store THEN Mary walked her dog. |
| $\leftrightarrow$ | Biconditional | "If and only if" | $P \leftrightarrow Q$: Bob went to the store if and only if Mary walkeld her dog. |
Observe that the negation connective $\neg$ only requires a single statement. The conjunction, disjunction, and implication statements all require two statements.
We can combine statements and connectives together to form larger "formulas" (the define of a formula in propositional logic will be defined more precisely later on). In doing so we MUST be careful and add parentheses where necessary to avoid ambiguity. For example, consider the statement:
(1)This statement reads:
IF (Bob went to the store OR Mary walked her dog) THEN Jack had cereal for breakfast.
For another example:
(2)This statement reads as follows:
IF ((Bob does NOT go to the store) AND (IF Mary walked her dog THEN Jack had cereal for breakfast)) THEN Bob went to the store.
Clearly the formula above does not make sense. Bob cannot both go to the store and not go to the store. We will deal with these problems later.