Propositional logic, also known as sentential calculus or propositional calculus, is the study of propositions that are formed by other propositions and logical connectives. Propositional logic is not concerned with the structure and of propositions beyond the atomic formulas and logical connectives, the nature of such things is dealt with in informal logic. Propositional logic may be studied with a formal system known as a propositional logic. The most commonly studied and most popular formal system used is (truth functional) classical propositional logic with natural deduction, which this article mostly will talk about.
- Propositional variables (also known as placeholders: The atomic formulas of propositional logic. These are viewed as variables representing statements. They are variables that can take truth values.
- Logical connective: A symbol representing a truth function. They are used to form larger formulas from smaller formulas.
- Formal language: A set of strings that consits of symbols from some alphabet that conforms to some formal grammar (also known as formation rules or rules of formation).
- Well-Formed formula: An expression that conforms to the rules of a formal language.
A propositional logic may be described as an ordered tuple ).
- The alpha set is the set of all propositional variables.
- The omega set is the set of all logical connectives. The omega set is often partitioned into the following several sets: . A set is a set of logical connectives with arity .
- The zeta set is the set of transformation rules, such as rules of inference or Replacement rules.
- The iota set is the set of axioms or Axiom schemas.
The formal language of the logic may be defined inductively as follows:
- Base: Any element of the alpha set is a well-formed formula of .
- Logical connectives: If are propositional variables and is an element of , then is a well formed formula (though this could be represented in Infix notation or even postfix notation). If the logical connective is a binary operation
- Closure: Nothing else is a well-formed formula of the language .
Rules of formation for truth-functional classical propositional logicEdit
The formal rules of a formal language tell which strings of symbols from some alphabet belong to a formal language or not. These are the rules of the underlying formal language of standard propositional logic .
- All propositional variables are well-formed formulas.
- If is a well-formed formula, then so is .
- If and are well-formed formulas, then , , and are well-formed formulas.
To evaluate the truth of a well-formed formula in standard truth functional classical propositional logic , a special function (where is the set of Atomic formulas) known as a valuation is used. The truth evaluation is typically defined using the following T-Schema:
- is true if and only if
- is true if and only if it is not the case that is true
- is true if and only if and is true. (This is the interpretation for Conjunction. The word and has a technical meaning that means both)
- is true if and only if or is true. (This is the interpretation for Inclusive Disjunction. The word or in this context is a technical word whose meaning may possibly be understood as "either or or both". It is not to be confused with the logical connective Exclusive Disjunction, which is found in some formal systems)
- is true if and only if is true or it is not the case that is true. (This is the interpretation of a Material conditional. The word or was used in a technical sense, just as the interpretation for the disjunction).
- is true if and only if if and only if is true (this is the interpretation of the Biconditional, if and only if in this case means either both are true or both or false.
Alternatively, one can use truth tables.
Transformation rules of truth-functional classical propositional logic (Natural Deduction)Edit
Rules of inference: