Conditional proof

Transformation rules
Propositional calculus
Rules of inference
Rules of replacement
Predicate logic
Rules of inference

A conditional proof is a proof that takes the form of asserting a conditional, and proving that the antecedent of the conditional necessarily leads to the consequent.

Overview

The assumed antecedent of a conditional proof is called the conditional proof assumption (CPA). Thus, the goal of a conditional proof is to demonstrate that if the CPA were true, then the desired conclusion necessarily follows. The validity of a conditional proof does not require that the CPA be true, only that if it were true it would lead to the consequent.

Conditional proofs are of great importance in mathematics. Conditional proofs exist linking several otherwise unproven conjectures, so that a proof of one conjecture may immediately imply the validity of several others. It can be much easier to show a proposition's truth to follow from another proposition than to prove it independently.

A famous network of conditional proofs is the NP-complete class of complexity theory. There is a large number of interesting tasks (see List of NP-complete problems), and while it is not known if a polynomial-time solution exists for any of them, it is known that if such a solution exists for some of them, one exists for all of them. Similarly, the Riemann hypothesis has many consequences already proven.

Symbolic logic

As an example of a conditional proof in symbolic logic, suppose we want to prove A → C (if A, then C) from the first two premises below:

1. A → B    ("If A, then B")
2. B → C ("If B, then C")
3. A (conditional proof assumption, "Suppose A is true")
4. B (follows from lines 1 and 3, modus ponens; "If A then B; A, therefore B")
5. C (follows from lines 2 and 4, modus ponens; "If B then C; B, therefore C")
6. A → C (follows from lines 3–5, conditional proof; "If A, then C")

See also

References

  • Robert L. Causey, Logic, sets, and recursion, Jones and Barlett, 2006.
  • Dov M. Gabbay, Franz Guenthner (eds.), Handbook of philosophical logic, Volume 8, Springer, 2002.

Read other articles:

Operación Inundación de Al-Aqsa

Operación Inundación de Al-Aqsa Parte de Guerra Israel-Gaza Edificio residencial quemado en el kibutz de Beeri tras el ataque.Fecha 7-9 de octubre de 2023Lugar Sur de IsraelCoordenadas 31°21′49″N 34°30′28″E / 31.363527777778, 34.507694444444Resultado Hamás, junto con otros grupos palestinos, traspasa la barrera entre Israel y Gaza y ocupa varias zonas israelíes.Consecuencias El ataque fue repelido tras numerosas bajas civiles y militares y se inició la Guerra Is...

 

Karl Leonhard Reinhold

Karl Leonhard ReinholdGambar karya Peter Copmann [da], 1820Lahir(1757-10-26)26 Oktober 1757Wina, Keharyapatihan AustriaMeninggal10 April 1823(1823-04-10) (umur 65)Kiel, Konfederasi JermanPendidikanJesuitenkollegium St. Anna (1772–1773)Barnabitenkollegium St. Michael (1773–1778)Universitas Leipzig(1784; tanpa gelar)EraFilsafat abad ke-18KawasanFilsafat BaratAliranPencerahan Austria[1]Idealisme JermanInstitusiBarnabitenkollegium St. Michael (1778–1783)Universita...

 

Libri Carolini

Mosaik Tabut Perjanjian, sekitar 806 dari sebuah oratori di Germigny-des-Prés yang dibangun oleh Uskup Theodulf dari Orléans, yang diyakini merupakan pengarang dari karya tersebut. Libri Carolini (Buku-buku Charles), Opus Caroli regis contra synodum (Karya Raja Charles melawan Sinodo), yang juga disebut Buku-Buku Charlemagne atau singkatnya Carolines, adalah karya dalam empat buku yang terdiri atas komando Charlemagne, sekitar tahun 790 Libri Carolini tidak pernah mempromulgasikannya pada w...

Tomasz Iwan

Polish footballer Tomek Iwan Iwan in 2012Personal informationFull name Tomasz IwanDate of birth (1971-06-12) 12 June 1971 (age 52)Place of birth Słupsk, PolandPosition(s) MidfielderYouth career Jantar Ustka Gryf SłupskSenior career*Years Team Apps (Gls)1991–1992 Olimpia Poznań 17 (1)1992–1993 ŁKS Łódź 10 (0)1993–1994 Warta Poznań 31 (7)1994–1995 Roda JC 30 (4)1995–1997 Feyenoord 45 (3)1997–2001 PSV 73 (5)2001 Trabzonspor 0 (0)2001 RBC Roosendaal 10 (1)2001–2002 Aust...

 

