[ЗМІСТ]      [Далі]       [Назад]

 

2. Розгалужені програми

2.1. Умови

2.1.1. Алгебра висловлювань

2.1.2. Імплікація, тотожність, альтернатива

2.1.3. Властивості умов

2.2. Бульові інструкції

2.2.1. Бульове присвоєння

2.2.2. Розгалуження

2.2.3. Порівняння розгалужених алгоритмів

2.3. Програмування розгалужених алгоритмів

 

2. РОЗГАЛУЖЕНІ ПРОГРАМИ

 

У розглянутих досі арифметичних алгоритмах залишилися відкритими багато питань. Зокрема - це питання попередження відмов. Звичайно, відмова - це наслідок некоректних дій: помилок і описок. Чи Завжди відмови неминучі? Як уникнути беззахисності інструкцій перед неправильними даними?

Бажано було б всі можливі ситуації, які виникають в процесі виконання алгоритму, розділити навпіл. До першої групи віднести сприятливі, до другої - несприятливі. Однак так можливе ділення не тільки навпіл, але і на більшу кількість частин, візьмемо, наприклад, сигнум-функцію.

Передусім помітимо, що відповіді операційного пристрою на питання пристрою керування самі можуть служити об'єктом перетворень: їх можна було б запам'ятовувати, порівнювати один з одним і т.д. Так крім арифметичних виразів виникає потреба у виразах іншого питально - ствердного характеру. Їх значення - це відповіді  "так" чи  "ні" на питання відносно наявності тих або інших співвідношень між величинами, що використовуються. Такі вирази походять з математичної логіки, тому часто називаються логічними. На нашу думку термін  "логічний" вводить в оману, тому, що логічний вираз може стати безглуздим, наприклад, 1=2. Таким чином, об'єднувати логічно вірні і спірні вирази під назвою логічних не варто. Наслідуючи Н.Вірта, будемо називати їх умовами або бульовими виразами на ім'я їх дослідника англійського математика Дж.Буля (1815-1864).

Використання бульових виразів в інформатиці значне і повсюдне. Крім безпосередніх застосувань для вибору зручного ходу обчислень, (зокрема,  управління циклами), в перспективі більш віддаленої до перетворення умов зведуться питання аналізу алгоритмів і програм і, в деякій мірі, сам процес побудови алгоритмів.

 

2.1. Умови

2.1.1. Алгебра висловлювань

 

У попередній частині вже розглядалися змінні з обмеженими множинами значень. Зараз мова буде йти мало не про найпростіші з них: висловлювання, здатні приймати усього одне з двох можливих значень. Самі ці значення в принципі можна було б означати як-завгодно: "так", "ні"; 1 або 0; "істина" і "хибність" - важливо тільки уміти відрізняти одне з них від іншого. Ці значення вважають одне запереченням іншого. Домовимося означати відповідь  "так" буквами Іст, а відповідь  "ні" - буквами Хиб. Областю істинності B2 назвемо множину, яка складається з двох величин

B2 ={ Хиб, Іст }.

Множину В2 перетворюємо в алгебру - її називають алгеброю висловлювань. Для цього визначимо три бульових операції:

 а) диз’юнкція х V у дає по двох висловлюваннях х і у нове висловлювання, хибне тоді і тільки тоді, коли хибні одночасно х і у; у всіх інших випадках диз’юнкція істинна;

 b) кон’юнкция х & у дає по двох висловлюваннях х і у нове висловлювання, істинне тільки тоді, коли одночасно істинні х і у; у всіх інших випадках кон’юнкція хибна;

 c) заперечення Øx дає по висловлюванню х нове висловлювання, протилежне за змістом. Визначення бульових операцій можна задати такими таблицями

 

  х   у 

 х V у

 х & у

 

  х 

  Øx 

 Хиб Хиб

  Хиб 

  Хиб 

 

 Хиб

 Іст

 Хиб Іст 

  Іст 

  Хиб 

 

 Іст

 Хиб

 Іст Хиб

  Іст 

  Хиб 

 

 

 

 Іст Іст

  Іст 

  Іст 

 

 

 

 

Тепер, використовуючи бульові значення Іст і Хиб, ідентифікатори для позначення бульових змінних і констант, визначимо поняття найпростішого бульового виразу - висловлювання - по звичайній (див. розділ 1.2.3) схемі. Висловлювання - це булів вираз, який визначається індуктивно:

 - якщо b - бульова константа або змінна, то b - (просте) висловлювання;

 - якщо b і c висловлювання, то (b V c), (b & c), (¬ b) - (складені) висловлювання.

