Declarații complexe. Tipurile și condițiile lor de adevăr. Valoarea de adevăr

Proprietăți

Luați în considerare câteva proprietăți ale produsului cartezian:

1. Dacă A,B sunt mulţimi finite, atunci A× B- finală. Și invers, dacă unul dintre mulțimile multiplicatoare este infinit, atunci rezultatul produsului lor este o mulțime infinită.

2. Numărul de elemente din produsul cartezian este egal cu produsul numerelor de elemente ale mulțimilor multiplicatoare (dacă sunt finite, desigur): | A× B|=|A|⋅|B| .

3. A np ≠(A n) p- în primul caz, este indicat să se considere rezultatul produsului cartezian ca o matrice de dimensiuni 1× np, în al doilea - ca o matrice de dimensiuni n× p .

4. Legea comutativă nu este îndeplinită, deoarece perechile de elemente ale rezultatului produsului cartezian sunt ordonate: A× B≠B× A .

5. Legea asocierii nu este îndeplinită: ( A× B)× C≠A×( B× C) .

6. Există distributivitate în ceea ce privește operațiile de bază pe mulțimi: ( A∗B)× C=(A× C)∗(B× C),∗∈{∩,∪,∖}

11. Conceptul de enunț. Enunţuri elementare şi compuse.

afirmație este o afirmație sau o propoziție declarativă despre care se poate spune că este adevărată (T-1) sau falsă (L-0), dar nu ambele în același timp.

De exemplu, „Astăzi ploua"," a completat Ivanov munca de laborator Nr. 2 la fizică.

Dacă avem mai multe afirmații inițiale, atunci din ele folosind uniuni logice sau particule putem forma enunțuri noi a căror valoare de adevăr depinde numai de valorile de adevăr ale enunțurilor originale și de conjuncțiile și particulele specifice care participă la construcția noului enunț. Cuvintele și expresiile „și”, „sau”, „nu”, „dacă... atunci”, „prin urmare”, „dacă și numai atunci” sunt exemple de astfel de conjuncții. Declarațiile originale sunt numite simplu , și noi enunțuri construite din ele cu ajutorul anumitor uniuni logice - constitutiv . Desigur, cuvântul „simplu” nu are nimic de-a face cu esența sau structura afirmațiilor originale, care în sine pot fi destul de complexe. În acest context, cuvântul „simplu” este sinonim cu cuvântul „original”. Important este că se presupune că valorile de adevăr ale propozițiilor simple sunt cunoscute sau date; în orice caz, ele nu se discută în niciun fel.

Deși o afirmație precum „Azi nu este joi” nu este alcătuită din două enunțuri simple diferite, pentru uniformitatea construcției este tratată și ca una compusă, deoarece valoarea sa de adevăr este determinată de valoarea de adevăr a unei alte afirmații „Astăzi este joi”. "

Exemplul 2 Următoarele declarații sunt tratate ca declarații compuse:

Am citit Moskovsky Komsomolets și am citit Kommersant.

Dacă a spus-o, atunci este adevărat.

Soarele nu este o stea.

Dacă este soare și temperatura depășește 25 0 , voi ajunge cu trenul sau mașina

Enunțurile simple incluse în enunțurile compuse pot fi ele însele complet arbitrare. În special, ele însele pot fi compozite. Tipurile de bază de enunțuri compuse descrise mai jos sunt definite independent de enunțurile simple care le formează.

12. Operațiuni pe extrase de cont.

1. operație de negație.

