7.3. Який зв’язок між алгеброю логіки та двійковим кодуванням?
7. Логічні засади функціонування ЕОМ. Логічні вирази. Логічні елементи.Типові логічні вузли: тригер, суматор.
7.1. Що таке логіка алгебри?
Алгебра логіки- це математичний апарат, за допомогою якого записують, обчислюють, спрощують і перетворюють логічні висловлювання.
Творцем алгебри логіки є англійський математик Джордж Буль, що жив у ХIХ столітті, на честь якого ця алгебра названа булевою алгеброю висловлювань.
Логічний вислів- це будь-яка оповідальна пропозиція, у відношенні якого можна однозначно сказати, істинно воно або неправильно.
Приміром, пропозицію “6 — парне число” слід вважати висловлюванням, оскільки воно істинне. Пропозиція “Рим - столиця Франції” теж висловлювання, оскільки воно хибне.
Зрозуміло, не всяка пропозиція є логічним висловлюванням. Висловлюваннями не є, наприклад, пропозиції "учень десятого класу" та "інформатика - цікавий предмет". Перша пропозиція нічого не стверджує про учня, а друга використовує надто невизначене поняття “цікавий предмет”. Питання та оклику речення також не є висловлюваннями, оскільки говорити про їх істинність чи хибність не має сенсу.
Пропозиції типу “у містіAпонад мільйон жителів”, “у нього блакитні очі” не є висловлюваннями, оскільки для з'ясування їхньої істинності чи хибності потрібні додаткові відомості : про яке конкретно місто чи людину йдеться Такі пропозиції називаютьсявисловлювальними формами.
Висловна форма- це оповідальна пропозиція, яка прямо або опосередковано містить хоча б одну змінну і стаєвисловлюванням, коли всі змінні заміщаються своїми значеннями.
Алгебра логіки розглядає будь-яке висловлювання лише з одного погляду — чи воно істинним чи хибним. Зауважимо, що часто важко встановити істинність висловлювання. Так, наприклад, вислів “площа поверхні Індійського океану дорівнює 75 млн кв. км ” в одній ситуації можна вважати помилковим, а в іншій — істинним. Помилковим - оскільки зазначене значення неточне і взагалі не є постійним. Істинним — якщо розглядати його як деяке наближення, прийнятне практично.
Уживані у звичайній промові слова і словосполучення"не", "і", "або", "якщо. , то", "тоді і тільки тоді"та інші дозволяють із вже заданих висловлювань будувати нові висловлювання Такі слова та словосполучення називаютьсялогічними зв'язками.
Висловлювання, утворені з інших висловлювань за допомогою логічних зв'язок, називаютьсяскладовими. Висловлювання, які є складовими, називаютьсяелементарними.
Так, наприклад, з елементарних висловлювань “Петров - лікар”, “Петров - шахіст” за допомогою зв'язки “і” можна отримати складний вислів “Петров — лікар і шахіст”, що розуміється як “Петров — лікар, який добре грає у шахи”.
За допомогою зв'язки "або" з цих же висловлювань можна отримати складний вислів "Петров - лікар або шахіст", що розуміється в алгебрі логіки як "Петров або лікар, або шахіст, або лікар і шахіст одночасно».
Істинність чи хибність одержуваних таким чином складових висловлювань залежить від істинності чи хибності елементарних висловлювань.
Щоб звертатися до логічних висловлювань, їм призначаютьімена.Нехай черезАпозначено вислів “Тімур поїде влітку на море”, а черезВ- висловлювання "Тимур влітку вирушить у гори". Тоді складний вислів “Тимур влітку побуває і на морі, і в горах” можна коротко записати якА та В. Тут "і" - логічна зв'язка,А,В- логічні змінні , які можуть приймати тільки два значення - "істина" або "брехня", що позначаються, відповідно, "1" і "0"
Кожна логічна зв'язка розглядається як операція над логічними висловлюваннями і має свою назву та позначення:
(1)Операція, що виражається словом “не”, називаєтьсязапереченнямі позначається рисою над висловлюванням (або знаком ù). Вислів істинний, коли A хибний, і хибний, коли A істинний. приклад. "Місяць - супутник Землі" (А); "Місяць - не супутник Землі" ( ).
(2)Операція, що виражається зв'язкою "і", називаєтьсякон'юнкцією(лат. conjunctio - з'єднання) або логічним множенням і позначається точкою "•" (може також позначатися знаками Ù або &). Висловлювання А•В істинно тоді і лише тоді, коли обидва висловлювання А і В істинні. Наприклад, висловлювання
“10 ділиться на 2 та 5 більше 3”
істинно, а висловлювання
“10 ділиться на 2 та 5 не більше 3”, “10 не ділиться на 2 та 5 більше 3”, “10 не ділиться на 2 та 5 не більше 3”
(3)Операція, що виражається зв'язкою “або”(у нероздільному, невиключному сенсі цього слова),називаєтьсядиз'юнкцією(лат. disjunctio - поділ) абологічним додаваннямі позначається знакомv(або плюсом).Висловлювання А v В хибно тоді і тільки тоді, коли обидвависловлювання А і В хибні. Наприклад, висловлювання
"10 не ділиться на 2 або 5 не більше 3"
хибно, а висловлювання
"10 ділиться на 2 або 5 більше 3", "10 ділиться на 2 або 5 не більше 3", "10 не ділиться на 2 або 5 більше 3"
(4)Операція, що виражається зв'язками “якщо . то”, “з . слід”, “. тягне .”, називаєтьсяімплікацією(лат.implico- тісно пов'язані) і позначається знаком ® . Висловлювання А ® В хибно тоді і тільки тоді, коли А істинно, а В — хибно.
Яким чином імплікація пов'язує два елементарних висловлювання?Покажемо це з прикладу висловлювань: “даний чотирикутник — квадрат” (А) і “біля цього чотирикутника можна описати коло” (В). Розглянемо складове висловлюванняА® В, яке розуміється як “якщо даний чотирикутник квадрат, то біля нього можна описати коло”.Є три варіанти, коли висловлювання А® В істинно:
1.Аістинно іВістинно, тобто даний чотирикутник квадрат, і біля нього можна описати коло;
2.Ахибно іВістинно, тобто даний чотирикутник не є квадратом, але біля нього можна описати коло (зрозуміло, це справедливо не для будь-якого чотирикутника);
3.Aхибно іBхибно, тобто цей чотирикутник не є квадратом, і біля нього не можна описати коло.
Лежен лише один варіант: А істинно і В хибно, тобто даний чотирикутник є квадратом, але біля нього не можна описати коло.
У звичайній мові зв'язка “якщо . то” описує причинно-наслідковий зв'язок між висловлюваннями. Але в логічних операціях сенс висловлювань не враховується.Розглядається лише їхня істинність чи хибність. Тому не треба бентежитися "безглуздістю" імплікацій, освічених висловлюваннями, зовсім не пов'язаними за змістом. Наприклад, такими:
"якщо президент США - демократ, то в Африці водяться жирафи", "якщо кавун - ягода, то в бензоколонці є бензин".
(5)Операція, що виражається зв'язками "тоді і тільки тоді", "необхідно і достатньо", ".рівносильно.”, називаєтьсяеквіваленцієюабоподвійною імплікацієюі позначається знаком«або
. Вислів А« В істинно тоді і тільки тоді, коли значення А і В збігаються.
"24 ділиться на 6 тоді і тільки тоді, коли 24 ділиться на 3", "23 ділиться на 6 тоді і тільки тоді, коли 23 ділиться на 3"
істинні, а висловлювання
"24 ділиться на 6 тоді і тільки тоді, коли 24 ділиться на 5", "21 ділиться на 6 тоді і тільки тоді, коли 21 ділиться на 3"
Висловлювання А і В, що утворюють складове висловлювання А« В, можуть бути зовсім не пов'язані за змістом,наприклад: “три більше двох” (А), "пінгвіни живуть в Антарктиді" (В). Запереченнями цих висловлювань є висловлювання “три не більше двох” ( ), “пінгвіни не живуть в Антарктиді” ( ). Утворені з висловлюваньА,Вскладові висловлюванняA«Bі «істинні, а висловлюванняA« і «B- помилкові.
Отже, намирозглянуто п'ять логічних операцій: заперечення, кон'юнкція, диз'юнкція, імплікація та еквівалентність.
А®В = v В.
А«В = (v В) • (v А).
Таким чином,операцій заперечення, диз'юнкції та кон'юнкції достатньо, щоб описуватита обробляти логічні висловлювання.
7.2. Що таке логічна формула?
За допомогою логічних змінних та символів логічних операцій будь-яке висловлювання можна формалізувати, тобто замінитилогічною формулою.
Визначеннялогічної формули:
1.Будь-яка логічна змінна та символи “істина” (“1”) та “брехня” (“0”) — формули.
2.ЯкщоАіВ— формули, то , (А • В), (А v В), (А®B), (А«В) - формули.
3.Жодних інших формул в алгебрі логіки немає.
Як приклад розглянемо вислів “якщо куплю яблука чи абрикоси, то приготую фруктовий пиріг”. Цей вислів формалізується у вигляді(A v B)® C; така сама формула відповідає висловлюванню “якщо Ігор знає англійську чи японську мову, він отримає місце перекладача”.
Як показує аналіз формули(A v B)® C, при певних поєднаннях значень зміннихA,BтаCвона набуває значення "істина", а при деяких інших поєднаннях - значення "брехня" (розберіть самостійно ці випадки). Такі формули називаютьсяздійсненними.
Деякі формули набувають значення "істина" при будь-яких значеннях істинності вхідних до них змінних. Такою буде, наприклад, формулаА v, що відповідає вислову “Цей трикутник прямокутний або косокутний”. Ця формула істинна тоді, коли трикутник прямокутний, і тоді, коли трикутник не прямокутний. Такі формули називаютьсятотожно істинними формуламиаботавтологіями. Висловлювання, що формалізуються тавтологіями, називаютьсялогічноістинними висловлюваннями.
Як інший приклад розглянемо формулуА• , якій відповідає, наприклад, висловлювання “Катя найвища дівчинка у класі, й у класі є дівчатка вище Кати”. Очевидно, що ця формула хибна, тому що абоА, або обов'язково хибно. Такі формули називаютьсятотожно хибними формуламиабосуперечностями. Висловлювання, що формалізуються протиріччями, називаютьсялогічно хибними висловлюваннями.
Якщо дві формули А і В “одночасно”, тобто приоднакових наборах значень змінних, що входять до них, приймають однакові значення, то вони називаютьсярівносильними.
Рівносильність двох алгебри формул логіки позначається символом “=” або символом “º”. Заміна формули інший, їй рівносильною, називається рівносильним перетворенням даної формули.
7.3. Який зв'язок між алгеброю логіки та двійковим кодуванням?
Математичний апарат алгебри логіки дуже зручний для опису того, як функціонують апаратні засоби комп'ютера, оскільки основною системою числення в комп'ютері є двійкова, в якій використовуються цифри 1 і 0, а значень логічних змінних також два: "1" і "0".
З цього випливає два висновки:
1. одні й самі пристрої комп'ютера можуть застосовуватися обробки і зберігання як числової інформації, поданої в двійковій системі числення, і логічних змінних;
2. на етапі конструювання апаратних засобів алгебра логіки дозволяє значно спростити логічні функції, що описують функціонування схем комп'ютера, і, отже, зменшити кількість елементарних логічних елементів, десятки тисяч яких складаються основні вузли комп'ютера.
7 . 4 . Щотаке схеми І, АБО, НЕ, І-НЕ, АБО-НЕ?
Схема І реалізує кон'юнкцію двох або більше логічних значень.
Умовне позначення на структурних схемах схеми І з двома входами представлено на рис. 5.1. Таблиця істинності - у таблиці 5.1.