FANDOM


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 functionalclassical propositional logic with natural deduction, which this article mostly will talk about.

ConceptsEdit

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

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

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

TruthEdit

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 \Alpha 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)Edit

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:Edit

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.