Diskrečioji matematika. Žegalkino polinomas, NDF, NKF.

Rasti žegalkino polinomą, NDF ir NKF
[tex]\left ( x_{1}\bigoplus x_{2} \right )\rightarrow \left ( x_{1}x_{2} \right )[/tex]

1. Rasime Žegalkino polinomą neapibrėžtinių koeficientų metodu.

Duotosios formulės bendroji Žegalkino polinomo išraiška atrodys taip:
[tex]Ax_{1}x_{2}\oplus Bx_{1}\oplus Cx_{2}\oplus D[/tex]

Nusibraižykime reikšmių lentelę


Atitinkamai pagal pirmą, antrą, trečią ir ketvirtą eilutes susidarome lygčių sistemą (į bendrąją Žegalkino polinomo išraišką įstatome atitinkamas kiekvienos eilutės [tex]x_{1}[/tex] ir [tex]x_{2}[/tex] reikšmes):

[tex]\begin{cases} (A\&0\&0)\oplus (B\&0)\oplus (C\&0)\oplus D\sim D \\ (A\&0\&1)\oplus (B\&0)\oplus (C\&1)\oplus D\sim C \oplus D \\ (A\&1\&0)\oplus (B\&1)\oplus (C\&0)\oplus D\sim B \oplus D \\ (A\&1\&1)\oplus (B\&1)\oplus (C\&1)\oplus D\sim A \oplus B \oplus C \oplus D \end{cases}[/tex]

Vadinasi, pagal formulės reikšmių stulpelio reikšmes turėsime išspręsti tokią lygčių sistema:

[tex]\begin{cases} D \sim 1 \\ C \oplus D \sim 0 \\ B \oplus D \sim 0 \\ A \oplus B \oplus C \oplus D \sim 1 \end{cases}[/tex]

Taikydami sumos moduliu 2 ([tex]\oplus[/tex]) savybes nesunkiai randame, kad

[tex]\begin{cases} A \sim 0 \\ B \sim 1 \\ C \sim 1 \\ D \sim 1 \end{cases}[/tex]

Vadinasi, gavome tokį polinomą:
[tex](0\&x_{1}\&x_{2})\oplus (1\&x_{1})\oplus(1\&x_{2})\oplus1\sim x_{1}\oplus x_{2}\oplus1[/tex]

~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~

2. Rasime duotosios Būlio funkcijos NDF (normaliąją disjunkcinę formą) ir NKF (normaliąją konjunkcinę formą) naudodamiesi jau susidaryta reikšmių lentele bei ekvivalenčiais pertvarkymais.

2.1. Naudojantis reikšmių lentele
2.1.1.Rasime NDF

Pasižymime lentelės eilutes, kuriose Būlio funkcija įgyja reikšmes, lygias 1 (nuspalvinta raudonai). Pagal kiekvieną tokią eilutę sudarome konjunktą, sujungtą disjunkcijomis ([tex]K_{1}\vee K_{2}\vee K_{3}\vee ... \vee K_{n}[/tex]), t.y. pirmosios eilutės, kurioje Būlio funkcija įgyja reikšmę 1, konjunktas bus [tex]\overline{x_{1}} \& \overline{x_{2}}[/tex], o ketvirtosios eilutės, kur [tex]x_{1}=1[/tex] ir [tex]x_{2}=1[/tex], konjunktas bus [tex]x_{1} \& x_{2}[/tex] (atitinkamai kintamuosius, kurių reikšmės lygios 1, paliekame tokius pačius, o kur lygios 0, parašome kintamojo neiginį).

Taip gauname, kad duotosios funkcijos NDF, kuri yra tobula, nes KIEKVIENAS konjunktas yra sudarytas iš VISŲ kintamųjų (šiuo atveju [tex]x_{1}[/tex] ir [tex]x_{2}[/tex]):

[tex]((x_{1} \oplus x_{2}) \to (x_{1} \& x_{2})) \sim (\overline{x_{1}} \& \overline{x_{2}}) \vee (x_{1} \& x_{2})[/tex].

~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~
2.1.2. Rasime NKF


Šiuo atveju priešingai - pasižymime eilutes, kuriose Būlio funkcija įgyja reikšmes, lygias 0. Sudarysime disjunktus, sujungtus konjunkcijomis. Disjunktą gausime, 1 keisdami atitinkamo kintamojo neiginiu, o 0 - atitinkamu kintamuoju, pavyzdžiui, iš antros eilutės ([tex]x_{1}=0[/tex] ir [tex]x_{2}=1[/tex]) sudarome disjunktą [tex]x_{1} \vee \overline{x_{2}}[/tex]. Toliau iš trečios eilutės ([tex]x_{1}=1[/tex] ir [tex]x_{2}=0[/tex]) sudarome disjunktą [tex]\overline{x_{1}} \vee x_{2}[/tex]. Tokiu būdu gauname NKF, kuri taip pat yra tobula:

[tex]((x_{1} \oplus x_{2}) \to (x_{1} \& x_{2})) \sim (x_{1} \vee \overline{x_{2}}) \& (\overline{x_{1}} \vee x_{2})[/tex].