Negarea afirmației A ( se citește „nu A"," nu este adevărat că A"), ceea ce este adevărat când A fals și fals când A- Adevărat.

Afirmatii negative Ași numit opus.

2. operație de conjuncție.

conjuncţie declarații Ași V se numeste afirmatie A B(citit " Ași V”), ale căror semnificații adevărate sunt determinate dacă și numai dacă ambele enunțuri Ași V Adevărat.

Conjuncția de propoziții se numește produs logic și este adesea denotată AB.

Lasă declarația A– „în martie, temperatura aerului de la 0 С la + 7 C» și spunând V- „Plouă în Vitebsk”. Atunci A B va fi astfel: „în luna martie, temperatura aerului de la 0 С la + 7 Cși plouă în Vitebsk”. Această conjuncție va fi adevărată dacă există afirmații Ași V Adevărat. Dacă se dovedește că temperatura a fost mai mică 0 С sau nu a fost ploaie în Vitebsk, atunci A B va fi fals.

3 . operație de disjuncție.

disjuncție declarații Ași V se numeste afirmatie A B (A sau V), care este adevărat dacă și numai dacă cel puțin una dintre afirmații este adevărată și falsă - când ambele afirmații sunt false.

Disjuncția propozițiilor se mai numește și sumă logică A+B.

Declaratia " 4<5 sau 4=5 ' este adevarat. Din moment ce afirmația „ 4<5 „este adevărat, iar afirmația” 4=5 ' este fals, atunci A B este o afirmație adevărată 4 5 ».

4 . operație de implicare.

implicare declarații Ași V se numeste afirmatie A B("dacă A, atunci V", "de la A ar trebui să V”), a cărui valoare este falsă dacă și numai dacă A adevărat, și V fals.

În implicație A B afirmație A numit fundație, sau trimiterea și declarația V – consecinţă, sau concluzie.

13. Tabele de adevăr al afirmațiilor.

Un tabel de adevăr este un tabel care stabilește o corespondență între toate seturile posibile de variabile logice incluse într-o funcție logică și valorile funcției.

Tabelele de adevăr sunt folosite pentru:

Calcularea adevărului afirmațiilor complexe;

Stabilirea echivalenței declarațiilor;

Definițiile tautologiilor.

Stabilirea adevărului afirmațiilor complexe.

Exemplul 1 Determinați adevărul afirmației C

Soluţie. Compoziția unei declarații complexe include 3 declarații simple: A, B, C. Coloanele din tabel sunt umplute cu valori (0, 1). Sunt indicate toate situațiile posibile. Propozițiile simple sunt separate de propozițiile complexe printr-o linie verticală dublă.
La alcătuirea tabelului, trebuie avut grijă să nu se confunde ordinea acțiunilor; umplerea coloanelor, ar trebui să se deplaseze „din interior spre exterior”, adică. de la formule elementare la cele din ce în ce mai complexe; ultima coloană de populată conține valorile formulei originale.

A	V	CU	A+	· CU

Tabelul arată că această afirmație este adevărată numai dacă A=0, B=1, C=1. În toate celelalte cazuri este fals.

14. Formule echivalente.

Două formule Ași V sunt numite echivalente dacă iau aceleași valori logice pentru orice set de valori ale propozițiilor elementare incluse în formulă.

Echivalența este indicată de semnul „”. Pentru transformarea formulelor în echivalente, un rol important îl au echivalențele de bază, exprimând unele operații logice prin altele, echivalențe, exprimând legile de bază ale algebrei logicii.

Pentru orice formule A, V, CU echivalentele sunt valabile.

I. Echivalenţe de bază

legea idempotei

1-adevarat

0-fals

Legea contradicției

Legea mijlocului exclus

legea absorbtiei

formule de divizare

legea legaturii

II. Echivalenţe care exprimă unele operaţii logice în termenii altora.

legea lui de Morgan

III. Echivalenţe care exprimă legile de bază ale algebrei logicii.

legea comutativă

drept asociativ

drept distributiv

15. Formule ale logicii propoziționale.

Tipuri de formule în logica propozițională clasică- în logica propozițională se disting următoarele tipuri de formule:

1. Legile(formule identice adevărate) - formule care, pentru orice interpretare a variabilelor propoziționale, capătă valoare "Adevărat";

2. contradictii(formule identice false) - formule care, pentru orice interpretare a variabilelor propoziționale, capătă valoare "fals";

3. Formule satisfăcătoare- cele care capătă sens "Adevărat" pentru cel puțin un set de valori de adevăr ale variabilelor propoziționale incluse în acestea.

Legile de bază ale logicii propoziționale clasice:

1. Legea identității: ;

2. Legea contradictiei: ;

3. Legea mijlocului exclus: ;

4. Legile comutativității și: , ;

5. Legile distributivității sunt relative la , și invers: , ;

6. Legea eliminării termenului adevărat al conjuncției: ;

7. Legea eliminării termenului fals al disjuncției: ;

8. Legea contrapoziției: ;

9. Legile expresibilității reciproce a conectivelor propoziționale: , , , , , .

Procedura de rezolvare- o metodă care permite fiecărei formule să stabilească dacă este o lege, o contradicție sau o formulă fezabilă. Cea mai comună procedură de rezolvare este metoda tabelului de adevăr. Cu toate acestea, el nu este singurul. O metodă eficientă de rezolvare este metoda forme normale pentru formulele logice propoziționale. forma normala formula logică propozițională este o formă care nu conține semnul de implicație „”. Există forme normale conjunctive și disjunctive. Forma conjunctivă conține doar semnele de conjuncție „”. Dacă o formulă redusă la forma normală conjunctivă conține o subformulă a formei, atunci întreaga formulă în acest caz este contradicţie. Forma disjunctivă conține doar semne de disjuncție „”. Dacă o formulă redusă la forma normală disjunctivă conține o subformula a formei, atunci întreaga formulă în acest caz este lege. În toate celelalte cazuri, formula este formulă satisfăcătoare.

16. Predicate și operații asupra lor. Cuantificatori.

O propoziție care conține una sau mai multe variabile și care, pentru anumite valori ale variabilelor, este o declarație se numește formă propozițională sau predicat.

În funcție de numărul de variabile incluse în propunere, se disting simple, duble, triple etc. predicate notate respectiv: A( X), V( X, la), CU( X, la, z).

Dacă este dat un predicat, atunci îi sunt asociate două mulțimi:

1. Setul (domeniul) definiției X, constând din toate valorile variabilelor, la înlocuirea lor într-un predicat, acesta din urmă se transformă într-o declarație. Când se specifică un predicat, domeniul său este de obicei specificat.

2. Adevărul set T, constând din toate acele valori ale variabilelor, la substituirea lor în predicat se obține o afirmație adevărată.

Setul de adevăr al unui predicat este întotdeauna un submult al domeniului său, adică .

Puteți efectua aceleași operații pe predicate ca și pe instrucțiuni.

1. Negare predicat A( X) definit pe mulțimea X se numește predicat adevărat pentru acele valori pentru care predicatul A( X) se transformă într-o afirmație falsă și invers.

Din această definiție rezultă că predicatele A( X) și B( X) nu sunt negații unul altuia dacă există cel puțin o valoare pentru care predicatele A( X) și B( X) se transformă în propoziții cu aceleași valori de adevăr.

Mulțimea de adevăr a predicatului este complementul la mulțimea de adevăr a predicatului A( X). Notăm cu T A mulțimea de adevăr a predicatului A( X), iar prin T - setul de adevăr al predicatului . Atunci .

2. conjuncţie predicate A( X) și B( XX) V( X X X, sub care ambele predicate se transformă în enunțuri adevărate.

Mulțimea de adevăr al conjuncției predicatelor este intersecția mulțimilor de adevăr ale predicatului A( X) V( X). Dacă notăm mulțimea de adevăr a predicatului A(x) cu T A și mulțimea de adevăr a predicatului B(x) cu T B și mulțimea de adevăr a predicatului A(x) B(x) cu , atunci

3. disjuncție predicate A( X)și B( X) definit pe multimea X se numeste predicatul A( X) V( X), care se transformă într-o adevărată propunere pentru acele și numai acele valori X X, sub care cel puțin unul dintre predicate s-a transformat într-un enunț adevărat.

Setul de adevăr al unei disjuncții de predicate este unirea seturilor de adevăr ale predicatelor care o formează, i.e. .

4.implicare predicate A( X) și B( X) definit pe multimea X se numeste predicatul A( X) V( X), care este fals pentru acele și numai acele valori ale variabilei pentru care primul predicat devine adevărat și al doilea devine fals.

Setul de adevăr al implicației predicatelor este unirea mulțimii de adevăr al predicatului B( X) cu adaos la mulțimea de adevăr a predicatului A( X), adică

5. Echivalenţă predicate A( X) și B( X) definit pe mulțimea X se numește predicat care se transformă într-un enunț adevărat pentru toate acele și numai acele valori ale variabilei pentru care ambele predicate se transformă fie în enunțuri adevărate, fie în afirmații false.

Setul de adevăr al echivalentului predicatelor este intersecția setului de adevăr al predicatului cu setul de adevăr al predicatului.

Operații de cuantificare pe predicate

Un predicat poate fi tradus într-un enunț prin metoda substituției și prin metoda „cuantificatorului suspendat”.

Despre numerele 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, puteți spune: a) toate numerele date sunt prime; b) niste dintre numerele date sunt pare.

Deoarece se poate spune că aceste propoziții sunt adevărate sau false, propozițiile rezultate sunt propoziții.

Dacă eliminăm cuvântul „toți” din propoziția „a”, iar cuvântul „unii” din propoziția „b”, atunci obținem următoarele predicate: „numerele date sunt prime”, „numerele date sunt impare”.

Cuvintele „toți” și „unii” se numesc cuantificatori. Cuvântul „cuantificator” este de origine latină și înseamnă „cât”, adică cuantificatorul arată câte (toate sau unele) obiecte sunt menționate într-o anumită propoziție.

Există două tipuri principale de cuantificatori: cuantificatorul general și cuantificatorul existențial.

Termeni „oricare”, „oricare”, „toată lumea” sunt numite – cuantificator universal. Desemnat .

Fie A( X) este un anumit predicat dat pe mulțimea X. Sub expresia A( X) vom înțelege că afirmația este adevărată atunci când A( X) este adevărată pentru fiecare element al mulțimii X și falsă în caz contrar.

În exemplul 1 pentru R1 domeniu de definiție: , set de valori - . Pentru R2 domeniu de definiție: , set de valori: .

În multe cazuri, este convenabil să folosiți o reprezentare grafică a unei relații binare. Se desfășoară în două moduri: cu ajutorul punctelor din avion și cu ajutorul săgeților.

În primul caz, două linii reciproc perpendiculare sunt alese ca axe orizontale și verticale. Pe axa orizontală se așează elementele setului Ași trageți o linie verticală prin fiecare punct. Pe axa verticală se așează elementele setului B trageți o linie orizontală prin fiecare punct. Punctele de intersecție ale liniilor orizontale și verticale descriu elementele produsului direct

18. Metode de stabilire a relaţiilor binare.

Orice submulțime a produsului cartezian A × B se numește relație binară definită pe o pereche de mulțimi A și B (în latină, „bis” înseamnă „de două ori”). În cazul general, prin analogie cu relațiile binare, se pot considera și relații n-are ca șiruri ordonate de n elemente luate dintr-una din n mulțimi.

Simbolul R este folosit pentru a desemna o relație binară Deoarece R este o submulțime a mulțimii A×B, putem scrie R⊆A×. Dacă este necesar să se indice că (a, b) ∈ R, adică există o relație R între elementele a ∈ A și b ∈ B, atunci scrieți aRb.

Modalități de a specifica relații binare:

1. Aceasta este utilizarea regulii, conform căreia sunt indicate toate elementele cuprinse în această relație. În loc de o regulă, puteți enumera elementele unei relații date prin enumerarea lor directă;

2. Tabular, sub formă de grafice și folosind secțiuni. Baza metodei tabelare este un sistem de coordonate dreptunghiular, în care elementele unui set sunt reprezentate de-a lungul unei axe, iar elementele altui set de-a lungul celei de-a doua. Intersecțiile coordonatelor formează puncte care denotă elementele produsului cartezian.

Pe (figura 1.16) este afișată grila de coordonate pentru mulțimi. Punctele de intersecție a trei drepte verticale cu șase orizontale corespund elementelor mulțimii A×B. Cercurile de pe grilă marchează elementele relației aRb, unde a ∈ A și b ∈ B, R denotă relația „divizează”.

Relațiile binare sunt date de sisteme de coordonate bidimensionale. Evident, toate elementele produsului cartezian a trei mulțimi pot fi reprezentate în mod similar într-un sistem de coordonate tridimensional, patru mulțimi într-un sistem cu patru dimensiuni etc.;

3. Metoda de specificare a relațiilor folosind secțiuni este folosită mai rar, așa că nu o vom lua în considerare.

19. Reflexivitatea unei relații binare. Exemplu.

În matematică, o relație binară pe o mulțime se numește reflexivă dacă fiecare element al acestei mulțimi este în relație cu el însuși.

Proprietatea reflexivității pentru relații date de către o matrice este caracterizată prin faptul că toate elementele diagonale ale matricei sunt egale cu 1; pentru relațiile date de grafic, fiecare element are o buclă - un arc (x, x).

Dacă această condiție nu este îndeplinită pentru niciun element al mulțimii, atunci relația se numește antireflexivă.

Dacă relația antireflexivă este dată de o matrice, atunci toate elementele diagonale sunt zero. Când o astfel de relație este dată de un grafic, fiecare vârf nu are o buclă - nu există arce de forma (x, x).

Formal, antireflexivitatea unei relaţii este definită ca: .

Dacă condiția de reflexivitate nu este îndeplinită pentru toate elementele mulțimii, se spune că relația este nereflexivă.

©2015-2019 site
Toate drepturile aparțin autorilor lor. Acest site nu pretinde autor, dar oferă o utilizare gratuită.
Data creării paginii: 2016-04-12

Exemplul 1 Determinați adevărul afirmației C
Soluţie. Compoziția unei declarații complexe include 3 declarații simple: A, B, C. Coloanele din tabel sunt umplute cu valori (0, 1). Sunt indicate toate situațiile posibile. Propozițiile simple sunt separate de propozițiile complexe printr-o linie verticală dublă.
La alcătuirea tabelului, trebuie avut grijă să nu se confunde ordinea acțiunilor; umplerea coloanelor, ar trebui să se deplaseze „din interior spre exterior”, adică. de la formule elementare la cele din ce în ce mai complexe; ultima coloană de populată conține valorile formulei originale.

A	V	CU		A+		· CU



0	1	1	0	0	1	1

Tabelul arată că această afirmație este adevărată numai dacă A=0, B=1, C=1. În toate celelalte cazuri este fals.

Echivalența afirmațiilor.

Tabelele de adevăr pot fi folosite pentru a stabili echivalența a două sau mai multe afirmații.

Afirmațiile sunt numite echivalente dacă valorile corespunzătoare fiecăreia dintre ele se potrivesc în tabelul de adevăr.

Exemplul 2 Se susține că propoziția A + B C este echivalentă cu propoziția (A + B) (A + C)
Soluţie. Verificarea se realizează prin compilarea unui tabel de adevăr.


A	V	CU	B C	A+B C	A+B	A+C	(A+B) (A+C)

Comparând coloanele a 5-a și a 8-a, ne asigurăm că toate valorile obținute prin formula A + B · C coincid cu valorile obținute prin formula (A + B) · (A + C), adică afirmațiile sunt echivalente (echivalente). Unul îl poate înlocui pe celălalt.
Declarațiile echivalente (echivalente) sunt legate prin semnul º A + B · Cº (A + B) · (A + C).
Observați diferența dintre echivalență și echivalență.
O echivalență este o operație logică care permite, conform a două afirmații date A și B, construirea unui nou A «B.
Echivalența, pe de altă parte, este relația dintre două propoziții compuse prin care valorile lor de adevăr sunt întotdeauna aceleași.

Tautologie.

Să fie dat enunțul A+ și este necesar să se facă un tabel de adevăr.
Afirmația A este falsă, adevărul său nu depinde de adevărul afirmației A.

Luați în considerare afirmația B+.
În acest caz, propoziția B+ este întotdeauna adevărată, indiferent de adevărul lui B.

V		B+

Enunțurile, al căror adevăr este constant și nu depinde de adevărul afirmațiilor simple incluse în ele, ci este determinat doar de structura lor, se numesc identice sau tautologii.
Există afirmații identic adevărate și identic false.
În formule, fiecare afirmație identic adevărată este înlocuită cu 1 și identic fals - cu 0. Legea mijlocului exclus.
A º 0
B+ º 1

Exemplul 3 Demonstrați tautologia (XÙ Y)® (XÚ Y)
Soluţie.

pentru că propoziția (XÙ Y)® (XÚ Y) este întotdeauna adevărată, atunci este o tautologie.

Exemplul 4 Demonstrați tautologia ((X® Y)Ù (Y® Z))® (X® Z)
Soluţie.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F

X	Y	Z	X® Y	Y®Z	X®Z	F1Ù F2	(F1Ù F2) ® F3

Tabelul arată că enunţul studiat este o tautologie, deoarece este cu adevărat permanent.

Întrebări și sarcini.

1. Care dintre următoarele afirmații:

a) (A+C); b) +B; c) +C); d) A+;
echivalent cu afirmația (B+C)

