Резюме. Статията е посветена на използването на графичния конструктор на комбинационни схеми LC в обучението по дискретна математика. Конструкторът представлява програмна система, позволяваща графично или таблично задаване, изчертаване и изчисляване на комбинационни схеми за представяне на булеви функции. С негова помощ е създадена примерна разработка за преподаване на пълни множества в един класически раздел от дискретната математика, каквато е теорията на булевите функции. Разработката е предназначена за учители и университетски преподаватели, преподаващи дискретна математика.

Ключови думи: logic circuits, boolean functions, graphic user interface

1. Въведение

Поради своята актуалност и важност учебната дисциплина „Дискретна математика“ е основна както за университетските курсове по математика и компютърни науки, така и за профилираната подготовка по информатика в средните училища. Един важен раздел в дискретната математика е теорията на булевите (двоичните) функции. Тези функции се изучават и в задължителната подготовка на учениците в СОУ по учебната дисциплина „Информатика“ в IX клас. Необходимият минимум от знания е описан в (Бърнев и др., 2001). Известно е, че заедно с таблиците и формулите комбинационните схеми са един от най-популярните методи за представяне на булеви функции. За да не се превърнат учебните занятия в часове по чертане, е необходимо да се използват подходящи графични средства, които съществено да облекчават конструирането на комбинационните схеми.

В настоящата статия се разглежда конкретно приложение на конструктора на комбинационни схеми Logical Circuits (LC) (Kiskinov et al., 2014) \({ }^{8}\) за представяне на булеви функции. Подробно описание на конструктора на комбинационни схеми LC е направено в (Kiskinov et al., 2014). Той е създаден с образователна цел според изискванията, представени в (Рахнев & Стоева, 2010) и е предназначен основно да подпомага изучаването на теорията на булевите функции. Избран е след внимателен анализ на съществуващите графични системи за създаване на комбинационни схеми. Повечето от другите известни на автора графични системи – например Logisim \({ }^{4}\), TkGate \({ }^{6}\), HADES \({ }^{2}\), LogicSim \({ }^{5}\), DigitalSimulator \({ }^{1}\), са предназначени предимно за конструиране на електронни компоненти и поради тяхната сложност не са подходящи за обучение на ученици и студенти. Софтуерни програми, предназначени за обучение, са още xLogicCircuits \({ }^{7}\) и JLS \({ }^{3}\). Първата е примитивна и отстъпва на LC по всички компоненти. JLS \({ }^{3}\) е много мощна система, което обаче я прави доста сложна за обучаемите – факт, който пречи на масовото й използване в обучението по „Дискретна математика“. Конструкторът LC превъзхожда и двете по няколко показателя.

– Той не само контролира, но и подпомага процеса на конструиране, като улеснява разполагането и изцяло поема свързването на елементите така, че схемата да стане максимално прегледна.

– Не позволява конструирането на грешна схема. И в \({ }^{7}\), и в \({ }^{3}\) е възможно например да се конструират схеми със „зацикляне“ – нещо, което LC не допуска.

– Конструкторът LC превъзхожда всички по-горе изброени системи и поради липсата на фиксиран набор от базови елементи (обикновено това са AND, OR и NOT) и възможността да се дефинират таблично елементи от тип „blackbox“ („черна кутия“).

– LC има предимство и по отношение на автоматичното изчертаване на схемите.

Тема на настоящата работа е една примерна разработка на тема „Пълни множества от булеви функции“ с използване на комбинационни схеми, създавани с графичния конструктор LC. Като основа на разработката е залегнало изложението на темата за пълнота на множества от булеви функции в (Zahariev, 2013). По-различни описания на същата тема могат да се намерят в (Денев, 1984), (Grossman, 1990), (Манев, 2005) и (Байнов и др. 1990). Показано е примерно изложение на темата с използване на комбинационни схеми с активното използване на графичния конструктор LC.

2. Примерна разработка на темата „Пълни множества от булеви функции“ с използване на графичния конструктор LC

