Concepte de bază și definiții
Vom lua în considerare doar un număr finit de argumente ale funcției. Să considerăm un set de vectori X =, coordonatele Ko
toryh poate lua doar două valori - 0 sau 1. Apoi setului X este format din 2 n vectori diferiți. Pentru fiecare vector al simbolurilor X este 0 sau 1, și anume va produce un mapare a unei multitudini de X Y =.
Definiția 1.1.1. funcții booleene sau switch-off
Funcția clorhidric este o funcție care oferă un mapare X Y [1].
Din această definiție rezultă că funcția f (x 1, .... X n) se numește o comutare în cazul în care, precum și argumentele sale pot lua doar valorile alfabetului din două litere, de exemplu, 0 și 1.
Deoarece argumentele funcției de comutare poate lua doar două valori, atunci domeniul oricare dintre funcția de comutare este finită. Un set de valori numite argumente stabilite și se notează cu un 1. ..., o i. ..., a n. unde a i este 0 sau 1 (i = 1, ..., n). Fiecare set poate fi reprezentat de numărul n-biți binar, un număr binar de numere de n-biți este 2 n. Prin urmare, orice comutare
definitiv funcție poate fi definită prin 2 n seturi.
De exemplu, funcțiile de comutare a două argumente sunt definite pe patru seturi (00, 01, 10, 11) și funcția de comutare a trei argumente - opt. Astfel, funcția de comutare poate fi dată de un tabel care enumeră toate valorile posibile ale argumentelor funcției (seturi) și valorile seturi corespunzătoare acestor funcții. Un astfel de tabel este numit un tabel de adevăr al funcției de comutare. EXEMPLU Funcția de trei argumente de comutare așa cum se arată în tabelul. 1.1.
Tabelul 1.1 Tabel de valori ale funcției de comutare
1,1,1,1,1 - treizeci și primul set.
Un kit care cuprinde toate unitățile (1,1, ..., 1), menționată ca un singur set.
N argumente ale funcției de comutare definite de 2 n seturi pentru care poate lua valorile 0 sau 1. Prin urmare, în corespondență cu fiecare dintre funcția de comutare poate fi furnizat n-bit 2
număr binar. Numărul 2 n biți numere binare este de 2 2 n. astfel de
Kim, numărul de funcții diferite de comutare argumente n
desigur, și egal cu 2 2 n.
Atribuim fiecare dintre numărul funcției de comutare egal cu numărul binar format de valorile funcției de comutare pe toate seturile. Acest număr este scris de la stânga la dreapta, începând cu valoarea funcției la zero set. De exemplu, numărul binar format de valorile din tabel funcției. 1.1, 00111010 (2). egal cu 58 în zecimala și funcția poate fi descrisă după cum urmează:
f (x 1, x 2, x 3) = f 58 (x 1, x 2, x 3).
Exemplul 1.1. Crearea unui tabel de adevăr pentru funcția de comutare numărul 23805 patru argumente.
Decizie. Patru comutare argumente funcționale este determinată aprilie 2 = 16 seturi (Tabel. 1.2). Pentru valori ale funcțiilor reprezintă numărul 23805 în notație binară: 23805 (10) = = 101110011111101 (2). Numărul binar rezultat are 15 biți, și să reprezinte este necesară funcția de comutare pentru a completa codul de 16 biți: 0101110011111101.
Tabelul 1.2 Tabelul 23805 de comutare Funcția f (x 1, x 2, x 3, x 4)
Definiția 1.1.2. Dacă două funcții de comutare f (x 1 ..., x n)
și φ (x 1 ..., x n) din același număr de argumente iau pe toate seturile posibile de valori ale argumentelor valori egale, funcțiile f și φ spus să fie egale.
Egalitatea a funcțiilor f și cp este scris după cum urmează:
f (x 1 ..., x n) = φ (x 1 ..., x n).
Definiția 1.1.3. Funcția de comutare f (x 1 ... x i-1, x i, x i + 1 ..., x n) în mod substanțial independent de argument x i. în cazul în care relația
f (x 1 ... x i-1. 0, x i + 1 ..., x n) ≠ f (x 1 ... x i-1. 1, x i + 1 ..., x n).
În caz contrar, ei spun că argumentul x i funcționalitatea depinde imaterială și x i este argumentul său fictiv. Funcția de comutare nu se modifică în cazul în care argumentele sale pentru a adăuga orice număr de argumente fictive sau cruce din argumentele care sunt fictive.
1.1. Funcția de comutare a unuia sau a două argumente
Funcția 1.2.1.Pereklyuchatelnye de un argument.
Există patru funcții de comutare a unui singur argument, care sunt enumerate în tabelul. 1.3.
Funcția f 0 (x) este identic zero. Se numește constanta si zero, notat f 0 (x) = 0.
Funcția f 1 (x) repetarea valorii argument și, prin urmare, este identic egal cu variabila x.
f 2 (x) funcția are o valoare valori opuse ale argumentului: dacă x = 0, f 2 (x) = 1; dacă x = 1, atunci f 2 (x) = 0. Această funcție este numită o inversare sau negare x și x este administrat pentru indicația specifică aceasta
Funcția f 3 (x) este identic egal cu unu. Se numește concentrare
Unitatea de constante si se noteaza cu f 3 (x) = 1.
1.2.2. Funcția de comutare a două argumente. Există șaisprezece funcții de comutare diferite a două argumente, fiecare dintre care este definit în patru seturi. Aceste funcții sunt prezentate în tabel. 1.4.
Printre cele șaisprezece funcții de comutare sunt funcții considerate în p.1.2.1:
Funcția de comutare a două argumente
Inhibarea y
interzicerea funcția x
Modulo 2 sum (nonequivalence logic)
Adăugarea logică (disjuncție)
Operațiunea Pierce (Pierce săgeată)
Echivalența (echivalență logică)
Implicarea y la x
Implicațiile de la x la y
Operațiunea Schaeffer (Sheffer accident vascular cerebral)
Luați în considerare unele dintre funcția de comutare a două argumente. Funcția f 1 (x, y) este numit conjuncție sau multiplicare logică. Tabelul de adevăr al acestei funcții coincide cu tabelul multiplicării două numere binare de un bit. Puteți introduce funcția de n argumente, care corespunde produsului numerelor binare cu un singur bit n. Această funcție de comutare este egală cu una, dacă și numai dacă toate argumentele sale sunt egale cu unu. Ar trebui să dețină pentru conjuncțiilor
x 0 = 0; x 1 = x; x x = x;
x y = y x; x x = 0.
7 Funcția f (x, y) este numit disjuncție sau adăugarea logică. Această funcție este egală cu zero numai atunci când toate argumentele sale sunt zero. Puteți introduce funcția de n argumente, care corespunde adăugării logice numerelor binare cu un singur bit n. Acest comutator
Funcția negativă este zero dacă și numai dacă toate argumentele sale sunt zero. Pentru conjuncția dintre următoarele relații:
x 0 = x; x 1 = 1; x x = x;
x y = y x; x x = 1.
Adevărul Tabelul 6 Funcția f (x, y) coincide cu adăugarea a două singur tabel de numere binare modulo doi. Puteți introduce funcția de n argumente, care corespunde sumei modulo n două numere binare cu un singur bit. Această funcție de comutare este determinată de condiția ca acesta este egal cu una, dacă numărul de argumente este egal cu zero, unul ciudat și dacă numărul de argumente este chiar. Iată câteva relații pentru valoarea modulului doi:
x 0 = x; x 1 = x; x x = 0;
x x x = x; x y = y x.
Considerat șaisprezece funcții a două argumente (noi le vom numi elementare) vă permit să construiască noi funcții de comutare, după cum urmează:
• prin renumerotarea argumente;
• Prin înlocuirea funcției de noi caracteristici în loc de argumente. Funcția obținută din funcțiile f 1. f 2. ..., f k prin aplicarea
(Posibil mai multe) dintre aceste două reguli se va numi o suprapunere de funcții f 1. f 2. ..., f k. De exemplu, având funcțiile de bază ale inversiune, conjuncție, disjuncție, implicit, interzicerea, modulo doi, puteți face o nouă funcție de comutare:
f (x, y, z) = ((x y) z) ((y → z) x).
Utilizarea tabelului, stabilește funcțiile de bază pot fi setate într-un tabel de orice funcție de comutare, este o suprapunere a acestor funcții.
Exemplul 2.1. Reprezentat ca funcție de masă f (x, y, z) = ((x y) z) ((y → z) x).
Decizie. Funcția f (x, y, z) va fi scris secvențial coloane în tabelul. 1.5 rezultatele intermediare obținute după fiecare operațiune: