Deoarece pentru orice set de valori variabile din domeniul de definire al predicatului se transformă într-o declarație, aceleași operații logice sunt definite pe setul de predicate ca și pentru enunțuri. În același timp, conținutul predicatelor este abstractizat. Predicatele sunt considerate numai în ceea ce privește semnificația lor. Cu alte cuvinte, predicatele echivalente nu diferă.

Definiția 1: Prin negare - predicat local
, definit pe platou
, numit nou - predicat local definit pe aceeași mulțime. Indicat de:
. Se scrie: „Nu este adevărat că
" Predicat
evaluează la adevărat numai pentru acele argumente pentru care valoarea predicatului
există o „minciună” și invers. Cu alte cuvinte, predicatul
satisfăcut de acele şi numai acele argumente care nu satisfac predicatul dat
.

Predicat dublu
evaluează la adevărat pentru acele și numai acele valori variabile
din domeniul definirii predicatului, pentru care predicatul
ia valoarea „fals”, adică...

Definiția 2: Prin conjuncție - predicat local
, definit pe platou
, Și
- predicat local
, definit pe platou
, numit nou
- predicat local definit pe o mulțime
, notat cu Scrie: "
Și
" Acest predicat evaluează ca adevărat numai pentru acele valori de argument pentru care predicatele
Și
ia simultan valoarea „adevărat”.

Dacă, de exemplu,
- un predicat cu două locuri definit pe o mulțime
, A
- un predicat unar definit pe o mulțime , apoi conjuncția acestor predicate
există un predicat cu trei locuri definit pe mulțime
. Acest nou predicat se evaluează ca adevărat pentru astfel de triple de elemente
,
,
,
, pentru care
Și
.

Disjuncția, implicarea și echivalența predicatelor sunt definite în mod similar. Valorile predicatelor pentru valori date ale variabilelor libere sunt determinate în conformitate cu operații logice specifice. Operațiuni
poate fi aplicat și la predicate care au variabile comune. În acest caz, numărul de variabile ale predicatului compus rezultat va fi egal cu numărul de variabile diferite din membrii săi. În special, dacă operațiuni
se aplică la doi - predicate locale în funcție de aceleași variabile, apoi ca urmare a aplicării operațiilor logice obținem - un predicat local în funcție de aceleași variabile.

Lăsa
Și
- Două - predicate locale în funcţie de aceleaşi variabile. Apoi:

a) setul de adevăr al unei conjuncții este egal cu intersecția setului de adevăr al membrilor ei;

b) setul de adevăr al unei disjuncții este egal cu unirea seturilor de adevăr ale membrilor săi.

Nu este greu să arătăm că conjuncția a două predicate este identic adevărată dacă și numai dacă ambele predicate date sunt identic adevărate. O disjuncție a două predicate este satisfiabilă dacă și numai dacă cel puțin unul dintre ele este satisfiabil. O disjuncție a două predicate este identic falsă dacă și numai dacă ambele predicate date sunt identic false. Implicația a două - predicate locale în funcție de aceleași argumente, este identic adevărat dacă și numai dacă concluzia sa este o consecință a premiselor. Echivalența a doi - predicatele locale care depind de aceleași variabile sunt identic adevărate dacă și numai dacă ambele predicate sunt echivalente.

Orice ecuație (inegalitate) care conține variabile este un predicat definit pe aceeași mulțime pe care este dată ecuația (inegalitatea). Mulțimea soluțiilor unei ecuații (inegalitatea) nu este altceva decât mulțimea de adevăr a predicatului. Aceasta înseamnă că atunci când înlocuiți rădăcinile unei ecuații (sau soluțiile unei inegalități) în loc de necunoscute, se vor obține enunțuri adevărate. Dacă, în loc de variabile, numerele care nu sunt soluții sunt substituite în ecuație (inegalitate), atunci se vor obține afirmații false. Orice sistem de ecuații (inegalități) poate fi considerat ca o conjuncție de predicate. Rezolvarea unui sistem înseamnă găsirea domeniului de adevăr al conjuncției de predicate. Un set de ecuații (inegalități) nu este altceva decât o disjuncție de predicate. Echivalența ecuațiilor (inegalităților) înseamnă echivalența predicatelor corespunzătoare.

Dacă
, apoi spun că argumentul
satisface acest predicat. De exemplu, numărul 3 satisface predicatul
, iar numărul 1 nu-l mulțumește.

