22 Rökfræði

2.3 Gerð sanngildistaflna

Ljósmynd sýnir fjórar manneskjur sem vinna saman að því að ljúka púsluspili. — **Mynd 2.8.** Rétt eins og við lausn þrautar þarf forritari að skoða allar mögulegar lausnir til að taka tillit til hverrar hugsanlegrar niðurstöðu. (mynd: aðlögun á verkinu „Deadline Xmas 2010“ eftir Allan Henderson/Flickr, CC BY 2.0)

Námsmarkmið

Eftir að hafa lokið þessum hluta ættir þú að geta:

túlkað neitanir, samtengingar og mistengingar og beitt þeim;
búið til sanngildistöflu með neitunum, samtengingum og mistengingum;
búið til sanngildistöflu fyrir samsetta yrðingu og túlkað gildi hennar.

Kannastu við bókaflokkinn Choose Your Own Adventure eftir Edward Packard? Í þessum leikjabókum getur lesandinn tekið sér hlutverk einnar persónu og tekið ákvarðanir sem hafa áhrif á framvinduna. Val lesandans leiðir þannig til ólíkrar atburðarásar og mismunandi söguloka. Að skrifa tölvuforrit er að nokkru leyti líkt því að skrifa slíka bók. Forritarinn þarf að taka tillit til alls mögulegs inntaks frá notanda og ákveða hvað gerist í hverju tilviki. Síðan þarf hann að skrifa forritið þannig að það taki tillit til allra þessara mögulegu niðurstaðna.

Sanngildistafla er myndrænt verkfæri til að greina öll möguleg sanngildi rökfræðilegra hlutyrðinga og ákvarða gildi yrðingar eða rökfærslu ásamt öllum hugsanlegum niðurstöðum. Raðir töflunnar sýna allar mögulegar niðurstöður fyrir yrðinguna sem tilgreind er efst í hverjum dálki. Ein rökfræðileg yrðing $p$ hefur tvö möguleg sanngildi, satt eða ósatt. Í sanngildistöflum táknar stórt T satt og stórt F ósatt.

Í þessum hluta notar þú þekkingu úr hlutunum Yrðingar og magnarar og Samsettar yrðingar til að greina rökfærslur og ákvarða sanngildi þeirra og gildi. Rökfærsla er gild ef niðurstaðan leiðir af forsendunum, hvort sem forsendurnar eru sannar eða ósannar. Síðan skoðar þú sanngildistöflur neitunar, samtengingar og mistengingar og notar þær til að greina samsettar yrðingar með þessum tengjum.

Neitanir, samtengingar og mistengingar túlkaðar og notaðar

Neitun yrðingar hefur andstætt sanngildi við upphaflegu yrðinguna. Þegar $p$ er sönn er $~ p$ ósönn, en þegar $p$ er ósönn er $~ p$ sönn.

Dæmi 2.12

Sanngildi neitunar fundið

Ákvarðaðu sanngildi neitunar hverrar rökfræðilegrar yrðingar.

$p$ : $3 + 5 = 8.$
$q$ : Allir hestar eru mustanghestar.
$~ r$ : Nýja-Delí er ekki höfuðborg Indlands.

Lausn

$p$ er sönn því 3 + 5 er jafnt og 8. Neitun $p$ , $~ p : 3 + 5 \neq 8$ er því ósönn.
$q$ er ósönn því til eru önnur hestakyn en mustanghestar, til dæmis Clydesdale-hestar og arabískir hestar. Neitun $q$ , $~ q$ er því sönn.
$~ r$ er ósönn því Nýja-Delí er höfuðborg Indlands. Neitun $~ r$ , $r$ er því sönn.

Samtenging er rökfræðileg og-yrðing. Hún er aðeins sönn ef báðar yrðingarnar sem mynda hana eru sannar. Sé að minnsta kosti önnur yrðingin ósönn er og-yrðingin ósönn.

Dæmi 2.13

Sanngildi samtengingar fundið

Miðað við yrðingarnar $p : 4 + 7 = 11,$ $q : 11 - 3 = 7,$ auk $r : 7 \times 11 = 77,$ skaltu ákvarða sanngildi hverrar samtengingar.

