Reprezentări ale funcțiilor booleene prin extinderi cu privire la variabile

Seturi și relații.

Seturi și specificațiile acestora. Operații pe seturi. Diagramele lui Euler-Venn. Puterea setului. Seturi finite și numărate. Relația. Proprietățile relațiilor. Operațiuni peste relații. Relația de echivalență. Bătăi și relația de echivalență. Relații ordonate parțiale și stricte. Funcții și mapări. Injectarea, surjecția, suprapunerea, bijecția, funcțiile inverse.







Referințe: [1], p. 5-10; [3], partea 2; [4], Ch. 1-3; [5], Ch. 1.

Algebre booleene. Elemente ale logicii matematice.

Funcțiile booleene. Metode ale sarcinii. Variabile esențiale și fictive. Formule booleene. Proprietățile de bază ale operațiilor logice. Forme normale perfecte. Polynom Zhegalkin. Clase închise de funcții. Sisteme complet funcționale. Teoreme privind completitudinea funcțională. Exemple de baze funcționale complete. Problema minimizării funcțiilor booleene. Scheme de elemente funcționale. Mașini de stat finite. Teorii formale. Conceptul de expresie. Tautologie. Calculul propozițiilor. Logica predicatelor.

Referințe: [1], p. 14-53; [2], Ch. 3.8; [3], pct. 1.4; [4], Ch. 4, 5; [5], Ch. 3.4.

Echivalența formulelor booleene.

Funcțiile booleene pot fi specificate fie folosind tabelele de adevăr (unic), fie folosind formule logice (unic). Dacă tabelele de adevăr ale două formule booleene coincid, atunci aceste formule sunt echivalente și definesc aceeași funcție booleană.

Un exemplu. Verificați echivalența formulelor booleene:







Construim masa adevărului pentru funcție.

Coloanele rezultate în tabelele de adevăr sunt aceleași, prin urmare, formulele sunt echivalente.

Variabile esențiale și fictive.

Variabila () a unei funcții booleene este numită funcție falsă. dacă există egalitate

pentru orice valori ale variabilelor. În caz contrar, variabila este numită esențială. Seturile de valori ale variabilelor din ultima egalitate se consideră a fi vecine în variabilă.

Un exemplu. Identificați variabilele de funcții esențiale și funcționale (11110011).

Pentru comoditate, prezentăm tabelul de adevăr.

Să vedem dacă variabila este semnificativă sau fictivă. Luați în considerare valorile funcției pe seturile adiacente variabilei:

. Prin urmare, variabila este esențială.

Să luăm acum în considerare valorile funcției pe seturile ale căror vecine se află în variabila:

. Prin urmare, variabila este esențială.

Luați în considerare valorile funcției pe seturile adiacente variabilei:

Pe toate perechile de seturi variabile variabile de variabile, funcția are valori egale, de unde variabila este una fictivă.

Reprezentări ale funcțiilor booleene prin extinderi în variabile.

Forma normală disjunctivă normală (SDNF) pentru o funcție booleană. nu egal cu zero, are forma:

unde simbolul este definit după cum urmează:

Algoritm pentru construirea CDNF.

1. Construiți o tabelă de adevăr pentru o funcție booleană dată.

2. Fiecare valoare elementară a unei funcții booleene va corespunde unei conjuncții elementare. unde - setul corespunzător de valori ale variabilelor. În conjuncțiile pe care le scriem. în cazul în care. și. în cazul în care. Conjuncțiile sunt legate printr-un semn.

Formă normală conjunctivă normală (SKNF) pentru funcție. diferit de unitatea de identitate, are forma:

Algoritm pentru construirea SKNF.

1. Construiți o tabelă de adevăr pentru o funcție booleană dată.

2. O disjuncție elementară corespunde fiecărei valori zero a funcției booleene. unde este setul corespunzător de valori ale variabilelor. În disjuncția pe care o scriem. în cazul în care. și. în cazul în care. Disjuncțiile sunt legate printr-un semn.

Orice funcție booleană poate fi reprezentată ca un polinom Zhegalkin:

în cazul în care. unde semnul denumește suma modulo 2.







Trimiteți-le prietenilor: