Опис: Алгебра логіки - певна частина математичної логіки, яка називається обчисленням висловлювань. Висловлення - твердження, яке може бути істинним ( «так») або хибним ( «ні»). Одне і те ж висловлювання не може бути одночасно істинним і хибним.
Розмір файлу: 68.13 KB
Роботу скачали: 30 чол.
Якщо ця робота Вам не підійшла внизу сторінки є список схожих робіт. Так само Ви можете скористатися кнопкою пошук
Тема 1.5. Основні поняття алгебри логіки
1.5.1. Основні визначення алгебри логіки
1.5.2. Зв`язок між алгеброю логіки і двійковим кодуванням
1.5.3. Елементарні логічні функції і логічні елементи
1.5.4. Довільні логічні функції # 150; ДНФ і КНФ
1.5.5. Контрольні питання по темі «Основні поняття алгебри логіки»
1.5.6. Тестові завдання по темі «Основні поняття алгебри логіки»
1.5.1. Основні визначення алгебри логіки
алгебра логіки # 150; певна частина математичної логіки, яка називається обчисленням висловлювань.
висловлювання # 150; твердження, яке може бути істинним ( «так») або хибним ( «ні»). Одне і те ж висловлювання не може бути одночасно істинним і хибним. Тому в алгебрі логіки розглядаються тільки 2 значення висловлювань:
справжнє (йому ставиться в відповідність значення 1);
помилкове (йому ставиться в відповідність значення 0).
Алгебра логіки, відволікаючись від смислової змістовності висловлювань, дає можливість визначити, істинні або помилкові складові висловлювання (функції) алгебраїчними методами.
Логічні змінні величини і функції від них, які можуть приймати тільки 2 значення # 150; 0 і 1. називаються логічними чи Булевського змінними і функціями. Значення логічної функції залежить від конкретного поєднання значень всіх її n аргументів - набору аргументів.
Логічна функція від n двійкових аргументів повністю визначається таблицею істинності. Таблиця істинності - це таблиця, в яку записані значення логічної функції для кожного з 2 n наборів аргументів на вході. Для того щоб повністю визначити логічну функцію, досить перерахувати або все набори, при яких ця функція приймає значення, рівні 1. або все набори, при яких ця функція приймає значення, рівні 0.
1.5.2. C в'язь між алгеброю логіки і двійковим кодуванням
Математичний апарат алгебри логіки дуже зручний для опису того, як функціонують апаратні засоби комп'ютера, оскільки основною системою числення, з якою працює комп'ютер, є двійкова система числення, в якій використовуються тільки цифри 1 і 0.
З цього випливає:
одні й ті ж пристрої комп'ютера можуть застосовуватися для обробки і зберігання як числової інформації, представленої в двійковій системі числення, так і логічних змінних;
на етапі конструювання апаратних засобів алгебра логіки дозволяє значно спростити логічні функції, що описують функціонування схем комп'ютера, і, отже, зменшити число елементарних логічних елементів, з десятків тисяч яких складаються основні вузли комп'ютера.
Дані і команди в комп'ютері представляються у вигляді двійкових послідовностей різної структури і довжини. Існують різні фізичні способи кодування двійкової інформації. В електронних пристроях комп'ютера виконавчі одиниці найчастіше кодуються більш високим рівнем напруги, ніж виконавчі нулі, наприклад, як показано на рис. 1.5.2-1.
Логічний елемент комп'ютера # 150; це частина електронної логічної схеми, яка реалізує елементарну логічну функцію.
Найпростішими логічними елементами комп'ютерів є електронні схеми «І», «АБО», «НЕ», «І # 150; НЕ», «АБО # 150; НЕ». Кожен логічний елемент має своє умовне позначення, яке виражає його логічну функцію, але не вказує на те, яка саме електронна схема в ньому реалізована. Це спрощує запис і розуміння складних логічних схем.
Роботу логічних елементів, як і логічних функцій, описують за допомогою таблиць істинності.
1.5.3. Елементарні логічні функції і логічні елементи
Логічні функції, залежні від однієї або двох змінних, називаються елементарними. До основних логічним функцій відносяться такі елементарні функції: заперечення; логічне множення; заперечення від логічного множення; роз'єднання; заперечення від логічного складання; рівнозначність; заперечення рівнозначності.
Функція заперечення - це логічна функція від одного аргументу, яка приймає значення 1. якщо аргумент дорівнює 0. і приймає значення 0. Якщо аргумент дорівнює 1. і називається запереченням (інверсією) або логічною функцією НЕ.
Запис логічної функції НЕ # 150 ;. де межа над змінної # 150; ознака інверсії. Логічна функція НЕ від одного аргументу описується й таблицею істинності:
Запис логічної функції:
Логічний елемент «АБО # 150; НЕ »складається з елемента« АБО »і інвертора і
здійснює заперечення результату логічної функції "АБО" .Условное позначення на структурних схемах логічного елемента «АБО # 150; НЕ »з двома входами представлено на рис. 1.5.3-5.
У складних виразах з використанням логічних операцій І, АБО, НЕ спочатку виконуються операції заперечення НЕ. потім операції кон'юнкції І та, в останню чергу, операції диз'юнкції АБО.
Для того щоб змінити зазначену послідовність виконання операцій, в виразах слід використовувати дужки.
1.5.4. Довільні логічні функції # 150; ДНФ і КНФ
Припустимо, що довільна логічна функція n аргументів задана єдиним набором аргументів, при якому ця функція приймає значення 1.
Складемо кон'юнкцію (логічну функцію І) від усіх n аргументів: аргументи, які в зазначеному наборі рівні 0, візьмемо зі знаком інверсії, а аргументи, що дорівнюють 1 в зазначеному наборі, - без знака інверсії, так як згідно з визначенням кон'юнкції, щоб логічна функція І приймала значення 1. необхідно, щоб всі аргументи були рівні 1.
Приклад 1.5.4-1. Задана логічна функція від 4 аргументів Х1, Х2, Х3, Х4. яка приймає значення 1 при наборі Х1 = 0, Х2 = 1, Х3 = 1, Х4 = 0 і 0 при всіх інших наборах.
Складемо вираз для цієї функції:
Припустимо, що довільна логічна функція n аргументів задана єдиним набором аргументів, при якому ця функція приймає значення 0.
Складемо диз'юнкцію (логічну функцію АБО) від усіх n аргументів наступним чином: аргументи, рівні 0 в заданому наборі, візьмемо без знака інверсії, а аргументи, рівні в заданому наборі 1. - зі знаком інверсії, так як згідно з визначенням диз'юнкції, щоб логічна функція АБО приймала значення 0. необхідно, щоб всі аргументи були рівні 0.
Приклад 1.5.4-2. Задана логічна функція від чотирьох аргументів Х1, Х2, Х3. Х4. яка приймає значення 0 при наступному наборі Х1 = 0, Х2 = 0, Х3 = 1, Х4 = 1 і 1 при всіх інших наборах.
Складемо вираз для цієї функції:
Довільна логічна функція, задана перерахуванням всіх наборів аргументів, при яких вона набуває значення 1. визначається наступним чином: для кожного з цих наборів складається кон'юнкція, а потім утворюється диз'юнкція всіх цих кон'юнкція.
Приклад 1.5.4-3. Припустимо, що функція 4 аргументів Х1, Х2, Х3, Х4 приймає значення 1 при наборах:
Х1 = 1 Х2 = 0 Х3 = 1 Х4 = 0
Х1 = 0 Х2 = 0 Х3 = 1 Х4 = 1
Х1 = 1 Х2 = 1 Х3 = 0 Х4 = 1
і 0 на всіх інших наборах.
Тоді функція буде мати вигляд:
Для будь-якого з перерахованих наборів функція F (Х1, Х2, Х3, Х4) буде являти собою диз'юнкцію однієї 1 і інших 0. тобто буде дорівнює 1. а на інших наборах буде являти собою диз'юнкцію одних нулів, тобто буде дорівнює 0.
Довільна логічна функція, задана перерахуванням всіх наборів аргументів, при яких вона набуває значення 0. визначається наступним чином: для кожного з цих наборів складається диз'юнкція, а потім утворюється кон'юнкція всіх цих диз'юнкцій.
Приклад 1.5.4-4. Припустимо, що задана функція від 3 аргументів F (Х1, Х2, Х3). яка приймає значення 0 при наборах
і 1 при всіх інших наборах.
Тоді функція, сформована таким чином, буде мати вигляд:
Для будь-якого з перерахованих наборів функція F (Х1, Х2, Х3) буде являти собою кон'юнкцію одного нуля і інших одиниць, тобто буде дорівнює 0. а на інших наборах представлятиме кон'юнкцію одних одиниць, тобто дорівнює 1.
З вищевикладеного можна зробити наступний висновок: довільна логічна функція від n аргументів може бути виражена через логічні функції І, АБО, НЕ (кон'юнкцію, диз'юнкцію, заперечення).
Логічні функції, що представляють собою диз'юнкції окремих членів, кожен з яких є в свою чергу деяка функція, яка містить тільки кон'юнкції і інверсії, називаються логічними функціями диз'юнктивній форми.
Логічні функції диз'юнктивній форми, в яких інверсія застосовується лише безпосередньо до аргументів, наприклад, але не до більш складних функцій, як, наприклад, називаються нормальними диз'юнктивними функціями.
Якщо кожен член диз'юнктивній нормальної функції від n аргументів містить всі n аргументів, частина з яких зі знаком інверсії, а частина без нього, то функція називається досконалою (СДНФ). Наприклад, функція
є СДНФ.
Кожен член такої форми звертається в 1 лише при деякому єдиному наборі аргументів, а число членів дорівнює числу різних наборів, що звертають функцію в 1.
В недосконалих діз'юнктівних нормальних функціях від n аргументів деякі члени містять кількість аргументів менше, ніж n. Такі члени приймають значення 1 при декількох наборах аргументів. Тому і число членів в недосконалих формах менше, ніж число членів в скоєних формах цих же функцій.
являє собою досконалу кон'юнктівную нормальну форму логічних функцій (СКНФ).
Приклад 1.5.4-5. Скласти вираз для функції, яка приймає значення 1 на наборах 2 і 6.
Запишемо числа 2 і 6 у двійковій системі:
2 в двійковій системі # 150; 10 (або 010),
6 в двійковій системі # 150; 11 0.
Це означає, що шукана функція буде функцією від 3 змінних: Х1, Х2, Х3.
Набори, на яких функція звертається в 1.
Складемо вираз для функції
Що таке алгебра логіки?
Для чого використовується булевська алгебра (алгебра логіки)?
Що називається висловленням?
Які значення приймають висловлювання?
Що вивчає алгебра логіки?
Які змінні називаються логічними чи Булевського?
Які функції називають логічними?
Чим визначається логічна функція?
Що таке таблиця істинності?
Які логічні функції називаються елементарними?
Яка функція називається функцією заперечення?
Яким чином описується функція заперечення?
Яка функція називається функцією логічного множення?
Яким чином описується функція логічного множення?
Яка функція називається функцією логічного додавання?
Яким чином описується функція логічного складання?
Як описується функція заперечення від логічного множення?
Як описується функція заперечення від логічного додавання?
Який порядок виконання операцій заперечення, кон'юнкції і диз'юнкції в складних логічних виразах?
Як висловити довільну логічну функцію, яка на єдиному наборі аргументів приймає значення 1?
Як висловити довільну логічну функцію, яка на єдиному наборі аргументів приймає значення 0?
Як виражається довільна логічна функція, задана перерахуванням наборів аргументів, на яких вона приймає значення 1.
Як виражається довільна логічна функція, задана перерахуванням наборів аргументів, на яких вона приймає значення 0.
Які логічні функції називаються логічними функціями диз'юнктивній форми?
Які логічні функції називаються логічними функціями кон'юнктівной форми?
Які логічні функції називаються нормальними функціями?
Які логічні функції називаються досконалими?
Назвіть відміну логічних функцій досконалої і недосконалої форм.
1.5.6. Тестові завдання по темі «Основні поняття алгебри логіки»
Логічна функція є
диз'юнктивній нормальною функцією
- досконалої кон'юнктівной нормальною функцією (СКНФ)
досконалої диз'юнктивній нормальною функцією (СДНФ)
алгебра логіки # 150; це
- певна частина математичної логіки, яка називається обчисленням висловлювань
- частина математики, що займається обчисленням виразів
- частина математики, що займається обчисленням виразів алгебри із застосуванням законів логіки
Логічні змінні та логічні функції можуть набувати наступних значень ...
Логічна функція повністю визначається
- таблицею істинності
- одиничним набором аргументів
- нульовим набором аргументів
- таблицею наборів аргументів
Елементарні логічні функції залежать
- від одного або двох аргументів
- від трьох аргументів
- від чотирьох аргументів
- від будь-якої кількості аргументів
Порядок виконання логічних операцій в складних логічних виразах наступний
- заперечення, логічне множення, логічне додавання
- логічне множення, заперечення, логічне додавання
- логічне множення, логічне додавання, заперечення
- будь-який
Логічні функції називаються нормальними функціями
- якщо інверсія застосовується безпосередньо до аргументів
- якщо інверсія застосовується до окремих логічним функціям
- якщо інверсія застосовується до всієї логічної функції
- немає правильної відповіді
Логічні функції називаються досконалими
- якщо кожен член диз'юнктивній (або кон'юнктівной) нормальної функції від n аргументів містить всі n аргументів
- якщо кожен член диз'юнктивній (або кон'юнктівной) нормальної функції від n аргументів містить n аргументів з запереченнями
- якщо кожен член диз'юнктивній (або кон'юнктівной) нормальної функції від n аргументів містить хоча б один аргумент з запереченням
- якщо кожен член диз'юнктивній (або кон'юнктівной) нормальної функції від n аргументів містить всі n аргументів без заперечень
Якщо логічна функція приймає значення 0 на наборах 0, 2, 3, 5, то вона приймає значення 1
- на наборах 1, 4, 6, 7
- на наборах 4, 5, 7
- на наборах 6, 7
- на наборах 1, 2, 3, 4, 5
Досконалої кон'юнктівной нормальною функцією (СКНФ є