Книга за учителя София, 2000 г. Анубис увод

Конюнкцията ~A.B.C е участвала в слепване със всяка една от останалите три. Всички неотбелязани конюнкции в таблицата, свързани с дизюнкция образуват съкратената форма. Важно за алгоритъма е, че една конюнкция може да участва в повече от едно слепване и за да получите съкратената форма трябва да направите всички възможни слепвания.

Задачите 10 и 11 са актуални примери за нетривиални съждения, за които неотдавна се наложи да бъдат препазгледани в много компютърни програми. Причината беше, че авторите на болшинството програми написани през миналото хилядолетие, не бяха обърнали внимание на приближаващата година, кратна на 400. Разбира се, че такава година се среща за пръв път в историята на програмирането и затова бе убягнала от вниманието на програмистите. Всъщност високосни са тези години, които се делят на 4, но от тях трябва да се изключат тези, които се делят на 100 и на 4, да се включат обратно делящите се на 400 (каквато е годината 2000).

Нека означим с X съждението “N се дели 4”. Математическият запис на такова съждение е 4|N и се чете “4 дели N”. Да означим с Y съждението 100|N, а със Z – съждението 400|N. На пръв поглед изглежда, че търсената формула е X~YZ. Но това не е така. Да проверим вярностната стойност на тази формула, когато N=2000. Вярностната стойност на всяко от съжденията X, Y и Z е истина, защото 2000 се дели едновременно на 4, 100 и 400. Следователно вярностната стойност на ~Y е неистина и такава ще бъде и вярностната стойност на формулата X~YZ, в която ~Y участва в конюнкция.

В урока е показано как трябва да се постъпва в такъв случай – трябва да се построи булевата функция на бъдещата формула и след това да се напише формулата като се използва Теоремата на Бул и да се опрости получената формула, ако това е възможно (лесно могат да се посочат съждителни формули, които не подлежат на опростяване). Всъщност има четири булеви функции, които решават задачата, представени съвместно в следната таблица:

На мястото на всяка от двете звезди може да стои както 0 така и 1, защото няма числа, които се делят на 400, но не се делят на 100 и коя от двете стойности ще поставим е без значение. Да вземем най-простия случай – нули и на двете места. По Теоремата на Бул търсената формула е X.~Y.~Z X.Y.Z. Тази формула не може да бъде опростена по начина, описан по горе. Ако обаче поставим 1 на мястото на втората звезда, ще получим формулата X.~Y.~ZX.~Y.ZX.Y.Z, която се опростява до X.~YX.Z. Ето защо по-горе подчертахме необходимоста да се познава апарата на булевите функции.

Колкото да задача 11 не е необходима да се правят сложни пресмятания. След като е решена задача 10, решението на задача 11 е отрицанието на решението на задача 10, т.е. ~( X.~YX.Z).
ФОРМАЛНИ ЕЗИЦИ И ГРАМАТИКИ

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

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

Преподаването на този материал изисква много добра математическа подготовка, както от учителите, така и от учениците. Предполагаме, че засега уводът в теорията на формалните езици няма да се преподава от много учители и затова няма да се спираме подробно на този урок тук.

За учителите, които се наемат да преподават искаме да обърнем внимание на две особености. Първо, терминологията в теорията на формалните езици е взимствана от терията на естествените езици, като е леко отместена. На понятието буква във формалните езици съответства дума в естествените, а на думите във формалните езици – изреченията на естествените.

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

Ще дадем тук кратки идеи за решаване на задачи 3, 4 и 5. За езика, състоящ се от всички естествени числа в двоична бройна система, терминали ще бъдат двете цифри на двоичната система – 0 и 1. Един от нетерминалите и аксиома на граматиката ще бъде обектът на формалната дефиниция “двоично число”. Тъй като не искаме думите от езика да имат водещи нули, ще се наложи отделно да дефинираме нетерминала “двоичен низ” за произволна последователност от нули и единици. Ето и съответните правила:
(1) “двоичен низ”  0

(2) “двоичен низ”  1

(3) “двоичен низ”  0“двоичен низ”

(4) “двоичен низ”  1“двоичен низ”

(5) “двоично число”  0

(6) “двоично число”  1“двоичен низ”

С така построената граматика получаваме двоичното представяне на нулата с извода:

“двоично число”  0

 10“двоичен низ”

 101
в който последователно са приложени правилата (6), (3) и (4).

По аналогия с горната граматика лесно може да се построи граматиката на естествените числа в десетична бройна система без водещи нули:

“цифра”  0|“ненула”

“низ”  “цифра”

“низ”  “цифра”“низ”

“число”  0

“число”  “ненула”“низ”

По традиция разделени с отвесна черта записваме десните части на правила с еднаква лява част. Тази задача може да дадете за домашна работа, а ако сте я решавали в клас, да поискате за домашна работа да се напишат изводи за някои от думите на езика и да се нарисуват съответните йерархични структури (дървета на извод). По същия начин може да направите граматика за езика на представянията на естествените числа в произволна позиционна бройна система.

Езикът от задача 5 е един от възможните езици на имената на променливи в езиците за програмиране. Граматиката на този език е по-лесна:

“буква”  a|b|c|…|y|z

“име”  “буква” | “име”“буква” |“цифра”“буква”

В имената на реалните езици за програмиране се допускат и други букви, например знакът за подчертаване. В езика BASIC пък се допуска името да завършва с някой от специалните знаци $, # и %. Всяка от тези модификации на понятието име на променлива може да използвате за да решите задача за съставяне на граматика.

(Примерна тема)

Left(модул,3) Mid(етика,3,2)Right(акация,3)

=модификация
2. Подредете лексикографски и според стойностите им следните числа: 123, 7289, 44, 13, 2030, 040, 72890, 7, 332266, 432, 56.
3. Намерете броя на четирицифрените десетични числа.
4. Извършете означените действия 1101001110₍₂₎ + 111001101₍₂₎ – 1010101₍₂₎ а получения резултат превърнете в десетична броина система.
5. Докажете или опровергайте следното твърдение:

X.~(Y.~Z)=(X.~Y).(X.~Z)