În logica matematică, pe lângă operațiile logice asupra predicatelor, există și operații cuantificare , care fac logica predicatelor mult mai bogată în conținut în comparație cu logica propozițională. În acest caz, ca și în cazul celor mai simple operații, predicatele sunt considerate numai din punctul de vedere al semnificațiilor lor, adică. predicatele echivalente nu diferă. Operațiile principale de cuantificare sunt: ​​cuantificatorul general și cuantificatorul de existență, care sunt duale între ele.

Definiția 3: Lăsa
- un predicat unar definit pe o mulțime nevidă

într-o declarație:
(se citește: „pentru oricine efectuat
"), numit cuantificator general (sau o declarație universală). Afirmație
adevărat dacă și numai dacă predicatul dat
identic adevărat (adică domeniul de adevăr al predicatului
coincide cu setul
).

Simbol se numeste cuantificator general fata de o variabila , scrie: „pentru toată lumea " sau "pentru toată lumea " Ei spun că vorba
este rezultatul aplicării unui cuantificator general unui predicat
. Simbol provine din cuvântul englezesc „All” (tradus: „all”).

De exemplu, pentru predicate "
" Și "
", definite pe mulțimea numerelor reale, enunțurile universale corespunzătoare vor avea forma:
– „fiecare număr real este egal cu el însuși” (adevărat) și
– „fiecare număr real este mai mare decât 2” (fals).

Teorema 1: Dacă
- un predicat de un loc definit pe o mulțime finită constând din
elemente ,,…,, atunci enunțul universal corespunzător este echivalent cu conjuncția
zicale:

Dovada. Într-adevăr, conform definiției cuantificatorului general, enunțul

identic adevărat, adică când totul este adevărat
enunţuri obţinute dintr-un predicat dat prin înlocuirea variabilei argumente ,,…,respectiv. Ultima observație este posibilă dacă și numai dacă conjuncția acestora
declarații. Acestea. termenii echivalenței sunt atât adevărați, cât și falși și, prin urmare, echivalența este dovedită.

Teorema arată că pentru predicate definite pe o mulțime finită, operația de aplicare a unui cuantificator general poate fi exprimată printr-o conjuncție. Pentru predicate definite pe o mulțime infinită, acest lucru nu se poate face; în acest caz, operația de aplicare a cuantificatorului general este complet nouă.

Definiție 4: Lăsa
- un predicat unar definit pe o mulțime
. Operație care transformă un predicat
într-o declarație
(se citește: „există , satisfacand predicatul
"), numit cuantificator de existență (sau o afirmație existențială). Afirmație
va fi adevărat dacă și numai dacă predicatul
executabil. Această afirmație va fi falsă dacă predicatul
identic fals.

Simbol se numeste cuantificator existential fata de o variabila . Se poate citi: „există astfel încât
", sau "va exista așa ceva , Ce
" Simbol provine din cuvântul englezesc „Exist” (există).

Teorema 2: Dacă
– un predicat de un loc definit pe o mulțime finită de
elemente ,,…,, atunci afirmația existențială corespunzătoare este echivalentă cu disjuncția
zicale:

Dovada: Definiție: afirmație
va fi fals dacă și numai dacă toate sunt false
enunţuri care se obţin dintr-un predicat dat prin înlocuirea unei variabile argumente ,,…,respectiv. Ultima observație este posibilă dacă și numai dacă disjuncția acestora
declarații. Acestea. termenii unei echivalențe sunt atât adevărați, cât și falși, prin urmare echivalența este adevărată.

Această teoremă afirmă că pentru predicate definite pe mulțimi finite, operația de aplicare a unui cuantificator existențial poate fi exprimată în termeni de disjuncție. Pentru predicate definite pe mulțimi infinite, acest lucru nu se poate face. Operația de aplicare a cuantificatorului existențial este atunci complet nouă.

Trebuie amintit că pentru orice predicat
, definit pe platou
expresii
Și
Acestea sunt afirmații, nu predicate. Prezența variabilei aici este pur extern, legat de metoda de notare. Prin urmare variabila , incluse în expresii
Și
, numit variabila asociata, spre deosebire de variabila inclusă în predicat
, unde este numită variabila gratuit. Dacă aplicăm operația cuantificatorilor „atârnați” unui predicat cu două locuri
de o variabilă, apoi ca rezultat predicatul cu două locuri se va transforma într-un predicat cu un singur loc cu o variabilă liberă. Raționament similar poate fi efectuat pentru a doua variabilă. Se numește variabila asupra căreia a fost aplicat cuantificatorul legătură variabil. Dacă aplicăm operația de cuantificare la - un predicat local cu privire la o variabilă, apoi se va transforma în
- predicat local.

Dacă într-un predicat toate variabilele sunt legate, atunci acest predicat este o declarație. De exemplu, luați în considerare predicatul
, definit pe un set de numere. Să facem o declarație
. Aceasta este o afirmație falsă care afirmă că există un astfel de număr , care este mai mare decât orice număr (- număr singular pentru toată lumea ). Schimbând cuantificatorii, obținem o nouă afirmație:
. Această afirmație afirmă că pentru orice număr poți alege un număr ca acesta , că inegalitatea este valabilă
(pentru fiecare există un număr ). Această afirmație este adevărată. Se poate observa că atunci când cuantificatorii sunt rearanjați, sensul enunțului se schimbă. Prin urmare, rearanjarea spre deosebire de cuantificatori este o operație inacceptabilă. Cuantificatorii cu același nume pot fi interschimbați. Mai mult, cuantificatorii cu același nume pot fi combinați într-unul singur, de exemplu: . De asemenea, este inacceptabil să folosiți mai mulți cuantificatori pentru aceeași variabilă, de exemplu:
.

Definiția 5: printr-o declarație universală , corespunzătoare - predicat local
, definit pe platou

aplicare consistentă cuantificatori de generalitate asupra variabilelor
in orice ordine.

Această afirmație este desemnată și citită pe scurt după cum urmează: „pentru toată lumea
efectuat
».

Definiția 6: printr-o afirmație existențială, relevante - predicat local
, definit pe platou
, este o declarație obținută din
aplicare consistentă cuantificatori de existență peste variabile
in orice ordine.

Afirmația existențială rezultată se notează și se citește astfel: „există un astfel de set
, care se realizează
».

De exemplu, pentru predicatul cu două locuri "
» afirmațiile corespunzătoare au forma:
– „pentru oricare două numere reale: primul este mai mare decât al doilea” (fals) și
– „există două numere reale, dintre care primul este mai mare decât al doilea” (adevărat).

Teorema 3: (Condiție pentru adevărul identic al unui predicat cuantificat).

‑predicat local derivat din - predicat local
, definit pe platou
, prin aplicarea unui cuantificator general cu privire la orice variabilă, este identic adevărat dacă și numai dacă predicatul dat
– identic adevărat.

Dovada: Într-adevăr, să fie dat
- predicat local
, definit pe platou
. Prin definiție, acest predicat va fi identic adevărat dacă și numai dacă valoarea lui pentru valorile arbitrare ale argumentelor este „adevărată”. Aceasta înseamnă că afirmația universală este adevărată

, definit pe platou
. Ultima observație este posibilă dacă și numai dacă predicatul
– identic adevărat, dar pentru că argumente
au fost alese în mod arbitrar, atunci aceasta este echivalentă cu adevărul identic al dat - predicat local
. Teorema a fost demonstrată.

Teorema 4: (Condiție pentru falsitatea identică a unui predicat cuantificat).

-predicat local derivat din - predicat local
, definit pe platou
, prin aplicarea unui cuantificator existențial cu privire la o variabilă, este identic fals dacă și numai dacă predicatul dat este identic fals.

Dovada: Să avem
- predicat local
, definit pe platou
. Va fi identic fals dacă și numai dacă valoarea sa pentru argumente luate în mod arbitrar
există o „minciună”. Aceasta înseamnă că afirmația existențială este falsă
, corespunzător predicatului unar
, definit pe platou
. Acesta din urmă este posibil dacă și numai dacă predicatul
este identic fals, iar din moment ce argumente
au fost alese aleatoriu, apoi asta - predicat local
este identic fals. Q.E.D.

Până acum am pus în contrast predicate cu propoziții. Cu toate acestea, este mai convenabil să numărați declarațiile 0 - predicate locale. Atunci oricare două afirmații adevărate și oricare două afirmații false ar trebui considerate echivalente între ele.

Conceptul de predicat

Definiția 1

Predicat- o declarație care conține variabile care iau valoarea $1$ sau $0$ (adevărat sau fals) în funcție de valorile variabilelor.

Exemplul 1

De exemplu, expresia $x=x^5$ este un predicat deoarece este adevărat pentru $x=0$ sau $x=1$ și fals pentru toate celelalte valori ale lui $x$.

Definiția 2

Se numește o mulțime pe care un predicat acceptă numai valori adevărate set de adevăr al predicatului$I_p$.

Predicatul este numit identic adevărat, dacă pe orice set de argumente se evaluează la adevărat:

$P (x_1, \dots, x_n)=1$

Predicatul este numit identic fals, dacă pe orice set de argumente se evaluează ca fals:

$P (x_1, \dots, x_0)=0$

Predicatul este numit fezabil, dacă se evaluează ca adevărat pe cel puțin un set de argumente.

Deoarece predicatele pot lua doar două valori (adevărat/fals sau $0/1$), apoi le pot fi aplicate toate operațiile algebrei logice: negație, conjuncție, disjuncție etc.

Exemple de predicate

Fie predicatul $R(x, y)$: $“x = y”$ desemnează relația de egalitate, unde $x$ și $y$ aparțin mulțimii numerelor întregi. În acest caz, predicatul R va fi adevărat pentru toți egali $x$ și $y$.

Un alt exemplu de predicat este WORKS($x, y, z$) pentru relația „$x$ funcționează în orașul y pentru compania $z$”.

Un alt exemplu de predicat este LIKE($x, y$) pentru „x-i place y” pentru $x$ și $y$, care aparțin lui $M$ - mulțimea tuturor oamenilor.

Astfel, un predicat este tot ceea ce este afirmat sau negat despre subiectul judecății.

Operații asupra predicatelor

Să luăm în considerare aplicarea operațiilor de algebră logică la predicate.

Operatii logice:

Definiția 3

Conjuncția a două predicate $A(x)$ și $B(x)$ sunt un predicat care capătă o valoare adevărată pentru acele și numai acele valori de $x$ din $T$ pentru care fiecare dintre predicate capătă o valoare adevărată și o valoare falsă în orice moment.în toate celelalte cazuri. Setul de adevăr $T$ al unui predicat este intersecția setului de adevăr al predicatelor $A(x)$ și $B(x)$. De exemplu: predicat $A(x)$: „$x$ este un număr par”, predicatul $B(x)$: „$x$ este divizibil cu $5$”. Astfel, predicatul ar fi „$x$ este un număr par și este divizibil cu $5$” sau „$x$ este divizibil cu $10$”.

Definiția 4

Disjuncția a două predicate $A(x)$ și $B(x)$ sunt un predicat care evaluează fals pentru acele și numai acele valori de $x$ de la $T$ pentru care fiecare dintre predicate evaluează fals și evaluează adevărat în toate celelalte cazuri. Setul de adevăr al unui predicat este uniunea domeniilor de adevăr ale predicatelor $A(x)$ și $B(x)$.

Definiția 5

Negarea unui predicat $A(x)$ este un predicat care se evaluează ca adevărat pentru toate valorile lui $x$ în $T$ pentru care $A(x)$ evaluează ca fals și invers. Mulțimea de adevăr a predicatului $A(x)$ este complementul lui $T"$ la mulțimea $T$ din mulțimea $x$.

Definiția 6

Implicația predicată $A(x)$ și $B(x)$ este un predicat care este fals pentru acele și numai acele valori ale lui $x$ din $T$ pentru care $A(x)$ este adevărat și $B(x )$ este fals și se evaluează ca adevărat în toate celelalte cazuri. Se citește: „Dacă $A(x)$, atunci $B(x)$”.

Exemplul 2

Fie $A(x)$: „Numărul natural $x$ este divizibil cu $3$”;

$B(x)$: „Numărul natural $x$ este divizibil cu $4$”.

Să creăm un predicat: „Dacă un număr natural $x$ este divizibil cu $3$, atunci este și divizibil cu $4$.”

Mulțimea de adevăr a unui predicat este unirea mulțimii de adevăr a predicatului $B(x)$ și complementul la mulțimea de adevăr a predicatului $A(x)$.

Pe lângă operațiile logice, operațiile cuantice pot fi efectuate pe predicate: utilizarea cuantificatorului universal, a cuantificatorului de existență etc.

Cuantificatori

Definiția 7

Cuantificatori-- operatori logici, a căror aplicare la predicate îi transformă în afirmații false sau adevărate.

Definiția 8

Cuantificator-- operații logice care limitează domeniul de adevăr al unui predicat și creează o declarație.

Cele mai frecvent utilizate cuantificatori sunt:

cuantificator universal (notat cu simbolul $\forall x$) - expresia „for all $x$” (“for any $x$”);

cuantificator de existență (notat cu simbolul $\există x$) - expresia „există $x$ astfel încât...”;

cuantificator de unicitate și existență (notat cu $\exists !x$) - expresia „există exact un $x$ astfel încât...”.

În logica matematică există un concept legând sau cuantificare, care denotă atribuirea unui cuantificator unei formule.

Exemple de utilizare a cuantificatorilor

Fie predicatul „$x$ este un multiplu de $7$”.

Folosind cuantificatorul universal, putem scrie următoarele afirmații false:

orice număr natural este divizibil cu $7$;

fiecare număr natural este divizibil cu $7$;

toate numerele naturale sunt divizibile cu $7$;

care va arăta astfel:

Poza 1.

Pentru a scrie afirmații adevărate folosim cuantificator de existență:

există numere naturale care sunt divizibile cu $7$;

există un număr natural care este divizibil cu $7$;

cel puțin un număr natural este divizibil cu $7$.

Intrarea va arăta astfel:

Figura 2.

Fie dat predicatul pe mulțimea $x$ de numere prime: „Un număr prim este impar”. Punând cuvântul „oricare” în fața predicatului, obținem o afirmație falsă: „Orice număr prim este impar” (de exemplu, $2$ este un număr prim par).

Punem cuvântul „există” în fața predicatului și obținem o afirmație adevărată: „Există un număr prim care este impar” (de exemplu, $x=3$).

Astfel, un predicat poate fi transformat într-un enunț prin plasarea unui cuantificator în fața predicatului.

Operații pe cuantificatoare

Pentru a construi negația enunțurilor care conțin cuantificatori, folosim regula de negație a cuantificatorilor:

Figura 3.

Să luăm în considerare propozițiile și să alegem predicate dintre ele, indicând domeniul de adevăr al fiecăreia dintre ele.

1 . Operațiune de negație.

Negare predicat P(x), dat pe platou X, este un predicat definit pe aceeași mulțime și adevărat pentru acele și numai acele valori XX, sub care predicatul P(x) capătă sensul unei minciuni.

2 . Operația conjuncției.

Conjuncție predicate P(x)Și Q(x), definit pe platou X, se numește predicat P(x)Q(x), dat pe același set și transformându-se într-un enunț adevărat pentru acele și numai acele valori XX,în care ambele predicate capătă valori de adevăr.

Dacă desemnăm TR P(x), TQ- setul de adevăr al predicatului Q(x), și setul de adevăr al conjuncției lor TPÙQ, apoi, se pare, TPÙQ = TP Ç T.Q.

Să demonstrăm această egalitate.

1. Lasă A X si se stie ca AÎ TPÙQ . Prin definiția unui set de adevăr, aceasta înseamnă că predicatul P(x)Q(x) se transformă într-o afirmație adevărată când x = a, adică afirmație R(a)Q(a) este adevarat. Deoarece această afirmație este o conjuncție, atunci prin definiția unei conjuncții obținem că fiecare dintre enunțuri R(a)Și Q(a) de asemenea adevărat. Înseamnă că ATRȘi ATQ. Astfel, am arătat că TPÙQ Ì TRÇ TQ.

2. Să demonstrăm afirmația inversă. Lăsa A- un element arbitrar al multimii X si se stie ca AÎ TP Ç TQ. Prin definiția intersecției mulțimilor, aceasta înseamnă că ATRȘi ATQ, de unde obținem asta R(a)Și Q(a)- enunţuri adevărate, deci conjuncţia de enunţuri R(a)Q(a) va fi de asemenea adevărat. Aceasta înseamnă că elementul A aparține setului de adevăr al predicatului P(x)Q(x), adică AÎ TPÙQ .

Din 1 și 2, în virtutea definiției mulțimilor egale, rezultă că egalitatea TPÙQ =TRÇ TQ, ceea ce trebuia dovedit.

Acest lucru poate fi reprezentat vizual după cum urmează.

3. Operația de disjuncție.

Disjuncție predicate P(x)Și Q(x) se numește predicat P(x)Q(x Xși transformându-se într-o afirmație adevărată pentru acele și numai acele valori XX, pentru care cel puţin unul dintre predicate capătă valoare de adevăr P(x) sau Q(x).

În mod similar, este dovedit că TPÚQ = TP È T.Q.

4 .Operația de implicare.

Prin implicare predicate P(x)Și Q(x), definit pe platou X, se numește predicat P(x)Q(x), definite pe același set Xși transformându-se într-o afirmație falsă pentru acele și numai acele valori XX, la care P(x) capătă valoarea adevărului și Q(x)- sensul minciunii.

5 .Operaţia de echivalare.

Echivalenţă predicate P(x)Și Q(x), definit pe platou X, se numește predicat P(x)Q(x), definite pe același set Xși acceptând valoarea adevărului pentru acele și numai acele valori XX, pentru care valorile fiecăruia dintre predicate sunt fie adevărate, fie false. Adevărul stabilit în acest caz arată astfel:

TPÛQ = .

Exemplu. Pe platou M=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} predicatele sunt date: Oh)- "număr X nedivizibil cu 5 », B(x) - « X- numărul este par", C(x) - « X- numărul este prim", D(x)- "număr X multiplu 3 " Găsiți setul de adevăr al următoarelor predicate:

A) Oh)B(x); b) Topor); c) C(x)A(x); d) B(x)D(x)și descrieți-le folosind diagramele Euler-Venn.