2. Utilizați tabele de adevăr pentru a determina care dintre următoarele formule sunt tautologii:
A) " ); b) ; v) ;

G) ; e) (X® Y)" (Y® X); f) (X® Y) «;

g) (X® Y)«.

3. Stabiliți adevărul afirmației

4. Sunt afirmațiile echivalente?
și ?

5. Stabiliți dacă afirmația dată este o tautologie:
A) ; b)

6. Pentru fiecare formulă, veniți cu propozițiile pe care le formalizează:
A) ; b) ; v) .

7. Din afirmații simple: „Viktor este un înotător bun” - A; „Victor se scufundă bine” - V; „Victor cântă bine” - C, a fost făcută o declarație complexă, a cărei formulă arată astfel:
X=(A+C)· (A+B). Stabiliți dacă afirmația X este echivalentă cu afirmația: „Victor este un înotător bun și Victor cântă bine”.

8.
A) ; b) ;
c) ((X1® X2)® X3) u (X3 « X1); d) ((X® Y)Ù (Y® Z))® (X® Z).

9. Stabiliți adevărul afirmațiilor:
A) , , ;
b) , , ;
v) , , ;
G), , .

Legile logicii

Echivalențele formulelor logice propoziționale sunt adesea numite legile logicii.
Cunoașterea legilor logicii vă permite să verificați corectitudinea raționamentului și a dovezilor.
Încălcarea acestor legi duc la erori logice și contradicții care decurg din acestea.
Le enumerăm pe cele mai importante dintre ele:
1. Xº X Legea identității
2. Legea contradictiei
3. Legea mijlocului exclus
4. Legea dublei negații
5. XÙ Xº X , XÚ Xº C Legile idempotentei
6. C Ù U º U Ù C , C Ú U º U Ú C Legile comutativității (deplasării)
7. (C Ù U) Ù Z ºC Ù (U Ù Z) , (C Ú U) Ú Z º C Ú (U Ú Z) - Legile asociativității (compatibilității)
8. C Ù (U Ú Z) º (C Ù U) Ú (C Ù Z) , C Ú (U Ù Z) º (C Ú U) Ù (C Ú Z) - Legile distributivității (distribuției)
9. , legile lui De Morgan
10. XÙ 1º C , C Ú 0 º C
11. C Ù 0 º 0 , C Ú 1 º 1
12. C Ù (C Ú U) º C , C Ú (C Ù U) º C Legile de absorbție
13. (C Ú U) Ù ( Ú U) º U , (C Ù U) Ú ( Ú U) º U Lipirea legilor