$p \land q$
$~ q \land r$
$~ p \land q$

Lausn

$p$ er sönn en $q$ er ósönn. Þar sem önnur yrðingin er sönn en hin ósönn er samtengingin ósönn.
$q$ er ósönn og því er $~ q$ sönn og $r$ er sönn. Báðar yrðingarnar eru því sannar og samtengingin sönn.
$~ p$ er ósönn og $q$ er ósönn. Þar sem báðar yrðingarnar eru ósannar er samtengingin ósönn.

Mistenging er rökfræðileg yrðing með inniföldu eða. Hún er sönn ef önnur eða báðar hlutyrðingarnar eru sannar. Rökfræðileg yrðing með inniföldu eða er aðeins ósönn ef báðar hlutyrðingarnar eru ósannar.

Dæmi 2.14

Sanngildi mistengingar fundið

Miðað við yrðingarnar $p : 4 + 7 = 11,$ $q : 11 - 3 = 7,$ auk $r : 7 \times 11 = 77,$ skaltu ákvarða sanngildi hverrar mistengingar.

$p \lor q$
$~ q \lor r$
$~ p \lor q$

Lausn

$p$ er sönn en $q$ er ósönn. Önnur yrðingin er sönn og hin ósönn, svo mistengingin er sönn.
$q$ er ósönn og því er $~ q$ sönn og $r$ er sönn. Báðar yrðingarnar eru því sannar og mistengingin sönn.
$~ p$ er ósönn og $q$ er ósönn. Þegar allar hlutyrðingarnar eru ósannar er mistengingin ósönn.

Í næsta dæmi notar þú forgangsröð setningatengja til að finna sanngildi samsettra yrðinga með neitunum, samtengingum og mistengingum og skráir niðurstöðurnar í töflu. Þegar sanngildistafla er gerð fyrir rökfærslu þar sem sanngildi hverrar hlutyrðingar er þekkt er notuð tveggja raða tafla. Fyrri röðin inniheldur tákn hlutyrðinganna og seinni röðin sanngildi þeirra. Bættu við eins mörgum dálkum og þarf fyrir gildi hverrar samsettrar yrðingar. Síðasti dálkurinn sýnir heildaryrðinguna og sanngildi hennar.

Dæmi 2.15

Sanngildi samsettra yrðinga fundið

Miðað við yrðingarnar $p : 4 + 7 = 11,$ $q : 11 - 3 = 7,$ auk $r : 7 \times 11 = 77,$ skaltu búa til sanngildistöflu og ákvarða sanngildi hverrar samsettrar yrðingar.

$~ p \land q \lor r$
$~ p \lor q \land r$
$~ (p \land r) \lor q$

Lausn

Skref 1: Yrðingin „ $~ p \land q \lor r$ “ inniheldur þrjár grunnyrðingar, $p$ , $q$ og $r$ og þrjú setningatengi, $~, \land, \lor .$ Þegar svigar sýna forgangsröð tengjanna verður yrðingin $(((~ p) \land q) \lor r) .$
Skref 2: Eftir að forgangsröðinni hefur verið beitt gerum við tveggja raða töflu með dálki fyrir hverja grunnyrðingu og efni hvers svigapars. Svigapörin eru þrjú og því þarf dálk fyrir $~ p,$ innstu svigana, dálk fyrir $(~ p) \land q,$ næstu sviga og $((~ p) \land q) \lor r$ í síðasta dálk fyrir ystu svigana.
Skref 3: Þegar taflan er tilbúin metum við sanngildi yrðinganna frá vinstri til hægri. Sanngildi $p$ , $q$ og $r$ eru satt, ósatt og satt; því setjum við T, F og T í aðra röð töflunnar. Þar sem $p$ er sönn er $~ p$ ósönn.
Skref 4: Næst er metið $~ p \land q$ samkvæmt töflunni: $~ p$ er ósönn og $q$ er einnig ósönn, svo $~ p \land q$ er ósönn, því samtenging er aðeins sönn þegar báðar hlutyrðingar hennar eru sannar. Settu F undir fyrirsögnina í töflunni.
Skref 5: Að lokum sýnir taflan að $(~ p \land q)$ er ósönn en $r$ er sönn, svo heildaryrðingin $(~ p \land q) \lor r$ er ósatt eða satt, það er satt, því mistenging er sönn þegar að minnsta kosti önnur hlutyrðingin er sönn. Settu T í síðasta dálkinn. Heildaryrðingin $~ p \land q \lor r$ er sönn.
$p$ $q$ $r$ $~ p$ $(~ p) \land q$ $((~ p) \land q) \lor r$

T F T F F T
Skref 1: Beitum forgangsröð setningatengja á upphaflegu samsettu yrðinguna $~ p \lor q \land r$ og fáum $(((~ p) \lor q) \land r) .$
Skref 2: Taflan þarf dálka fyrir $p, q, r, ~ p, (~ p) \lor q,$ auk $((~ p) \lor q) \land r .$
Skref 3: Sanngildi $p$ , $q$ , $r$ og $~ p$ eru þau sömu og í lið 1.
Skref 4: Næst er $~ p \lor q$ ósatt eða ósatt, sem er ósatt. Settu F undir yrðinguna. Mistenging er aðeins ósönn í þessu tilviki.
Skref 5: Að lokum mynda $~ p \lor q$ og $r$ samtengingu yrðinganna $~ p \lor q$ og $r$ , svo gildin eru ósatt og satt og samtengingin því ósönn. Mundu að og-yrðing er aðeins sönn þegar báðar yrðingarnar sem mynda hana eru sannar. Heildaryrðingin $~ p \lor q \land r$ er ósönn.

$p$ $q$ $r$ $~ p$ $(~ p) \lor q$ $((~ p) \lor q) \land r$

T F T F F F
Skref 1: Beitum forgangsröð setningatengja á upphaflegu yrðinguna og fáum: $((~ (p \land r)) \lor q)$ .
Skref 2: Taflan þarf eftirfarandi dálka: $p, q, r, p \land r, ~ (p \land r),$ auk $~ (p \land r) \lor q .$
Skref 3: Sanngildi $p$ , $q$ og $r$ eru þau sömu og í dæmum 1 og 2.
Skref 4: Taflan sýnir að $p \land r$ er satt og satt, það er satt. Neitun samtengingar $p$ og $r$ er ósönn, enda hefur neitun alltaf andstætt sanngildi við upphaflegu yrðinguna.
Skref 5: Að lokum er $~ (p \land r) \lor q$ mistenging $~ (p \land r)$ og $q$ , svo gildin eru ósatt eða ósatt og heildaryrðingin er ósönn.
$p$ $q$ $r$ $p \land r$ $~ (p \land r)$ $~ (p \land r) \lor q$

T F T T F F

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

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

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

Sanngildistöflur fyrir allar hugsanlegar niðurstöður

Mundu úr hlutanum Yrðingar og magnarar að neitun hefur alltaf andstætt sanngildi við upphaflegu yrðinguna. Sé yrðingin $p$ ósönn er neitun hennar $~ p$ sönn en sé yrðingin $p$ sönn er neitun hennar $~ p$ ósönn. Til að gera sanngildistöflu fyrir neitun yrðingarinnar $p$ skaltu bæta við dálki með fyrirsögninni $~ p$ . Skráðu í hverja röð sanngildi sem er andstætt samsvarandi gildi í dálki $p$ , eins og taflan sýnir.

Neitun
$p$	$~ p$
T	F
F	T

Samtengingar og mistengingar eru samsettar yrðingar sem myndast þegar tvær rökfræðilegar yrðingar eru tengdar með setningatengjunum „og“ og „eða“. Hvaða áhrif hefur það á fjölda mögulegra niðurstaðna og þar með fjölda raða í sanngildistöflunni? Margföldunarlögmálið, einnig kallað grundvallartalningarreglan, segir að fjöldi leiða til að velja eitt stak úr safni með $n$ stökum og annað stak úr safni með $m$ stökum sé margfeldi $m$ og $n$ . Þar sem yrðingarnar $p$ og $q$ hafa hvor um sig tvö möguleg sanngildi, satt eða ósatt, leiðir af margföldunarlögmálinu að mögulegu niðurstöðurnar eru $2 \times 2 = 4$ : {TT, TF, FT, FF}.