Домовимося про таке старшинство бульових операцій: диз’юнкція, кон’юнкція, заперечення - в порядку зростання. Скорочують запис бульового виразу так само, як і алгебраїчного, опускаючи неістотні дужки.

Використовуючи табличне визначення бульових операцій, значення бульового виразу обчислюють за значеннями простих висловлювань, що складають його. Наприклад, при х= Хиб, у= Хиб, z= Іст

¬х & (у V¬ z)= ¬Хиб & (Хиб V¬ Іст)= Іст & (Хиб V Хиб)= Іст & Хиб= Хиб.

Аналогічно з алгеброю чисел, в алгебрі логіки можна встановити тотожності, які використовуються для спрощення бульових виразів.

    Властивість 2.1. Нехай р, q, r Î B2.  Тоді справедливі тотожності:

     а) комутативність диз’юнкції і кон’юнкції

       р V q º q V р,   р & q º q & р;

    b) асоціативність диз’юнкції і кон’юнкції

       (р V q) V r º р V (q V r),  (р & q) & r º р & (q & r);

    c) дистрибутивність кон’юнкції відносно диз’юнкції

       р & (q V r) º р & q V р & r,

       дистрибутивність диз’юнкції відносно кон’юнкції

       р V q & r º (р V q) & (р V r);

    d) властивості бульових констант

       р V Іст º Іст,  р V Хиб º р,

       р & Іст º р,  р & Хиб º Хиб;

    e) ідемпотентність

       р V р º р,   р & р º р;

    f) подвійне заперечення

       Ø( Øp) º p;

    g) правила де Моргана (1806-1871)

       Ø(p V q) º Øp & Øq,

       Ø(p & q) º Øp V Øq;

    h) закон виключення третього

       р V Ø р º Іст;

    i) закон протиріччя

       р & Ø р º Хиб.

      Доведення проводять перебором всіх можливих  значень  р, q і r, порівнюючи значення виразів зліва та справа.

      Для прикладу розглянемо комутативність диз’юнкції

 

  р   q

 р V q

 q V р

 Хиб Хиб

  Хиб 

  Хиб 

 Хиб Іст

  Іст 

  Іст 

 Іст Хиб

  Іст 

  Іст 

 Іст Іст

  Іст 

  Іст 

 

і дистрибутивність диз’юнкції відносно кон’юнкції

 

  р   q   r

q & r

р V q & r

р V q

 р V r

 (р V q) & (р V r)

 Хиб Хиб Хиб

  Хиб

    Хиб  

  Хиб

  Хиб

        Хиб      

 Хиб Хиб Іст

  Хиб

    Хиб  

  Хиб

  Іст

        Хиб      

 Хиб Іст Хиб

  Хиб

    Хиб  

  Іст

  Хиб

        Хиб      

 Хиб Іст Іст

  Іст

    Іст  

  Іст

  Іст

        Іст      

 Іст Хиб Хиб

  Хиб

    Іст  

  Іст

  Іст

        Іст      

 Іст Хиб Іст

  Хиб

    Іст  

  Іст

  Іст

        Іст      

 Іст Іст Хиб

  Хиб

    Іст  

  Іст

  Іст

        Іст      

 Іст Іст Іст

  Іст

    Іст  

  Іст

  Іст

        Іст      

 

      Інші тотожності доводяться аналогічно.¦

 