Soluţie: a) Aflați mulțimea de adevăr a predicatelor.

A(x): T = (1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19);

B(x): T = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20).

Set de adevăr al unei conjuncții Oh)B(x) există adevăruri T Și T .

În mod informal, un predicat poate fi definit ca o anumită afirmație, al cărei sens depinde de valorile variabilelor obiective din mulțime M, pe care este definit predicatul.

A) P(x): “X este un număr prim”;

(Aici și în cele ce urmează, pentru a specifica un predicat, vom folosi o formă scurtă de notație, care este descrisă în detaliu după cum urmează: „ X este un număr prim")

b) D(x,y) : “X este complet divizibil cu y”;

c) R(x,y): “X > y”.

Orice set numeric poate fi considerat ca un set de subiecte pentru aceste exemple, în special, în exemplele a), b) - M= Í , și în c) - M= Ñ .

Mai strict predicat poate fi definit ca o mapare n puterea setului M, numită localitatea sau aritatea unui predicat într-o mulțime de două elemente B = {1, 0}

Când se substituie într-un predicat în loc de variabilele subiect set de valori obținem o declarație logică (deci , a ). Astfel, un predicat este o declarație variabilă (sau un sistem de enunțuri), al cărui adevăr este determinat de înlocuirea diferitelor valori ale variabilelor subiectului.