Trjámyndin og taflan á mynd 2.9 sýna fjórar hugsanlegar niðurstöður fyrir yrðingarnar $p$ og $q$ .

Trjámynd sýnir tvö möguleg sanngildi yrðingarinnar p, satt og ósatt. Frá hvorri grein liggja tvær greinar fyrir q, satt og ósatt. Taflan við hlið trésins sýnir fjórar samsetningar sanngilda p og q: TT, TF, FT og FF.

Samtenging er rökfræðileg og-yrðing. Hún er aðeins sönn ef báðar yrðingarnar sem mynda hana eru sannar. Sé að minnsta kosti önnur yrðingin ósönn er og-yrðingin ósönn.

Mistenging er rökfræðileg yrðing með inniföldu eða. Hún er sönn ef önnur eða báðar yrðingarnar eru sannar. Rökfræðileg yrðing með inniföldu eða er aðeins ósönn ef báðar hlutyrðingarnar eru ósannar.

Samtenging (OG)			Mistenging (EÐA)
$p$	$q$	$p \land q$	$p$	$q$	$p \lor q$
T	T	T	T	T	T
T	F	F	T	F	T
F	T	F	F	T	T
F	F	F	F	F	F

Dæmi 2.16

Sanngildistöflur gerðar til að greina samsettar yrðingar

Búðu til sanngildistöflu til að greina allar hugsanlegar niðurstöður hverrar eftirfarandi rökfærslu.

$p \lor ~ q$
$~ (p \land q)$
$(p \lor ~ q) \land r$

Lausn

Skref 1: Þar sem grunnyrðingarnar eru tvær, $p$ og $q$ , sem hafa hvor um sig tvö möguleg sanngildi, þarf taflan $2 (2) = 4$ raðir fyrir allar niðurstöður: TT, TF, FT og FF. Dálkarnir eru fyrir $p$ , $q$ , $~ q$ auk $p \lor ~ q .$
Skref 2: Hvert gildi í dálki $~ q$ er andstætt samsvarandi gildi í dálki $q$ : F, T, F og T.
Skref 3: Til að ljúka síðasta dálkinum skaltu meta hvert gildi í dálki $p$ með samsvarandi gildi í dálki $~ q$ með setningatenginu eða.
$p$ $q$ $~ q$ $p \lor ~ q$

T T F T

T F T T

F T F F

F F T T
Skref 1: Dálkarnir eru fyrir $p$ , $q$ , $p \land q,$ auk $~ (p \land q)$ . Þar sem grunnyrðingarnar eru tvær, $p$ og $q$ , þarf taflan fjórar raðir fyrir allar niðurstöður.
Skref 2: Dálkurinn $p \land q$ er fylltur með því að meta samsvarandi gildi úr dálkunum $p$ og $q$ með og-setningatenginu.
Skref 3: Síðasti dálkurinn, $~ (p \land q)$ , er neitun $p \land q$ -dálksins.

$p$ $q$ $p \land q$ $~ (p \land q)$

T T T F

T F F T

F T F T