legea 1 formulat de filosoful grec antic Aristotel. Legea identității afirmă că gândul conținut într-un enunț rămâne neschimbat pe tot parcursul argumentului în care apare această afirmație.

Legea contradicției spune că nicio propoziție nu poate fi adevărată în același timp cu negația ei.
„Acest măr este copt” și „Acest măr nu este copt”.

Legea mijlocului exclus spune că pentru fiecare afirmație există doar două posibilități: această afirmație este fie adevărată, fie falsă. Nu există a treia. „Astăzi primesc 5 sau nu-l primesc.” Fie o propoziție este adevărată, fie negația ei este adevărată.

Legea dublei negații. A nega negația unei afirmații este același lucru cu a afirma această afirmație.
„Nu este adevărat că 2× 2¹ 4”

Legile impotentei. Nu există exponenți și coeficienți în algebra logicii. Conjuncția de „factori” identici este echivalentă cu unul dintre ei.

Legile comutativității și asociativității. Conjuncția și disjuncția sunt similare cu semnele cu același nume pentru înmulțirea și adăugarea numerelor.
Spre deosebire de adunarea și înmulțirea numerelor, adunarea și înmulțirea logică sunt egale în raport cu distributivitatea: nu numai conjuncția este distributivă în raport cu disjuncția, dar disjuncția este distributivă în raport cu conjuncția.

