Teh­tä­vä:
Sie­ven­tä­mi­nen pro­po­si­tio­lo­gii­kas­sa

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Täs­sä teh­tä­väs­sä har­joi­tel­laan li­sää pro­po­si­tio­lo­gii­kan ope­raat­to­rei­den käyt­töä ja tu­tus­tu­taan kaa­vo­jen sie­ven­tä­mi­seen yk­sin­ker­tai­sem­paan muo­toon. Teh­tä­väs­sä käy­te­tään klas­sis­ta kak­si­ar­vo­lo­giik­kaa, eli kol­mas to­tuus­ar­vo U ei ole käy­tös­sä.

Hiu­kan to­tuus­tau­luis­ta

Yleen­sä lo­gii­kan al­keis­kurs­seil­la on to­tuus­tau­lu­teh­tä­viä. Mi­nus­ta to­tuus­tau­lut ovat tyl­sä ja vir­he­al­tis tek­niik­ka, jo­ten täl­lä vep­pi­si­vul­la on to­tuus­tau­lun laa­ti­mis­teh­tä­viä vain tä­mä yk­si, ja se­kin pie­ni. Va­lit­se ne ja vain ne koh­dat joi­hin tu­lee T.

Täy­den­nä kaa­van (P ∨ ¬Q ∨ R) ∧ (¬P ∨ ¬Q ∧ R) to­tuus­tau­lu.

 P  Q  R   P ∨ ¬Q ∨ R   ¬P ∨ ¬Q ∧ R  ko­ko kaa­va
FFF
FFT
FTF
FTT
TFF
TFT
TTF
TTT
tai

Toi­sin­päin on vä­hem­män tyl­sää, mut­ta sin­ne pääs­täk­sem­me aloi­tam­me tyl­säs­ti. Mi­ten voi hel­pos­ti muo­dos­taa kaa­van, jo­ka tuot­taa yh­del­lä to­tuus­tau­lun ri­vil­lä T ja muil­la ri­veil­lä F? Vas­tausKäy­dään lä­pi kaik­ki pro­po­si­tiot X ja muo­dos­te­taan jo­kai­ses­ta niis­tä osa­kaa­va. Osa­kaa­va on ¬X, jos ko. ri­vil­lä X on F, ja osa­kaa­va on X, jos ko. ri­vil­lä X on T. Osa­kaa­vat yh­dis­te­tään ope­raat­to­ril­la ∧. Mi­ten voi hel­pos­ti muo­dos­taa (mah­dol­li­ses­ti pit­kän) kaa­van, jo­ka tuot­taa joil­la­kin to­tuus­tau­lun ri­veil­lä T ja muil­la ri­veil­lä F? Vas­tausMuo­dos­te­taan jo­kai­ses­ta T-ri­vis­tä kaa­va edel­lä ku­va­tul­la ta­val­la, ja yh­dis­te­tään ne ope­raat­to­ril­la ∨.

Muo­dos­ta edel­lä ku­va­tul­la ta­val­la al­la ole­vaa to­tuus­tau­lua vas­taa­va kaa­va.
tai
 P  Q  R 
FFF F
FFT F
FTF T
FTT F
TFF F
TFT T
TTF F
TTT F

Toi­vot­ta­vas­ti olet hok­san­nut, et­tä jos T-ri­ve­jä on pal­jon, niin edel­lä ku­vat­tu ta­pa tuot­taa pit­kiä kaa­vo­ja! Toi­si­naan on mah­dol­lis­ta löy­tää pal­jon ly­hyem­pi kaa­va.

Kir­joi­ta to­tuus­tau­lua vas­taa­vat kaa­vat. Mel­ko köm­pe­löt­kin kaa­vat hy­väk­sy­tään, mut­ta to­del­li­set tai­tu­rit saa­vat ai­kaan mel­ko ly­hyet kaa­vat. Voit vaik­ka ke­hit­tää jon­kin kel­paa­van kaa­van, jät­tää sen ylä­ri­vil­le, li­sä­tä pe­rään <=> ja ala­ri­vil­lä ke­hit­tää mah­dol­li­sim­man ly­hyen kel­paa­van kaa­van. Vih­je ψMuo­dos­ta ¬ψ ja täy­den­nä si­tä.

 P  Q  R   φ  ψ  χ 
FFF FTF
FFT FTF
FTF FTT
FTT FTF
TFF TTT
TFT FFT
TTF TTF
TTT FTT
φ ⇔ tai
ψ ⇔ tai
χ ⇔ tai