العلاقات الزيمبابوية الكوستاريكية

العلاقات الزيمبابوية الكوستاريكية زيمبابوي كوستاريكا   زيمبابوي   كوستاريكا تعديل مصدري - تعديل   العلاقات الزيمبابوية الكوستاريكية هي العلاقات الثنائية التي تجمع بين زيمبابوي وكوستاريكا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومر...

 

1994 Green Bay Packers season

NFL team season 1994 Green Bay Packers seasonOwnerGreen Bay Packers, Inc.PresidentBob HarlanGeneral managerRon WolfHead coachMike HolmgrenHome fieldLambeau FieldMilwaukee County StadiumResultsRecord9–7Division place2nd NFC CentralPlayoff finishWon Wild Card Playoffs(vs. Lions) 16–12Lost Divisional Playoffs(at Cowboys) 9–35 ← 1993 Packers seasons 1995 → The 1994 season was the Green Bay Packers' 74th season in the National Football League (NFL), their 76th over...

Toro Rosso STR4

Toro Rosso STR4 Sébastien Bourdais nel Gran Premio di Spagna 2009 Descrizione generale Costruttore  Toro Rosso Categoria Formula 1 Squadra Scuderia Toro Rosso Progettata da Adrian NeweyGeoff WillisRob MarshallPeter Prodromou Sostituisce Toro Rosso STR3 Sostituita da Toro Rosso STR5 Descrizione tecnica Meccanica Telaio Monoscocca composita modellata in fibra di carbonio a nido d'ape Motore Ferrari 2.4 V8 Trasmissione a 7 rapporti semi-automatica Dimensioni e pesi Peso 605 kg Altro Carbu...

 

Chronospecies

Species derived from extinct ancestor In palaeontology, the evidence for species and evolution comes mainly from the comparative anatomy of fossils. A chronospecies is defined in a single lineage (solid line) whose morphology changes with time. At some point, palaeontologists judge that enough change has occurred that two forms (A and B), separated in time and anatomy, once existed. If only sporadic examples of each survive in the fossil record, the forms will appear sharply distinct. A chron...

 

Ricky Ponting with the Australian cricket team in India in 2008–09