2.1.2. Імплікація, тотожність, альтернатива

 

      Розглянемо деякі корисні бульові функції, що не увійшли  до стандартного бульового типу.

      Нехай p,q,r,p1,p2  Î B2. Імплікацією (від латинського implico - тісно зв'язую) p É q - читається  "р спричиняє  q" або "якщо р то q" - назвемо бульову функцію, задану виразом

            p É q º Øp V q.

      Висловлювання р називається основою, q - висновком.

      Використовуючи визначення операцій заперечення і диз’юнкції (див. п.2.1.1) значення імпликації задаються таблицею

 

  р   q

  Ø р

  р É q

 Хиб Хиб

 Іст

   Іст  

 Хиб Іст

 Іст

   Іст  

 Іст Хиб

 Хиб

   Хиб  

 Іст Іст

 Хиб

   Іст  

 

 тобто справедливе ще одне визначення

                ¦ Іст, якщо р = Хиб;

       p É q º <

                ¦ q, якщо р = Іст.

      Булів вираз b(р,  q,. .., r) називають тотожньо-істинним, якщо він приймає істинне значення при всіх можливих  значеннях своїх аргументів

       b(р,  q,. .., r) º  Іст.

    Властивість 2.2. Наступні вирази тотожньо-істинні

       a) (p & q) É p º Іст;

       b) p É (p V q) º Іст.

    Доведення проводять шляхом порівняння таблиць або видаленням імплікації та застосуванням властивостей 2.1. Наприклад,

       a) (p & q) É p º Ø(p & q) V p  {за означенням імплікації}

                      º Øp V Øq V p  {правило де Моргана}

                      º p V Øp V Øq  {комутативність диз’юнкції}

                      º Іст V Øq  {виключення третього}

                      º   Іст  {властивість констант}.¦

    Властивість 2.3. Справедливі тотожності

       a) Øp É q º Øq É p;

       b) Øp É Øq º q É p;

       c) (p & q)  É r º p É (q É r);

       d) p É (q V r) º (p É q) V r.

    Доведення a):

        Øp É q º Ø( Øp) V q  {за означенням}

               º p V q  {подвійне заперечення}

               º q V p  {комутативність диз’юнкції}

               º Ø( Øq) V p  {подвійне заперечення}

               º Øq É p  {визначення імпплікації}.¦

Імплікація використовується для визначення двох інших бульових функцій.

Тотожність - це бульова функція, задана виразом

E(p, q) = (p É q) & (q É p).

Дамо табличне визначення тотожності

 

 p

 q

 Øp

 Øq

 p  É q

 q  É p

 (p  É q)&(q  É p)

Хиб

Хиб

 Іст

 Іст

  Іст 

  Іст 

        Іст       

Хиб

Іст

 Іст

 Хиб

  Іст 

  Хиб 

        Хиб       

Іст

Хиб

 Хиб

 Іст

  Хиб 

  Іст 

        Хиб       

Іст

Іст

 Хиб

 Хиб

  Іст 

  Іст 

        Іст       

 

Розглядаючи побудовану таблицю, бачимо, що функція Е(р, q) дійсно виражає тотожність виразів р і q, оскільки приймає значення істина тоді і тільки тоді, коли значення виразів р і q співпадають.

Значить, записуючи тотожність p º q, ми розуміємо тотожню істинність виразу Е(р, q)  º Іст.

      Тепер визначимо тримісну бульову функцію альтернативи

 

                     ¦ q, якщо р = Іст;

       if (p,q,r) = <

                     ¦ r, якщо р = Хиб.

 

      Запис if (р,q,r) читається так: "якщо р, то q, інакше r".

      Властивість 2.4. Справедлива тотожність

       if (p,q,r) º (p É q) & ( Øp É r).

      Доведення. Розберемо два випадки. Нехай р = Іст. Тоді

       р É   q = Іст É   q = Ø Іст V q = Хиб V q = q;

       Ø р É   r = Ø Іст É   r = ØØ Іст V r = Іст V r = Іст.

    Тому

       (p É q) & ( Øp É r) = q & Іст = q = if(Іст,q,r).

    При р = Хиб маємо

       р É   q = Хиб É   q = Ø Хиб V q = Іст V q = Іст;

       Ø р É   r = Ø Хиб É   r = ØØ Хиб V r = Хиб V r = r. Тому

       (р É  q) & (Ø р É r) = Іст & r = r = if (Хиб,q,r).

    Що і потрібно було довести.¦

      По ходу ми довели

      Наслідок 2.1. Правила видалення альтернативи

       a) if (Іст,q,r) º q ;

       b) if (Хиб,q,r) º r;

       c) if (р,q,q) º q .

      Зв'яжемо альтернативу із запереченням, кон’юнкцією, диз’юнкцією та імплікацією.

      Властивість 2.5. Справедливі тотожності

       a) if ( Øp,q,r) º if (p,r,q);

       b) if (p  & p ,q,r) º if (p ,if (p ,q,r),r);

               1    2             1      2

       c) if (p  V p ,q,r) º if (p ,q,if (p ,q,r));

               1    2             1        2

       d) if (p   É p ,q,r) º if (p ,if (p ,q,r),q).

               1     2             1      2

    Доведення.

    a) if ( Øp,q,r) º ( Øp É q) & ( Ø Øp  É r) º

                    º (p  É r) & ( Øp  É q)     º if (p,r,q).

 

    b) Нехай р = Хиб. Тоді р  & р = Хиб,

              1             1    2

 