Înțelesul legilor lui De Morgan(August de Morgan (1806-1871) - matematician și logician scoțian) poate fi exprimat în formulări verbale scurte:
- negaţia unui produs logic este echivalentă cu suma logică a negaţiilor factorilor.
- negaţia unei sume logice este echivalentă cu produsul logic al negaţiilor termenilor.

Puteți demonstra legile logicii:
1) folosirea tabelelor de adevăr;
2) cu ajutorul echivalenţelor.
Să demonstrăm legile lipirii și absorbției cu ajutorul echivalențelor:
1) (C Ú U) Ù ( Ú U) º (C + U) × ( + U) º C × + U × + U × U + C × U ºU × + U + C × U º U × +U (1 + C) º U × + U º U ( + 1) º U (Legea lipirii)

2) C Ù (C Ú U) º C × C + C × U º C + C × U º C (1 + U) º C (Legea absorbției)

Exercițiu. Demonstrați legile logicii folosind tabele de adevăr.

Transformări de identitate

Formule simplificate.

Exemplul 1 Simplificați formula (AÚB) (AÚC)
Soluţie.
a) Deschideți suporturile (A Ú B) (A ÚC) º A A Ú A C Ú B A Ú B C
b) Conform legii echivalenței A · A º A , prin urmare,
A A Ú A C ÚB A Ú B C º A ÚA C Ú B A Ú B C
c) În afirmațiile A și A C punem paranteze pe A și folosind proprietatea AÚ1º 1, obținem B C
d) Ca și la punctul c), tragem afirmația A.
AÚB A Ú B Cº A (1ÚB)ÚB Cº A Ú B C
Astfel, am demonstrat legea distributivității.

2. Transformări „absorbție” și „lipire”

Exemplul 2 Simplificați expresia АУ A B

Soluţie. A ÚA B º A (1 Ú B) º A - absorbție

Exemplul 3 Simplificaţi expresia A · B Ú A · - semne de adunare logică;
- semne de înmulțire logică.
Și vor fi folosite:
- semne de negaţie şi înmulţire logică;
- semne de negație și adunare logică.

Exemplul 5 Transformați formula astfel încât să nu folosească semne de adunare logice.
Soluţie. Să folosim legea dublei negații și apoi formula de Morgan.

Exemplul 6 Transformați formula astfel încât să nu folosească semnele înmulțirii logice.
Soluţie. Folosind formulele lui de Morgan și legea dublei negații, obținem:

Tema programului: Declarații și operațiuni asupra acestora.

Obiectivele lecției:

1) Rezumați cunoștințele teoretice pe tema: „Enunțuri și operații asupra lor”.

2) Luați în considerare algoritmi pentru rezolvarea sarcinilor pe tema „Enunțuri și operații asupra lor”, rezolvați probleme.

3) Să-și formeze capacitatea de a prezice propria activitate, capacitatea de a-și organiza activitatea și de a o analiza.

Perioada de grație: 1 oră.

Baza teoretica

Conceptul de bază al logicii matematice este conceptul de „enunț simplu”. O afirmație este de obicei înțeleasă ca orice propoziție declarativă care afirmă ceva despre ceva și, în același timp, putem spune dacă este adevărat sau fals în condiții date de loc și timp. Valorile logice ale afirmațiilor sunt „adevărate” și „false”.

Exemple de expresii.
1) Moscova se află pe Neva.
2) Londra este capitala Angliei.
3) Soimul nu este un peste.
4) Numărul 6 este divizibil cu 2 și 3.
Afirmațiile 2), 3), 4) sunt adevărate, iar afirmația 1) este falsă.
Evident, propoziția „Trăiască Rusia!” nu este o afirmație.
Există două tipuri de afirmații.
O afirmație, care este o singură declarație, este de obicei numită simplă sau elementară. Exemple de propoziții elementare sunt propozițiile 1) și 2).
Enunțurile care se obțin din cele elementare cu ajutorul conjunctivelor gramaticale „nu”, „și”, „sau”, „dacă .... atunci ...”, „atunci și numai atunci”, sunt de obicei numite complexe sau compuse .
Deci, afirmația 3) se obține din enunțul simplu „Șoimul este un pește” cu ajutorul negației „nu”, afirmația 4) se formează din enunțurile elementare „Numărul 6 este divizibil cu 2”, „Numărul 6 este divizibil cu 3”, legat de uniunea „și”.
În mod similar, enunțurile complexe pot fi obținute din enunțuri simple folosind conectivele gramaticale „sau”, „dacă și numai atunci”.
În algebra logicii, toate enunțurile sunt considerate numai din punctul de vedere al semnificației lor logice, iar conținutul lor lumesc este abstractizat. Se crede că fiecare afirmație este fie adevărată, fie falsă și nicio afirmație nu poate fi atât adevărată, cât și falsă.
Afirmațiile elementare sunt indicate prin litere mici ale alfabetului latin: x, y, z, ..., a, b, c, ...; valoarea adevărată a enunțului este numărul 1, iar valoarea falsă este litera numărul 0.
Dacă afirmaţia A adevărat, vom scrie a = 1, si daca A fals, atunci a = 0.

Operații logice asupra enunțurilor

Negare.

Negația afirmației x se numește propoziție nouă, ceea ce este adevărat dacă propoziția X fals și fals dacă afirmația X Adevărat.

Negarea unei declarații X marcat și citit "nu X" sau "nu este adevarat ca x".

Semnificațiile logice ale unui enunț pot fi descrise folosind un tabel.

Tabelele de acest fel sunt numite tabele de adevăr.
Lăsa X afirmație. Deoarece este și enunț, este posibil să se formeze negația enunțului, adică enunțul, care se numește dubla negație a enunțului. X. Este clar că semnificațiile logice ale afirmațiilor Xși se potrivesc.

De exemplu, pentru afirmația „Putin este președintele Rusiei”, negativul ar fi afirmația „Putin nu este președintele Rusiei”, iar dubla negație ar fi afirmația „Nu este adevărat că Putin nu este președintele al Rusiei”.

Conjuncție.