F F F T
Skref 1: Yrðingin hefur þrjár grunnyrðingar, $p$ , $q$ og $r$ . Hver hefur tvö möguleg sanngildi, satt eða ósatt og margföldunarlögmálið gefur $2 (2) (2) = 8$ niðurstöður. Taflan þarf því átta raðir. Helmingur þeirra hefur satt fyrir fyrstu yrðinguna og helmingur ósatt.
Skref 2: Fyrsti dálkurinn fyrir $p$ hefur fjögur T og síðan fjögur F. Í öðrum dálki fyrir $q$ , þegar $p$ er sönn, er helmingur niðurstaðna fyrir $q$ sannur og hinn helmingurinn ósannur. Sama mynstur endurtekur sig þegar $p$ er ósönn. Dálkur $q$ hefur því TT, FF, TT, FF.
Skref 3: Dálkur þriðju yrðingarinnar, $r$ , skiptist á T og F. Eftir grunnyrðingarnar þrjár þarf dálka fyrir $~ q$ , $p \lor ~ q$ og $(p \lor ~ q) \land r$ .
Skref 4: Dálkur neitunar $q$ , $~ q$ , hefur andstætt sanngildi við hvert gildi í dálki $q$ .
Skref 5: Næst eru sanngildin fyllt inn í dálk yrðingarinnar $p \lor ~ q .$ Eða-yrðingin er sönn ef að minnsta kosti önnur yrðinganna $p$ eða $~ q$ er sönn, annars er hún ósönn.
Skref 6: Fylltu að lokum dálk samtengingarinnar $(p \lor ~ q) \land r$ . Til að meta hana skaltu tengja dálk $p \lor ~ q$ og dálk $r$ með setningatenginu og. Mundu að og-yrðing er aðeins sönn þegar bæði gildi eru sönn; annars er hún ósönn. Heildarsanngildistaflan er:
$p$ $q$ $r$ $~ q$ $p \lor ~ q$ $(p \lor ~ q) \land r$

T T T F T T

T T F F T F

T F T T T T

T F F T T F

F T T F F F

F T F F F F

F F T T T T

F F F T T F

$p$	$q$	$~ q$	$p \lor ~ q$
T	T	F	T
T	F	T	T
F	T	F	F
F	F	T	T

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

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

Gildi samsettrar yrðingar ákvarðað með sanngildistöflu

Rökfræðileg yrðing er gild ef hún er alltaf sönn, óháð sanngildi hluta hennar. Til að prófa gildi samsettrar yrðingar er gerð sanngildistafla fyrir allar hugsanlegar niðurstöður. Ef síðasti dálkurinn, sem sýnir heildaryrðinguna, inniheldur aðeins sönn gildi er yrðingin gild.

Dæmi 2.17

Gildi samsettra yrðinga ákvarðað

Búðu til sanngildistöflu og ákvarðaðu gildi hverrar eftirfarandi yrðingar.

$~ p \land q$
$~ (p \land ~ p)$

Lausn

Skref 1: Þar sem yrðingarnar eru tvær, $p$ og $q$ , sem hafa hvor um sig tvö möguleg sanngildi, verða $2 (2) = 4$ raðir í töflunni: TT, TF, FT og FF.
Skref 2: Dálkarnir eru fyrir $p$ , $q$ , $~ p$ og $~ p \land q .$ Hvert gildi í dálki $~ p$ er andstætt samsvarandi gildi í dálki $p$ .
Skref 3: Til að ljúka síðasta dálkinum skaltu meta hvert gildi í dálki $~ p$ með samsvarandi gildi í dálki $q$ með setningatenginu og . Síðasti dálkurinn inniheldur að minnsta kosti eitt ósatt gildi og yrðingin $~ p \land q$ er því ekki gild.
$p$ $q$ $~ p$ $~ p \land q$

T T F F

T F F F

F T T T

F F T F
Skref 1: Þar sem yrðingin $~ (p \land ~ p)$ hefur aðeins eina grunnyrðingu hefur sanngildistaflan aðeins tvær raðir. Yrðingin $p$ getur verið sönn eða ósönn.
Skref 2: Dálkarnir eru fyrir $p$ , $~ p$ , $p \land ~ p,$ auk $~ (p \land ~ p) .$ Reiknaðu gildin í dálkinum $p \land ~ p$ með setningatenginu og, því táknið $\land$ táknar samtengingu eða rökfræðilega og-yrðingu. Satt og ósatt er ósatt og ósatt og satt er einnig ósatt.
Skref 3: Síðasti dálkurinn er neitun hvers gildis í þriðja dálki. Bæði eru ósönn og neitun þeirra því sönn. Þar sem öll gildi síðasta dálksins eru sönn er yrðingin $~ (p \land ~ p)$ gild.
$p$ $~ p$ $p \land ~ p$ $~ (p \land ~ p)$