It has been suggested that this article be merged with Early life of Ricky Ponting to Ricky Ponting. (Discuss) Proposed since March 2024. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ricky Ponting with the Australian cricket team in India in 2008–09 – news · newspapers · books · scholar · JSTOR (Ma...

G.I. Blues

1960 film by Norman Taurog, Hal B. Wallis G.I. BluesTheatrical release posterDirected byNorman TaurogWritten by Edmund Beloin Henry Garson Produced byHal B. WallisStarring Elvis Presley Juliet Prowse CinematographyLoyal GriggsEdited byWarren LowMusic byJoseph J. LilleyProductioncompanyHal Wallis ProductionsDistributed byParamount PicturesRelease date November 4, 1960 (1960-11-04) (New York)[1] Running time104 minutesCountryUnited StatesLanguageEnglishBox office$4.3 ...

 

Mumbai

Mumbai MumbaiQuốc gia Ấn ĐộBangMaharashtraĐặt tên theoMumba Chính quyền • Cao ủy Thành phốJairaj PhatakDiện tích • Thành phố603,71 km2 (23,309 mi2) • Đô thị24,700,000 km2 (9,500,000 mi2)Độ cao8 m (26 ft)Dân số (2023) • Thành phố18,983,645 (Hạng thứ nhất)Múi giờIST (UTC+05:30)Mã bưu chính400 xxxMã điện thoại...

 

1969 Cleveland mayoral election

1969 mayoral election in Cleveland, Ohio 1969 Cleveland mayoral election ← 1967 November 4, 1969 1971 →   Nominee Carl Stokes Ralph Perk Party Democratic Republican Popular vote 120,559 116,806 Percentage 50.48% 48.91% Mayor before election Carl Stokes Democratic Elected Mayor Carl Stokes Democratic Elections in Ohio Federal government U.S. President 1804 1808 1812 1816 1820 1824 1828 1832 1836 1840 1844 1848 1852 1856 1860 1864 1868 1872 1876 1880 1884 1888 18...

1982 New York Jets season

1982 season of NFL team New York Jets 1982 New York Jets seasonOwnerLeon HessHead coachWalt MichaelsHome fieldShea StadiumResultsRecord6–3Division place6th AFCPlayoff finishWon Wild card playoffs(at Bengals) 44–17Won Divisional Playoffs(at Raiders) 17–14Lost AFC Championship(at Dolphins) 0–14Pro BowlersC Joe FieldsT Marvin PowellWR Wesley WalkerRB Freeman McNeilDE Mark Gastineau ← 1981 Jets seasons 1983 → The 1982 New York Jets season was the 23rd season for...

 

J. Alexander (model)

Runway coach, consultant, model J. AlexanderAlexander hosting the It Gets Better Project Holiday Show 2014.BornAlexander Jenkins (1958-04-12) April 12, 1958 (age 66)The Bronx, New York City, New York, U.S.Other namesMiss JOccupation(s)Runway coach, consultantYears active1979–presentKnown forTelevision personality and runway coachingChildren1 Alexander Jenkins (born April 12, 1958[1][2]), known as J. Alexander or Miss J, is an American reality television p...

 

Kung-fu

Para otros usos de este término, véase Kung-fu (desambiguación).Kung-fu Nombre chinoChino 功夫 TransliteracionesMandarínHanyu Pinyin GōngfuWade–Giles kung-fuBopomofo ㄍㄨㄥ ㄈㄨMinHokkien POJ kang-huWuRomanización kon fuCantonésJyutping gung fu[editar datos en Wikidata] Kung-fu (en chino simplificado, 功夫; en chino tradicional, 功夫; pinyin, gōngfu) es un término global para referirse a las artes marciales de origen chino (wushu o quanfa) basada en un...

Bell 214

Bell 214B Bell 214 adalah sebuah Helikopter menengah-angkat berasal dari seri Bell Helicopter UH-1 Huey. Bell 214ST nomor model yang sama, tetapi yang lebih besar, modifikasi derivatif bermesin ganda. Referensi Pranala luar Wikimedia Commons memiliki media mengenai Bell 214. lbsPesawat Bell Aircraft dan Bell HelicopterDaftar pesawat Bell Aircraft dan Bell Helicopter Tanda perusahaan 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 ...

 

Clas Thunberg

Questa voce sull'argomento pattinatori su ghiaccio finlandesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Clas ThunbergNazionalità Finlandia Altezza167 cm Pattinaggio di velocità Termine carriera1928 Palmarès Competizione Ori Argenti Bronzi Olimpiadi 5 1 1 Vedi maggiori dettagli  Modifica dati su Wikidata · Manuale Arnold Clas Robert Thunberg (Helsinki, 5 aprile 1893 – Helsinki, 28 aprile 1973) è stato un pattinatore di veloc...

 

Leif Størmer

Norwegian paleontologist and geologist Leif StørmerStørmer in 1933Born(1905-07-01)July 1, 1905Kristiania, NorwayDiedMay 15, 1979(1979-05-15) (aged 73)Oslo, NorwayNationalityNorwegianAlma materUniversity of OsloSpouseIngegerd Wiborg AltenAwardsOrder of St. Olav, Defence Medal 1940–1945, Reusch Medal, Nansen Prize Leif Størmer (1 July 1905 – 15 May 1979) was a Norwegian paleontologist and geologist. He was professor of historical geology at the University of Oslo from 1946 to 1...

Divisi Tenggara (NBA)

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Divisi Tenggara NBA – berita · surat kabar · buku · cendekiawan · JSTOR Divisi Tenggara merupakan salah satu divisi yang berada di Wilayah Timur NBA. Divisi ini terdiri dari lima tim, Atlanta Hawks,...

 

Украинская музыка

У этой статьи надо проверить нейтральность. На странице обсуждения должны быть подробности. Украи́нская му́зыка (укр. Українська музика) — достижения музыкальной культуры украинского народа; результат многовекового исторического процесса формирования и развития свое...