Excerpt
66 : pa A AA, P> A,B6,4, i F> A,, ALB, A, S Žiirgės į D/5K/BSB-—21 A. (> ) L AAA. Riza £ E AAB: Az (> ) ; F> A, AXB, AZ AMARA o) [L „AVB, A iu? A,,A (> 1) EB AIA A i (B =iAj A,A: (> =) $15. Rezoliucijų metodas Daugelio įdomių uždavinių sprendim.s ( tarp …
Excerpt
67 moje. i o “ Vietoje įprastos formos 4 EO E elementarios Ši aiūskėi jus) naudosimės šekių "konjunktyvios nermalinės for- | mos ušrašymu EL, aka Er aa priimta rezoliucijų metode vadinti diajunktais, o į juos. įei- nančius loginius kintamuosius arba jų …
Excerpt
68 2, [aPY4. Ipv? C,: Pvą Gi IE VT Nė viename iš disjunktų nėra priešingų literų. Šiems disjunktams negalime taikyti rezoliucijos taisyklės. :Simboliu Ol žymėsime tuščią disjunktą. 3. p.Pp.pva) Er B) Cc. P Cs: pvą (, ir C, rezolventė yra (0. 19.TEOREMA. …
Excerpt
69 Pavyzdys. n S 2 5= fipvą 14,3 a „1P.P,8 yra tuščio disjunkto įrodymas, nea 1pVą 65,1465,9P yra IPV4,,14 rezolventė, pe5, O yra IP,P. rezolventė. Iš 19 teoremos išplaukia, kad, jei a įrodomas iš 6 dis- junkių aibės £C,,..,C +) „ tai formulė ŽU neįvyk.- …
Excerpt
70 4) disjunktai, į kuriuos įeina.ir R, ir Pra Ek B E Jei pirmas poaibia tuščias (panašiai nagrinėjamas ir at- vejis, kai antras poaibis tuščias), tai formulė ž mų yra neįvykdoma 1 ją įeina ne daugiau kaip Ą i 10- ginių kintamųjų. Jai galioja indukcinė …
Excerpt
> » i | : - š | Kaga “ $0,1,..-,R-1]) vadinsime daugisreilkšmės logikos arba k-reikš- mės logikos funkcijomis. Atveju, kai k = 2, gauname Zunkci- jas, kurias nagrinėjome ankstesniuose paragrafuose. Daugelis rezultatų galioja ir daugiareikšmei logikai, …
Excerpt
72 5,6 funkcijos yra konjunkcijos spibendrinimas. 7) max (x,*;) - disjunkcijos apibendrinimas. 8) X;+x, (mod K). : Kaip matome,, dvireikšmės logikos funkcijos turi po ke- lis analogus daugiereikšmėje logikoje. Punkcijų aibė [16,6 3 vadinama pilna, jei bet …
Excerpt
1 galime išreikšti duotos aibės funkcijų superpozicija. To ir pakaks, kad galėtume tvirtinti, kad duota aibė pilna. Jix) = 11 max Įx+4) Ji r LLk-14 ga k 7 Iš tikrųjų, jei x=č ., tai kairė pusė lygi ė- 1 "dešinė ; š * max [4+4) = 1£(k-21.=> k-1 (vk EE i 4 …
Excerpt
74 II SKYRIUS. PREDIKATŲ SKAIČIAVIMAS $1. Kvantoriai. Predikatai Šiame skyriuje apibendrinsime teiginio sąvoką. Nagrinė- sime teiginius, priklausančius nuo parametro. Be to, laikysi- me, kad yra duotos tų parametrų kitimo sritys. Pavyzdžiui, "x pirminis …
Excerpt
, Ė 75 Predikatų pavyzdžiai: ai. 1. Argumentų kitimo sritis - realių skaičių aibė R. a) lygybės predikatas Li=i4) Liz4)=1 tada ir tik) "tada, kai X=4. ») Pl244)]=i tada ir tik tada, kai X g. c) Mix) =1 tada ir tik tada, kai …
Excerpt
76 roms argumentų kitimo sritims. . / Tarkime, Pla, X) - n-vietis predikaias, kurio ar- gumentų kitimo sritis yra aibė M. Predikatas vadinamas: 1) tapačiai teisingu, jei bet kuriam kintamųjų rinkiniui jo reikšmė yra li, š 2) tapačiai klaidingu, jei bet …
Excerpt
sis iki aga 117 kitimo „sritys yra aibė WM. Ž 1. TP(24,22,--, Aa) yra tapačiai teisinga tada ir tik tada, kai P(31,32,...,xn) yra tapačiai klaidinga. TP(XL X) =1 tada ir tik tada, kai PL(,.-,*k)=0 | 2į PRis, 22) lx, „aTa ) yra tapačiai teisin- ga tada ir …
Excerpt
"78 tuoja toks X„€M | kad PbGl=1 „T I einas priešingų atveju. Ie Px) nepriklauso nuo parametro x. Jei „a *,) n-vietis prėdikaias, 5ai Žx-Plx,,.--„12) …
Excerpt
179 tamųjų. Pvz., vietoje (P(x,4) 0043) | rašysime Pfx,1).£ 0ix), b) praleisti skliaustus, jeigu neiginys yra prieš tei- "ginius arba „predikatinius kintamuosius. Pvz., vaė6ipjė T PE4S-- 01 rašysime TP, An], Ą Vadinsiue formulę A. Kiekvienoje formulėje …
Excerpt
80 kad formulėse kintamieji yra pažymėti taip, kad kiekvienas kintamasis arba tik laisvas, arba tik priklausomas. Be to, skirtingi kvantorių simboliai susieja skirtingus kintamuo- sius. Uždaviniai. l. Kurie kintamieji yra laisvi ir kurie priklausomi a) Vx …
Excerpt
81 e) KSŲ, d) Xi, e) x dalosi iš y, ž)X4+4 dalosi iš 2. 4. Parašyti Žormulę be laisvų kintamųjų aibėje N, kuri teisinga tada ir tik tada, kai . : a) neegzistuoja vienetas, b) pirminių akaičių aibė baigtinė, e) egzistuoja diūžiausias natūrinis skaičius, d) …
Excerpt
ir seką G,,.:.,0„ (a, € M) , kad, pakeitus formulėse F predikatinius kintamuosius E predikatais 0,0... 0. „teiginius Pi,pa,. „p reikšmėmis Vim, laisvus kintamuosius x, „aso. X, aibės M elementais. a,,01,. „0, , gautos formulės reikšmė tūžų, lygi vienetui. …
Excerpt
> 83 Predikatinį kintamąjį P keičiame į L, 4 į 1, tada-F = 1. Taigi F nėra tapačiai klaidinga aibėje N. F nėra ir tapačiai teisinga aibėje N, nes, jeigu g priskirsime O-reikšmę, P-L, tai | P:ž: 04 2 i F = I+PG) > Vy Ry). F tapačiai teisinga bet kurioje …
Excerpt
S ir tik tada, kai F yra tapačiai teiaingas, arba nei P, neilF nėra tapačiai teisingas, Lema įrodyta. - Nustatyti, ar formulė yra tapačiai teisinga - vienas pag- rindinių metematinės logikos tikslų, Įrodinėjant +eoremas ES mašinomis, pėkanka mokėti …
Excerpt
85 Taigi mes mokame nustatyti,ar formulė (yra tapačiai tei- singa duotoje baigtinėje aibėje, ir tuo pačiu mokame nustatyti, Ž ar ji yra tapačiai klaidinga, ar yra įvykdoma duotoje baigti- | "nėjo aibėje. 2 Ar kiekviena įvykdoma formulė yra įvykdoma „ir …
Excerpt
86 T ki Ž las, sak ti ia, a+)=1, t.y. U04,04)]> 1, kas prieštarauja sąlygai V < 10(2,2) į TA(44 „94,)=4- A Uždaviniai š 1.Nustatyti, ar šios Žormulės yra tapačiai teisingos: a) P(x) > 34Pl4), b) VxPix) > IyP(4), e) Vz P(x) = T1341PB), a) (Va Pla) L Vy …
Excerpt
87 $4. Lygiavertės formulės Jeigu, pakeitus predikatinius kintamuosius kuriaią nora predikaiais aibėje M (vietų skaičius predikatuose turi būti toks pat, kaip ir is una žibs predikatiniuose kintamuosiuo= se), teiginius:kuriomis nors reikšmėmis iš [0,13 ir …
Excerpt
88 o 3. Tvirtinimas " Jxf6) klaidingas" teisingas tada ir tiktai tada, kai "kiekvienam y P(4) klaidingas", kuris yra teisingas tada ir tiktai tada, kai "kiekvienam y TR4) teisingas". Tai- gi P „2 Va 1P(3c) Ė T 2 Face) (3) 4. Remiantis (2), (3) bei …
Excerpt
“89 Iš tikrųjų, tarkime, Vx P(x) v (0 yra teisinga kurioje nors aibėje M, atitinkamai pakeitus kiatamuosius, ei ginius ir laisvus kintamuosius, Tada Vx P(x) = 4 arba 0=1. Pirmuoju atveju P(x) yra teisingas, esant bet kokiam x iš M. Tada ir PlixX)vŲ yra …
Excerpt
90 kintamuosius), 2 logiškai klaidingas, jei yra LST klai- dingas žormulės atskiras atvejis. Jei KR-R „taaĄ> R yra tapačiai teisinga formulė.“ Taigi .iš 1-12 pavyzdžių galime gauti daug logiškai teisingų | ivirtinisų. „Uždaviniai Nustatyti, ar logiškai …
Excerpt
diedas soli i i į 4 į 91 iės 15 tik jos. 1 TEOREMA. Tarkime, egzistuoja algoritmas, kuris/bet ko- kiai formulei, kurioje nėra teiginių, nustato, ar ji tapačiai teisinga. Tada egzistuoja algoritmas, kuris bet kuriai formu- lei F nustato, ar ji tapačiai …
Excerpt
: i 92 moje, jei FX Wx Mk WMR kur kiekviena W, = srba ANe zV. „ o R - formulė, kurioje nėra kvantorių. | i 3 TEOREMA. Tarkime, egzistuoja algoritmas, kuris bet aaa „formulei F preneks ngpsEtžReJĘ formoje nustato, ar Fr tapačiai , teisinga. Tada egzistuoja …
Excerpt
4 93 ž : joks kintamasis nėra kartu ir laisves, ir priklausomas, o bet kurie du kvantoriai skiariasi kintamai siais. Teorema įro- Bytas : Uždaviniai: Parašyti preneks normaline forma: a) Tax Vy ae V (Pla) > 42 Oz), | ») x vą Pacų) 8 Ax Vy Aaa), e) Ta Vy …
Excerpt
94 tai teorema įrodyta. Todėl nagrinėsime atvejį, kai aibėje M yra daugiau negu 2“ elementų. Kadkngi F yra įvykdoma aibėje M, tai egzistuoja n predikatų 3; aa aibėje M, ku- riais pakeitus predikatinius kintamuosius, F=1 (dar rei- kia pakeisti teiginius ir …
Excerpt
22 TRS teisinga kiekyiženoje aibėje, I eiėda ne daugiau kaip NA elementų. 5 : Anira vertus, formulė (į kurią įeina tik M predikatai) gali būti tapačiai teisinga aibėje iš k elėmenių ir nebūti tapačiai teisinga aibėje išk-1 cienėkio. Pateiksime keletą …