Едно множество F от булеви (двоични) функции се нарича пълно, ако всяка функция може да се реализира с формула над F. Теоремата на Бул гласи, че множеството, съставено от конюнкция, дизюнкция и отрицание, е пълно. Тази теорема не само ни дава първото (и важно) пълно множество, но предлага алгоритъм как произволна булева функция може да бъде реализирана с помощта на тези три функции. Това ще покажем със следния пример.

Пример 1

Нека \(f\) е произволна булева функция на три променливи, например следната:

Функцията \(f\) се реализира със следната формула:

\[ f\left(x_{1}, x_{2}, x_{3}\right)=\overline{x_{1} x_{2}} x_{3} \vee \overline{x_{1}} x_{2} x_{3} \vee x_{1} x_{2} \overline{x_{3}} \vee x_{1} x_{2} x_{3} \]

Формулата е дизюнкция с четири логически събираеми, при което първото \(\overline{x_{1} x_{2}} x_{3}\) става 1 точно тогава, когато всичките три променливи имат точно тези стойности, за които функцията става 1 за първи път (значи за \(\langle 0,0,1\rangle\), понеже \(f(0,0,1)=1)\). Второто логическо събираемо става 1 точно за стойностите на променливите от четвъртия ред на таблицата, когато \(f\) за втори път става 1 (значи за \(\langle 0,1,1\rangle\), понеже \(f(0,1,1)=1\) ) и т. н.

За представяне на тази примерна функция с комбинационна схема ще използваме конструктора LC с реализирани таблично три функции AND, OR, NOT. Комбинационната схема, реализираща функцията от примера, е:

За да не можем да показваме формулата от теоремата на Бул само с помощта на примери, е необходимо да въведем означение, показващо дали в конюнкцията една променлива участвува с отрицанието си, или не. Този проблем се решава, като дефинираме специално двоично степенуване:

\[ x^{\alpha}:=\left\{\begin{array}{l} x, \alpha=1 \\ \bar{x}, \alpha=0 \end{array}\right. \]

Сега вече можем да твърдим, че всяка булева функция (с изключение на нулевата функция, която обаче се представя с \(x_{1} \overline{x_{1}}\) ) се реализира чрез следната формула над конюнкция, дизюнкция и отрицание:

Тази формула се нарича канонична дизюнктивна нормална форма.

След успеха, постигнат с намирането на първото пълно множество от теоремата на Бул, възниква въпросът, съществуват ли и други пълни множества. Следната теорема ни помага да намерим и други пълни множества от двоични функции: когато всички функции от едно пълно множество F могат да бъдат реализирани с формули над друго множество G, тогава и само тогава множеството G също е пълно.

Така можем да докажем, че следните множества са пълни:

\(F_{1}=\left\{\overline{x_{1}}, x_{1} x_{2}\right\}\) е пълно, понеже \(x_{1} \vee x_{2}=\overline{\overline{x_{1} x_{2}}}\)

Реализираме \(O R\) с конструктора \(L C\) при таблично зададени NOT и AND:

\(F_{2}=\left\{\overline{x_{1}}, x_{1} \vee x_{2}\right\}\) е пълно, защото \(x_{1} x_{2}=\overline{\overline{x_{1}} \vee \overline{x_{2}}}\).

Реализираме AND с конструктора \(L C\) при таблично зададени NOT и \(O R\) :

\(F_{3}=\left\{x_{1} \downarrow x_{2}\right\}\) е пълно, защото \(\overline{x_{1}}=x_{1} \downarrow x_{1} u x_{1} \vee x_{2}=\left(x_{1} \downarrow x_{2}\right) \downarrow\left(x_{1} \downarrow x_{2}\right)\).

Реализираме NOT (схема 4) и OR (схема 5) с конструктора LC при таблично зададена NOR:

\(F_{4}=\left\{x_{1} \mid x_{2}\right\}\) е пълно, защото \(\overline{x_{1}}=x_{1} \mid x_{1}\) и \(x_{1} x_{2}=\left(x_{1} \mid x_{2}\right) \mid\left(x_{1} \mid x_{2}\right)\).

Реализираме NOT (схема 6) и AND (схема 7) с конструктора LC при таблично зададена NAND:

\(F_{5}=\left\{x_{1}+x_{2}, x_{1} x_{2}, 1\right\}\) е пълно, защото \(\overline{x_{1}}=x_{1}+1\).

Реализираме NOT с конструктора LC при таблично зададени XOR и ONE:

Множествата \(F_{3}\) и \(F_{4}\) се състоят от една-единствена функция. Такива функции, които сами образуват пълно множество, се наричат шеферови функции.

Множеството \(F_{5}\) ни предоставя възможност да въведем и една друга нормална форма. Формула от вида \(E_{1}+E_{2}+\cdots+E_{n}\), където събираемите \(E_{1}, E_{2}, \ldots, E_{n}\) са различни и всяко събираемо \(E_{i}=x_{i_{1}} x_{i_{2}} \ldots x_{i_{k}}\) е конюнкция на различни променливи или константата 1, се нарича полином на Жегалкин. От факта, че \(F_{5}\) е пълно и от това, че полиномът на Жегалкин е не друго, а максимално опростена формула над \(F_{5}\), следва, че всяка функция се представя с полином на Жегалкин. Тъй като броят на полиномите на Жегалкин съвпада с броя на всички булеви функции, то следва, че това представяне е единствено.

Като илюстрация ще разгледаме следния пример:

Пример 2 Нека \(f\) е произволна булева функция на три променливи, например следната:

За функции на три променливи общият вид на полинома на Жегалкин изглежда така:

\(f\left(x_{1}, x_{2}, x_{3}\right)=a x_{1} x_{2} x_{3}+b_{1} x_{2} x_{3}+b_{2} x_{1} x_{3}+b_{3} x_{1} x_{2}+c_{1} x_{1}+c_{2} x_{2}+c_{3} x_{3}+d\).

Двоичните коефициенти \(a, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}, c_{3}, d\) показват дали съответното събираемо участва в полинома, или не. От таблицата, ред по ред, се намират стойностите на двоичните коефициенти за конкретната функция:

