Практичне заняття №2 алгебра логіки
Мета заняття: вивчити основи алгебри логіки.
Питання, що розглядаються:
-
Основні поняття: проста і складне висловлювання, логічні операції, логічні вирази, логічна функція.
-
Порядок виконання логічних операцій.
-
Алгоритм побудови таблиць істинності.
-
Схеми базових логічних елементів.
-
Закони логіки
Основні поняття алгебри логіки
Логічною основою комп’ютера є алгебра логіки, яка розглядає логічні операції над висловлюваннями.
Алгебра логіки – це розділ математики, що вивчає висловлювання, що розглядаються зі сторони їх логічних значень (істини або хибності) і логічних операцій над ними.
Логічне висловлювання – це будь-яке розповідне речення, стосовно якого можна однозначно сказати, чи є воно істинним або хибним.
Приклад 2.1. «3 – просте число» є висловлюванням, оскільки воно є істинним.
Не будь-яке речення є логічним висловлюванням.
Висловлювальна форма – це розповідне речення, яке прямо або опосередковано містить хоча б одну змінну і стає висловлюванням, коли всі змінні заміщаються своїми значеннями.
Приклад 2.2 «x+2>5» - висловлювальна форма, яка при x>3 є істинною, а в протилежному випадку хибною.
Алгебра логіки розглядає будь-яке висловлювання з однієї точки зору – є воно істинним або хибним.
Слова і словосполучення «не», «і», «або», «якщо ..., то», «тоді і тільки тоді» та інші дозволяють з вже заданих висловів будувати нові висловлювання. Такі слова і словосполучення називаються логічними зв'язками.
Висловлювання, утворені з інших висловлювань за допомогою логічних зв'язок, називаються складними (складними). Висловлювання, які не є складовими, називаються елементарними (простими).
Приклад. Вислів «Число 6 ділиться на 2» - просте висловлювання. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - складене висловлювання, утворене з двох простих за допомогою логічної зв'язки «і».
Істинність або хибність складових висловлювань залежить від істинності чи хибності елементарних висловлювань, з яких вони складаються.
Щоб звертатися до логічних висловлювань, їм призначають імена.
Приклад 2.3. Позначимо через А просте висловлювання «число 6 ділиться на 2», а через В просте висловлювання «число 6 ділиться на 3». Тоді складене висловлювання «Число 6 ділиться на 2, і число 6 ділиться на 3» можна записати як «А і В». Тут «і» - логічна зв'язка, А, В - логічні змінні, які можуть приймати тільки два значення - «істина» або «брехню», що позначаються, відповідно, «1» і «0».
Кожна логічна зв'язка розглядається як операція над логічними висловленнями і має свою назву та позначення (табл. 1).
Таблиця 2.1
Позначення операції |
Читається |
Назва операції |
Альтернативні позначення |
¬ |
НЕ |
Заперечення (інверсія) |
Риска зверху |
|
І |
Кон'юнкція (логічне множення) |
& |
|
АБО |
Диз'юнкція (логічне додавання) |
+ |
XOR |
АБО … АБО |
Виключаюче АБО (додавання по модулю 2) |
|
НЕ Операція, що виражається словом «не», називається запереченням і позначається рискою над висловлюванням (або знаком ¬). Висловлювання ¬А істинне, коли A помилкове, і помилкове, коли A істинне.
Приклад 2.4. Нехай А = «Сьогодні похмуро», тоді ¬А = «Сьогодні не похмуро».
І Операція, що виражається зв'язкою «і», називається кон'юнкцією (лат. conjunctio - з'єднання) або логічним множенням і позначається крапкою « • » (може також позначатися знаками або &). Висловлювання А • В істинне тоді і тільки тоді, коли обидва висловлювання А і В істинні.
Приклад 2.5. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - істинний, а вислів «Число 6 ділиться на 2, і число 6 більше 10» - хибний.
АБО Операція, що виражається зв'язкою «або» (в прямому сенсі цього слова), називається диз'юнкцією (лат. disjunctio - поділ) або логічним додаванням і позначається знаком (або плюсом). Висловлювання АВ хибне тоді і тільки тоді, коли обидва висловлювання А і В хибні.
Приклад 2.6. Вислів «Число 6 ділиться на 2 або число 6 більше 10» - істинний, а вислів «Число 6 ділиться на 5 або число 6 більше 10» - хибний.
АБО ... АБО Операція, що виражається зв'язками «Або ... або», називається виключаюче АБО чи додавання по модулю 2 і позначається XOR або . Висловлювання АВ істинне тоді і тільки тоді, коли значення А і В не збігаються.
Приклад 2.7. Вислів «Число 6 або непарне або ділиться без залишку на 2» є істинним, а вислів «Або число 6 парне або число 6 ділиться на 3» - помилковий, так як істинні обидва висловлювання, що входять в нього.