Movatterモバイル変換

[0]ホーム

Jump to content

Material conditional

Edit links

From Wikipedia, the free encyclopedia

Logical connective

"Logical conditional" redirects here. For other related meanings, seeConditional statement.

Not to be confused withMaterial inference orMaterial implication (rule of inference).

Material conditional
IMPLY

Definition	$x\to y$
Truth table	$(1011) {\displaystyle (1011)}$
Logic gate
Normal forms
Disjunctive	${\overline {x}}+y$
Conjunctive	${\overline {x}}+y$
Zhegalkin polynomial	$1\oplus x\oplus xy$
Post's lattices
0-preserving	no
1-preserving	yes
Monotone	no
Affine	no
Self-dual	no
v t e

Logical connectives

NOT	$\neg A,-A,{\overline {A}},{\sim }A$
AND	$A\land B,A\cdot B,AB,A\mathop {\&} B,A\mathop {\&\&} B$
NAND	$A\mathrel {\overline {\land }} B,A\uparrow B,A\mid B,{\overline {A\cdot B}}$
OR	$A\lor B,A+B,A\mid B,A\parallel B$
NOR	$A\mathrel {\overline {\lor }} B,A\downarrow B,{\overline {A+B}}$
XNOR	$A\odot B,{\overline {A\mathrel {\overline {\lor }} B}}$
└equivalent	$A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B$
XOR	$A\mathrel {\underline {\lor }} B,A\oplus B$
└ nonequivalent	$A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B$
implies	$A\Rightarrow B,A\supset B,A\rightarrow B$
nonimplication (NIMPLY)	$A\not \Rightarrow B,A\not \supset B,A\nrightarrow B$
converse	$A\Leftarrow B,A\subset B,A\leftarrow B$
converse nonimplication	$A\not \Leftarrow B,A\not \subset B,A\nleftarrow B$

Related concepts

Applications

Notation

[edit]

In logic and related fields, the material conditional is customarily notated with an infix operator $\to$ (U+2192 →RIGHTWARDS ARROW).^[1] The material conditional is also notated using the infixes $\supset$ and $\Rightarrow$ (U+2283 ⊃SUPERSET OF andU+21D2 ⇒RIGHTWARDS DOUBLE ARROW respectively).^[2] In the prefixedPolish notation, conditionals are notated as $C p q {\displaystyle Cpq}$ . In a conditional formula $p\to q$ , the subformula $p {\displaystyle p}$ is referred to as theantecedent and $q {\displaystyle q}$ is termed theconsequent of the conditional. Conditional statements may be nested such that the antecedent or the consequent may themselves be conditional statements, as in the formula $(p\to q)\to (r\to s)$ .

History

[edit]

InArithmetices Principia: Nova Methodo Exposita (1889),Peano expressed the proposition "If $A {\displaystyle A}$ , then $B {\displaystyle B}$ " as $A {\displaystyle A}$ Ɔ $B {\displaystyle B}$ with the symbol Ɔ, which is the opposite of C.^[3] He also expressed the proposition $A\supset B$ as $A {\displaystyle A}$ Ɔ $B {\displaystyle B}$ .^[4]^[5]^{[citation needed]}Hilbert expressed the proposition "IfA, thenB" as $A\to B$ in 1918.^[1]Russell followed Peano in hisPrincipia Mathematica (1910–1913), in which he expressed the proposition "IfA, thenB" as $A\supset B$ . Following Russell,Gentzen expressed the proposition "IfA, thenB" as $A\supset B$ .Heyting expressed the proposition "IfA, thenB" as $A\supset B$ at first but later came to express it as $A\to B$ with a right-pointing arrow.Bourbaki expressed the proposition "IfA, thenB" as $A\Rightarrow B$ in 1954.^[6]^[7]

Semantics

[edit]

Truth table

[edit]

From aclassical semantic perspective, material implication is thebinary truth functional operator which returns "true" unless its first argument is true and its second argument is false. This semantics can be shown graphically in the followingtruth table:

$A {\displaystyle A}$	$B {\displaystyle B}$	$A\to B$
F	F	T
F	T	T
T	F	F
T	T	T

One can also consider the equivalence $A\to B\equiv \neg (A\land \neg B)\equiv \neg A\lor B$ .

The conditionals $(A\to B)$ where the antecedent $A {\displaystyle A}$ is false, are called "vacuous truths".Examples are ...