Deoarece predicatele iau valori din mulțime B , atunci sunt definite operații logice ~ pentru ei. În plus, pentru predicate sunt introduse operațiile de afirmare a universalității și de afirmare a existenței.

Operaţia de afirmare a universalităţii pune în corespondenţă forma expresivă P(x) declarație (a se citi ca, P(x) adevărat pentru toată lumea X din multi M, pe care este definit predicatul). O afirmație este adevărată dacă și numai dacă afirmația P(a) adevărat pentru orice element.

Operația afirmare a existenței pune în corespondență forma expresivă P(x) declarație (a se citi așa cum există X din multi M, pentru care declarația P(x) Adevărat). O afirmație este adevărată dacă și numai dacă afirmația P(a) adevărat pentru cel puțin un element.

Semnele " și $ sunt numite cuantificatori ai universalității și existenței (cuantificator tradus din latină - determinarea cantității). Trecerea de la forma expresivă. P(x) la instrucțiuni sau se numește atașarea unui cuantificator sau legarea unei variabile X(uneori prin cuantificarea variabilei X). O variabilă cu un cuantificator se numește legată, o variabilă nelegată se numește liberă. Sensul variabilelor legate și libere în expresiile predicate este diferit. O variabilă liberă este o variabilă obișnuită care poate lua valori diferite de la M, și expresia P(x)– o afirmație variabilă în funcție de sens X. Expresii și nu depind de o variabilă X iar la fix PȘi M au un sens foarte clar. Variabilele care sunt în esență legate nu se găsesc doar în logica matematică. De exemplu, în expresii sau variabile X conectat, la fix f prima expresie este egală cu un anumit număr, iar a doua este o funcție a AȘi b.