Pastaba: Reikšmių lentelės pagalba dažnai vietoje norimos NDF ir NKF rasime TNDF (tobulą normaliąją disjunkcinę formą) ir TNKF (tobulą normaliąją konjunkcinę formą), todėl pateikiu ir kitą NDF ir NKF radimo būdą.
~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~
2.2. Ekvivalenčiais pertvarkymais
Neapsisunkinant, konstruoti NDF ir NKF galima vadovaujantis šia žingsnių seka:
a) Pašaliname visas operacijas, išskyrus neiginį, konjunkciją ir disjunkciją.
b) Įkeliame neiginį į skliaustus.
c) Taikome distributyvumo dėsnius.
~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~
2.2.1. Rasime NKF

[tex]((x_{1} \oplus x_{2})\to (x_{1} \& x_{2}))\sim (\overline{(x_{1} \leftrightarrow x_{2})} \to (x_{1} \& x_{2})) \sim \\ (\overline{\overline{(x_{1} \leftrightarrow x_{2})}} \vee  (x_{1} \& x_{2})) \sim ((x_{1} \leftrightarrow x_{2}) \vee  (x_{1} \& x_{2})) \sim \\(((x_{1} \to x_{2}) \& (x_{2} \to x_{1}))\vee (x_{1} \& x_{2})) \sim (((\overline{x_{1}} \vee x_{2}) \& (\overline{x_{2}} \vee x_{1})) \vee (x_{1} \& x_{2}))\sim [/tex]
[taikome distributyvumo dėsnius, t.y. [tex]\vee (x_{1} \& x_{2})[/tex] įkeliame į skliaustus]

[tex]\sim ((\overline{x_{1}}\vee x_{2})\vee (x_{1} \& x_{2})) \& ((\overline{x_{2}}\vee x_{1})\vee (x_{1} \& x_{2})) \sim (\overline{x_{1}}\vee x_{2}\vee (x_{1} \& x_{2})) \& (\overline{x_{2}}\vee x_{1}\vee (x_{1} \& x_{2}))\sim \\[/tex]
[atitinkamai [tex]\overline{x_{1}}\vee [/tex] ir [tex]\overline{x_{2}}\vee [/tex] keliame į skliaustus] [tex]\sim (x_{2}\vee ((\overline{x_{1}} \vee x_{1}) \& (\overline{x_{1}}\vee x_{2}))) \& (x_{1}\vee ((x_{1}\vee \overline{x_{2}}) \& (\overline{x_{2}} \vee x_{2}))) \sim \\ (x_{2}\vee (1 \& (\overline{x_{1}}\vee x_{2}))) \& (x_{1}\vee ((x_{1}\vee \overline{x_{2}}) \& 1)) \sim (x_{2}\vee (\overline{x_{1}}\vee x_{2})) \& (x_{1}\vee (x_{1}\vee \overline{x_{2}})) \sim \\ (x_{2}\vee \overline{x_{1}}\vee x_{2}) \& (x_{1}\vee x_{1}\vee \overline{x_{2}}) \sim (x_{2}\vee \overline{x_{1}}) \& (x_{1}\vee \overline{x_{2}}).[/tex] Matome, sukonstruotas NKF yra tas pats, kokį ir radome reikšmių lentelės pagalba.
~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~
2.2.2. Rasime NDF

[tex]... \sim (((\overline{x_{1}}\vee x_{2}) \& (\overline{x_{2}}\vee x_{1}))\vee (x_{1} \& x_{2}))[/tex] [tvarkysime tik prieš disjunktą skliausteliuose esantį reiškinį, t.y. [tex](\overline{x_{1}}\vee x_{2}) \&[/tex] kelsime į skliaustus].

[tex]\\((\overline{x_{1}}\vee x_{2}) \& (\overline{x_{2}}\vee x_{1})) \sim ((\overline{x_{1}}\vee x_{2}) \& \overline{x_{2}})\vee ((\overline{x_{1}}\vee x_{2}) \& x_{1})) \sim [/tex] [atitinkamai [tex]\& \overline{x_{2}}[/tex] ir [tex]\& x_{1}[/tex] keliame į skliaustus][tex]\sim ((\overline{x_{2}} \& \overline{x_{1}})\vee (x_{2} \& \overline{x_{2}}))\vee ((\overline{x_{1}} \& x_{1})\vee (x_{1} \& x_{2})) \sim ((\overline{x_{2}} \& \overline{x_{1}})\vee 0)\vee (0\vee (x_{1} \& x_{2}))\sim (\overline{x_{2}} \& \overline{x_{1}})\vee (x_{1} \& x_{2}).[/tex]

Viską sujungus gauname, kad
[tex]... \sim (((\overline{x_{1}}\vee x_{2}) \& (\overline{x_{2}}\vee x_{1}))\vee (x_{1} \& x_{2})) \sim (\overline{x_{2}} \& \overline{x_{1}})\vee (x_{1} \& x_{2}) \vee (x_{1} \& x_{2}) \sim (\overline{x_{2}} \& \overline{x_{1}})\vee (x_{1} \& x_{2}).[/tex]
~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~