\[ \begin{aligned} & \mathrm{d}=1 \\ & c_{3}+\mathrm{d}=0 \Rightarrow c_{3}=1 \\ & c_{2}+\mathrm{d}=1 \Rightarrow c_{2}=0 \\ & b_{1}+c_{2}+c_{3}+\mathrm{d}=0 \Rightarrow b_{1}=0 \end{aligned} \]

\[ \begin{aligned} & c_{1}+\mathrm{d}=1 \Rightarrow c_{1}=0 \\ & b_{2}+c_{1}+c_{3}+\mathrm{d}=1 \Rightarrow b_{2}=1 \\ & b_{3}+c_{1}+c_{2}+\mathrm{d}=0 \Rightarrow b_{3}=1 \\ & a+b_{1}+b_{2}+b_{3}+c_{1}+c_{2}+c_{3}+\mathrm{d}=0 \Rightarrow \mathrm{a}=0 \end{aligned} \]

Следователно полиномът на Жегалкин на нашата функция е:

\(f\left(x_{1}, x_{2}, x_{3}\right)=x_{1} x_{3}+x_{1} x_{2}+x_{3}+1\).

За представяне с комбинационна схема ще използваме конструктора LC с реализирани таблично три функции AND, XOR, ONE. Комбинационната схема, реализираща функцията от примера, е:

3. Заключение

Авторът счита, че с помощта на създадените с конструктора LC комбинационни схеми е постигнато по-добро изложение на темата за пълни множества от булеви функции. Възможността за бързо и удобно конструиране с LC позволява по-интензивно използване на комбинационни схеми за представяне на булеви функции. Освен това LC дава възможност за разглеждане и решаване на много повече като количество и качество задачи, което неминуемо повишава успеваемостта на учебния процес. Дори самото използване на компютър чрез конструктора LC би могло да се използва и за повишаване на интереса на студентите и учениците (виж напр. Маврова & Сярова, 2011) в една класическа математическа дисциплина, каквато е дискретната математика.

4. Благодарности

Тази работа е подпомогната по проект НИ13-ФМИ-002 на поделение „Научна и приложна дейност“ при Пловдивския университет „П. Хилендарски“.

БЕЛЕЖКИ

1. DigitalSimulator: http://web.mit.edu/ara/www/ds.html, (последно посетен 18.05.2014)