Jat­koa var­ten huo­maa, et­tä edel­lä kaa­van φ sa­rak­kees­sa on 2 ja kaa­van ψ sa­rak­kees­sa 7 T:tä.

Edel­lä ku­vail­tiin kaa­va, jo­ka tuot­taa yh­del­lä to­tuus­tau­lun ri­vil­lä T ja muil­la F. Seu­raa­va ta­voi­te on hah­mot­taa, mi­tä saa­daan muo­dos­ta­mal­la sa­mal­la pe­riaat­teel­la ly­hyem­pi kaa­va, jos­sa vain osa pro­po­si­tiois­ta on mu­ka­na. Jos pro­po­si­tiot ovat p, q, r ja s, niin sel­lai­nen kaa­va nou­dat­taa kie­li­op­pia

K ::= L | K ∧ L
L ::= A | ¬A
A ::= p | q | r | s

Ku­kin pro­po­si­tiois­ta p, q, r ja s esiin­tyy kaa­vas­sa enin­tään ker­ran. Kaa­va voi siis ol­la esi­mer­kik­si q∧¬r∧¬p, mut­ta ei voi ol­la ¬s∧s. Kuin­ka mon­ta T on kaa­van sa­rak­kees­sa kaa­van to­tuus­tau­lus­sa, jos kaa­vas­sa on kaik­kiaan il­moi­tet­tu mää­rä pro­po­si­tioi­ta?

1 tai
2 tai
3 tai
4 tai

Jos eri pro­po­si­tioi­ta on kaik­kiaan n kap­pa­let­ta ja kaa­vas­sa esiin­tyy i pro­po­si­tio­ta, niin kuin­ka mon­ta T on kaa­van sa­rak­kees­sa? (Edel­lä oli n = 4 ja i vaih­te­li 1, 2, 3 ja 4.)
tai

Täl­lä ta­val­la voi­daan poi­mia mon­ta T-ri­viä ly­hyel­lä kaa­val­la, mut­ta vain jos ne si­jait­se­vat to­tuus­tau­lus­sa so­pi­vas­ti toi­siin­sa näh­den.

Suu­ruus­jär­jes­tys­kaa­vo­ja

So­vel­luk­sis­sa pro­po­si­tioi­na on usein jo­tain konk­reet­tis­ta. Har­joit­te­lem­me si­tä het­ken ai­kaa. (Muo­dol­li­ses­ti tä­mä ei ole pro­po­si­tio­lo­giik­kaa vaan kvant­to­ri­ton­ta pre­di­kaat­ti­lo­giik­kaa.)

Var­mis­tam­me en­sin, et­tä muu­ta­ma tär­keä pe­rus­kaa­va on tut­tu.

¬(x < y) ⇔ tai
x < y ∨ x = y ⇔ tai
x < y ∧ x = y ⇔ tai
x ≤ y ∨ x = y ⇔ tai
x ≤ y ∧ x = y ⇔ tai
x < y ∨ x > y ⇔ tai
x < y ∧ x > y ⇔ tai
x ≤ y ∨ x ≥ y ⇔ tai
x ≤ y ∧ x ≥ y ⇔ tai

Sit­ten teem­me vai­heit­tain kaa­vo­ja ku­vis­ta.

[suorakaide (-1,1)(3,4)] Kir­joi­ta muut­tu­jaa x kos­ke­va eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen va­sen­ta ja oi­keaa reu­naa se­kä nii­den vä­liin jää­vää aluet­ta. Älä vie­lä vä­li­tä y-koor­di­naa­teis­ta.
tai

Kir­joi­ta muut­tu­jaa y kos­ke­va eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen ylä- ja ala­reu­naa se­kä nii­den vä­liin jää­vää aluet­ta. Älä vä­li­tä x-koor­di­naa­teis­ta.
tai

Kir­joi­ta eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen peit­tä­mää aluet­ta reu­nat mu­kaan lu­kien.
tai

Kir­joi­ta eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen peit­tä­mää aluet­ta va­sen ja ylä­reu­na mu­kaan lu­kien mut­ta oi­kea ja ala­reu­na pois lu­kien. Nur­kis­ta vain va­sen ylä­nurk­ka on mu­ka­na.
tai

Kir­joi­ta eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen nurk­kia (siis nel­jää eril­lis­tä pis­tet­tä).

tai

Kir­joi­ta eh­to, jo­ka vas­taa ohei­sen suo­ra­kai­teen reu­naa (siis va­sen reu­na, oi­kea reu­na, ylä­reu­na ja ala­reu­na, mut­ta ei si­säl­le jää­viä pis­tei­tä).