Astfel, enunțurile nu vorbesc despre proprietățile elementelor individuale ale mulțimii M, ci despre proprietățile setului în sine M. Adevărul sau falsitatea acestor afirmații nu depinde de modul în care este desemnată variabila subiect inclusă în ele și poate fi înlocuită cu orice altă variabilă subiect, de exemplu y, și obțineți enunțuri și , având același sens și aceleași valori de adevăr ca enunțurile originale.

În general, pentru n predicat -ary, dacă , pot fi efectuate operațiile de afirmare a universalității sau existenței k ori (ordinea de alegere a variabilelor pentru care este alocat cuantificatorul poate fi oricare, excluzând repetarea acestora) și obțineți expresia

unde desemnează cuantificatorul universalității sau existenței. Variabilele în forma de declarație (1) sunt legate și libere.

Relația de comandă. Seturi comandate

Definiție. Atitudine R pe un platou X se numeste relatie de ordine daca este tranzitiva si asimetrica sau antisimetrica.

Definiție. Atitudine R pe un platou X se numește relație de ordine strictă dacă este tranzitivă și asimetrică.

Exemple relații de ordine strictă: „mai mult” pe mulțimea numerelor naturale, „mai mare” pe mulțimea oamenilor etc.

Definiție. Atitudine R pe un platou X se numește relație de ordin nestrict dacă este tranzitivă și antisimetrică.

