Rezumat: Clasa funcțiilor Pn booleană n variabile. Reprezentarea geometrică a funcțiilor booleene. Specificarea funcțiilor booleene folosind tabele. funcții booleene ale primului și a 2 variabile. Boolean (logic) formulă. Solutia problemelor de logica propozitionala folosind formule și funcții booleene
funcții booleene de n variabile
Funcții Boolean 1 În literatura de specialitate internă acestea sunt, de asemenea, de multe ori se face referire la funcții ca Boolean. numit după matematicianul britanic al secolului al XlX-lea, George. Boole, care a folosit pentru prima dată metode algebrice pentru a rezolva probleme logice. Ele formează cea mai simplă clasa nontrivial de funcții discrete - argumente și valorile lor pot lua doar două valori (în cazul în care o multitudine de valori de putere este egal cu 1, este o caracteristică banal -! Constantă). Pe de altă parte, această clasă este destul de bogat, iar funcțiile sale au multe proprietăți interesante. funcții booleene sunt utilizate în logica, inginerie electrică, multe domenii ale informaticii.
Fie B cele două elemente set. atunci
mulțimea tuturor secvențelor binare (seturi de vectori) de lungime n. Funcția booleană n variabile (argumente) este orice funcție f: B n -> B. Fiecare dintre xi sale argumente (x1 xn.). 1 <= i <= n. может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из Bn также может быть 0 или 1. Обозначим через множество всех булевых функций от n переменных. Нетрудно подсчитать их число.
Dovada .Indeed Teorema 1.1 numărul de funcții în k set -Element A în set B m -Element m este egal cu k. În cazul nostru, B =. și A = B n. Apoi, m = 2 și k = | B n | = 2 n. Aceasta implică teorema.
Există mai multe moduri diferite de prezentare și interpretare a funcțiilor booleene. În această secțiune considerăm prezentarea geometrică și tabelare. și prezentarea de formule logice. Cele „echivalențele și formele normale“ vor fi afișate ca o functie booleana poate fi reprezentat prin formulele de formă specială - formele normale disjunctive și conjunctive și polinoame Zhegalkin. În plus, conferințele „Preliminarii“ și „Inducerea și combinatorica“ (curs „Introducere în schemă, mașinile și algoritmi“) vor fi luate în considerare două moduri de reprezentare a funcțiilor booleene. logică și diagrame de decizie binare ordonate.
Reprezentarea geometrică
Bn poate fi considerată ca o unitate cub n-dimensional. Fiecare set de zerouri și cele de lungime n setează vârful cubului. Fig. 3.1 Unitate reprezentate cuburi Bn cu n = 3,4.
În același timp, există un natural unu la unu corespondență între un subset de noduri de cuburi de unități n-dimensionale și funcții booleene de n variabile: subgrupul corespunde funcției sale caracteristice
De exemplu, fața superioară a cubului B 3 (nodurile sale alocate în figură) corespunde funcției f. f (0,0,1) = f (0,1,1) = f (1,0,1) = f (1,1,1) = 1 și f (0,0,0) = f (0 , 1,0) = f (1,0,0) = f (1,1,0) = 0. Este evident că cele de mai sus de potrivire de fapt o singură: fiecare funcție booleana f din n seturi de variabile subset Af = 1. xn) |. f (xn x1) = 1> nodurile B n. De exemplu, funcția identic egal cu 0 specifică un set gol, și funcționează identic egal cu 1, definește mulțimea tuturor nodurilor B n.
vedere din tabel
Funcții booleene pe un număr mic de argumente prezentate în mod convenabil prin intermediul unor tabele. Tabel pentru funcția f (x1. Xn) are n + 1 coloana. Argumentul primul n coloane sunt specificate valorile x1. xn. și (n + 1), valoarea th coloană a funcției la aceste argumente - f (x1 xn.).
Tabelul 3.1. Reprezentarea tabelară a funcției f (x1. Xn)