T F F T

F T F T

$p$	$q$	$~ p$	$~ p \land q$
T	T	F	F
T	F	F	F
F	T	T	T
F	F	T	F

$p$	$~ p$	$p \land ~ p$	$~ (p \land ~ p)$
T	F	F	T
F	T	F	T

Athugaðu skilning þinn

Rökfærsla er _____ ef niðurstaða hennar leiðir af forsendunum.

Rökfræðileg yrðing er gild ef hún er alltaf _____.

_____ _____ er verkfæri til að greina allar hugsanlegar niðurstöður rökfræðilegrar yrðingar.

Sanngildistafla samtengingarinnar

p \wedge q

hefur _____ raðir sanngilda.

Sanngildistafla neitunar rökfræðilegrar yrðingar $\text{~}p$ hefur _____ raðir sanngilda.

Æfingar úr hluta 2.3

Finndu sanngildi hverrar eftirfarandi yrðingar.

p

7 \times 3 = 21

. Hvert er sanngildi

\text~p

q

: Sólin snýst um jörðina. Hvert er sanngildi

\text~q

\text~r

: Þyngdarhröðunin er

9,81\,

m/s². Hvert er sanngildi

r

s

: Dan Brown er ekki höfundur bókarinnar Da Vinci lykillinn. Hvert er sanngildi

\text~{\text(\text{~}s)}

t

: Spergilkál er grænmeti. Hvert er sanngildi

\text~{\text(\text{~}t)}

Í eftirfarandi æfingum eru gefnar yrðingarnar p: „1 + 2 = 3“, q: „Fimm er slétt tala“ og r: „Sjö er frumtala“. Finndu sanngildi hverrar eftirfarandi yrðingar.

\text~q

p \wedge q

p \vee q

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

10.

p \wedge \text{~}q

11.

p \wedge r

12.

q \wedge r

13.

q \wedge \text{~}r

14.

q \vee \text{~}r

15.

\text{~}(p \wedge r)

16.

p \vee q \wedge r

17.

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

18.

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

19.

q \vee r \vee p

20.

\text{~}q \wedge r \wedge p

Ljúktu sanngildistöflunni í eftirfarandi æfingum og ákvarðaðu sanngildi yrðingarinnar í síðasta dálki.

21.

$p$	$q$	$r$	$\text{~}p$	$\text{~}p \vee q$	$(\text{~}p \vee q) \wedge r$
T	T	T

22.

$p$	$q$	$r$	$\text{~}p$	$\text{~}p \wedge q$	$(\text{~}p \wedge q) \wedge r$
F	T	F

23.

$p$	$q$	$r$	$\text{~}p$	$\text{~}r$	$\text{~}p \wedge q$	$(\text{~}p \wedge q)\vee \text{~}r$
F	F	F

24.

$p$	$q$	$r$	$\text{~}p$	$\text{~}r$	$\text{~}p \vee q$	$(\text{~}p \vee q) \vee \text{~}r$
F	F	F

Í eftirfarandi æfingum eru gefnar yrðingarnar p: „Allir þríhyrningar hafa þrjár hliðar“, q: „Sumir rétthyrningar eru ekki ferningar“ og r: „Fimmhyrningur hefur átta hliðar“. Búðu til sanngildistöflu og ákvarðaðu sanngildi hverrar samsettrar yrðingar.

25.

\text{~}r \wedge q \wedge p

26.

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

27.

\text{~}p \vee q \wedge r

28.

\text{~}p \vee \text{~}q \vee r

Búðu til sanngildistöflu fyrir allar hugsanlegar niðurstöður hverrar eftirfarandi rökfærslu.

29.

$\text{~}q \wedge q$

30.

$\text{~}p \vee \text{~}q$

31.

$\text{~}p \wedge \text{~}q$

32.

$p \wedge q \vee r$

Búðu til sanngildistöflu og ákvarðaðu gildi hverrar eftirfarandi yrðingar.

33.

$\text{~}q \vee q$

34.

$p \wedge \text{~}q$

35.

$p \wedge q \vee \text{~}p$

36.

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