Exemple relații de ordin nestrict: „nu mai mult” pe mulțimea numerelor reale, „fii divizor” pe mulțimea numerelor naturale etc.

Definiție. O multime de X se numește ordonat dacă pe el este specificată o relație de ordine.

Exemplu. Pe platou X= (1; 2; 3; 4; 5) sunt date două relații: „ X £ la" Și " X- separator la».

Ambele relații au proprietăți de reflexivitate, antisimetrie și tranzitivitate (construiți grafice și verificați singur proprietățile), adică. sunt relaţii de ordine non-strict. Dar prima relație are proprietatea conexiunii, în timp ce a doua nu.

Definiție. Relația de comandă R pe un platou X se numește relație de ordin liniar dacă are proprietatea conexiunii.

În școala elementară sunt studiate multe relații de ordine. Deja în clasa I există relații „mai puțin”, „mai mult” pe setul de numere naturale, „mai scurt”, „mai lung” pe setul de segmente etc.

Întrebări de control

1. Definiți o relație binară pe o mulțime X.

2. Cum se scrie o afirmație conform căreia elementele XȘi la sunt într-o relație R?

3. Enumeraţi modalităţi de definire a relaţiilor.

4. Formulați proprietățile pe care le pot avea relațiile. Cum sunt reflectate aceste proprietăți în grafic?

