22 Rökfræði

2.6 Reglur De Morgans

Landslagsmynd af brú yfir vatn. — **Mynd 2.12.** Reglur De Morgans gegndu lykilhlutverki í þróun táknrænnar stærðfræðirökfræði og ruddu brautina fyrir uppfinningu tölvunnar. (mynd breytt frá „Golden Gate Bridge (San Francisco Bay, California, USA)“ eftir James St. John/Flickr, CC BY 2.0)

Námsmarkmið

Eftir að hafa lokið þessum hluta átt þú að geta:

notað reglur De Morgans til að neita samtengingum og mistengingum.
myndað neitun skilyrðingar.
notað sanngildistöflur til að meta reglur De Morgans.

Framlag Augustusar De Morgan og Georges Boole til rökfræðinnar á 19. öld ruddi brautina fyrir þróun tölvunnar. Tölvan er ef til vill mesta uppfinning 20. aldar. Boole-rökfræði er undirstaða tölvunarfræði og stafrænnar rafeindatækni. Án hennar hefði tæknibylting síðari hluta 20. aldar og upphafs þeirrar 21. — þar á meðal tilkoma tölvukubba, örgjörva og internetsins — ekki verið möguleg. Öll nútímaforritunarmál nota yrðingar úr Boole-rökfræði sem eru þýddar yfir í skipanir sem rafrásir tölvunnar skilja; þannig getur tölvan starfað. En hvaðan kemur heiti þessarar rökfræði?

Fólk í stærðfræði

George Boole

Mynd 2.13. Boole-algebra lagði grunn að hönnun stafrænna tölvurása. (mynd: „Circuit Board“ eftir Squeezyboy/Flickr, CC BY 2.0)

George Boole fæddist í Lincolnshire á Englandi árið 1815. Faðir hans var skósmiður og veitti honum nokkra grunnmenntun, en Boole var að mestu sjálfmenntaður. Hann hóf kennslu sextán ára og stofnaði eigin skóla tvítugur. Árið 1849, 34 ára gamall, var hann skipaður prófessor í stærðfræði við Queens College í Cork á Írlandi. Árið 1854 gaf hann út ritgerðina Rannsókn á lögmálum hugsunarinnar, sem stærðfræðikenningar rökfræðinnar og líkinda byggjast á. Ritgerðin varð grundvöllur Boole-algebru og stafrænna rafrása.

Heimild: Posamentier, Alfred og Spreitzer, Christian, „Chapter 35 George Boole: English (1815–1864)“, bls. 279–283, Math Makers: The Lives and Works of 50 Famous Mathematicians, Prometheus Books, 2019.

Neitun samtenginga og mistenginga

Í 1. kafla var Venn-mynd notuð í dæmi 1.37 til að sanna reglu De Morgans um fyllimengi sammengis. Þar sem fyllimengi samsvarar neitun og sammengi samsvarar mistengingu eru til hliðstæðar reglur De Morgans í rökfræði.

Reglur De Morgans gera okkur kleift að skrifa neitun samtenginga og mistenginga án þess að nota orðalagið „Það er ekki svo að …“ um það sem stendur innan sviga. Þannig verður skrifleg eða munnleg yrðing oft skýrari og auðskiljanlegri.

Dæmi 2.26

Reglu De Morgans beitt við neitun samtenginga og mistenginga

Skrifaðu neitun hverrar yrðingar með orðum án þess að nota orðalagið „Það er ekki svo að …“.

Kristin er lífverkfræðingur og Thomas er efnaverkfræðingur.
Viðkomandi fékk sér köku eða ís.

Lausn

Yrðingin „Kristin er lífverkfræðingur og Thomas er efnaverkfræðingur“ hefur formið $p \land q$ , þar sem $p$ er yrðingin „Kristin er lífverkfræðingur“ og $q$ er yrðingin „Thomas er efnaverkfræðingur“. Samkvæmt reglu De Morgans er neitun samtengingarinnar, $~ (p \land q)$ , rökfræðilega jafngild $~ p \lor ~ q .$ $~ p$ táknar yrðinguna „Kristin er ekki lífverkfræðingur“ og $~ q$ táknar yrðinguna „Thomas er ekki efnaverkfræðingur“. Neitunin hefur því formið $~ p \lor ~ q$ og með orðum er svarið: „Kristin er ekki lífverkfræðingur eða Thomas er ekki efnaverkfræðingur.“
Yrðingin „Viðkomandi fékk sér köku eða ís“ hefur formið $p \lor q,$ þar sem $p$ er yrðingin „Viðkomandi fékk sér köku“ og $q$ er yrðingin „Viðkomandi fékk sér ís“. Samkvæmt reglu De Morgans um neitun mistengingar gildir $~ (p \lor q) \equiv ~ p \land ~ q .$ Lausnin er því yrðingin: „Viðkomandi fékk sér hvorki köku né ís.“

