eMatematikas.lt Naujienos Kategorijos Nauja tema Nariai Prisijungti Registruotis
       

Kategorijos

Naudingos temos

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

Kategorija: Aukštoji matematika

572

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

Paskutinį kartą atnaujinta 2017-10-17

0

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ę
https://i.imgur.com/mM5eY5d.jpg

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
https://i.imgur.com/5UaNAd8.jpg
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

https://i.imgur.com/Ut9f0Vs.jpg
Š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]
~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~  ~

Paskutinį kartą atnaujinta 2018-02-03

0

Norėdami rašyti žinutes privalote prisijungti!