Conjuncția (înmulțirea logică) a două afirmații x și y se numește o nouă propoziție, care este considerată adevărată dacă ambele propoziții x și y adevărat și fals dacă cel puțin unul dintre ele este fals.
conjuncţie de propoziţii x și y notat cu simbolul x&y ( , xy), citit "x și y". zicale x și y sunt numiți membri ai conjuncției.
Valorile logice ale conjuncției sunt descrise de următorul tabel de adevăr:

De exemplu, pentru afirmațiile „6 este divizibil cu 2”, „6 este divizibil cu 3”, conjuncția lor va fi afirmația „6 este divizibil cu 2 și 6 este divizibil cu 3”, ceea ce este evident adevărat.

Din definiția operației de conjuncție se poate observa că uniunea „și” în algebra logicii este folosită în același sens ca și în vorbirea de zi cu zi. Dar în vorbirea obișnuită nu se obișnuiește să se combine două enunțuri care sunt departe unul de celălalt în conținut cu uniunea „și”, iar în algebra logicii, se ia în considerare conjuncția oricăror două enunțuri.

Disjuncția

Disjuncția (adunarea logică) a două afirmații x și y se numește o nouă propoziție care este considerată adevărată dacă cel puțin una dintre propoziții X y adevărat și fals dacă ambele sunt false. Disjuncția propozițiilor X y notat cu simbolul "x V y", citit "x sau y". zicale X y se numesc termeni ai disjuncţiei.
Valorile logice ale disjuncției sunt descrise de următorul tabel de adevăr:

În vorbirea de zi cu zi, uniunea „sau” este folosită într-un sens diferit: exclusiv și neexclusiv. În algebra logicii, uniunea „sau” este întotdeauna folosită într-un sens neexclusiv.

Implicare.

Implicația a două afirmații x și y Se numește o nouă propoziție care este falsă dacă x este adevărat și y este fals și adevărat în toate celelalte cazuri.
Implicația afirmațiilor X y notat cu simbolul , citit „dacă x, atunci y” sau „din x urmează y”. afirmație X numită o condiție sau o premisă, o declarație la- consecință sau concluzie, afirmație urmărire sau implicare.

Valorile logice ale operației de implicare sunt descrise de următorul tabel de adevăr:

Folosirea cuvintelor „dacă....atunci...” în algebra logicii diferă de utilizarea lor în vorbirea de zi cu zi, unde avem tendința de a crede că dacă enunțul X fals, apoi afirmația „Dacă x, atunci y” nu are deloc sens. În plus, construirea unei propoziții de forma „dacă x atunci y”în vorbirea de zi cu zi, ne referim întotdeauna la propoziţia la rezultă din propunere X. Folosirea cuvintelor „dacă... atunci...” în logica matematică nu necesită acest lucru, deoarece sensul enunțurilor nu este luat în considerare în ea.
Implicația joacă un rol important în demonstrațiile matematice, deoarece multe teoreme sunt formulate în formă condiționată. „Dacă x, atunci y”. Dacă totuşi se ştie că X este adevărat și adevărul implicației este dovedit , atunci putem concluziona că concluzia este adevărată la .

Echivalenţă.

Echivalența a două afirmații x și y se numește o nouă propoziție, care este considerată adevărată atunci când ambele propoziții X y fie ambele adevărate, fie ambele false, și false în toate celelalte cazuri.

Echivalența declarației X y notat cu simbolul, citit „pentru x, este necesar și suficient ca y” sau „x dacă și numai dacă y”. zicale X y se numesc termeni de echivalenţă.
Valorile logice ale operației de echivalență sunt descrise de următorul tabel de adevăr:

Echivalența joacă un rol important în demonstrațiile matematice. Se știe că un număr semnificativ de teoreme sunt formulate sub formă de condiții necesare și suficiente, adică sub formă de echivalență. În acest caz, cunoscând adevărul sau falsitatea unuia dintre cei doi termeni de echivalență și dovedind adevărul echivalenței în sine, ajungem la concluzia că al doilea termen de echivalență este adevărat sau fals.

Sarcini practice

1. Stabiliți structura logică a următoarelor propoziții și scrieți-le în limbajul logicii propoziționale:

Dacă metalul este încălzit, se topește.
Nu este adevărat că disputele filozofice sunt insolubile.
Banii sunt un produs al dezvoltării spontane a relațiilor de mărfuri și nu rezultatul unui acord sau al oricărui alt act conștient.

2. Notează următoarele afirmații într-o formulă logică:

a) dacă afară plouă, atunci trebuie să iei o umbrelă cu tine sau să stai acasă;

B) dacă - dreptunghiular și laturile sunt egale, atunci

3. Verificați adevărul afirmației:

si daca, .

b) dacă, .

c) dacă, .

4. Verificați adevărul afirmației:

a) Ca să merg mâine la curs, trebuie să mă trezesc devreme. Dacă merg azi la cinema, mă voi culca târziu. Dacă mă culc târziu, mă trezesc târziu. Prin urmare, ori nu voi merge la cinema, ori nu voi merge la cursuri.

b) Voi merge fie la cinema, fie la piscină. Dacă merg la cinema, voi avea plăcere estetică. Dacă merg la piscină, voi avea plăcere fizică. Prin urmare, dacă voi obține plăcere fizică, nu voi obține plăcere estetică.

5 . La întrebarea: „Care dintre cei trei elevi a studiat matematica discretă?” s-a primit răspunsul corect: „Dacă l-a studiat pe primul, atunci l-a studiat pe al treilea, dar nu este adevărat că dacă l-a studiat pe al doilea, atunci l-a studiat pe al treilea”. Cine a studiat matematica discretă?

6. Stabiliți care dintre cei patru elevi a promovat examenul, dacă se știe:

dacă a trecut primul, atunci a trecut al doilea;

dacă a trecut al doilea, atunci a trecut al treilea sau primul nu a trecut;

dacă al patrulea nu trecea, atunci trecea primul, iar al treilea nu trecea;

dacă a trecut al patrulea, atunci a trecut primul.

Întrebări de control

1. Ce elemente sunt incluse în limbajul logicii?

2. Ce modalități de stabilire a validității unei formule a logicii cunoașteți?

Bibliografie

Practica #10-11

Tema programului: Formule de algebră propozițională.