... with $B {\displaystyle B}$ false:"IfMarie Curie is a sister ofGalileo Galilei, then Galileo Galilei is a brother of Marie Curie."
... with $B {\displaystyle B}$ true:"If Marie Curie is a sister of Galileo Galilei, then Marie Curie has a sibling."

Analytic tableaux

[edit]

Further information:Method of analytic tableaux

Formulas over the set of connectives $\{\to ,\bot \}$ ^[8] are calledf-implicational.^[9] Inclassical logic the other connectives, such as $\neg$ (negation), $\land$ (conjunction), $\lor$ (disjunction) and $\leftrightarrow$ (equivalence), can be defined in terms of $\to$ and $\bot$ (falsity):^[10] ${\begin{aligned}\neg A&\quad {\overset {\text{def}}{=}}\quad A\to \bot \\A\land B&\quad {\overset {\text{def}}{=}}\quad (A\to (B\to \bot ))\to \bot \\A\lor B&\quad {\overset {\text{def}}{=}}\quad (A\to \bot )\to B\\A\leftrightarrow B&\quad {\overset {\text{def}}{=}}\quad \{(A\to B)\to [(B\to A)\to \bot ]\}\to \bot \\\end{aligned}}$

The validity of f-implicational formulas can be semantically established by themethod of analytic tableaux. The logical rules are

${\frac {{\boldsymbol {\mathsf {T}}}(A\to B)}{{\boldsymbol {\mathsf {F}}}(A)\quad \mid \quad {\boldsymbol {\mathsf {T}}}(B)}}$	${\frac {{\boldsymbol {\mathsf {F}}}(A\to B)}{\begin{array}{c}{\boldsymbol {\mathsf {T}}}(A)\\{\boldsymbol {\mathsf {F}}}(B)\end{array}}}$
${\boldsymbol {\mathsf {T}}}(\bot )$ : Close the branch (contradiction) ${\boldsymbol {\mathsf {F}}}(\bot )$ : Do nothing (since it just asserts no contradiction)

Example: proof of

p\to \neg \neg p\quad

, bymethod of analytic tableaux

         F[p → ((p → ⊥) → ⊥)]          |         T[p]         F[(p → ⊥) → ⊥]          |         T[p → ⊥]         F[⊥] ┌────────┴────────┐F[p]              T[⊥] |                 |CONTRADICTION     CONTRADICTION(T[p], F[p])      (⊥ is true)

Example: proof of

\neg \neg p\to p\quad

, by method of analytic tableaux

         F[((p → ⊥) → ⊥) → p]          |         T[(p → ⊥) → ⊥]         F[p] ┌────────┴────────┐F[p → ⊥]          T[⊥] |                 |T[p]            CONTRADICTION (⊥ is true)F[⊥] |CONTRADICTION (T[p], F[p])

Hilbert-style proofs can be foundhere orhere.

Example: proof of

(p\to q)\to ((q\to r)\to (p\to r))

, by method of analytic tableaux

 1. F[(p → q) → ((q → r) → (p → r))]              |                       // from 1          2. T[p → q]          3. F[(q → r) → (p → r)]              |                       // from 3          4. T[q → r]          5. F[p → r]              |                       // from 5          6. T[p]          7. F[r]     ┌────────┴────────┐              // from 28a. F[p]          8b. T[q]     X        ┌────────┴────────┐     // from 4         9a. F[q]          9b. T[r]              X                 X

AHilbert-style proof can be foundhere.

Syntactical properties

[edit]

Further information:Natural deduction

The semantic definition by truth tables does not permit the examination of structurally identical propositional forms in variouslogical systems, where different properties may be demonstrated. The language considered here is restricted tof-implicational formulas.

Consider the following (candidate)natural deduction rules.

