Основні поняття алгебри логіки - студопедія

Загальні теоретичні відомості

Основні поняття алгебри логіки

Логічною основою комп'ютера є алгебра логіки, яка розглядає логічні операції над висловлюваннями.

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

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

Приклад. «3 - просте число» є висловлюванням, оскільки воно істинне.

Не всяке пропозицію є логічним висловлюванням.

Приклад. пропозиція «Давайте підемо в кіно» не є висловлюванням. Знаки запитання й спонукальні пропозиції висловлюваннями не є.

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

Приклад. «X + 2> 5» - висказивательной форма, яка при x> 3 є істинною, інакше помилковою.

Алгебра логіки розглядає будь-яке висловлювання тільки з однієї точки зору - чи є воно істинним або хибним. Слова і словосполучення «не», «і», «або», «якщо. то »,« тоді і тільки тоді »і інші дозволяють з вже заданих висловлювань будувати нові висловлювання. Такі слова і словосполучення називаються логічними зв'язками.

Висловлювання, утворені з інших висловлювань за допомогою логічних зв'язок, називаються складовими (складними). Висловлювання, які не є складовими, називаються елементарними (простими).

Приклад. вислів «Число 6 ділиться на 2» - просте висловлювання. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - складене висловлювання, утворене з двох простих за допомогою логічної зв'язки «і».

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

Щоб звертатися до логічних висловлювань, їм призначають імена.

Приклад. Позначимо через А просте висловлювання «число 6 ділиться на 2», а через В просте висловлювання «число 6 ділиться на 3». Тоді складене висловлювання «Число 6 ділиться на 2, і число 6 ділиться на 3» можна записати як «А і В». Тут «і» - логічна зв'язка, А, В - логічні змінні, які можуть приймати тільки два значення - «істина» або «брехня», що позначаються, відповідно, «1» і «0».

Кожна логічна зв'язка розглядається як операція над логічними висловлюваннями і має свою назву і позначення (табл. 1).

Таблиця 1. Основні логічні операції

НЕ Операція, що виражається словом «не», називається запереченням і позначається рисою над висловлюванням (або знаком). Висловлення А істинно, коли A помилково, і помилково, коли A істинно.

Приклад. Нехай А = «Сьогодні похмуро», тоді А = «Сьогодні не похмуро».

І Операція, що виражається зв'язкою «і», називається кон'юнкція (лат. Conjunctio - з'єднання) або логічним множенням і позначається крапкою «•» (може також позначатися знаками або ). Висловлення А • В істинно тоді і тільки тоді, коли обидва висловлювання А і В істинні.

Приклад. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - істинно, а висловлювання «Число 6 ділиться на 2, і число 6 більше 10» - помилково.

АБО Операція, що виражається зв'язкою «або» (в невиключає сенсі цього слова), називається диз'юнкція (лат. Disjunctio - поділ) або логічним складанням і позначається знаком

(Або плюсом). Висловлення А В хибно тоді і тільки тоді, коли обидва висловлювання А і В помилкові.

Приклад: Вислів «Число 6 ділиться на 2 або число 6 більше 10» - істинно, а висловлювання «Число 6 ділиться на 5 або число 6 більше 10» - помилково.

ЯКЩО ... ТО Операція, що виражається зв'язками «якщо ..., то», «з ... слід», «. тягне ... », називається импликацией (лат. implico - тісно пов'язані) і позначається знаком →. Висловлення А → В помилково тоді і тільки тоді, коли А істинно, а В брехливо.