5. Ce proprietăți trebuie să aibă o relație pentru ca aceasta să fie o relație de echivalență?

6. Cum este relația de echivalență legată de împărțirea unei mulțimi în clase?

7. Ce proprietăți trebuie să aibă o relație pentru ca aceasta să fie o relație de ordine?

Capitolul 5. Predicate și teoreme

În matematică există adesea propoziții care conțin una sau mai multe variabile, de exemplu: " X+ 2 = 7”, „orașul este situat pe Volga”. Aceste propoziții nu sunt afirmații, pentru că este imposibil să spunem despre ele dacă sunt adevărate sau false. Cu toate acestea, atunci când înlocuiți valori specifice pentru o variabilă X se transformă în afirmații adevărate sau false. Deci, în primul exemplu cu X= 5 obținem o afirmație adevărată și când X= 3 – afirmație falsă.

Definiție. O propoziție cu variabile, care, având în vedere valorile specifice ale variabilelor, se transformă într-un enunț, se numește formă propozițională sau predicat.

Pe baza numărului de variabile incluse în predicat, acestea se disting ca simple, duble etc. predicate și denotă A(X), ÎN(X y)…

Exemplu: A(X): « X este divizibil cu 2" – un predicat cu un singur loc, ÎN(X; la): "Drept X perpendicular pe o linie dreaptă la" este un predicat cu două locuri.

Trebuie avut în vedere că predicatul poate conține variabile implicit: „numărul este divizibil cu 2”, „elevul a primit o notă excelentă la examenul de matematică”.

Specificarea unui predicat, de regulă, implică și specificarea unui set din care sunt selectate valorile variabilelor incluse în predicat.

Definiție. Mulțimea (domeniul) definiției unui predicat este mulțimea X, constând din toate valorile variabilelor, atunci când sunt substituite într-un predicat, acesta din urmă se transformă într-o declarație.

Deci, predicatul " X> 2" poate fi considerat pe mulțimea numerelor naturale sau a numerelor reale.

Fiecare predicat A(X), X Î X definește un set TÌ X, constând din elemente care, atunci când sunt substituite în predicat A(X) în loc de X se dovedește a fi o afirmație adevărată.