Printre posibilele valori de adevăr ale unei variabile lingvistice Adevăr două valori atrag o atenție deosebită, și anume mulțimea goală și intervalul unitar, care corespund celor mai mici și mai mari elemente (în ceea ce privește includerea) rețelei de submulțimi de intervale fuzzy. Importanța acestor valori de adevăr se datorează faptului că pot fi interpretate ca valori de adevăr nedefinitși necunoscut respectiv. Pentru comoditate, vom desemna aceste valori de adevăr prin simboluri și , înțelegând că și sunt determinate de expresii

Valori necunoscutși nedefinit, interpretate ca grade de apartenenţă, sunt folosite şi în reprezentarea mulţimilor fuzzy de tip 1. În acest caz, există trei posibilităţi de exprimare a gradului de apartenenţă a unui punct în: 1) un număr din intervalul ; 2) ( nedefinit); 3) (necunoscut).

Să luăm în considerare un exemplu simplu. Lăsa

Luați un subset neclar al mulțimii formei

În acest caz, gradul de apartenență a elementului în mulțime este necunoscut, iar gradul de membru este nedefinit. Într-un caz mai general, poate fi

unde se înțelege că gradul de apartenență al unui element într-o mulțime este parțial necunoscut, iar membrul este interpretat după cum urmează:

. (6.56)

Este important să înțelegeți clar diferența dintre și. Când spunem că gradul de apartenență al unui punct dintr-o mulțime este , ne referim la funcția de apartenență nedefinit la punctul . Să presupunem, de exemplu, că este mulțimea numerelor reale și este o funcție definită pe mulțimea numerelor întregi și , dacă - par și , dacă - impar. Atunci gradul de apartenență al numărului la mulțime este , și nu 0. Pe de altă parte, dacă ar fi definit pe mulțimea numerelor reale și dacă și numai dacă este un număr par, atunci gradul de apartenență al numărului. la mulțime ar fi egal cu 0.

Deoarece putem calcula valorile de adevăr ale propozițiilor și, sauși nu având în vedere valorile de adevăr lingvistice ale afirmațiilor și , este ușor de calculat valorile , , , când . Să presupunem, de exemplu, că

, (6.57)

. (6.58)

Aplicând principiul generalizării, ca în (6.25), obținem

, (6.59)

După simplificare (6.59) se reduce la expresia

. (6.61)

Cu alte cuvinte, valoarea de adevăr a afirmației și, Unde , este o submulțime neclară a intervalului , al cărei grad de apartenență a punctului este egal cu (funcția de membru ) pe intervalul .

Orez. 6.4. Conjuncția și disjuncția valorilor de adevăr ale unei afirmații cu valoarea de adevăr este necunoscută ().

În mod similar, constatăm că valoarea de adevăr a afirmației sau exprimat ca

. (6.62)

Trebuie remarcat faptul că expresiile (6.61) și (6.62) sunt ușor de obținut folosind procedura grafică descrisă mai sus (vezi (6.38) și mai jos). Un exemplu care ilustrează acest lucru este prezentat în Fig. 6.4.

Revenind la caz, aflăm

(6.63)

si asemanator pentru .

Este instructiv să urmărim ceea ce se întâmplă cu relațiile de mai sus atunci când le aplicăm unui anumit caz de logică cu două valori, adică în cazul în care mulțimea universală are forma

sau în forma mai familiară

unde înseamnă Adevărat, A - fals. Deoarece există, putem identifica valoarea de adevăr necunoscut cu sens Adevărat sau fals, adică

Logica rezultată are patru valori de adevăr, și este o generalizare a logicii cu două valori în sensul Observației 6.5.

Deoarece setul universal de valori de adevăr constă din doar două elemente, este recomandabil să se construiască tabele de adevăr pentru operații și în această logică cu patru valori în mod direct, adică fără a utiliza formulele generale (6.25), (6.29) și ( 6.31). Astfel, aplicând principiul generalizării operației, obținem imediat

de unde rezultă neapărat că

Pe parcurs, ajungem la definiția obișnuită a conectivului ⟹ în logica cu două valori sub forma următorului tabel de adevăr:

După cum arată exemplul de mai sus, noțiunea de valoare de adevăr necunoscutîn combinație cu principiul generalizării ajută la înțelegerea unora dintre conceptele și relațiile logicii obișnuite cu două și trei valori. Aceste logici, desigur, pot fi considerate cazuri degenerate de logica fuzzy, în care adevărul valorează necunoscut este întregul interval de unitate, nu setul 0 + 1.

Aici: 1 - adevărat, 0 - fals.

1. X: triunghi ABC - acut. X: Nu este adevărat că triunghiul ABC este acut. Este ca: X: triunghi ABC - drept sau obtuz
2. A: Ivanova M. La examenul la matematică a primit 4. : Nu este adevărat că Ivanova M. la matematică a primit 4.

Definiție: Disjuncția dintre enunțurile A și B este o afirmație AB care este adevărată cu condiția ca cel puțin una dintre afirmațiile A sau B să fie adevărată.

Se citește „A sau B”.

Tabelul de adevăr pentru AB

Exemplu: 1. De data aceasta s-a prezentat inculpatul si a avut loc procesul. - adevărul

2. Într-un triunghi dreptunghic, suma oricăror două unghiuri este mai mare sau egală cu al treilea unghi, iar ipotenuza este mai mică decât catetul. - Minciuna

Definiție: O implicație a afirmațiilor A și B este o afirmație AB care este falsă numai dacă A este adevărat și B este fals.

Se citește: „Dacă A, atunci B”.

tabelul de adevăr

Exemplu: 1. Dacă trec testul, voi merge la cinema.

2. Dacă triunghiul este isoscel, atunci unghiurile de la baza lui sunt egale. Definiție: Un echivalent al afirmațiilor A și B este o afirmație AB care este adevărată dacă și numai dacă A și B au același adevăr (adică fie ambele sunt adevărate, fie ambele sunt false).

Ei citesc: „A dacă și numai dacă B” sau „A este necesar și suficient pentru B”

tabelul de adevăr

A doua sarcină, rezolvată cu ajutorul algebrei propoziționale, este de a determina adevărul unei anumite propoziții pe baza compilării formulei acesteia (procesul de formalizare) și al compilarii unui tabel de adevăr.

Exemplu: Dacă Saratov este situat pe malul Nevei, atunci urșii polari trăiesc în Africa.

R: Saratov este situat pe malul râului Neva;

Î: Urșii polari trăiesc în Africa