tai

[kolmio (-2,4)(2,0)(3,3)] Kir­joi­ta sen suo­ran yh­tä­lö, jo­ka kul­kee pis­teen (0,2) kaut­ta ja täs­mää ohei­sen kol­mion yh­teen si­vuun.
tai

Kir­joi­ta eh­to, jo­ka täs­mää nii­hin pis­tei­siin, jot­ka jää­vät äs­kei­sen suo­ran ylä­puo­lel­le.
tai

Kir­joi­ta ohei­sen kol­mion oi­kean­puo­leis­ta reu­naa vas­taa­van suo­ran yh­tä­lö.
tai

Kir­joi­ta ohei­sen kol­mion ylä­reu­naa vas­taa­van suo­ran yh­tä­lö.
tai

Kir­joi­ta ohei­sen kol­mion pis­tei­tä reu­nat pois lu­kien vas­taa­va eh­to.
tai

Sie­ven­tä­mi­nen ta­pauk­siin ja­ka­mal­la

Pro­po­si­tio­lo­gii­kas­sa voi sie­ven­tää ja pää­tel­lä mo­nel­la eri ta­val­la. Yk­si help­po te­ho­kas ta­pa, jos­ta voi jo­pa teh­dä Math­Checkil­lä tar­kas­tet­ta­via teh­tä­vä­sar­jo­ja, on va­li­ta jo­kin pro­po­si­tio, si­joit­taa sen ar­vok­si F ja sie­ven­tää, si­joit­taa sen ar­vok­si T ja sie­ven­tää, ja yh­dis­tää tu­lok­set. To­dis­tam­me täl­lä ta­val­la, et­tä

¬(P ↔ Q) ⇔ P ↔ ¬Q .

Tar­vit­sem­me seu­raa­vat apu­tu­lok­set.

Sit­ten to­dis­tam­me ta­voit­teem­me vai­heit­tain.

Seu­raa­vak­si to­dis­tam­me, et­tä ↔ on lii­tän­näi­nen eli (P ↔ Q) ↔ R ⇔ P ↔ (Q ↔ R). Tar­vit­sem­me seu­raa­van apu­tu­lok­sen. Vih­jeTie­to­ko­ne­pe­leis­sä­kin ai­kai­sem­min sa­man pe­lin ai­ka­na koh­da­tuil­la asioil­la saat­taa ol­la käyt­töä myö­hem­min.

Sit­ten to­dis­tam­me ta­voit­teem­me vai­heit­tain.

Seu­raa­vak­si ta­voit­tee­na on so­vel­taa tä­tä kei­noa it­se­näi­sem­min. Si­tä var­ten on hyö­dyk­si pa­laut­taa mie­leen, mi­tä P → Q tuot­taa sil­loin kun P tai Q on to­tuus­ar­vo­va­kio. Vih­je: P → Q voi­daan il­mais­ta il­man sym­bo­lia → täl­lä¬P ∨ Q ta­val­la.
F → Q ⇔
T → Q ⇔
P → F ⇔
P → T ⇔
tai

Pro­po­si­tio­naa­li­nen imp­li­kaa­tio → ei ole lii­tän­näi­nen, eli (P → Q) → R ⇔ P → (Q → R) ei pä­de. Va­lit­se al­ta pro­po­si­tio, si­joi­ta sen pai­kal­le vuo­ron­pe­rään F ja T, sie­ven­nä va­sen puo­li ja sie­ven­nä oi­kea puo­li. Va­lit­se alem­pa­na ole­vas­ta ruu­du­kos­ta ne pro­po­si­tion ja to­tuus­ar­von yh­dis­tel­mät, joil­la va­sen ja oi­kea puo­li sie­ve­ne­vät sa­moik­si.
P Q R
F T
(P → Q) → R ⇔ P → (Q → R) ⇔
tai

PQR
F
T
tai

Pro­po­si­tioil­la P, Q ja R on yh­teen­sä to­tuus­ar­vo­yh­dis­tel­mää. Ta­pauk­set, jois­sa edel­lä va­sen ja oi­kea puo­li sie­ve­ni­vät sa­moik­si, kat­ta­vat niis­tä . Tut­ki­mat­ta on enää to­tuus­ar­vo­yh­dis­tel­mää. Ne ovat nä­mäP ⇔ F, R ⇔ F ja Q on kum­pi ta­han­sa..
tai

