Propositional logic

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.

Concepts

• 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.

Formal description

A propositional logic $\mathcal{L}$ may be described as an ordered tuple $\mathcal{L}=\mathcal{L}(\Alpha,\Omega,\Zeta,\Iota$).

• The alpha set $\mathrm{A}$ is the set of all propositional variables.
• The omega set $\Omega$ is the set of all logical connectives. The omega set is often partitioned into the following several sets: $\Omega_1,\ldots,\Omega_k,\ldots,\Omega_n$. A set $\Omega_k$ is a set of logical connectives with arity $k$.
• The zeta set $\Zeta$ is the set of transformation rules, such as rules of inference or Replacement rules.
• The iota set $\Iota$ is the set of axioms or Axiom schemas.

The formal language $\mathcal{Q}$ of the logic $L$ may be defined inductively as follows:

1. Base: Any element of the alpha set is a well-formed formula of $\mathcal{Q}$.
2. Logical connectives: If $P_1,\ldots,P_k$ are propositional variables and $f$ is an element of $\Omega_k$, then $f(P_1,\ldots,P_2)$ 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
3. Closure: Nothing else is a well-formed formula of the language $Q$.

Rules of formation for truth-functional classical propositional logic

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 $\mathcal{L}_1$.

• All propositional variables are well-formed formulas.
• If $\phi$ is a well-formed formula, then so is $\lnot\phi$.
• If $\phi$ and $\psi$ are well-formed formulas, then $\phi \land \psi$, $\phi \lor \psi$, $\phi \leftrightarrow \psi$ and $\phi \to \psi$ are well-formed formulas.

Similar rules also apply to other formal systems that are a form of propositional logic. Constants for contradiction and tautology may also be added.

Truth

To evaluate the truth of a well-formed formula in standard truth functional classical propositional logic $\mathcal{L}$, a special function $v:\Alpha \to \mathbb{B}$ (where $\mathrm{A}$ is the set of Atomic formulas) known as a valuation is used. The truth evaluation is typically defined using the following T-Schema:

• $P$ is true if and only if $v(P)=true$
• $\lnot\phi$ is true if and only if it is not the case that $\phi$ is true
• $\phi \land \psi$ is true if and only if $\phi$ and $psi$ is true. (This is the interpretation for Conjunction. The word and has a technical meaning that means both)
• $\phi \lor \psi$ is true if and only if $\phi$ or $\psi$ 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)
• $\phi \to \psi$ is true if and only if $\phi$ is true or it is not the case that $\psi$ 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).
• $\phi \leftrightarrow \psi$ is true if and only if $\phi$ if and only if $\psi$ 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)

Rules of inference:

Name:	Rule:
Modus Ponens	$P \to Q, P \vdash Q$
Modus Tollens	$P \to Q, \lnot Q, \vdash \lnot P$
Disjunctive Syllogism	$P \lor Q, \lnot P, \vdash Q$
Conjunction Introduction	$P, Q \vdash P \land Q$
Conjunction Elimination	$P \land Q \vdash P$ $P \land Q \vdash Q$
Disjunction Introduction	$P \vdash P \lor Q$
Biconditional Introduction	$P \to Q, Q \to P \vdash P \leftrightarrow Q$
Constructive Dilemma	$P \to Q, R \to S, P \lor R \vdash Q \lor S$
Disjunction Elimination/Proof by cases	$P \to Q, R \to Q, P \lor R \vdash Q$
Destructive Dilemma	$P \to Q, R \to S, \lnot Q \lor \lnot S \vdash \lnot P \lor R$
Biconditional Elimination	$P \leftrightarrow Q \vdash P \to Q$ $P \leftrightarrow Q \vdash P \to Q$
Absorption	$P \to Q \vdash P \to (P \land Q)$
Modus ponendo tollens	$\lnot(P \land Q), P \vdash \lnot Q$

Replacement rules:

Name:	Rule:
Double Negation	$\lnot \lnot P \Leftrightarrow P$
Associative property	$(P \wedge (Q \wedge R)) \Leftrightarrow ((P \wedge Q) \wedge R)$ $(P \vee (Q \vee R)) \Leftrightarrow ((P \vee Q) \vee R)$.
Commutative property	$P \wedge Q \Leftrightarrow Q \wedge P$ and $P \vee Q \Leftrightarrow Q \vee P$
Distributive property	$(P \land (Q \lor R)) \Leftrightarrow ((P \land Q) \lor (P \land R))$ $(P \lor (Q \land R)) \Leftrightarrow ((P \lor Q) \land (P \or R))$
DeMorgan's Laws	$\lnot (P \land Q) \Leftrightarrow (\lnot P \lor \lnot Q)$ $\lnot (P \lor Q) \Leftrightarrow (\lnot P \land \lnot Q)$
Tautology	$P \lor P \Leftrightarrow P$ $P \land P \leftrightarrow P$
Exportation	$((P \land Q) \to R) \Leftrightarrow (P \to (Q \to R))$
Material Implication	$P \to Q \Leftrightarrow \lnot P \lor Q$
Transposition	$P \to Q \Leftrightarrow \lnot Q \to \lnot P$