Mis veebilehti külastad? Anna Teada Sulge
Facebook Like
Küsitlus


Diskreetse matemaatika elemendid (0)

1 Hindamata
Punktid

Esitatud küsimused

  • Mitu serva saab olla k komponendi ja n tipu korral ?
  • Milliseid täisgraafe saab joonistada ühe joonega ?
  • Kustutame ühe lehe (miks alati leidub ?
  • Miks leiab Floyd - Warshalli algoritm tõesti lühima võimaliku ahela iga kahe tipu vahel ?
 
Säutsu twitteris
Diskreetse matemaatika elemendid 2013/2014
LAUSEARVUTUS. TÕESTUSED.

1. Lausearvutuse lausetele esitatavad tingimused. [1]

  • Välistatud kolmanda seadus. Iga lause on kas tõene või väär.
  • Mittevasturääkivuse seadus. Ükski lause ei saa olla nii tõene kui ka väär.
  • Nende nõuete põhjal kuuluvad vaadeldavate hulka ainult nii sugused laused , mis midagi väidavad, kusjuures sellel väitel on olemas ühene tõeväärtus.
  • . Välistatud kolmanda seaduse nõudel jäävad kõrvale kõik küsilaused ja paljud hüüdlaused, samuti kõik käsud ning mõttetud sõnaühendid. Mitte-vasturääkivuse seadus välistab mitmesugused paradoksid, näiteks „See lause siin on väär“, ja muud taolised väited, mille tõeväärtust pole võimalik üheselt määrata.
  • Tehte tulemuseks saadud lause tõeväärtus sõltub ainult komponentlausete tõeväärtustest.

2. Lausearvutuse tehted . Tehete järjekord . Lausearvutuse valem. [1]

Tehted
  • Eitus (märk ¬). Igapäevakeeles väljendab eitus lause mittekehtimist, näiteks „Lehis ei

ole okaspuu “. Selle lause võib kirja panna valemiga ¬A, kus A = „Lehis on okaspuu“.
  • Konjunktsioon (märk &) tähendab seost „ja“. Näiteks „Puhub tuul ja sajab vihma“ on

valemkujul A & B.

on valemkujul A ∨ B. Sidesõna „või“ kasutatakse siin mittevälistavas tähenduses: „Kas
A või B või mõlemad“. Igapäevases keeles on käibel ka välistav „või“: „Kas A või B,
aga mitte mõlemad“, näiteks „Ma külvan põllule rukist või panen põllule kartulid“.
Disjunktsiooni all mõistame mittevälistavat „võid“.
  • Implikatsioon (märk →) väljendab tingimuslikku konstruktsiooni „kui . . . , siis . . . “.

Näiteks „Kui Sven terve aasta korralikult õpib, siis suudab ta kevadel eksamid hõlpsasti
ära teha“ või „Kui kehtib teoreem P, siis kehtib teoreem Q“. Mõlemad laused võib kirja
panna valemiga A → B.

siis, kui“ ehk „siis ja ainult siis, kui“. Näiteks lause „hulk X on kinnine parajasti siis, kui
X ühtib oma sulundiga“ on valemkujul A ↔ B.
Tehete järjekord
  • ¬, &, ∨, →, ↔
  • vasakassotsiatiivsus: kui mitme liikme konjuktsioonis või disjunktsioonis sooritatakse

tehteid vasakult paremale, siis võib tehete järjekorda täpsustavatest sulgudest loobuda
  • Valemi välimised sulud võib ära jätta
Lausearvutuse valem
DEF: Lausearvutuse valemid on parajasti need, mida saab koostada alltoodud reeglite abil:
○ iga lausemuutuja on lausearvutuse valem
○ kui F on lausearvutuse valem, siis ka ¬F on lausearvutuse valem
○ kui F ja G on lausearvutuse valemid, siis ka (F & G), (F ∨ G), (F → G) ja (F ↔ G) on
lausearvutuse valemid

3. Väärtustus . Tõeväärtustabel . Samaselt tõene valem. Samaselt väär valem. Kehtestatav valem. Nende omaduste kontrollimine. Seosed valemiklasside vahel. [1]

Väärtustus:
  • Juhul, kui vaatluse all on korraga hulk lausemuutujaid ja me omistame tõeväärtuse

igale muutujale, siis nimetatakse sellist tõeväärtuste komplekti väärtustuseks. N: Olgu
muutujatekomplekt A, B, C, siis nende üks võimalik väärtustus on A=1, B=0, C=1 ehk (1,0,1)
Tõeväärtustabel:
  • Tehete toimet võib ülevaatlikumalt kirjeldada tõeväärtustabeliga, mille vasakus osas on valemi argumentide kõikvõimalikud väärtused, paremas osas aga tehete tulemused.

Samaselt tõene valem:
  • Lausearvutuse valemit F nimetatakse samaselt tõeseks, kui ta on igal väärtusel tõene.
  • tautoloogia, loogiliselt tõene valem N: A ∨ ¬A

Samaselt väär valem:
  • Lausearvutuse valemit F nimetatakse samaselt vääraks, kui ta on igal väärtusel väär.
  • kontradiktsioon, loogiliselt väär valem N: A & ¬A

Kehtestav valem:
  • Laussearvutuse valemit F nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtusel

tõene.
Nende omaduste kontrollimine:
  • Valemi omaduste tuvastamisel tuleb tüüpiliselt otsustada, kas leidub väärtustus, millel valem on tõene, või väärtustus, millel valem on väär. Alati saab seda küsimust lahendada tõeväärtustabeliga, kuid mõnikord võib kiiremini sihile jõuda valemi struktuuri analüüsides. Näiteks kui on vaja kindlaks teha, kas etteantud valem saab olla mingil väärtustusel tõene, siis uurime kõigepealt , millised peavad olema valemi peatehte poolte tõeväärtused , et valem oleks tõene, seejärel püüame leida väiksemate komponentide tõeväärtused, siis omakorda veel väiksemate omad jne, liikudes valemi struktuuris järk-järgult üha sügavamale. Kui sellise analüüsi käigus satume alati vastuolule, siis valem ühelgi väärtustusel tõene ei ole ning on järelikult samaselt väär. Kui aga jõuame ilma vastuolu kohtamata välja lausemuutujateni, siis saame kätte väärtustuse, millel valem on tõene.
  • Tõestuspuu. Puu tipuks on uuritav valem koos kontrollitava tõeväärtusega. Kui oleme kindlaks teinud valemi mingi osa tõeväärtuse, siis kirjutame tulemuse valemi alla, selle alla omakorda valemi osa analüüsimisel saadud tulemuse jne. Kui osutub, et mingil sammul on valemi osadel mitu sobivat varianti tõeväärtusi, siis jaguneb analüüs sellel sammul harudeks , mida jätkatakse üksteisest sõltumatult.

Seosed valemiklasside vahel:
  • Teoreem 1: Valem F on samaselt tõene parajasti siis, kui tema eitus ¬F on samaselt

väär.
Tõestus. Andes valemis F esinevatele lausemuutujatele suvalise väärtustuse, näeme, et
valemite F ja ¬F tõeväärtused on vastupidised. Järelikult kui F on igal väärtustusel
tõene, siis ¬F on igal väärtustusel väär ja ümberpöördult.
  • Teoreem 2: Valem F on kehtestatav parajasti siis, kui tema eitus ¬F ei ole samaselt tõene.

Tõestus. Kui F on kehtestatav, siis väärtustusel, kus F on tõene, on valem ¬F väär ja ei saa seetõttu olla samaselt tõene. Ümberpöördult, kui ¬F ei ole samaselt tõene, siis leidub väärtustus, kus ¬F on väär ja F on järelikult tõene.

4. Samaväärsed valemid. Lausearvutuse põhisamaväärsused. Valemite teisendamine samaväärsuste abil. Teoreem piisavatest tehete komplektidest. [1, L2 slaidid]

Samaväärsed valemid
  • DEF: Valemeid F ja G nimetatakse samaväärseteks, kui nende tõeväärtused on võrdsed igal neis valemeis esinevate muutujate väärtustel.
  • Teoreem: Valemid F ja G on samaväärsed parajasti siis, kui valemist F järeldub valem G ja valemist G järeldub valem F.
  • Teoreem : Valemid F ja G on samaväärsed parajasti siis, kui valem F ↔ G on samaselt tõene. Tõestus. Eeldame, et valemid F ja G on samaväärsed. Valime valemites F ja G esinevatele muutujatele suvalise väärtustuse. Kui valitud väärtustusel kehtib F = 1 ja G = 1, siis F ↔G = 1, kui aga valitud väärtustusel kehtib F = 0 ja G = 0, siis samuti F ↔ G = 1. Järelikult on valem F ↔ G tõene sõltumata väärtustusest ehk samaselt tõene. Eeldame nüüd ümberpöördult, et valem F ↔G on samaselt tõene. Valime selles valemis esinevatele muutujatele suvalise väärtustuse. Etekvivalents on tõene, siis kas F = 1, G = 1 või F = 0, G = 0. See tähendab, valemite F ja G tõeväärtused on suvalisel väärtustusel samad. Vastavalt definitsioonile on valemid F ja G samaväärsed.

Lausearvutuse põhisamaväärused
  • Idempotentsuse seadused:

F & F ≡ F ,
F ∨ F ≡ F .
  • Kommutatiivsuse seadused:

F & G ≡ G & F ,
F ∨ G ≡ G ∨ F .
  • Assotsiatiivsuse seadused:

(F & G) & H ≡ F & (G & H ),
(F ∨ G) ∨ H ≡ F ∨ (G ∨ H ).
  • Distributiivsuse seadused:

F & (G ∨ H ) ≡ F & G ∨ F & H ,
F ∨ G & H ≡ (F ∨ G) & (F ∨ H ).
  • Neelamisseadused:

F & (F ∨ G) ≡ F ,
F ∨ F & G ≡ F .

¬(F & G) ≡ ¬F ∨ ¬G,
¬(F ∨ G) ≡ ¬F & ¬G.
  • Kahekordse eituse seadus:

¬¬F ≡ F .
  • Liikmete elimineerimise reeglid, kus T on suvaline samaselt tõene valem ja V on suvaline samaselt väär valem:

F & T ≡ F ,
F & V ≡ V ,
F ∨T ≡T ,
F ∨ V ≡ F .
  • Implikatsiooni avaldis konjunktsiooni ja disjunktsiooni kaudu:

F → G ≡ ¬(F & ¬G),
F → G ≡ ¬F ∨ G.
  • Konjunktsiooni ja disjunktsiooni avaldis implikatsiooni kaudu:

F & G ≡ ¬(F → ¬G),
F ∨ G ≡ ¬F → G.
  • Ekvivalentsi avaldis teiste tehete kaudu:

F ↔ G ≡ F & G ∨ ¬F & ¬G,
F ↔G ≡ (F → G) & (G → F
Valemite teisendamine samaväärsuste abil
Samaväärsuste kasutamine teisendustes seisneb valemi mingi osavalemi asendamises temaga samaväärsega. Nagu algebras, säilitab selline osavalemi asendamine ka siin samaväärsuse ka terve valemi jaoks. Peamised kujud, millele teisendatakse, on:
○ esitused kahe tehte kaudu
○ nn normaalkujud
Teoreem piisavatest tehete komplektidest
Iga lausearvutuse valemi jaoks leidub temaga samaväärne valem, mis ei sisalda muid tehtemärke kui:
○ ¬, &
○ ¬, ∨
○ ¬, →
Tõestus: kolm ülejäänud tehet saab avaldada antud komplekti kaudu

5. Järeldumine . Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduste kontrollimisele. [1]

Järeldumine
  • DEF: Ütleme, et valemitest F1 , F2 , . . . , Fn järeldub valem G, kui igal neis valemeis esinevate muutujate väärtustusel, millel F1 , F2 , . . . , Fn on tõesed, on ka G tõene.
  • Teoreem järeldumise kohta: Valemitest F 1 , F 2 , . . . , F n järeldub valem G parajasti siis, kui valem F 1 & F 2 & . . . & F n → G on samaselt tõene.

Tõestus. Kui valemitest F 1 , F 2 , . . . , F n järeldub valem G, siis neil väärtustustel, millel valemid F 1 , F 2 , . . . , F n on tõesed, on ka valem G tõene, mistõttu F 1 &F 2 &. . .&F n →G on tõene. Väärtustustel, millel mõni valemitest F 1 , F 2 , . . . , F n on väär, on valem F 1 &F 2 &. . .&F n →G tõene seetõttu, et implikatsiooni eesliige on väär. Ümberpöördult, kui valem F 1 & F 2 & . . . & F n → G on samaselt tõene, siis igal väärtustusel, millel valemid F 1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene.
Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele
  • Samaväärus F ↔ G
  • Järeldumine F → G

6. Literaal , täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju , nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm , tema etappidel kasutatavad samaväärsused. [1]

Literaal
  • DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C
Täielik elementaalkonjuktsioon
  • DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln
Täielik disjunktiivne normaalkuju
  • DEF: Lausearvutuse valemi F täielikuks disjunktiivseks normaalkujuks (TDNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaarkonjunktsioonide disjunktsiooni.
Tõestuspiirkondade kirjeldused
TDNK olemasolu ja ühesus
Teoreem. Kui valem F ei ole samaselt väär, siis tal leidub täielikdisjunktiivne normaalkuju.
Järeldus. Kui valem F ei ole samaselt tõene, siis tal leidub täielikkonjunktiivne normaalkuju.
Tõestus. Et valem ¬F ei ole samaselt väär, siis leidub tal täielik disjunktiivne normaalkuju. Leiame mõlemast poolest eituse, seejärel viime paremal eituse sissepoole De Morgani seaduste abil. Nii saame Paremal poolel võis lausemuutujate ette tekkida kahekordseid eitusi. Jättes need ära, ongi tulemuseks valemi F täielik konjunktiivne normaalkuju
TDNK’le teisendamise algoritm, etappidel kasutatavad samaväärsused
  • Elimineerime implikatsioonid ja ekvivalentsid

F → G ≡ ¬F ∨ G,
F ↔ G ≡ F & G ∨ ¬F & ¬G
  • Viime eitused vahetult lausemuutujate ette, kasutades De Morgani seadusi

¬(F & G) ≡ ¬F ∨ ¬G,
¬(F ∨ G) ≡ ¬F & ¬G
Kui kuskile tekib kahekordne eitus, siis jätame selle ära.
  • Viime konjunktsioonid disjunktsioonidest sügavamale, kasutades distributiivsuse seadusi

F & (G ∨ H ) ≡ F & G ∨ F & H
(F ∨ G) & H ≡ F & H ∨ G & H
  • Eemaldame liikmed, mis sisaldavad vastandlikke literaalipaare, sest need liikmed on samaselt väärad. Igast järelejäänud liikmest kaotame literaalide kordused. Jätame välja korduvad liikmed.
  • Lisame igale elementaarkonjunktsioonile täiskomplektist puuduvad muutujad, kasutades seost F ≡ F & (A ∨ ¬A). Seejärel rakendame uuesti distributiivsuse seadusi ja korrutame sulud lahti
  • Jätame välja täielike elementaarkonjunktsioonide korduvad eksemplarid, kasutades idempotentsuse seadust F ∨ F ≡ F .

7. Boole ’i funktsioonide esitamine lausearvutuse valemitega. [1, L3 slaidid]

  • DEF: Kaheelemendilisel hulgal defineeritud funktsioone nim Boole’i funktsioonideks.
  • Teoreem: Iga Boole’i funktsiooni f(X1, … , Xn1, Xn) saab esitada lausearvutuse valemina milles ei ole muid tehtemärke, kui &, ∨ ja ¬.

8. Lausearvutuse (tehted, valemid, samaväärsus, teisendamine, normaalkuju jne) seosed programmeerimise, infosüsteemide jms-ga.

Telefoniraamatu ülesanne, kuidas leiab kiiremini jne..

9. **Tõestamise strateegiad, mis tulenevad eelduste või juba tõestatud faktide kujust : konjunktsioon, disjunktsioon, implikatsioon, ekvivalents, eitus, üldisus , olemasolu. [3]


Implikatsiooni tõestamise tavaline taktika on järgmine. Eeldame, et lisaks teoreemi eeldustele kehtib ka B. Tõestame

10. Üldisuse kvantoriga väite tõestamine induktsiooniga naturaalarvudel. [2, 3, L15 slaidid]


Kvantoreid sisaldavate valemite korral eeldame, et on fikseeritud mingi universaalne hulk ja tähendab: „iga korral hulgast kehtib “, tähendab: „leidub selline , et kehtib “.
Vaatame nüüd läbi kõik loogilised seosed. Alustame nendest , mis esinesid ülaltoodud näites.
Tavaline üldisuse kvantoriga väite tõestamise esimene samm on selline: Tähistagu muutuja suvalist universaalse hulga elementi.
Formaalselt tähendab suvalisus seda, et peame valima uue tähise, et eeldustes ei oleks elemendi kohta midagi väidetud. Sealhulgas
80% sisust ei kuvatud. Kogu dokumendi sisu näed kui laed faili alla

Logi sisse ja saadame uutele kasutajatele faili TASUTA e-mailile

Vasakule Paremale
Diskreetse matemaatika elemendid #1 Diskreetse matemaatika elemendid #2 Diskreetse matemaatika elemendid #3 Diskreetse matemaatika elemendid #4 Diskreetse matemaatika elemendid #5 Diskreetse matemaatika elemendid #6 Diskreetse matemaatika elemendid #7 Diskreetse matemaatika elemendid #8 Diskreetse matemaatika elemendid #9 Diskreetse matemaatika elemendid #10 Diskreetse matemaatika elemendid #11 Diskreetse matemaatika elemendid #12 Diskreetse matemaatika elemendid #13 Diskreetse matemaatika elemendid #14 Diskreetse matemaatika elemendid #15 Diskreetse matemaatika elemendid #16 Diskreetse matemaatika elemendid #17 Diskreetse matemaatika elemendid #18 Diskreetse matemaatika elemendid #19 Diskreetse matemaatika elemendid #20 Diskreetse matemaatika elemendid #21 Diskreetse matemaatika elemendid #22 Diskreetse matemaatika elemendid #23 Diskreetse matemaatika elemendid #24 Diskreetse matemaatika elemendid #25 Diskreetse matemaatika elemendid #26 Diskreetse matemaatika elemendid #27 Diskreetse matemaatika elemendid #28 Diskreetse matemaatika elemendid #29 Diskreetse matemaatika elemendid #30 Diskreetse matemaatika elemendid #31 Diskreetse matemaatika elemendid #32 Diskreetse matemaatika elemendid #33 Diskreetse matemaatika elemendid #34 Diskreetse matemaatika elemendid #35 Diskreetse matemaatika elemendid #36 Diskreetse matemaatika elemendid #37 Diskreetse matemaatika elemendid #38 Diskreetse matemaatika elemendid #39 Diskreetse matemaatika elemendid #40 Diskreetse matemaatika elemendid #41 Diskreetse matemaatika elemendid #42 Diskreetse matemaatika elemendid #43 Diskreetse matemaatika elemendid #44 Diskreetse matemaatika elemendid #45 Diskreetse matemaatika elemendid #46
Punktid 100 punkti Autor soovib selle materjali allalaadimise eest saada 100 punkti.
Leheküljed ~ 46 lehte Lehekülgede arv dokumendis
Aeg2015-03-27 Kuupäev, millal dokument üles laeti
Allalaadimisi 28 laadimist Kokku alla laetud
Kommentaarid 0 arvamust Teiste kasutajate poolt lisatud kommentaarid
Autor kellu1993 Õppematerjali autor

Lisainfo

Eksami konspekt

Märksõnad

Mõisted


Meedia

Kommentaarid (0)

Kommentaarid sellele materjalile puuduvad. Ole esimene ja kommenteeri


Sarnased materjalid

13
docx
Diskreetse matemaatika elemendid-eksami konspekt
42
pdf
Diskreetse matemaatika mõisted selgitustega
1
pdf
Diskreetse matemaatika elemendid
2
pdf
Diskreetse matemaatika elemendid
1
pdf
Diskreetse matemaatika elemendid
31
doc
Diskreetne matemaatika - konspekt
12
docx
Diskreetne matemaatika eksami kordamise materjal
11
docx
Diskreetne Matemaatika





Logi sisse ja saadame uutele kasutajatele
faili e-mailile TASUTA

Faili allalaadimiseks, pead sisse logima
või
Kasutajanimi / Email
Parool

Unustasid parooli?

UUTELE LIITUJATELE KONTO MOBIILIGA AKTIVEERIMISEL +50 PUNKTI !
Pole kasutajat?

Tee tasuta konto

Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun