Логічні основи алгоритмізації

Окрім теорії алгоритмів, ще одним важливим розділом математичної логіки, що має пряме відношення до програмування, є алгебра логіки (алгебра висловлювань).

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

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

Логічне висловлювання - це будь-яке твердження, про яке можна однозначно сказати, правильне (істинне) воно чи неправильне (хибне).

Основною властивістю є його істинність, інші властивості вважаються несуттєвими.

Значення істинності висловлювання позначають 1 або true, хибності - 0 або false (значення true та false називаються логічними константами). Наприклад, висловлювання А = «Київ – столиця України» є істинним, тобто значення його властивості істинність дорівнює true. Висловлення С = «3 > 5» є хибним, тобто значення його властивості істинність дорівнює false.

Висловлювання можуть бути простими (елементарними) і складеними. Складені висловлювання утворюються з простих. Для утворення нових висловлювань з вже заданих використовуються логічні зв’язки (операції), якими є слова і словосполучення "не" , "і" , "або", " якщо ..., то" , " тоді і тільки тоді" та інші.

Функцію f(х₁, х₂, …, х_n), яка набуває тільки значення 0 або 1, як і її аргументи, прийнято називати булевою (логічною). Аргументи булевої функції також називають булевими.

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

Довільна булева функція може бути задана табличним cпособом, у вигляді аналітичного виразу або графічно. Таке подання булевої функції використовується, зокрема, в задачах аналізу і синтезу цифрових схем комп’ютерів.

Подібно до того, як у математиці використовують таблиці додавання та множення для визначення результатів виконання цих арифметичних операцій, у математичній логіці значення істинності для логічних операцій, зазвичай задається за допомогою таблиць істинності. Таблиця істинності — математична таблиця, що широко використовується у математичній логіці, зокрема в алгебрі логіки, для обчислення значень булевих функцій. У таблиці істинності для кожного можливого набору значень властивості «істинність» висловлень наводиться відповідне значення цієї властивості для висловлення, яке є результатом виконання логічної операції над ними.

Алгебра логіки визначає три основні логічні операції:

- заперечення (інверсія),

- кон'юнкція (логічне множення);

- диз'юнкція (логічне додавання ).

Заперечення в логіці — це операція над висловлюванням, результатом якої є висловлювання, «протилежне» початковому. Результатом її застосування є утворення з висловлювання х такого складеного висловлювання, яке істинне тоді, коли х хибне, і хибне тоді, коли х істинне.

Позначається в математичній логіці знаком «Ø» і відповідає логічному зв’язку "не". Наприклад, запис Ø(х = у) читається таким чином: не (х дорівнює у), тобто значення буде істинним, якщо х не дорівнює у і хибним, якщо х дорівнює у.

За означенням, заперечення виконується над одним висловленням, яке може бути або істинним, або хибним. Тому таблиця істинності операції заперечення має такий вигляд:

 

х	Ø х

Кон’юнкція – операція, яка приймає значення ІСТИНА тоді і тільки тоді, коли усі її операнди мають значення ІСТИНА.

Результатом її застосування є утворення складного висловлювання, що містить 2 або більше простих висловлювання, і яке є істинним тоді і лише тоді, коли істинними є прості висловлювання, і хибним, якщо хоч одне з простих висловлювань хибне.

Дана операція позначається в математичній логіці як і відповідає логічному зв’язку І. Наприклад, запис (х > 0) (х < 1) означає, що даний логічний вираз прийме значення ІСТИНА, якщо х Î [0, 1], і значення ХИБНІСТЬ - в іншому випадку.

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

 

х	y	x Ù y

 

Диз'юнкція - операція, яка приймає значення ХИБНІСТЬ тоді і тільки тоді, коли усі її операнди мають значення «ХИБНІСТЬ».

Результатом її застосування є утворення складного висловлювання, що містить 2 або більше простих висловлювання, і яке є хибним тоді і лише тоді, коли хибними є усі прості висловлювання, і істиним, якщо хоч одне з простих висловлювань істине.

Дана операція позначається в математичній логіці як v і відповідає логічному зв’язку АБО. Наприклад , запис (x = 0) v ( x = l ) означає, що даний логічний вираз прийме значення ІСТИНА, якщо х - двійкова цифра ( 0 або 1).

Таблиця істинності операції диз'юнкція має такий вигляд:

 

х	y	x v y

 

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

.

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