if(р  & р ,q,r) = if(Хиб,q,r) = r.

    1    2

    Розглянемо праву частину

    if (р ,if (р ,q,r),r) = if(Хиб, if(р ,q,r),r) = r.

         1      2                       2

 

    Нехай р = Іст, р = Хиб. Тоді р  & р  = Хиб,

           1        2             1    2

 

if(р  & р , q, r) = if(Хиб, q, r) = r.

    1    2

    Розглянемо праву частину

    if(р , if(р , q,r),r) = if(Іст, if(Хиб,q,r),r) = if(Хиб,q,r) = r.

        1      2

 

    Нарешті р = Іст, р = Іст. Тоді р  & р  = Іст,

             1        2             1    2

 

if(р  & р ,q,r) = if(Іст,q,r) = q.

    1    2

    Знов розглянемо праву частину

    if(р , if(р ,q,r),r) = if(Іст, if(Іст,q,r),r) = if(Іст,q,r) = q.

        1      2

    Випадки c) і d) доведіть самостійно.¦

 

2.1.3. Властивості умов

 

Розглянемо тепер зв'язок між висловлюванням і арифметичними виразами. Наприклад, вираз "2+2 = 4" може служити прикладом тотожно-істинного висловлювання, а "3 > 5" - тотожньо-хибного. Висновок про істинність виразу х+у = 4 або х>3 залежав би від значень, отриманих числовими змінними, так само як складеного виразу (х+у = 4) & (х>3).

З'єднаємо бульові вирази з арифметичними, застосувавши поняття відношення. Відношення дає одне бульове значення за одною або декільком (частіше за все двом) арифметичним величинам. На кожній з числових множин, що використовується - N, Z і Q, утворимо стандартний набір відношень:

 

       х рівне у, або х = у;

       х не рівне у, або х <> у;

       х менше, ніж у, або х < у;

       х більше, ніж у, або х > у;

       х менше або рівне у, або х <= у;

       х більше або рівне у, або х >= у.

Будемо вважати, що при довільних значеннях х і у  приведені відношення приймають бульові значення Іст і Хиб в залежності від того, справедливі вони, чи ні. Наприклад, х > 5 = Іст при х = 6 і х > 5 = Хиб  при х = 3.

Визначимо Rel = { =, <>, <, >, <=, >= }.

Приймаючи Хиб < Іст можна поширити відношення Rel також на область істинності B2. Правда, в цьому випадку вони просто  виражаються через бульові операції, наприклад, p < q = Øp & q, p <= q = p É q.

Встановимо зв'язок між відношеннями Rel та бульовими операціями.

Властивість 2.6. Справедливі тотожності

    a) x<>y º  Ø(x=y) º x<y V x>y;

    b) x<=y º  Ø(x>y) º x<y V x=y;

    c) x>=y º  Ø(x<y) º x>y V x=y.

 

Доведення. a) Розглянемо довільні значення a, b виразів х і у, відповідно. Можливі три випадки.

    - Нехай а<b. Тоді

            а<>b = Іст,

       Ø (а=b) = Ø Хиб = Іст,

       а<b V а>b = Іст V Хиб = Іст.

    - Нехай а=b. Тоді

            а<>b = Хиб

       Ø (а=b) =  ØІст = Хиб,

       а<b V а>b = Хиб V Хиб = Хиб.

    - Нехай а>b. Тоді

            а<>b = Іст,

        Ø(а=b) = Ø Хиб = Іст,

       а<b V а>b = Хиб V Іст = Іст.

Тотожності b) і c) доводяться аналогічно.¦

Зауваження 2.1. Відносно висловлювання відношення мають таку істотну особливість: вони можуть  виявитися невизначеними при певних аргументах. Наприклад, відношення 1/х = у не має значення  при х = 0. Тому, розглядаючи відношення, необхідно враховувати три випадки: істинність, хибність та невизначеність.¦

 

Тепер візьмемо за зразок визначення висловлювання з п.2.1.1. та узагальнимо поняття бульового виразу, доповнивши його відношеннями.

