Abstract. The paper considers the use of the graphic constructor of combinational schemes LC in Discrete mathematics teaching. The constructor is a program system, which helps graphics or table determination, drawing and computation of combinational schemes in Boolean functions representations. An exemplary working out is created by it to teach complete sets in a classic chapter of Discrete mathematics like the theory of Boolean functions. The paper is addressed to secondary school teachers and university lecturers, who teach Discrete mathematics.

Keywords: 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