Приклад. Вислів «якщо студент здав всі іспити на« відмінно », то він отримає стипендію». Очевидно, цю імплікації слід визнати помилковою лише в тому випадку, коли студент здав на «відмінно» всі іспити, але стипендії не отримав. В інших випадках, коли не всі іспити здані на «відмінно» і стипендія отримана (наприклад, в силу того, що студент проживає в малозабезпеченій сім'ї) або коли іспити взагалі не здані і про стипендії не може бути й мови, імплікації можна визнати істинною.

Рівносильно Операція, що виражається зв'язками «тоді і тільки тоді», «необхідно і достатньо», «. рівносильно ... », називається еквіваленціі або подвійний импликацией і позначається знаком ↔ або

Висловлення А↔В істинно тоді і тільки тоді, коли значення А і В збігаються.

Приклад: Вислів «Число є парним тоді і тільки тоді, коли воно ділиться без залишку на 2» є істинним, а висловлювання «Число є непарних тоді і тільки тоді, коли воно ділиться без залишку на 2» - помилково.

АБО ... АБО Операція, що виражається зв'язками «Або ... або», називається виключає АБО або складанням по модулю 2 і позначається XOR або. Висловлення А В істинно тоді і тільки тоді, коли значення А і В не збігаються.

Приклад. Вислів «Число 6 або непарній або ділиться без залишку на 2» є істинним, а висловлювання «Або число 6 парне або число 6 ділиться на 3» - помилково, так як істинні обидва висловлювання входять до нього.

Зауваження. Імплікації можна виразити через диз'юнкцію і заперечення:

.

Еквіваленцію можна виразити через заперечення, диз'юнкцію і кон'юнкцію:

.

Що виключає Або можна виразити через заперечення, диз'юнкцію і кон'юнкцію:

.

Висновок. Операцій заперечення, диз'юнкції і кон'юнкції досить, щоб описувати і обробляти логічні висловлювання.

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

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

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

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

Приклад. - логічна функція двох змінних A і B.

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

Наведемо таблицю істинності основних логічних операцій (табл. 2)

Спираючись на дані таблиці істинності основних логічних операцій можна складати таблиці істинності для більш складних формул.

Алгоритм побудови таблиць істинності для складних виразів:

1. Визначити кількість рядків:

• кількість рядків = 2 n + рядок для заголовка,

• n - кількість простих висловлювань.

2. Визначити кількість стовпців:

• кількість стовпців = кількість змінних + кількість логічних операцій;

• визначити кількість змінних (простих виразів);

• визначити кількість логічних операцій і послідовність їх виконання.

Приклад 1. Скласти таблицю істинності для формули І-НЕ, яку можна записати так:.

1. Визначити кількість рядків:

На вході два простих висловлювання: А і В, тому n = 2 і кількість рядків = 2 2 + 1 = 5.

2. Визначити кількість стовпців:

Вираз складається з двох простих виразів (A і B) і двох логічних операцій (1 інверсія, 1 сполучення), тобто кількість стовпців таблиці істинності = 4.

3. Заповнити стовпці з урахуванням таблиць істинності логічних операцій (табл. 3).

Таблиця 3. Таблиця істинності для логічної операції

Примітка: І-НЕ називають також «штрих Шеффера» (позначають |) або «антікон'юнкція»; АБО-НЕ називають також «стрілка Пірса» (позначають ↓) або «антідіз'юнкція».

Приклад 2. Скласти таблицю істинності логічного виразу.

1. Визначити кількість рядків:

На вході два простих висловлювання: А і В, тому n = 2 і кількість рядків = 2 2 + 1 = 5.

2. Визначити кількість стовпців:

Вираз складається з двох простих виразів (A і B) і п'яти логічних операцій (2 інверсії, 2 кон'юнкції, 1 диз'юнкція), тобто кількість стовпців таблиці істинності = 7.

Спочатку виконуються операції інверсії, потім кон'юнкції, в останню чергу операція диз'юнкції.

3. Заповнити стовпці з урахуванням таблиць істинності логічних операцій (табл. 5).

Таблиця 5. Таблиця істинності для логічної операції

Логічні формули можна також представляти за допомогою мови логічних схем.

Існує три базових логічних елемента, які реалізують три основні логічні операції:

• логічний елемент «І» - логічне множення - кон'юнктор;

• логічний елемент «АБО» - логічне додавання - діз'юнктор;

• логічний елемент «НЕ» - інверсію - інвертор.

Оскільки будь-яка логічна операція може бути представлена ​​у вигляді комбінації трьох основних, будь-які пристрої комп'ютера, що виробляють обробку або зберігання інформації, можуть бути зібрані з базових логічних елементів, як з "цеглинок".

Логічні елементи комп'ютера оперують з сигналами, що представляють собою електричні імпульси. Є імпульс - логічний зміст сигналу - 1, немає імпульсу - 0. На входи логічного елемента надходять сигнали-значення аргументів, на виході з'являється сигнал-значення функції.

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