Умовою F будемо називати булів вираз, побудований індуктивно за правилом:

    - якщо F бульова константа або змінна, то F - умова;

    - якщо е ,  е  - арифметичні вирази, r відношення з Rel, то

            1    2

F = (е  r е ) - умова;

      1    2

    - якщо F ,  F  - умови, r відношення з Rel, то F = (F  r F ) - умова;

            1    2                                       1    2

    - якщо F ,  F  - умови, то F = (F V F ), F = (F & F ), F = (Ø F ) – умови.

            1    2                   1   2         1   2           1

Як звичайно, умовимося про скорочення, вважаючи, що насамперед виконуються арифметичні операції, потім - відношення і в останню чергу - бульові операції.

Перевіркою умови будемо називати обчислення її значення в залежності від значень бульових та арифметичних змінних, що використовуються в ній. Наприклад, нехай х=1, у=2, z=3, р=Іст, q=Хиб,  тоді

       х<у & у<z    = Іст;

       х=4 V р      = Іст;

       х=4 & р      = Хиб;

      Ø (х+у=z)     = Хиб;

       Ø(х+у=z & q) = Іст.

 

Домовимося про наступне скорочення. Якщо F - умова, справедлива до виконання деякої інструкції Р, а  G - умова, справедлива після виконання Р, то цю властивість будемо записувати так

       { F } Р { G }.

При цьому умова F називається передумовою інструкції Р, а G - післяумовою Р.

Тепер аналогічно з альтернативою дамо визначення умовного виразу. Нехай F - умова, a, b - арифметичні вирази. Умовним назвемо вираз

 

                     ¦ a, якщо F = Іст;

     IF (F, a, b) = <                                      (2.1)

                     ¦ b, якщо F = Хиб.

 

Умовні вирази дозволяють компактно записувати деякі функції і в такій якості часто будуть використовуватися в майбутньому. Так, наприклад, визначення  модуля числа за допомогою умовного виразу

 

       abs(х) = IF (х>0, х,-x)

з урахуванням (2.1) приймає звичний вигляд, так само як і функція сигнум

 

       sign(х) = IF (х<0,-1, IF (х=0,0,1)).

Повернемося до зауваження 2.1. Вираз, який містить в собі невизначений підвираз, природно вважається невизначеним. Однак по відношенню до умовного виразу, це буде не завжди так. Ось приклад. Вираз

 

       А(х) = IF (х=0,1,1/х)

вважаємо визначеним при всіх х, хоч підвираз 1/х не допускає рівності х=0; на цей випадок він захищений умовою х<>0.

Займемося узагальненням властивостей альтернативи по відношенню до умовних виразів. Враховуючи можливу невизначеність, порівнювати умовні вирази важче.

    Вираз В називають розширенням виразу А, якщо:

    1) з визначеності А при деяких значеннях аргументів слідує, що В також визначено при цих же значеннях аргументів, причому

    2) значення обох виразів співпадають А = В.

Іншими словами, при фіксованих значеннях аргументів можливий один з трьох випадків:

    1) А і В обидва невизначені;

    2) А і В визначені, причому А = В;

    3) B визначено, а А - ні.

Вираз А в цьому випадку називають також звуженням виразу В.

Позначення: А Ì В, В É А.

Наприклад, IF (х>0 V х/у<1, х/z, х*у) - звуження виразу IF (х>0, х/z, IF (х/у<1, х/z, х*у)) (перевірте!).

Вирази А і В тотожні  А  В, якщо одночасно А Ì В і В Ì А.

 

    Аналог властивості 2.5 і наслідку 2.1 для умовних виразів дає

    Властивість 2.7. Нехай F, F  і F  - умови. Тоді

                               1    2

 

       a) IF (Іст,a,b) º a;

       b) IF (Хиб,a,b) º b;

       c) IF (F,a,b) º IF ( ØF,b,a);

       d) IF (F,a,a)  Ì  a;

       e) IF (F  & F ,a,b)  Ì  IF (F , IF (F ,a,b),b);

               1    2              1       2

 

       f) IF (F  V F ,a,b)  Ì  IF (F ,a, IF (F ,a,b));

               1    2              1         2

 

       g) IF (F  É F ,a,b)  Ì  IF (F , IF (F ,a,b),a).

               1    2              1       2

    Для доведення необхідно врахувати випадки невизначеності умов F, F1 та F2.

[ЗМІСТ]      [Далі]       [Назад]