Propositional logic- formal language
Propositional Logic (PL) is a formal language, which has syntax, a set of symbols, and semantics. It is not a natural language such as English.
All languages have a set of symbols, meanings assigned to the significant units and rules for constructing compound constructions out of atomic constructions.
- For example, the letter ‘Z’ is part of English, but not part of Hindi.
- For example, ‘snow’ means snow in English, but ‘Schnee’ means snow in the German language.
- For example, English is a Subject-Verb-Object language, while Arabic is Subject-Object-Verb.
The syntax of a language is known as the grammar of the language. The semantics of a language is known as the meaning of the significant parts. Sentences of most natural languages are possible to translate such as Greek, English, German, French, etc… into PL.
Propositional Logic is a language that focuses on a small set of expressions. These Propositional Logic expressions are the words used to connect propositions (sentences): ‘and’, ‘or’, ‘if…, then’, ‘not’, ‘if and only if’, and combinations of them.
The Syntax of PL: Symbols
Propositional Letters:
- P, Q, R, S, T, U, V, W, X, Y, and Z
Logical Operators:
- ‘→’ arrow
- ‘¬’ broken arrow
- ‘≡’ triple bar
- ‘∧’ carrot
- ‘v’ wedge
Grouping Symbols:
- ‘(, )’ parentheses, and ‘[,]’ brackets
The language of Propositional logic is the object-language. The object language is the actual language that is used for communicating in that language. For example, just as the word ‘good’ is part of the object language of English and the formula ‘(P ∧ Q)’ is part of the object language of PL. The object language of Propositional logic must be distinguished from the meta-language for Propositional logic. The meta-language for PL is the language used for talking about Propositional logic. It is not part of Propositional logic and is primarily used to describe the grammar and meaning of formulas at a level of generality. The meta-language variables are the lower case English letters such as p, q, r,…z.
Well-formed formulas of propositional logic
All propositional letters P….Z are the atomic well-formed formulas. The well-formed formulas of propositional logic are those which we obtain by using the construction rules given below, and only those, finitely many times:
¬: If p is a well-formed formula, then so is (¬p).
∧: If p and q are well-formed formulas, then so is (p ∧ q).
∨: If p and q are well-formed formulas, then so is (p ∨ q).
→: If p and q are well-formed formulas, then so is (p → q).
Nothing is a well-formed formula unless it follows the above rules.
Examples
Not well-formed
- P¬
- QP
- ∧R
- A→
- ≡∨ R)
Well-formed
- (P → (Q ∧ R))
- (V ≡ (¬R ∧ S))
- (Q ∧ (R ∨ S))
- (S → (R → T))
- (P → ¬(R ≡ S))
Propositional logic is a language that only focuses on propositional connectives and operators. In English the main propositional connectives are ‘not’, ‘and’, ‘or’, ‘if…, then…’, and ‘if and only if’. Since Propositional logic is only focused on these terms it only has semantics for these terms. The semantics for Propositional logic is binary and exclusive. There are only two truth-values: T (true) and F (false), and no statement can be both T and F. It is important to note that the semantics of Propositional logic is for the logical operators of its language: ‘→’, ‘¬’, ‘≡’, ‘∧’, and ‘∨’.
Logicians try to give definitions of the propositional operators of Propositional logic that match perfectly with the logical meaning of ‘and’, ‘or’, ‘not’, ‘if…then…’, and ‘if and only if’. However, there are many cases in which the English use of, for example ‘and’ or ‘if…, then…’, does not match the actual definition given to carrot and arrow.
Truth-Tables
A truth table is a table for visually displaying the distribution of truth (T) and falsity (F) across a compound formula given the basic inputs from the atomic letters.
| p | q | |
| T | T | |
| T | F | |
| F | T | |
| F | F |
Broken Arrow, Negation
The definition of a broken arrow is intended to capture the logical meaning of the logical operator ‘not’, and the function of negation. The main idea is that the output is the opposite of the input.
| p | ¬ p |
| T | F |
| F | T |
Carrot, Conjunction
The definition of carrot is intended to capture the logical meaning of the logical operator ‘and’, and the function of the conjunction. The main idea is that the output is true only if both inputs are true.
| p | q | (p ∧ q) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Wedge, Disjunction
The definition of wedge is intended to capture the logical meaning of the logical operator ‘or’, and the function of disjunction. The main idea is that the output is true as long at least one input is true.
| p | q | (p ∨ q) |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Arrow, Material Conditional
The definition of the arrow is intended to capture the logical meaning of the logical operator ‘if…., then…’, and the function of the material conditional. The main idea is that the output is false only when the first input is true, and the second input is false.
| p | q | (p → q) |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Triple Bar, Biconditional
The definition of the triple bar is intended to capture the logical meaning of the logical operator ‘if and only if’, and the function of biconditional. The main idea is that the output is true just in case the inputs are the same.
| p | q | (p ≡ q) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Here is the definition of propositional logic formulas grammar in the Backus Naur Form (BNF).
φ ::= p | (¬φ) | (φ ∧ φ) | (φ ∨ φ) | (φ → φ)
Where p stands for any atomic proposition and each occurrence of φ to the right of::= stands for any already constructed formula.
For example, φ being (((¬p) ∧ q) → (p ∧ (q ∨ (¬r))))
p
q
r
(¬p)
((¬p) ∧ q)
(¬r)
(q ∨ (¬r))
((p ∧ (q ∨ (¬r))))
(((¬p) ∧ q) → (p ∧ (q ∨ (¬r))))
For humans, dealing with brackets is a tedious task. We need them for the reason that formulas have a tree-like structure, although we prefer to represent them linearly.
Here is a parse tree representing a well-formed formula φ.
Now note how brackets become unnecessary in this parse tree since the paths and the branching structure of this tree remove any possible ambiguity in interpreting φ.