Definiție. Mulțimea formată din toate acele valori, a căror substituire în predicat produce o afirmație adevărată, se numește mulțime de adevăr a predicatului (notat T).

Exemplu. Luați în considerare predicatul A(X): « X < 5», заданный на множестве натуральных чисел. T = {1; 2; 3; 4}.

Predicatele, ca și enunțurile, pot fi elementare sau compuse. Predicatele compuse sunt formate din cele elementare folosind conective logice.

Lăsa T A A(X), T V– domeniul de adevăr al predicatului ÎN(X).

Definiție. Conjuncția predicatelor A(X) Și ÎN(X) se numește predicat A(X) Ù ÎN(X X Î X, pentru care ambele predicate sunt adevărate.

Să arătăm asta T A Ù ÎN = T AÇ T V.

Dovada. 1) Lasă A Î T A Ù ÎN Þ A(A) Ù ÎN(A) este o afirmație adevărată. Prin definiția conjuncției avem: A(A) - Adevărat, ÎN(A) – adevărat Þ A Î T AÙ A Î T VÞ A Î T AÇ T VÞ T A Ù ÎN Ì T AÇ T V.

2) Lasă bÎ T AÇ T VÞ b Î T AÙ b Î T VÞ A(b) - Adevărat, ÎN(b) – adevărat Þ prin definiţia conjuncţiei A(b) Ù ÎN(b) – afirmație adevărată Þ b Î T A Ù ÎN Þ T AÇ T VÌ T A Ù ÎN .

Deoarece T A Ù ÎN Ì T AÇ T VȘi T AÇ T VÌ T A Ù ÎN, apoi prin proprietatea de egalitate a multimilor T A Ù ÎN = T AÇ T V, ceea ce trebuia dovedit.

Rețineți că regula rezultată este valabilă și pentru predicate care conțin mai multe variabile.

Exemplu. Să ne uităm la predicate A(X): « X < 10», ÎN(X): « X A(X) Ù ÎN(X): « X < 10 и делится на 3».

T A= {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, T V= (3; 6; 9; 12; 15; …), apoi T A Ù ÎN = {3; 6; 9}.

Definiție. Disjuncția predicatului A(X) Și ÎN(X) se numește predicat A(X) Ú ÎN(X), ceea ce este valabil pentru acele și numai acele valori X Î X, pentru care cel puțin unul dintre predicate este adevărat.

Poți dovedi (pe cont propriu) asta T A Ú ÎN = T AÈ T V.

Exemplu. Să ne uităm la predicate A(X): « X divizibil cu 2", ÎN(X): « X este divizibil cu 3", dat pe mulțimea numerelor naturale. Să găsim domeniul de adevăr al predicatului A(X) Ú ÎN(X): « X divizibil cu 2 sau 3."

T A= {2; 4; 6; 8; 10;…}, T V= {3; 6; 9; 12; 15; …}, T A Ú ÎN = {2; 3; 4; 6; 8; 9; …}.

Definiție. Negarea predicatului A(X) numit predicat . Este adevărat pentru acele și numai acele valori X Î X, pentru care predicatul A(X) este fals și invers.

Rețineți că = .

Definiție. Prin implicarea predicatelor A(X) Și ÎN(X) se numește predicat A(X) Þ ÎN(X) (a se citi: „Dacă A(X), Acea ÎN(X)")). Se transformă într-o afirmație falsă pentru acele valori X Î X, pentru care predicatul A(X) este adevărată, iar predicatul ÎN(X) este fals.

Din definiție avem că predicatul A(X) Þ ÎN(X) este fals pe platou T AÇ și, prin urmare, este adevărat la complementul acestui set. Folosind legile operațiilor asupra mulțimilor, avem: .

Întrebări de control

1. Ce se numește formă expresivă sau predicat?

2. Ce predicate se disting prin numărul de variabile incluse în ele? Dă exemple.

3. Ce mulţime se numeşte domeniul de definire a predicatului?

4. Ce mulţime se numeşte mulţimea de adevăr a unui predicat?

5. Ce se numește conjuncție de predicate? Demonstrați o egalitate care conectează domeniul de adevăr al unei conjuncții de predicate cu domeniile de adevăr ale acestor predicate.

6. Dați definiții ale disjuncției, negației și implicației predicatelor. Scrieți egalitățile care conectează domeniile de adevăr ale unei conjuncții de predicate cu domeniile de adevăr ale acestor predicate.