Definiție: O formulă care este adevărată, indiferent de ce valori iau variabilele sale propoziționale, se numește tautologie sau o formulă identic adevărată.

Definiție: Formulele F 1 și F 2 se numesc echivalente dacă echivalentul lor este o tautologie.

Definiție: Dacă formulele F 1 și F 2 sunt echivalente, atunci propozițiile Р 1 și Р 2 care inițiază aceste formule sunt numite echivalente în logica propozițională.

Echivalențele de bază, cele mai comune se numesc legile logicii. Enumerăm câteva dintre ele:

1. X X - legea identității
2. X L - legea contradictiei
3. XI - legea excluderii celui de-al treilea
4. X - legea dublei negații

5. legi ale comutativității
6. X (Y Z) (X Y) Z legea asociativității

X (Y Z) (X Y) Z legea distributivă

7. Legile lui De Morgan

8. legi de articulare a unei variabile cu o constantă

Folosind legile logicii, puteți transforma formule.

4. Din multele formule care sunt echivalente între ele, luați în considerare două. Sunt forma normală conjunctivă perfectă (CKNF) și forma normală disjunctivă perfectă (PDNF). Ele sunt construite pentru o formulă dată pe baza tabelului său de adevăr.

Clădirea SDNF:

-- sunt selectate rândurile corespunzătoare valorilor de adevăr (1) ale formulei date;
-- pentru fiecare linie selectată, compunem o conjuncție de variabile sau negațiile acestora, astfel încât seturile de valori ale variabilelor prezentate în linie să corespundă cu valorile adevărate ale conjuncției (pentru aceasta, trebuie să luați variabilele care în această linie au luat valorile fals (0) cu semn de negație, iar variabilele , luând valori de adevăr (1) fără negație);
-- se face o disjuncție a conjuncțiilor rezultate.

Din algoritm rezultă că pentru orice formulă este posibil să se compună un SDNF și, în plus, singurul, dacă formula nu este identic falsă, adică. acceptând numai valori false.

Compilarea SKNF se realizează conform următorului algoritm:

-- selectați acele rânduri ale tabelului în care formula evaluează fals (0);
-- din variabilele din fiecare astfel de rând, faceți o disjuncție, care ar trebui să ia valorile - fals (0). Pentru a face acest lucru, toate variabilele trebuie să o introducă cu valoarea false, de aceea cele care sunt adevărate (1) trebuie înlocuite cu negația lor;
- faceți o conjuncție din disjuncțiile obținute.

Evident, orice formulă care nu este o tautologie are SKNF.

SDNF și SKNF sunt utilizate pentru a obține consecințe din această formulă.

Exemplu: Faceți un tabel de adevăr al SDNF și SKNF pentru formula: .

Tabelul de adevăr al SDNF și SKNF

5. Luați în considerare forma propozițională „Râul se varsă în Marea Neagră”. Conține o variabilă și poate fi reprezentată ca „Râul x se varsă în Marea Neagră”.

În funcție de valorile variabilei X, propoziția este fie adevărată, fie falsă, adică. este specificată maparea unui set de râuri pe o mulțime de două elemente. Să notăm această mapare, atunci:

Astfel, avem o funcție, toate valorile căreia aparțin mulțimii.

Definiție: O funcție ale cărei valori aparțin tuturor unei mulțimi se numește predicat.

Literele care denotă predicate sunt numite simboluri predicate.

Predicatele pot fi setate:

a) o formulă propozițională,

b) formula, i.e. specificând interpretarea simbolului predicat,

c) o masă.

1) P - „se varsă în Marea Neagră”.

Această formulă înseamnă că „râul a se varsă în Marea Neagră”.

2) Predicatul P este dat de formula propozițională: „să fie număr prim din mulțimea primelor 15 numere naturale”.
3) În formă tabelară, predicatul are forma:

Sfera predicatelor poate fi orice set.

Dacă predicatul își pierde sensul pentru orice set de variabile de intrare, atunci se presupune în general că acest set corespunde valorii lui A.

Dacă predicatul conține o variabilă, atunci se numește unară, două variabile - cu două locuri, n variabile - predicat cu n loc.

Pentru a traduce texte în limbajul predicatelor și a determina adevărul lor, este necesar să se introducă operații logice asupra predicatorilor și cuantificatorilor.

Operațiile se efectuează asupra predicatelor în același mod: negații, conjuncții, disjuncții, implicații, echivalențe.

Definiție: O submulțime a mulțimii M pe care este dat predicatul P, constând din acele și numai acele elemente ale lui M care corespund valorii ȘI a predicatului P, se numește mulțime de adevăr a predicatului P.

Setul de adevăr este notat.

Definiție: Negația unui predicat P este un predicat care este fals pentru acele seturi de valori variabile care fac P adevărat și adevărat pentru acele seturi de valori variabile care fac P fals.

Negativ este indicat.

Fii student la ABC.

Nu fii student la ABiK.

Dacă, atunci mulțimea, unde M este mulțimea pe care sunt date predicatele P și Q.

Definiție: O conjuncție de predicate este un predicat care este adevărat pentru acele și numai acele valori ale variabilelor incluse în ea care fac ambele predicate și adevărate.

fii fotbalist

A fi student

: fii fotbalist și fii student.

Definiție: o disjuncție de predicate este un predicat care este fals pentru acele seturi de variabile care fac ambele predicate false

să fie un număr natural par

fi un număr natural impar

: să fie un număr natural.

Definiție: O implicație a predicatelor este un predicat care este fals pentru acele și numai acele seturi de variabile incluse în el care se transformă într-un predicat adevărat și - într-unul fals.

Desemnat:

Fii un număr prim din mulțimea N

fi un număr impar

Fals și adevărat pentru alte numere naturale.

Definiție: O echivalență de predicat este un predicat care devine adevărat dacă ambele predicate sunt adevărate sau ambele sunt false.

Desemnat:

- „câștigă”, adică x câștigă y

Mai bine să cunoști istoria șahului, x știe mai bine decât y

înseamnă că x îl bate pe y la șah dacă și numai dacă cunoaște mai bine teoria.

Definiție: Predicatul decurge din predicat dacă implicația este adevărată pentru oricare dintre valorile variabilelor incluse în acesta.

Sunt desemnate: .

A fi student