Neitun skilyrðingar

Neitun yrðingar hefur andstætt sanngildi við upphaflegu yrðinguna. Neitun skilyrðingar, $~ (p \to q)$ , er samtenging $p$ og neitunar $q$ , $p \land ~ q .$ Skoðaðu sanngildistöfluna hér á eftir fyrir neitun skilyrðingarinnar.

$p$	$q$	$p \to q$	$~ (p \to q)$
T	T	T	F
T	F	F	T
F	T	T	F
F	F	T	F

Neitun skilyrðingar er aðeins sönn þegar $p$ er sönn en $q$ er ósönn. Það merkir að $~ (p \to q)$ er rökfræðilega jafngild $p \land ~ q,$ eins og eftirfarandi sanngildistafla sýnir.

$p$	$q$	$p \to q$	$~ (p \to q)$	$~ q$	$p \land ~ q$	$~ (p \to q) \leftrightarrow (p \land ~ q)$
T	T	T	F	F	F	T
T	F	F	T	T	T	T
F	T	T	F	F	F	T
F	F	T	F	T	F	T

Dæmi 2.27

Að mynda neitun skilyrðingar

Skrifaðu neitun hverrar skilyrðingar.

Ef Adele hlaut Grammy-verðlaun þá er hún söngkona.
Ef Henrik Lundqvist lék í atvinnumannahokkí þá vann hann ekki Stanley-bikarinn.

Lausn

Neitun skilyrðingarinnar $p \to q$ er yrðingin $p \land ~ q .$ Forliður skilyrðingarinnar er $p$ : „Adele hlaut Grammy-verðlaun“ og bakliður skilyrðingarinnar er $q$ : „Adele er söngkona.“ Neitun bakliðarins, $~ q$ , er yrðingin „Hún er ekki söngkona.“ Svarið er því $p \land ~ q :$ „Adele hlaut Grammy-verðlaun og hún er ekki söngkona.“
Forliðurinn er $p$ : „Henrik Lundqvist lék í atvinnumannahokkí“ og bakliður skilyrðingarinnar er $q$ : „Hann vann ekki Stanley-bikarinn.“ Neitun yrðingarinnar $q$ er yrðingin „Hann vann Stanley-bikarinn.“ Neitun skilyrðingarinnar er jafngild $p \land ~ q :$ „Henrik Lundqvist lék í atvinnumannahokkí og vann Stanley-bikarinn.“

Dæmi 2.28

Að mynda neitun skilyrðingar með mögnurum

Skrifaðu neitun hverrar skilyrðingar.

Ef allir kettir mala þá malar köttur maka míns.
Ef mörgæs er fugl þá fljúga sumir fuglar ekki.

Lausn

Neitun skilyrðingarinnar $p \to q$ er yrðingin $p \land ~ q .$ Forliður skilyrðingarinnar er $p$ : „Allir kettir mala“ og bakliður skilyrðingarinnar er $q$ : „Köttur maka míns malar.“ Neitun bakliðarins, $~ q$ , er yrðingin „Köttur maka míns malar ekki.“ Svarið er því $p \land ~ q :$ „Allir kettir mala en köttur maka míns malar ekki.“
Forliðurinn er $p$ : „Mörgæs er fugl“ og bakliður skilyrðingarinnar er $q$ : „Sumir fuglar fljúga ekki.“ Neitun yrðingarinnar $q$ er yrðingin „Allir fuglar fljúga.“ Neitun skilyrðingarinnar er því jafngild $p \land ~ q :$ „Mörgæs er fugl og allir fuglar fljúga.“

Margir eiginleikar talnakerfa og mengja gilda einnig um rökfræðilegar yrðingar. Taflan hér á eftir dregur saman nokkra gagnlegustu eiginleikana við að greina og mynda rökfærslur. Staðfesta má eiginleikana með sanngildistöflu.

Eiginleiki	Samtenging (OG)	Mistenging (EÐA)
Víxlregla	$p \land q \equiv q \land p$	$p \lor q \equiv q \lor p$
Tengiregla	$(p \land q) \land r \equiv p \land (q \land r)$	$(p \lor q) \lor r \equiv p \lor (q \lor r)$
Dreifiregla	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
Reglur De Morgans	$~ (p \land q) \equiv ~ p \lor ~ q$	$~ (p \lor q) \equiv ~ p \land ~ q$
Skilyrðing	$~ (p \to q) \equiv p \land ~ q$	$p \to q \equiv ~ p \lor q$

Dæmi 2.29

Neitun skilyrðingar með samtengingu eða mistengingu

Skrifaðu neitun hverrar skilyrðingar með reglu De Morgans.