2. HADES: http://tams-www.informatik.uni-hamburg.de/applets/hades/webdemos/ index.html, (последно посетен18.05.2014)

3. JLS: http://www.cs.mtu.edu/~pop/jlsp/bin/JLS.html, (последно посетен 18.05.2014)

4. Logisim : http://ozark.hendrix.edu/~burch/logisim/, (последно посетен18.05.2014)

5. LogicSim: http://www.tetzl.de/java_logic_simulator.html, (последно посетен18.05.2014)

6. TkGate: http://www.tkgate.org/index.html, (последно посетен 18.05.2014)

7. xLogicCircuits: http://math.hws.edu/TMCM/java/xLogicCircuits/, (последно посетен 18.05.2014)

8. www.lc.myplovdiv.com. (последно посетен 18.05.2014)

ЛИТЕРАТУРА

Байнов, Д., Костадинов, С., Павлов, Р. & Луканова, Л. (1990). Ръководство за решаване на задачи по дискретна математика. Пловдив: Университетско издателство ПУ.

Бърнев, П., Тотков, Г., Донева, Р., Шкуртов, В. & Гъров, К. (2001). „Информатика“, учебник за задължителна подготовка в IX клас на СОУ. Пловдив: Летера.

Денев, Й., Павлов, Р. & Деметрович, Я. (1984). Дискретна математика. София: Наука и изкуство.

Маврова, Р. & Сярова, П. (2001). Провокиране на интереса на учениците при обучението по математика. Научни трудове на Пловдивски университет, том 48, кн. 2 – Методика на обучението, 35 – 46.

Манев, К. (2005). Въведение в дискретната математика. София: КЛМН (ISBN 954-535-136-5).

Рахнев, А. \(\&\) Стоева, М., (2010). Принципи и технологии за изграждане на по-требителски интерфейс за уеб и десктоп приложения. Сборник доклади Национална конференция „Образованието в информационното общество“, Пловдив, \(27-28\) май 2010 г., \(308-316\).

Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan (ISBN 0-02348331-8).

Kiskinov H., Radev V., Stoeva M., A graphic constructor for logic circuits design, International Journal of Recent Development in Engineering and Technology, Vol. 2 (2014), No. 4, 24 – 29.

ZaharievA., A.Golev, H.Kiskinov, EinfuehrungindietheoretischeInformatik, LightningSource UK Ltd 2013, ISBN978-3-99034-207-7

REFERENCES

Baynov, D., Kostadinov, S., Pavlov, R. & Lukanova, L. (1990). Rakovodstvo za reshavane na zadachi po diskretna matematika. Plovdiv: Universitetsko izdatelstvo PU.

Barnev, P., Totkov, G., Doneva, R., Shkurtov, V. & Garov, K. (2001). „Informatika”, uchebnik za zadalzhitelna podgotovka v 9 klas na SOU. Plovdiv: Letera.

Denev, Y., Pavlov, R. & Demetrovich, Ya. (1984). Diskretna matematika. Sofiya: Nauka i izkustvo.

Mavrova, R. & Syarova, P. (2001). Provokirane na interesa na uchenitsite pri obuchenieto po matematika. Nauchni trudove na Plovdivski universitet, tom 48, kn. 2 – Metodika na obuchenieto, 35-46.

Manev, K. (2005). Vavedenie v diskretnata matematika. Sofiya: KLMN (ISBN 954535-136-5).

Rahnev, A. & Stoeva, M., (2010). Printsipi i tehnologii za izgrazhdane na potrebitelski interfeys za ueb i desktop prilozheniya. Sbornik dokladi Natsionalna konferentsiya „Obrazovanieto v informatsionnoto obshtestvo”, Plovdiv, 27-28 may 2010 g., 308-316.

Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan (ISBN 0-02348331-8).

Kiskinov H., Radev V., Stoeva M., A graphic constructor for logic circuits design, International Journal of Recent Development in Engineering and Technology, Vol. 2 (2014), No. 4, 24-29.

ZaharievA., A.Golev, H.Kiskinov, Einfuehrungindietheoretische Informatik, Lightning Source UK Ltd 2013, ISBN978-3-99034-207-7