Si­joit­ta­mal­la tut­ki­mat­ta ole­vis­sa ta­pauk­sis­sa pro­po­si­tioil­le edel­lä mai­ni­tut to­tuus­ar­vot, (P → Q) → R sie­ve­nee muo­toon ja P → (Q → R) sie­ve­nee muo­toon .
tai

Muo­dos­ta mah­dol­li­sim­man ly­hyt kaa­va, jo­ka on to­si täs­mäl­leen sil­loin, kun (P → Q) → R ⇔ P → (Q → R) pä­tee.
tai

Mui­ta sie­ven­nys­kei­no­ja

Pro­po­si­tio­lo­gii­kas­sa voi pää­tel­lä myös kaa­vo­ja käyt­tä­mäl­lä sa­maan ta­paan kuin arit­me­tii­kas­sa. Esi­merk­ki­nä to­dis­tam­me, et­tä P → Q ⇔ ¬Q → ¬P. En­sin so­vel­la imp­li­kaa­tion eli­mi­noin­tia, sit­ten kak­sois­ne­gaa­tion eli­mi­noin­tia, ja lo­puk­si imp­li­kaa­tion mää­ri­tel­mää.




tai

So­vel­la en­sin imp­li­kaa­tion eli­mi­noin­tia, sit­ten de Mor­ga­nin la­kia, ja kek­si lop­pu it­se!




tai

Toi­si­naan sie­ven­tä­mi­ses­sä voi hyö­dyn­tää si­tä, et­tä jos dis­junk­tion jo­kin osa to­teu­tuu, mui­den osien to­tuus­ar­voil­la ei ole vä­liä.
Jos P ⇔ T, niin P ∨ ¬P ∧ Q ⇔ , ja
jos P ⇔ F, niin P ∨ ¬P ∧ Q ⇔ .
Sik­si P ∨ ¬P ∧ Q ⇔
tai

Sie­ven­nä P ∧ (¬P ∨ Q) ⇔
tai

Sie­ven­nä (P ∧ Q ∨ ¬Q ∧ R) ∧ (P ∨ ¬R) ⇔

tai vih­jeTä­hän pu­ree hy­vin ja­ko ta­pauk­siin P ⇔ F ja P ⇔ T.

Sie­ven­tä­mi­nen mil­lä vaan kei­nol­la

Sie­ven­nä seu­raa­vat lau­sek­keet mah­dol­li­sim­man yk­sin­ker­tai­seen muo­toon, jos­sa ei esiin­ny → ei­kä ↔. Va­lit­se it­se kei­not, joi­ta käy­tät. Yh­des­sä koh­das­sa on kak­si komp­lek­si­suus­ra­jaa. Väl­jem­män ra­jan saa­vut­ta­mi­nen riit­tää, mut­ta on hie­noa, jos saa­vu­tat tiu­kem­man­kin.

P → ¬P ⇔

tai

P ↔ Q ↔ P ⇔

tai

(P → Q) ∧ ¬(Q → P) ⇔

tai

P ∧ ¬Q ∨ Q ∧ R ∧ ¬P ∨ Q ∧ P ⇔ Vih­jeMi­hin muo­toon kaa­va sie­ve­nee, jos P ⇔ F? En­tä jos P ⇔ T?

tai

(P → Q) ∧ (Q → R) ∧ (R → P) ⇔ Vih­je 1Kaa­va koos­tuu kol­mes­ta osas­ta. Mil­lä osat on yh­dis­tet­ty? Mi­kä kun­kin osan to­tuus­ar­von tu­lee ol­la, jot­ta ko­ko kaa­van to­tuus­ar­vo oli­si T? Vih­je 2Osat on yh­dis­tet­ty ∧:lla ja kun­kin osan to­tuus­ar­von tu­lee ol­la T. Vih­je 3Jos si­joi­te­taan P ⇔ T, niin mi­kä Q:n to­tuus­ar­von tu­lee ol­la, jot­ta osuu­den P → Q to­tuus­ar­vo oli­si T? Vih­je 4Jos si­joi­te­taan P ⇔ F, niin mi­kä R:n to­tuus­ar­von tu­lee ol­la, jot­ta osuu­den R → P to­tuus­ar­vo oli­si T?
tai

y + 2x ≤ 11 ∧ ¬(y < 3 ∨ y − 6 ≥ 3x) ∨ y − 1 > x − 2 ⇔ Vih­je 1Piir­rä ku­va. Vih­je 2Ole tark­ka­na sen suh­teen, ovat­ko reu­na­ta­pauk­set mu­ka­na vai ul­ko­na.

tai

Loo­gi­ses­ti aja­tel­tu!