Ef mamma þarf að kaupa snakk þá fékk Mike vini í heimsókn og Bob var svangur.
Ef Juan fékk sér pítsu eða Chris fékk sér kjúklingavængi þá horfði pabbi á leikinn.

Lausn

Skilyrðingin hefur formið „ef $p$ , þá $q$ og $r$ “, þar sem $p$ er „Mamma þarf að kaupa snakk“, $q$ er „Mike fékk vini í heimsókn“ og $r$ er „Bob var svangur“. Neitun $p \to (q \land r)$ er $p \land ~ (q \land r) .$ Þegar reglu De Morgans er beitt á yrðinguna $~ (q \land r)$ fæst $~ q \lor ~ r$ og neitunin verður því $p \land (~ q \lor ~ r) .$ Samkvæmt dreifireglu samtengingar yfir mistengingu er þessi yrðing jafngild $(p \land ~ q) \lor (p \land ~ r) .$ Með orðum er yrðingin $(p \land ~ q) \lor (p \land ~ r)$ : „Mamma þarf að kaupa snakk og Mike fékk ekki vini í heimsókn eða mamma þarf að kaupa snakk og Bob var ekki svangur.“
Skilyrðingin hefur formið „ef $p$ eða $q$ , þá $r$ “, þar sem $p$ er „Juan fékk sér pítsu“, $q$ er „Chris fékk sér kjúklingavængi“ og $r$ er „Pabbi horfði á leikinn“. Neitun $(p \lor q) \to r$ er $(p \lor q) \land ~ r .$ Samkvæmt dreifireglu samtengingar yfir mistengingu er yrðingin jafngild $(p \land ~ r) \lor (q \land ~ r) .$ Með orðum er yrðingin $(p \land ~ r) \lor (q \land ~ r)$ : „Juan fékk sér pítsu og pabbi horfði ekki á leikinn, eða Chris fékk sér kjúklingavængi og pabbi horfði ekki á leikinn.“

Reglur De Morgans metnar með sanngildistöflum

Í 1. kafla lærðir þú að hægt er að sanna gildi reglna De Morgans með Venn-myndum. Einnig má nota sanngildistöflur til að sanna að tvær yrðingar séu rökfræðilega jafngildar. Ef tvær yrðingar eru rökfræðilega jafngildar geturðu valið það form sem er skýrara eða sannfærandi þegar þú setur fram rökfærslu.

Í næsta dæmi er gildi annarrar reglu De Morgans sannað með sanngildistöflu. Sömu aðferð má beita á hvaða tvær rökfræðilegar yrðingar sem taldar eru jafngildar. Ef síðasti dálkur sanngildistöflunnar inniheldur aðeins T er tvískilyrðingin sísanna og yrðingarnar tvær því rökfræðilega jafngildar.

Dæmi 2.30

Regla De Morgans um neitun samtengingar staðfest

Gerðu sanngildistöflu til að staðfesta að regla De Morgans um neitun samtengingar, $~ (p \land q) \equiv ~ p \lor ~ q$ , sé gild.

Lausn

Skref 1: Til að staðfesta rökfræðilegt jafngildi þarf fyrst að skipta tákni rökfræðilegs jafngildis, $\equiv$ , út fyrir tákn tvískilyrðingar, $\leftrightarrow$ . Yrðingin $~ (p \land q) \equiv ~ p \lor ~ q$ verður $~ (p \land q) \leftrightarrow ~ p \lor ~ q .$
Skref 2: Gerðu næst sanngildistöflu fyrir yrðinguna. Þar sem grunnyrðingarnar $p$ og $q$ eru tvær hefur taflan fjórar raðir sem ná yfir allar mögulegar niðurstöður. Dálkarnir eru $p$ , $q$ , $~ p$ , $~ q$ , $p \land q,$ $~ (p \land q),$ $~ p \lor ~ q,$ auk tvískilyrðingarinnar $~ (p \land q) \leftrightarrow ~ p \lor ~ q .$

$p$	$q$	$p \land q$	$~ (p \land q)$	$~ p$	$~ q$	$~ p \lor ~ q$	$~ (p \land q) \leftrightarrow (~ p \lor ~ q)$
T	T	T	F	F	F	F	T
T	F	F	T	F	T	T	T
F	T	F	T	T	F	T	T
F	F	F	T	T	T	T	T

Skref 3: Staðfestu að lokum að yrðingin sé gild með því að sýna að hún sé sísanna. Hér inniheldur síðasti dálkurinn aðeins T. Yrðingin er því gild og þar með er regla De Morgans um neitun samtengingar staðfest.

Athugaðu skilning þinn

Regla De Morgans um neitun samtengingar segir að

\text{~}\left( {p \wedge q} \right)