Implication Introduction (

\to

If assuming $A {\displaystyle A}$ one can derive $B {\displaystyle B}$ , then one can conclude $A\to B$ .

${\frac {\begin{array}{c}[A]\\\vdots \\B\end{array}}{A\to B}}$ ( $\to$ I)

$[A]$ is an assumption that is discharged when applying the rule.

Implication Elimination (

\to

This rule corresponds tomodus ponens.

${\frac {A\to B\quad A}{B}}$ ( $\to$ E)

${\frac {A\quad A\to B}{B}}$ ( $\to$ E)

Double Negation Elimination (

\neg \neg

${\frac {\begin{array}{c}(A\to \bot )\to \bot \\\end{array}}{A}}$ ( $\neg \neg$ E)

Falsum Elimination (

\bot

From falsum ( $\bot$ ) one can derive any formula.
(ex falso quodlibet)

${\frac {\bot }{A}}$ ( $\bot$ E)

Minimal logic: By limiting thenatural deduction rules toImplication Introduction ( $\to$ I) andImplication Elimination ( $\to$ E), one obtains (the implicational fragment of)^[10] minimal logic (as defined byJohansson).^[11]

Proof of

P\to \neg \neg P\quad

, within minimal logic

1.	[ P ]	// Assume
2.	[ P → ⊥ ]	// Assume
3.	⊥	// $\to$ E (1, 2)
4.	(P → ⊥) → ⊥)	// $\to$ I (2, 3), discharging 2
5.	P → ((P → ⊥) → ⊥)	// $\to$ I (1, 4), discharging 1

Intuitionistic logic: By addingFalsum Elimination ( $\bot$ E) as a rule, one obtains (the implicational fragment of)^[10] intuitionistic logic.

The statement

P\to \neg \neg P

is valid (already in minimal logic), unlike the reverse implication which would entail thelaw of excluded middle.

Classical logic: IfDouble Negation Elimination ( $\neg \neg$ E) is also permitted,^[14] the system defines (full!) classical logic.^[12]^[13]^[15]

A selection of theorems (classical logic)

[edit]

Inclassical logic material implication validates the following:

Contraposition:

(\neg Q\to \neg P)\to (P\to Q)

1.	[ (Q → ⊥) → (P → ⊥) ]	// Assume (to discharge at 9)
2.	[ P ]	// Assume (to discharge at 8)
3.	[ Q → ⊥ ]	// Assume (to discharge at 6))
4.	P → ⊥	// $\to$ E (1, 3)
5.	⊥	// $\to$ E (2, 4)
6.	(Q → ⊥) → ⊥	// $\to$ I (3, 5) (discharging 3)
7.	Q	// $\neg \neg$ E (6)
8.	P → Q	// $\to$ I (2, 7) (discharging 2)
9.	((Q → ⊥) → (P → ⊥)) → (P → Q)	// $\to$ I (1, 8) (discharging 1)

Peirce's law:

((P\to Q)\to P)\to P

1.	[ (P → Q) → P ]	// Assume (to discharge at 11)
2.	[ P → ⊥ ]	// Assume (to discharge at 9)
3.	[ P ]	// Assume (to discharge at 6)
4.	⊥	// $\to$ E (2, 3)
5.	Q	// $\bot$ E (4)
6.	P → Q	// $\to$ I (3, 5) (discharging 3)
7.	P	// $\to$ E (1, 6)
8.	⊥	// $\to$ E (2, 7)
9.	(P → ⊥) → ⊥	// $\to$ I (2, 8) (discharging 2)
10.	P	// $\neg \neg$ E (9)
11.	((P → Q) → P) → P	// $\to$ I (1, 10) (discharging 1)

Vacuous conditional (IPC):

\neg P\to (P\to Q)

1.	$[P\to \bot ]$	// Assume
2.	$[P]$	// Assume
3.	$\bot$	// $\to$ E (1, 2)
4.	$Q {\displaystyle Q}$	// $\bot$ E (3)
5.	$P\to Q$	// $\to$ I (2, 4) (discharging 2)
6.	$(P\to \bot )\to (P\to Q)$	// $\to$ I (1, 5) (discharging 1)

Import-export: $P\to (Q\to R)\equiv (P\land Q)\to R$
Negated conditionals: $\neg (P\to Q)\equiv P\land \neg Q$
Or-and-if: $P\to Q\equiv \neg P\lor Q$
Commutativity of antecedents: ${\big (}P\to (Q\to R){\big )}\equiv {\big (}Q\to (P\to R){\big )}$
Left distributivity: ${\big (}R\to (P\to Q){\big )}\equiv {\big (}(R\to P)\to (R\to Q){\big )}$

Similarly, on classical interpretations of the other connectives, material implication validates the followingentailments:

Antecedent strengthening: $P\to Q\models (P\land R)\to Q$
Transitivity: $(P\to Q)\land (Q\to R)\models P\to R$
Simplification of disjunctive antecedents: $(P\lor Q)\to R\models (P\to R)\land (Q\to R)$

Tautologies involving material implication include:

Reflexivity: $\models P\to P$
Totality: $\models (P\to Q)\lor (Q\to P)$
Conditional excluded middle: $\models (P\to Q)\lor (P\to \neg Q)$

Discrepancies with natural language

[edit]

Material implication does not closely match the usage ofconditional sentences innatural language. For example, even though material conditionals with false antecedents arevacuously true, the natural language statement "If 8 is odd, then 3 is prime" is typically judged false. Similarly, any material conditional with a true consequent is itself true, but speakers typically reject sentences such as "If I have a penny in my pocket, then Paris is in France". These classic problems have been called theparadoxes of material implication.^[16] In addition to the paradoxes, a variety of other arguments have been given against a material implication analysis. For instance,counterfactual conditionals would all be vacuously true on such an account, when in fact some are false.^[17]

In the mid-20th century, a number of researchers includingH. P. Grice andFrank Jackson proposed thatpragmatic principles could explain the discrepancies between natural language conditionals and the material conditional. On their accounts, conditionalsdenote material implication but end up conveying additional information when they interact with conversational norms such asGrice's maxims.^[16]^[18] Recent work informal semantics andphilosophy of language has generally eschewed material implication as an analysis for natural-language conditionals.^[18] In particular, such work has often rejected the assumption that natural-language conditionals aretruth functional in the sense that the truth value of "IfP, thenQ" is determined solely by the truth values ofP andQ.^[16] Thus semantic analyses of conditionals typically propose alternative interpretations built on foundations such asmodal logic,relevance logic,probability theory, andcausal models.^[18]^[16]^[19]

Similar discrepancies have been observed by psychologists studying conditional reasoning, for instance, by the notoriousWason selection task study, where less than 10% of participants reasoned according to the material conditional. Some researchers have interpreted this result as a failure of the participants to conform to normative laws of reasoning, while others interpret the participants as reasoning normatively according to nonclassical laws.^[20]^[21]^[22]

Notes

[edit]

^^a ^bHilbert 1918.
^Mendelson 2015.
^Van Heijenoort 1967.
^Note that the horseshoe symbol Ɔ has been flipped to become a subset symbol ⊂.
^Nahas 2022, p. VI.
^Bourbaki 1954, p. 14.
^Miller, Jeff (2020)."Earliest Uses of Symbols for Set Theory and Logic".Maths History (University of St Andrews). University of St Andrews. Retrieved10 June 2025.
^
Thewell-formed formulas are:
1. Eachpropositional variable is a formula.
2. " $\bot$ " is a formula.
3. If $A {\displaystyle A}$ and $B {\displaystyle B}$ are formulas, so is $(A\to B)$ .
4. Nothing else is a formula.
^Franco et al. 1999.
^^a ^b ^cf-implicational formulas cannot express all valid formulas inminimal (MPC) orintuitionistic (IPC) propositional logic — in particular, $\lor$ (disjunction) cannot be defined within it. In contrast, $\{\to ,\lor ,\bot \}$ is a complete basis for MPC / IPC: from these, all other connectives (e.g., $\land ,\neg ,\leftrightarrow ,\bot$ ) can be defined.
^Johansson 1937.
^^a ^bPrawitz 1965, p. 21.
^^a ^bAyala-Rincón & de Moura 2017, pp. 17–24.
^Instead of $\neg \neg$ E one can addreductio ad absurdum as a rule to obtain (full) classical logic:^[12]^[13]
${\frac {\begin{array}{c}[A\to \bot ]\\\vdots \\\bot \end{array}}{A}}$ (RAA)
^Tennant 1990, p. 48.
^^a ^b ^c ^dEdgington 2008.
^For example, "IfJanis Joplin were alive today, she would drive aMercedes-Benz", seeStarr (2019)
^^a ^b ^cGillies 2017.
^Von Fintel 2011.
^Oaksford & Chater 1994.
^Stenning & van Lambalgen 2004.
^Von Sydow 2006.

Bibliography

[edit]

Ayala-Rincón, Mauricio; de Moura, Flávio L. C. (2017).Applied Logic for Computer Scientists. Undergraduate Topics in Computer Science. Springer.doi:10.1007/978-3-319-51653-0.ISBN 978-3-319-51651-6.

Bourbaki, N. (1954).Théorie des ensembles. Paris: Hermann & Cie, Éditeurs. p. 14.

Edgington, Dorothy (2008)."Conditionals". In Edward N. Zalta (ed.).The Stanford Encyclopedia of Philosophy (Winter 2008 ed.).

Von Fintel, Kai (2011)."Conditionals"(PDF). In von Heusinger, Klaus; Maienborn, Claudia; Portner, Paul (eds.).Semantics: An international handbook of meaning. de Gruyter Mouton. pp. 1515–1538.doi:10.1515/9783110255072.1515.hdl:1721.1/95781.ISBN 978-3-11-018523-2.

Franco, John; Goldsmith, Judy; Schlipf, John; Speckenmeyer, Ewald; Swaminathan, R.P. (1999)."An algorithm for the class of pure implicational formulas".Discrete Applied Mathematics.96–97:89–106.doi:10.1016/S0166-218X(99)00038-4.

Gillies, Thony (2017)."Conditionals"(PDF). In Hale, B.; Wright, C.; Miller, A. (eds.).A Companion to the Philosophy of Language. Wiley Blackwell. pp. 401–436.doi:10.1002/9781118972090.ch17.ISBN 9781118972090.

Van Heijenoort, Jean, ed. (1967).From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. pp. 84–87.ISBN 0-674-32449-8.

Hilbert, D. (1918).Prinzipien der Mathematik (Lecture Notes edited by Bernays, P.).

Johansson, Ingebrigt (1937)."Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus".Compositio Mathematica (in German).4:119–136.

Mendelson, Elliott (2015).Introduction to Mathematical Logic (6th ed.). Boca Raton: CRC Press/Taylor & Francis Group (A Chapman & Hall Book). p. 2.ISBN 978-1-4822-3778-8.

Nahas, Michael (25 Apr 2022)."English Translation of 'Arithmetices Principia, Nova Methodo Exposita'"(PDF). GitHub. Retrieved2022-08-10.

Oaksford, M.; Chater, N. (1994). "A rational analysis of the selection task as optimal data selection".Psychological Review.101 (4):608–631.CiteSeerX 10.1.1.174.4085.doi:10.1037/0033-295X.101.4.608.S2CID 2912209.

Prawitz, Dag (1965).Natural Deduction: A Proof-Theoretic Study. Acta Universitatis Stockholmiensis; Stockholm Studies in Philosophy, 3. Stockholm, Göteborg, Uppsala: Almqvist & Wiksell.OCLC 912927896.

Starr, Willow (2019)."Counterfactuals". In Zalta, Edward N. (ed.).The Stanford Encyclopedia of Philosophy.

Stenning, K.; van Lambalgen, M. (2004). "A little logic goes a long way: basing experiment on semantic theory in the cognitive science of conditional reasoning".Cognitive Science.28 (4):481–530.CiteSeerX 10.1.1.13.1854.doi:10.1016/j.cogsci.2004.02.002.

Von Sydow, M. (2006).Towards a Flexible Bayesian and Deontic Logic of Testing Descriptive and Prescriptive Rules (doctoralThesis). Göttingen: Göttingen University Press.doi:10.53846/goediss-161.S2CID 246924881.

Tennant, Neil (1990) [1978].Natural Logic (1st, repr. with corrections ed.).Edinburgh University Press.ISBN 0852245793.

External links

[edit]

Edgington, Dorothy."Conditionals". InZalta, Edward N. (ed.).Stanford Encyclopedia of Philosophy.ISSN 1095-5054.OCLC 429049174.

v t e Commonlogical connectives
Tautology/True $\top$
Alternative denial (NAND gate) ${\overline {\wedge }}$ Converse implication $\Leftarrow$ Implication (IMPLY gate) $\Rightarrow$ Disjunction (OR gate) $\lor$
Negation (NOT gate) $\neg$ Exclusive or (XOR gate) $\oplus$ Biconditional (XNOR gate) $\odot$ Statement (Digital buffer)
Joint denial (NOR gate) ${\overline {\vee }}$ Nonimplication (NIMPLY gate) $\nRightarrow$ Converse nonimplication $\nLeftarrow$ Conjunction (AND gate) $\land$
Contradiction/False $\bot$
Philosophy portal

Commonlogical symbols

∧ or &

¬ or ~

↔ or ≡

universal
quantification

∃

existential
quantification

General

Theorems
(list),
paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps, cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive