Formal Logic
b
en.wikibooks.org
,Mayb 21,b 2017
Onbtheb28thbofbAprilb2012bthebcontentsbofbthebEnglishbasbwellbasbGermanbWikibooksbandbWikipedi
abprojectsbwereblicensedbunderbCreativebCommonsbAttribution-
ShareAlikeb3.0bUnportedblicense.b AbURIbtobthisblicensebisbgivenbinbtheblistbofbfiguresbonbpageb24
3.b Ifbthisbdocumentbisbabderivedbworkbfrombthebcontentsbofbonebofbthesebprojectsbandbthebconte
ntbwasbstillblicensedbbybthebprojectbunderbthisblicensebatbthebtimebofbderivationbthisbdocumentbhasb
tobbeblicensedbunderbthebsame,babsimilarborbabcompatibleblicense,basbstatedbinbsectionb4bbofbtheblicens
e.bTheblistbofbcontributorsbisbincludedbinbchapterbContributorsbonbpageb241.b TheblicensesbGPL,bLGP
LbandbGFDLbarebincludedbinbchapterbLicensesbonbpageb249,bsincebthisbbookband/orbpartsbofbitbmay
borbmaybnotbbeblicensedbunderboneborbmorebofbtheseblicenses,bandbthusbrequirebinclusionbofbtheseblic
enses.b Theblicensesbofbthebfiguresbarebgivenbinbtheblistbofbfiguresbonbpageb243.bThisbPDFbwasbgenerate
dbbybthebLATEXbtypesettingbsoftware.bThebLATEXbsourcebcodebisbincludedbasbanbattachmentb(sou
rce.7z.txt)binbthisbPDFbfile.b TobextractbthebsourcebfrombthebPDFbfile,byoubcanbusebthebpdfdetac
hbtoolbincludingbinbthebpopplerbsuite,borbthebhttp://www.bpdflabs.com/tools/pdftk-the-pdf-
toolkit/b utility.b Someb PDFb viewersb mayb alsob letb youb savebthebattachment btobabfile.b Afterbe
xtractingbitbfrombthebPDFbfilebyoubhavebtobrenamebitbtobsource.7z.bTobuncompressbthebresultingba
rchivebwebrecommendbthebusebofbhttp://www.7-
zip.org/.b ThebLATEXbsourcebitselfbwasbgeneratedbbybabprogrambwrittenbbybDirkbHünniger,bwhichbis
bfreelybavailablebunderbanb b openb b sourceb b licenseb b fromb b http://de.wikibooks.org/wiki/Benutzer:
Dirk_Huenniger/wb2pdf.
,Contents
1 Sets 3
1.1 Setsbandbelements .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 3
1.2 Subsets,b powerb sets,b setb operationsb .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 5
1.3 Orderedbsets,brelations,bandbfunctions .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 7
2 ThebSententialbLanguage 11
2.1 Languagebcomponents ..................................................................................................11
2.2 Notes .............................................................................................................................. 13
2.3 Translation .................................................................................................................... 14
2.4 Quotingbconvention...................................................................................................... 14
3 Formalb Syntax 17
3.1 Vocabulary..................................................................................................................... 17
3.2 Expressions ................................................................................................................... 17
3.3 Formationb rules ............................................................................................................ 18
3.4 Quotingbconvention...................................................................................................... 18
3.5 Additionalb terminology................................................................................................ 19
3.6 Examples ....................................................................................................................... 19
4 Informalb Conventions 21
4.1 Transformationb rules .................................................................................................... 21
4.2 Precedencebandbscope ..................................................................................................22
4.3 Examples .......................................................................................................................23
5 Formalb Semantics 25
5.1 Formalbsemantics ......................................................................................................... 25
5.2 Valuations......................................................................................................................26
5.3 Extendedb valuations..................................................................................................... 27
5.4 Example ......................................................................................................................... 27
6 TruthbTables 31
6.1 Basicb tables ................................................................................................................... 31
6.2 Example ......................................................................................................................... 41
6.3 Satisfactionbandbvaliditybofbformulae......................................................................... 45
6.4 Validitybofbarguments .................................................................................................. 47
6.5 Formulaebandbarguments ............................................................................................ 48
6.6 Implication ....................................................................................................................49
7 Expressibility 51
7.1 Truthb functions............................................................................................................. 51
III
, Contents
7.2 Expressingbarbitrarybtruthbfunctions......................................................................... 55
7.3 Normalbforms ............................................................................................................... 56
7.4 Interdefinabilityb ofb connectives .................................................................................. 57
7.5 Jointb andb alternativeb denials ...................................................................................... 63
8 PropertiesbofbSententialbConnectives 73
8.1 Bivalence ....................................................................................................................... 73
8.2 Analoguesbtobarithmeticblaws ..................................................................................... 73
8.3 Otherbtautologiesbandbequivalences ........................................................................... 82
8.4 Deductionbandbreductionbprinciples .......................................................................... 87
9 SubstitutionbandbInterchange 89
9.1 Substitution .................................................................................................................. 89
9.2 Interchange ................................................................................................................... 91
9.3 Summary ....................................................................................................................... 97
10 Translations 99
10.1 Englishb sententialb connectives .................................................................................... 99
10.2 Examples ..................................................................................................................... 105
11 Derivations 107
11.1 Derivations .................................................................................................................. 107
11.2 Soundnessbandbvalidity............................................................................................... 108
11.3 Turnstiles .................................................................................................................... 108
12 Inferenceb Rules 111
12.1 Overview....................................................................................................................... 111
12.2 Inferenceb rules ............................................................................................................. 112
12.3 Examples ...................................................................................................................... 115
13 ConstructingbabSimplebDerivation 117
13.1 Rules ............................................................................................................................. 117
13.2 Anbexamplebderivation ............................................................................................... 118
14 Subderivationsb andb Dischargeb Rules 129
14.1 Derivingbconditionals................................................................................................. 129
14.2 Negations .................................................................................................................... 133
14.3 Terminology .................................................................................................................137
15 Constructingb ab Complexb Derivation 139
15.1 Anbexamplebderivation .............................................................................................. 139
15.2 Thebcompletebderivation ............................................................................................155
16 Theorems 159
16.1 Anb example ................................................................................................................. 159
16.2 Justification:b Convertingbtobunabbreviatedbderivation ......................................... 163
16.3 Additionalb theorems ...................................................................................................167
IV
b
en.wikibooks.org
,Mayb 21,b 2017
Onbtheb28thbofbAprilb2012bthebcontentsbofbthebEnglishbasbwellbasbGermanbWikibooksbandbWikipedi
abprojectsbwereblicensedbunderbCreativebCommonsbAttribution-
ShareAlikeb3.0bUnportedblicense.b AbURIbtobthisblicensebisbgivenbinbtheblistbofbfiguresbonbpageb24
3.b Ifbthisbdocumentbisbabderivedbworkbfrombthebcontentsbofbonebofbthesebprojectsbandbthebconte
ntbwasbstillblicensedbbybthebprojectbunderbthisblicensebatbthebtimebofbderivationbthisbdocumentbhasb
tobbeblicensedbunderbthebsame,babsimilarborbabcompatibleblicense,basbstatedbinbsectionb4bbofbtheblicens
e.bTheblistbofbcontributorsbisbincludedbinbchapterbContributorsbonbpageb241.b TheblicensesbGPL,bLGP
LbandbGFDLbarebincludedbinbchapterbLicensesbonbpageb249,bsincebthisbbookband/orbpartsbofbitbmay
borbmaybnotbbeblicensedbunderboneborbmorebofbtheseblicenses,bandbthusbrequirebinclusionbofbtheseblic
enses.b Theblicensesbofbthebfiguresbarebgivenbinbtheblistbofbfiguresbonbpageb243.bThisbPDFbwasbgenerate
dbbybthebLATEXbtypesettingbsoftware.bThebLATEXbsourcebcodebisbincludedbasbanbattachmentb(sou
rce.7z.txt)binbthisbPDFbfile.b TobextractbthebsourcebfrombthebPDFbfile,byoubcanbusebthebpdfdetac
hbtoolbincludingbinbthebpopplerbsuite,borbthebhttp://www.bpdflabs.com/tools/pdftk-the-pdf-
toolkit/b utility.b Someb PDFb viewersb mayb alsob letb youb savebthebattachment btobabfile.b Afterbe
xtractingbitbfrombthebPDFbfilebyoubhavebtobrenamebitbtobsource.7z.bTobuncompressbthebresultingba
rchivebwebrecommendbthebusebofbhttp://www.7-
zip.org/.b ThebLATEXbsourcebitselfbwasbgeneratedbbybabprogrambwrittenbbybDirkbHünniger,bwhichbis
bfreelybavailablebunderbanb b openb b sourceb b licenseb b fromb b http://de.wikibooks.org/wiki/Benutzer:
Dirk_Huenniger/wb2pdf.
,Contents
1 Sets 3
1.1 Setsbandbelements .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 3
1.2 Subsets,b powerb sets,b setb operationsb .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 5
1.3 Orderedbsets,brelations,bandbfunctions .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b .b . 7
2 ThebSententialbLanguage 11
2.1 Languagebcomponents ..................................................................................................11
2.2 Notes .............................................................................................................................. 13
2.3 Translation .................................................................................................................... 14
2.4 Quotingbconvention...................................................................................................... 14
3 Formalb Syntax 17
3.1 Vocabulary..................................................................................................................... 17
3.2 Expressions ................................................................................................................... 17
3.3 Formationb rules ............................................................................................................ 18
3.4 Quotingbconvention...................................................................................................... 18
3.5 Additionalb terminology................................................................................................ 19
3.6 Examples ....................................................................................................................... 19
4 Informalb Conventions 21
4.1 Transformationb rules .................................................................................................... 21
4.2 Precedencebandbscope ..................................................................................................22
4.3 Examples .......................................................................................................................23
5 Formalb Semantics 25
5.1 Formalbsemantics ......................................................................................................... 25
5.2 Valuations......................................................................................................................26
5.3 Extendedb valuations..................................................................................................... 27
5.4 Example ......................................................................................................................... 27
6 TruthbTables 31
6.1 Basicb tables ................................................................................................................... 31
6.2 Example ......................................................................................................................... 41
6.3 Satisfactionbandbvaliditybofbformulae......................................................................... 45
6.4 Validitybofbarguments .................................................................................................. 47
6.5 Formulaebandbarguments ............................................................................................ 48
6.6 Implication ....................................................................................................................49
7 Expressibility 51
7.1 Truthb functions............................................................................................................. 51
III
, Contents
7.2 Expressingbarbitrarybtruthbfunctions......................................................................... 55
7.3 Normalbforms ............................................................................................................... 56
7.4 Interdefinabilityb ofb connectives .................................................................................. 57
7.5 Jointb andb alternativeb denials ...................................................................................... 63
8 PropertiesbofbSententialbConnectives 73
8.1 Bivalence ....................................................................................................................... 73
8.2 Analoguesbtobarithmeticblaws ..................................................................................... 73
8.3 Otherbtautologiesbandbequivalences ........................................................................... 82
8.4 Deductionbandbreductionbprinciples .......................................................................... 87
9 SubstitutionbandbInterchange 89
9.1 Substitution .................................................................................................................. 89
9.2 Interchange ................................................................................................................... 91
9.3 Summary ....................................................................................................................... 97
10 Translations 99
10.1 Englishb sententialb connectives .................................................................................... 99
10.2 Examples ..................................................................................................................... 105
11 Derivations 107
11.1 Derivations .................................................................................................................. 107
11.2 Soundnessbandbvalidity............................................................................................... 108
11.3 Turnstiles .................................................................................................................... 108
12 Inferenceb Rules 111
12.1 Overview....................................................................................................................... 111
12.2 Inferenceb rules ............................................................................................................. 112
12.3 Examples ...................................................................................................................... 115
13 ConstructingbabSimplebDerivation 117
13.1 Rules ............................................................................................................................. 117
13.2 Anbexamplebderivation ............................................................................................... 118
14 Subderivationsb andb Dischargeb Rules 129
14.1 Derivingbconditionals................................................................................................. 129
14.2 Negations .................................................................................................................... 133
14.3 Terminology .................................................................................................................137
15 Constructingb ab Complexb Derivation 139
15.1 Anbexamplebderivation .............................................................................................. 139
15.2 Thebcompletebderivation ............................................................................................155
16 Theorems 159
16.1 Anb example ................................................................................................................. 159
16.2 Justification:b Convertingbtobunabbreviatedbderivation ......................................... 163
16.3 Additionalb theorems ...................................................................................................167
IV