sé rökfræðilega jafngild ___________________.

Regla De Morgans um neitun mistengingar segir að

\text{~}\left( {p \vee q} \right)

sé rökfræðilega jafngild __________________.

Yrðingin

\text{~}\left( {p \to q} \right)

er rökfræðilega jafngild _____________.

\text{~}\left( {\text{~}\left( {p \to q} \right)} \right) \equiv p \to q

, sem merkir að skilyrðingin er rökfræðilega jafngild

\text{~}\left( {p \wedge \text{~}q} \right).

Beittu _______________________ á yrðinguna

\text{~}\left( {p \wedge \text{~}q} \right)

til að sýna að eftirfarandi jafngildi gildi:

p \to q \equiv \text{~}p \vee q.

Æfingar úr hluta 2.6

Í eftirfarandi æfingum skaltu nota reglur De Morgans til að skrifa hverja yrðingu án sviga.

\text{~}(\text{~}p \vee q)

\text{~}\left( {\text{~}p \wedge \text{~}q} \right)

\text{~}(p \wedge \text{~}q)

\text{~}\left( {\text{~}p \vee \text{~}q} \right)

Í eftirfarandi æfingum skaltu nota reglur De Morgans til að skrifa neitun hverrar yrðingar með orðum án orðalagsins „Það er ekki svo að …“

Sergei er hægri kantmaður og Patrick er markvörður.

Mario er smiður eða pípulagningamaður.

Luigi er pípulagningamaður eða hann er ekki tölvuleikjapersóna.

Ralph Macchio lék Karate Kid í upphaflegu kvikmyndinni og karate er ekki aðeins til sjálfsvarnar.

Sumum finnst spergilkál gott en systkinum mínum fannst það ekki gott.

10.

Sumum finnst súkkulaði ekki gott eða öllum finnst pítsa góð.

Í eftirfarandi æfingum skaltu beita reglunni um neitun skilyrðingar til að skrifa hverja yrðingu sem samtengingu eða mistengingu á táknrænu formi.

11.

\text{~}(p \to q)

12.

\text{~}(p \to \text{~}q)

13.

\text{~}(\text{~}p \to q)

14.

\text{~}(\text{~}p \to \text{~}q)

15.

\text{~}(p \wedge q \to \text{~}r)

16.

\text{~}(p \to q \vee r)

17.

\text{~}\left( {p \vee q \to \text{~}r} \right)

18.

\text{~}\left( {p \to q \wedge r} \right)

Í eftirfarandi æfingum skaltu beita reglunni um neitun skilyrðingar til að skrifa neitun hverrar skilyrðingar með orðum.

19.

Ef nemandi fær einkunnina 85 í lokaprófinu fær hann A í námskeiðinu.

20.

Ef einstaklingur stenst ekki ökuprófið fær hann ekki ökuskírteini.

21.

Ef nemandi vinnur ekki heimavinnuna spilar hann ekki tölvuleiki.

22.

Ef farþegi missir af strætisvagninum fer hann ekki í vinnuna í dag.

23.

Ef kappakstursökumaður er stöðvaður fyrir of hraðan akstur kemst hann ekki tímanlega á brautina fyrir keppnina.

24.

Ef René Descartes var heimspekingur þá var hann ekki stærðfræðingur.

25.

Ef George Boole fann upp Boole-algebru og Thomas Edison fann upp ljósaperuna þá er Pac-Man ekki besti tölvuleikur allra tíma.

26.

Ef Jonas Salk bjó til bóluefnið gegn mænusótt þá fékk barn hans bóluefnið eða mænusótt.

27.

Ef Billie Holiday söng blús eða Cyndi Lauper söng um sanna liti þá var John Lennon ekki Bítill.

28.

Ef Percy Jackson er eldingarþjófurinn og Artemis Fowl er spæjari þá mun Artemis Fowl ná Percy Jackson.

29.

Ef allar rokkstjörnur eru karlar þá er Pat Benatar ekki rokkstjarna.

30.

Ef Lady Gaga er rokkstjarna þá eru sumar rokkstjörnur konur.

31.

Ef gult og blátt gefa grænan lit þá eru allir litir fallegir.

32.

Ef hlébarðar eru blettóttir og sebrahestar röndóttir þá eru sum dýr ekki einlit.

Í eftirfarandi æfingum skaltu gera sanngildistöflu til að staðfesta að rökfræðilegi eiginleikinn sé gildur.

33.

p \to q \equiv \text{~}p \vee q

34.

p \to \text{~}q \equiv \text{~}p \vee \text{~}q

35.

\text{~}p \to q \equiv p \vee q

36.

\text{~}\left( {p \to \text{~}q \vee \text{~}r} \right) \equiv p \wedge q \wedge r