Основні питання числення алгебри логіки
Характеристика алгебри логіки. Система числення як спосіб подання довільного числа за допомогою алфавіту символів, які називають цифрами. Представлення чисел зі знаком: прямий, обернений і доповняльний код. Аналіз булевої функції та методів Квайна, Вейча.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | украинский |
| Дата добавления | 05.09.2011 |
| Размер файла | 2,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Завдання 1
Таблиця 1
|
Друга (молодша) цифра |
Перша (старша) цифра |
|||||||||||||
|
В8 |
1 |
2 |
4 |
7 |
5 |
3 |
||||||||
|
В7 |
3 |
1 |
2 |
4 |
7 |
5 |
||||||||
|
В6 |
2 |
4 |
7 |
5 |
3 |
1 |
||||||||
|
В5 |
5 |
3 |
1 |
2 |
4 |
7 |
||||||||
|
В4 |
9 |
7 |
5 |
3 |
1 |
2 |
||||||||
|
В3 |
7 |
5 |
3 |
1 |
2 |
4 |
||||||||
|
В2 |
4 |
2 |
1 |
3 |
5 |
7 |
||||||||
|
В8 |
В7 |
В6 |
В5 |
В4 |
В3 |
В2 |
В1 |
3 |
5 |
7 |
9 |
1 |
8 |
|
|
9 |
3 |
7 |
4 |
5 |
8 |
6 |
2 |
А |
Б |
В |
Г |
Д |
Е |
|
|
6 |
5 |
9 |
6 |
7 |
1 |
8 |
4 |
Є |
Ж |
З |
И |
І |
Ї |
|
|
8 |
7 |
6 |
8 |
9 |
3 |
1 |
6 |
Й |
К |
Л |
М |
Н |
О |
|
|
1 |
6 |
8 |
1 |
6 |
5 |
3 |
8 |
П |
Р |
С |
Т |
У |
Ф |
|
|
3 |
8 |
1 |
3 |
8 |
7 |
5 |
1 |
Х |
Ц |
Ч |
Ш |
Щ |
Ю |
|
|
7 |
1 |
3 |
5 |
1 |
9 |
7 |
3 |
Я |
Ь |
Завдання 1.1.Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці 1 кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій. Вважаючи це число десятковим, перевести його до шістнадцяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Завдання 1.2.Скласти шестизначне число, яке складається з отриманих за допомогою кодової таблиці 1.1 кодів 1-ої, 2-ої та 8-ої літер прізвища. При цьому перші 3 цифри відповідають цілій частині числа, а останні - дробовій. Вважаючи це число шістнадцятковим, перевести його до десяткової, вісімкової та двійкової систем числення з точністю відповідно 3, 3 та 5 розрядів після коми.
Завдання 2
Таблиця 2
|
abc |
f |
|
|
000 |
1ц4л |
|
|
001 |
||
|
010 |
||
|
011 |
||
|
100 |
2ц7л |
|
|
101 |
||
|
110 |
||
|
111 |
Визначити класи функцій алгебри логіки, до яких належить задана за допомогою таблиці функція трьох змінних (таблиця 2), і її функціональну повноту. (Де 1ц1л - переведений у двійковий код шістнадцядковий код першої цифри (1ц) першої літери (1л).
Таблиця
|
x1 |
x2 |
x3 |
x4 |
f1 |
f2 |
f3 |
f4 |
|
|
0 |
0 |
0 |
0 |
h1 |
1 |
h6 |
1 |
|
|
0 |
0 |
0 |
1 |
1 |
h1 |
1 |
h6 |
|
|
0 |
0 |
1 |
0 |
h2 |
0 |
h1 |
0 |
|
|
0 |
0 |
1 |
1 |
0 |
h2 |
0 |
h1 |
|
|
0 |
1 |
0 |
0 |
h3 |
1 |
h2 |
1 |
|
|
0 |
1 |
0 |
1 |
1 |
h3 |
1 |
h2 |
|
|
0 |
1 |
1 |
0 |
h4 |
0 |
h3 |
0 |
|
|
0 |
1 |
1 |
1 |
0 |
h4 |
0 |
h3 |
|
|
1 |
0 |
0 |
0 |
h5 |
1 |
h4 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
h5 |
1 |
h4 |
|
|
1 |
0 |
1 |
0 |
h6 |
0 |
h5 |
0 |
|
|
1 |
0 |
1 |
1 |
0 |
h6 |
0 |
h5 |
|
|
1 |
1 |
0 |
0 |
h1 |
1 |
h6 |
1 |
|
|
1 |
1 |
0 |
1 |
1 |
h1 |
1 |
h6 |
|
|
1 |
1 |
1 |
0 |
h2 |
0 |
h1 |
0 |
Таблиця
|
Елементні базиси |
h1 |
h3 |
h5 |
|
|
4І / 3АБО |
0 |
0 |
0 |
|
|
3І-НЕ / 4І-НЕ |
0 |
0 |
1 |
|
|
4АБО / 3І-НЕ |
0 |
1 |
0 |
|
|
3АБО-НЕ / 4АБО |
0 |
1 |
1 |
|
|
4І /3АБО-НЕ |
1 |
0 |
0 |
|
|
3І-НЕ / 4І |
1 |
0 |
1 |
|
|
4АБО / 3І |
1 |
1 |
0 |
|
|
3АБО-НЕ / 4АБО-НЕ |
1 |
1 |
1 |
Варіанти завдань вибираються відповідно до дня народження (дд.мм.рр).
Числа дати народження переводяться в двійкову систему числення і остання цифра числа привласнюється як значення h.
Отримати операторні форми функції, зобразити комбінаційну схему в заданому елементному базисі (таблиця 4).
Виконати спільну мінімізацію f1, f2, f3 (таблиця 3). Виконати канонічний метод структурного синтезу.
Зобразити комбінаційну схему для реалізації системи функцій f1, f2, f3.
Реалізувати функцію f4 (таблиця 3) у базисі Буля. На виході кожного елемента написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи повинні мати не більше двох входів. Навести таблиці істинності задіяних елементів.
Завдання 3.2. Функцію f4 реалізувати за допомогою дешифраторів. У кожного з задіяних дешифраторів кількість виходів не повинна перевищувати 16. Навести таблиці істинності, які показують роботу дешифраторів.
Завдання 2.1. Реалізувати функцію f4 у монобазисі І-НЕ. На виході кожного елемента І-НЕ написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
Завдання 2.2. Реалізувати функцію f4 у монобазисі Шеффера. На виході кожного елемента Шеффера написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи Шеффера повинні бути двовходовими. Навести таблицю істинності елемента Шеффера.
Завдання 2.3. Реалізувати функцію f4 у монобазисі АБО-НЕ. На виході кожного елемента АБО-НЕ написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Елементи можуть мати довільну кількість входів. Навести таблиці істинності задіяних елементів.
Завдання 2.4. Реалізувати функцію f4 у монобазисі Пірса. На виході кожного елемента Пірса написати формулу сигналу, який даним елементом реалізується. Для 5 довільних вхідних наборів визначити рівні сигналів (0 або 1) на виході кожного елемента схеми. Усі елементи Пірса повинні бути двовходовими. Навести таблицю істинності елемента Пірса.
Завдання 2.5. Функцію f4 реалізувати за допомогою мультиплексорів. У кожного з задіяних мультиплексорів кількість інформаційних входів не повинна перевищувати 16. Навести таблиці істинності, які пояснюють роботу задіяних мультиплексорів.
алгебра логіка цифра знак
Вступ
Сьогодні важко собі уявити діяльність людини без електронних обчислювальних машин (ЕОМ). З'явившись близько 40 років тому, ЕОМ відкрили нову сторінку в історії людських знань та можливостей, значно полегшили працю вчених, дали можливість вивчати найскладніші процеси.
Ідея використання програмного керування для побудови пристрою, що автоматично виконує арифметичні обчислення, вперше була висловлена англійським математиком Ч.Беббіджем ще в 1833 році. Проте його спроби побудувати механічний обчислювальний пристрій з програмним керуванням не мали успіху.
Фактично ця ідея була реалізована лише через 100 років, коли в 1942 році К.Цюзе в Німеччині і в 1944 році Т.Айкен в США побудували на електромагнітних реле обчислювальні машини з керуванням від перфострічки.
Ідея програмного керування обчислювальним процесом була суттєво розвинена американським математиком Дж. фон Мейменом, який в 1945 році сформулював принцип побудови обчислювальної машини з програмою, яка зберігається в пам'яті.
Перші ЕОМ з програмованим керуванням із програмою, яка зберігається в пам'яті з'явились практично одночасно в Англії, США та інших країнах.
Фундаментальний внесок в розвиток вітчизняної обчислювальної техніки вніс академік С.А.Лєбєдєв. Під його керівництвом в 1949-1951 роках в АНУРСР в Києві була побудована перша в нашій країні ЕОМ - мала електронна лічильна машина (МЕЛМ), а в 1952-1954 рр. - швидкодіюча електронна лічильна машина (ШЕЛМ), яка виконувала 8000 операцій/сек. і була на той час однією із найбільш швидкодіючих ЕОМ в світі.
Одну з перших в країні ЕОМ зібрали на початку 50-х років чл.-кор. АН СРСР І.С.Брук та його співробітники Н.Я.Матюхін та М.А.Карцев в Енергетичному інституті АН СРСР в Москві. Перша ЕОМ "Стрела", яка випускалась промисловістю, була розроблена науковим колективом під керівництвом Ю.Я.Базилевського.
Покоління ЕОМ визначається сукупністю взаємозв'язаних і взаємообумовлених суттєвих особливостей та характеристик, конструктивно-технологічної бази, що використовується при побудові машин, і архітектури, яка реалізується в машині (логічної організації).
Перші покоління утворювали лампові ЕОМ, промисловий випуск яких розпочався на початку 50-х років. В якості компонентів логічних елементів використовувались електронні лампи.
В обчислювальних машинах другого покоління, що з'явились наприкінці 50-х років, напівпровідникові прилади - транзистори - замінили електронні лампи, що суттєво підвищило надійність, знизило споживання потужності, зменшило габаритні розміри ЕОМ. Це дозволило створити ЕОМ, які мали великі логічні можливості та більш високу продуктивність. Поряд з машинами для наукових розрахунків, з'явилися ЕОМ для розв'язання планово-економічних задач (задач обробки даних) та керування виробничими процесами.
ЕОМ третього покоління з'явились в другій половиш 60-х років, коли фірма ІВМ (СІЛА) розробила систему машин ІВМ-360. Ця система мала вплив на логічну організацію машин загального призначення третього покоління, які були розроблені в інших країнах.
В останні роки з'явились ЕОМ та обчислювальні пристрої, які потрібно віднести до четвертого покоління. Контури цього покоління досить важко чітко визначити, так як в теперішній час воно представлене, головним чином, новими типами, що раніше не існували, обчислювальних засобів і тільки по відношенню до деяких питань (наприклад, заміна феритових запам'ятовувальних пристроїв напівпровідниковими) зачепило машини загального призначення, які виконують основний об'єм обчислювальних робіт в різного роду обчислювальних центрах.
Конструктивно-технологічною основою ЕОМ четвертого покоління є інтегральні схеми з великими (ВІС) і надвеликим (НВІС) ступенями інтеграції, які вміщують тисячі, десятки і сотні тисяч транзисторів в одному кристалі. В першу чергу на ВІС будують запам'ятовувальні пристрої ЕОМ.
Обчислювальні можливості мікро ЕОМ виявились достатніми для створення на їх основі в рамках ЕОМ четвертого покоління, нового за рядом експлуатаційних характеристик та способу використання типа обчислювальних пристроїв -персональних ЕОМ (персональних комп'ютерів), які отримали в теперішній час широке поширення.
В останній час визначились контури нового, п'ятого покоління ЕОМ. В значній мірі цьому допомогли публікації відомостей про проект ЕОМ п'ятого покоління, який розробляється провідними японськими фірмами та науковими організаціями.
Згідно цьому проекту ЕОМ і обчислювальні системи п'ятого покоління крім більш високої продуктивності та надійності при більш низькій вартості повинні мати такі якісно нові властивості:
- можливість взаємодії з ЕОМ за допомогою природної мови, людського голосу і графічних зображень;
- здатність системи "розуміти" вміст бази даних, яка при цьому перетворюється в "базу знань", і використовувати ці "знання" при розв'язку задач.
Очікується, що в машинах п'ятого покоління будуть використовуватися інтегральні мікросхеми з надвеликим ступенем інтеграції, які мають до 1-10 млн. транзисторів на кристалі. Для розробки таких схем будуть потрібні потужні системи автоматизації проектування.
алгебра логіка цифра знак
1. Системи числення та функції алгебри логіки
Система числення - це спосіб подання довільного числа за допомогою алфавіту символів, які називають цифрами. Є різні системи числення. Від їх особливостей залежить наочність відображення чисел та складність виконання операцій над ними.
Система числення, в якій значення кожної цифри в довільному місці послідовності цифр, яка означає запис числа, не змінюється, називається непозиційною. Якщо в послідовності цифр, які зображають число, має значення позиція цифри, то систему числення називають позиційною.
Щоб визначити число, недостатньо знати тип і алфавіт системи числення. Для цього необхідно ще додати правила, які дають змогу за значеннями цифр встановити значення числа. Найпростішим способом запису натурального числа є зображення його за допомогою відповідної кількості паличок або рисочок. Таким способом можна користуватися для невеликих чисел. Наступним кроком було винайдення спеціальних символів (цифр). У непозиційній системі кожен знак у записі незалежно від його місця означає одне й те ж саме число. Прикла-дом системи числення з дуже складним способом запису чисел і громіздкими правилами виконання арифметичних операцій є римська система числення, в якій роль цифр відіграють букви алфавіту: І - один, V - п'ять, Х - десять, С - сто, Z - п'ятдесят, D - п'ятсот, М - тисяча. Наприклад, число 324 = СССХХІV.
1.1 Позиційні системи числення
Позиційні системи числення характеризуються нао-чністю відображення чисел та простим виконанням арифметичних операцій. У позиційних системах числення при безпосередньому представленні цифр число записується у вигляді:
Кома у цій послідовності відділяє цілу частину числа від дробової. Позиції цифр, які рахуються від коми, називають розрядами. Кількісний еквівалент, що виражається цим записом, визначається так:
,
де:
§ - основа системи числення, тобто кількість різних цифр, які використовуються в позиційній системі числення,
§ - розрядність цілої частини числа,
§ - розрядність дробової частини числа
§ - цифри і-го розряду запису числа (),
§ - вага і-го розряду.
У цьому випадку вага і-го розряду в k разів більша за вагу ()-го розряду. Такі сис-теми числення називають системами з природним порядком ваги. До них належать двій-кова, вісімкова, десяткова і шістнадцяткова системи числення.
У звичній для нас десятковій системі числення довільне число подається цифрами від 0 до 9; при цьому має значення позиція цифри. Число в десятковій системі запису-ється у вигляді:
,
а значення числа обчислюється за таким виразом:
,
де:
§ - кількість цифр (розрядів) у цілій частині числа (зліва від коми),
§ - кількість розрядів у дробовій частині числа (справа від коми),
§ - значення і-го розряду (розряди цілої частини),
§ - значення і-го розряду (розряди дробової частини),
§ - значення числа.
Звичайно, що дробової або цілої частини числа може і не бути (N або М = 0).
1.2 Двійкові, вісімкові та шістнадцяткові числа
У зв'язку з тим, що елементи з двома станами використовуються як базові елементи комп'ютерної техніки, всі числа в комп'ютерах представляються у двійковій системі чис-лення. Розглянемо особливості цієї системи.
Двійкова система числення будується за тим самим правилом, що і десяткова, але в ній використовуються лише дві цифри - 0 та 1. Число у двійковій системі числення за-писується у вигляді:
,
а значення числа обчислюється за таким виразом:
де:
§ - кількість двійкових цифр (розрядів) у цілій частині числа,
§ - кількість двійкових розрядів у дробовій частині числа,
§ - значення і-го розряду цілої частини числа,
§ - значення і-го розряду дробової частини числа,
§ - значення числа.
Приклади двійкових чисел:
Часто у розробника, а то і в користувача комп'ютера, виникає потреба в перевірці ко-ректності виконання операцій над двійковими числами комп'ютером або його вузлом.
А оскільки в комп'ютерах опрацьовуються багаторозрядні двійкові числа, і оперувати з такими довгими послідовностями нулів та одиниць (наприклад, рядок із 32 цифр) не-зручно, то набули поширення вісімкова та шістнадцяткова системи числення. У вісімковій системі числення використовують вісім цифр від 0 до 7, а у шістнадцятковій - крім десяткових цифр від 0 до 9 використовують 6 літер латинського алфавіту (А, В, С, D, E, F) для позначення цифр від 10 до 15. Значення числа обчислюється за та-ким виразом:
,
де:
§ - кількість цифр (розрядів) у цілій частині числа (зліва від коми),
§ - кількість розрядів у дробовій частині числа (справа від коми),
§ - значення і-го розряду (розряди цілої частини),
§ - значення і-го розряду (розряди дробової частини),
§ - значення числа.
Особливістю цих систем є зручний перехід до двійкової системи та навпаки. Три двійкових розряди переводяться в один вісімковий, а чотири двійкових розряди - в один шістнадцятковий, як показано в табл. 1.1.
Таблиця 1.1
|
Bin |
0000 |
0001 |
0010 |
0011 |
0100 |
0101 |
0110 |
0111 |
|
|
Oct |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
Hex |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
Bin |
1000 |
1001 |
1010 |
1011 |
1100 |
1101 |
1110 |
1111 |
|
|
Oct |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
|
|
Hex |
8 |
9 |
A |
B |
C |
D |
E |
F |
Наприклад, двійкове число шістнадцятковій системі записуватиметься як 6D. Для переведення чисел із шістнадцяткової та вісімкової систем числення у двійкову необхідно кожну цифру числа, яке переводиться, замінити відповідно чотири- або трирозрядним двійковим еквівалентом - тетрадою або тріадою, а отримані двійкові цифри розташувати на місцях шістнадцяткових або вісімкових цифр.
У разі необхідності переведення чисел із десяткової системи числення у вісімкову, шістнадцяткову та двійкову переведення робиться лише в одну систему (вісімкову або шістнадцяткову). Подальше переведення виконується через двійкову систему, викорис-товуючи тріади та тетради.
Приклад 1. Переведемо число 12345,67 з десяткової системи числення у двійкову, ві-сімкову, шістнадцяткову.
1. Переведення цілої частини числа у вісімкову систему:
12345 : 8 = 1543, залишок 1;
1543 : 8 = 192, залишок 7;
192:8 = 24, залишок 0;
24 : 8 = 3, залишок 0;
3:8 = 0, залишок 3.
Результат: 30071.
2. Переведення дробової частини числа у вісімкову систему:
Наближений результат: 0,5270....
3. Отримання повного результату шляхом об'єднання результатів, отриманих в п. 1 та п. 2. Результат: 30071,5270....
4. Переведення результату у двійкову та шістнадцяткову системи числення (табл. 1.2). Поділ двійкового числа на тріади та тетради починається від коми ліворуч і праворуч. Результат:
Таблиця 1.2
|
3 |
0 |
0 |
7 |
1 |
, |
5 |
2 |
7 |
0 |
Oct |
||||||||||||||||||
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
, |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
3 |
0 |
3 |
9 |
, |
A |
B |
8 |
Hex |
1.3 Переведення чисел із системи числення з основою k у десяткову систему
Один із методів переведення чисел із системи числення з основою k у десяткову систему числення ґрунтується на використанні кількісного еквівалента числа. Для переведення необхідно записати число у його кількісному еквіваленті, замінивши цифри системи числення з основою k та основу k їхніми десятковими еквівалентами, а потім обчислити вираз за правилами десяткової арифметики.
Приклад 1. Переведемо двійкове число 1011,1001 у десяткову систему числення.
;
Таким чином, .
Приклад 2. Переведемо вісімкове число 105,71 у десяткову систему числення.
;
Результат: .
Приклад 3. Переведемо шістнадцяткове число 2ED,0A до десяткової системи числення.
Результат: .
Також ефективним є спосіб переведення числа з однієї системи в іншу за допомогою використання розширеного запису числа по схемі Горнера: ,
де:
§ - кількість цифр (розрядів) у цілій частині числа (зліва від коми),
§ - кількість розрядів у дробовій частині числа (справа від коми),
§ - значення і-го розряду (розряди цілої частини),
§ - значення і-го розряду (розряди дробової частини),
§ - значення числа,
§ - основа системи числення.
1.4 Переведення чисел із десяткової системи у систему числення з основою k
Розглянемо переведення чисел із десяткової системи числення у іншу однорідну позиційну систему числення з основою k, коли дії виконуються в десятковій системі. У разі цього переведення окремо виконується переведення цілої частини числа й окремо - дробової; результати потім додаються.
Цілу частину десяткового числа ділять на основу системи числення k за правила-ми десяткової арифметики до отримання залишку, який буде десятковим еквівалентом цифри молодшого розряду результату. Якщо частка від ділення не дорівнює 0, то вона стає діленим і процес ділення на k продовжується. Як тільки чергова частка стане рівною 0, процес ділення на k припиняється. Залишок, який отримали у результаті першого ділення на k, є цифрою розряду результату з вагою , залишок у результаті другого ділення - циф-рою з вагою і т. д. Останній залишок є цифрою старшого розряду результату.
Дробова частина десяткового числа множиться на k за правилами десяткової арифметики. В отриманому добутку від'єднується ціла частина, яка може дорівнювати 0, а дробова частина знову множиться на k із наступним від'єднанням цілої частини. Ця операція повторюється або до отримання нульової дробової частини добутку, або до отримання необхідної кількості розрядів числа . Цифра старшого розряду результату переведення (тобто, перша після коми) збігається з першою від'єднаною цілою части-ною, цифра другого розряду результату переведення - із другою від'єднаною цілою час-тиною і т.д. При цьому від'єднані цілі частини необхідно представити в системі числення з основою k.
Приклад. Переведемо десяткове число 11,5625 у двійкову систему числення з точніс-тю до п'яти розрядів після коми.
Переведення цілої частини:
11:2 = 5, залишок 1 (молодший розряд результату),
5:2=2, залишок 1,
2:2 = 1, залишок 0,
1:2 = 0, залишок 1 (старший розряд результату).
Результат: .
Процедура переведення дробової частини наведена у табл. 1.3.
Таблиця 1.3
|
Крок |
Дріб |
Результат множення на |
Ціла частина результату множення, яка вилучається |
Вага двійкового розряду |
|
|
1 |
0,5625 |
1,125 |
1 |
Старший (перший після коми) |
|
|
2 |
0,125 |
0,25 |
0 |
||
|
3 |
0,25 |
0,5 |
0 |
||
|
4 |
0,5 |
1,0 |
1 |
Молодший |
|
|
5 |
0,0 |
0,0 |
0 |
Результат: .
Повний результат:
1.5 Представлення чисел зі знаком
Для позначення знаку числа в звичайній арифметиці використовують символи «-» та «+». Як зазначалося, у комп'ютерній техніці використовують елементи з двома ста-нами, які можуть зберігати двійкову цифру (0 чи 1). Зрозуміло, що цю цифру доцільно використати і для позначення знаку числа, коли 0 відображає знак «+», а 1 - знак «-».
Для спрощення виконання арифметичних операцій додатні та від'ємні числа (тоб-то числа зі знаком) відображаються спеціальними кодами: прямим, оберненим та допо-вняльним.
1.5.1 Прямий код
У прямому коді лівий (його ще називають старшим) розряд позначає знак числа, а решта розрядів - саме число (рис. 1.1).
Рис. 1.1. Прямий код двійкового числа
Прямий код двійкового n-розрядного числа G визначається як
де А - величина, рівна вазі старшого разряду розрядної сітки (для дробових чисел , а для цілих чисел ). Діапазон представлення чисел в прямому коді . Додатні числа представляються кодами , а від'ємні .
Ознакою представлення додатних або від'ємних чисел є наявність нуля або одиниці відповідно в старшому розряді, який називається знаковим. Цифрові розряди прямого коду представляють модуль числа, що забезпечує наочність представлення чисел в пря-мому коді.
Наведемо кілька прикладів
1.5.2 Обернений код
В оберненому коді, як і у прямому, старший розряд позначає знак числа (0 - додатне число, а 1 - від'ємне). Розряди додатного числа записуються у звичайному вигляді, а від'ємного - в інвертованому вигляді (замість 0 пишеться 1 і навпаки).
Обернений код n-розрядного двійкового числа G визначається як
де В - величина найбільшого числа без знаку, яке може бути розміщене в n- розрядній сітці (для дробових чисел , а для цілих чисел ). Діапазон зміни чисел в оберненому коді . Додатні числа представляються кодами в діапазоні , а від'ємні - в діапазоні . За визначенням обернений код від'ємного числа є до-повненням модуля вихідного числа до найбільшого числа без знаку, яке може бути розмі-щене в розрядній сітці. В зв'язку з цим отримання оберненого коду двійкового від'ємного числа зводиться до отримання інверсії n-розрядного коду модуля цього числа
Знову варто навести кілька прикладів
1.5.3 Доповняльний код
Доповняльний код будується на основі оберненого. Якщо число додатне, то не про-водиться жодних дій, якщо від'ємне - після інвертування до молодшого розряду числа додається одиниця.
Доповняльний код n-розрядного двійкового числа G визначається як
де С - величина, рівна вазі розряду, який іде за старшим розрядом використаної роз-рядної сітки (для дробових чисел , а для цілих чисел ). Діапазон зміни чисел у прямому коді . Цифровими розрядами доповняльного коду додатного числа ви-ражається модуль цього числа. Як уже було зазначено, доповняльний код від'ємного числа зручно отримувати через обернений код шляхом додавання 1 до молодшого розряду обер-неного коду.
Розглянемо приклади
Найчастіше серед розглянутих кодів в комп'ютерах використовується доповняльний код. Це зумовлено більшою зручністю проведення арифметичних операцій над числами, представленими в такому коді, оскільки при його застосуванні операція алгебраїчного додавання зводиться до додавання арифметичного.
1.6 Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів
Основна вимога, яка ставиться до набору логічних елементів, полягає в тому, щоб за допомогою цього набору можна було побудувати будь-яку логічну схему. З огляду на те, що функціонування елементів однозначно описується функціями алгебри логіки (ФАЛ), застосовуючи операцію суперпозиції, можна з деякої системи ФАЛ отримати будь-яку, скільки завгодно складну ФАЛ. Тоді ця деяка система ФАЛ буде називатися функціонально повною (ФПС ФАЛ).
Функціонально повним є такий набір ФАЛ, який містить хоча б одну функцію, яка:
· не зберігає константу "0";
· не зберігає константу "1";
· не є монотонною;
· не є самодвоїстою;
· не є лінійною.
Якщо функція на нульовому наборі змінних дорівнює 0, тобто , то ця функція зберігає константу "0".
Якщо функція на одиничному наборі змінних дорівнює 1, тобто , то ця функція зберігає константу "1".
ФАЛ називається монотонною, якщо при будь-якому зростанні кількості "1" у послідовності сусідніх (тобто таких, які відрізняються тільки в одному розряді) наборів змінних значення функції не зменшується.
ФАЛ називається самодвоїстою, якщо на кожній парі протилежних наборів та вона приймає протилежні значення, тобто, якщо виконується умова:
ФАЛ називається лінійною, якщо її можна зобразити поліномом Жегалкіна без добутків змінних:
, де .
Для того щоб записати функцію, яка задана таблично, у вигляді полінома Жегалкіна, досить записати цю функцію у вигляді суми за модулем 2 тих наборів аргументів, на яких функція дорівнює 1. Після цього потрібно всі змінні, які входять до отриманого виразу з інверсіями, замінити за допомогою співвідношення , розкрити дужки і звести подібні члени за допомогою тотожності
, якщо кількість х непарна;
, якщо кількість х парна.
У табл. 1.2 наведені функції двох змінних і позначкою * вказана їх належність кожному з класів ФАЛ. У графі "Клас" позначено:
0 - зберігає константу "0";
1 - зберігає константу "1";
Л - лінійна;
М - монотонна;
С - самодвоїста.
Таблиця 1.4
|
0 |
0 |
1 |
1 |
Назва ФАЛ |
Вираз ФАЛ |
Клас |
||||||
|
0 |
1 |
0 |
1 |
0 |
1 |
Л |
М |
С |
||||
|
0 |
0 |
0 |
0 |
константа "0" |
0 |
* |
* |
* |
||||
|
0 |
0 |
0 |
1 |
кон'юнкція, І |
* |
* |
* |
|||||
|
0 |
0 |
1 |
0 |
заборона по |
* |
|||||||
|
0 |
0 |
1 |
1 |
* |
* |
* |
* |
* |
||||
|
0 |
1 |
0 |
0 |
заборона по |
* |
|||||||
|
0 |
1 |
0 |
1 |
* |
* |
* |
* |
* |
||||
|
0 |
1 |
1 |
0 |
сума за mod 2 |
* |
* |
||||||
|
0 |
1 |
1 |
1 |
диз'юнкція, АБО |
* |
* |
* |
|||||
|
1 |
0 |
0 |
0 |
АБО-НЕ (Пірса) |
||||||||
|
1 |
0 |
0 |
1 |
рівнозначність |
* |
* |
||||||
|
1 |
0 |
1 |
0 |
інверсія |
* |
* |
||||||
|
1 |
0 |
1 |
1 |
імплікація звор. |
* |
|||||||
|
1 |
1 |
0 |
0 |
інверсія |
* |
* |
||||||
|
1 |
1 |
0 |
1 |
імплікація пряма |
* |
|||||||
|
1 |
1 |
1 |
0 |
І-НЕ (Шеффера) |
||||||||
|
1 |
1 |
1 |
1 |
константа "1" |
1 |
* |
* |
* |
1) Оскільки на нульовому наборі , то ця функція не зберігає константу "0".
2) Оскільки на одиничному наборі , то ця функція не зберігає константу "1".
3) Послідовності сусідніх наборів подані в табл. 1.6 а, ..., е.
Оскільки на всіх шести послідовностях сусідніх наборів функція не є монотонною (а досить було б і на одному), то функція не є монотонною взагалі.
Таблиця 1.6
Таблиця 1.7
|
abc |
f |
abc |
f |
|
|
000 |
1 |
111 |
0 |
|
|
001 |
0 |
110 |
1 |
|
|
010 |
1 |
101 |
0 |
|
|
011 |
1 |
100 |
0 |
4) Пари протилежних наборів наведені в табл. 1.7. Оскільки на кожній парі протилежних наборів функція приймає протилежні значення, то вона є самодвоїстою. 5) Для визначення лінійності функції подамо її у вигляді полінома Жега. Оскільки поліном містить добутки змінних, то функція не є лінійною.
Отже, із п'яти необхідних для створення ФПС властивостей відсутня одна - несамодвоїстість, тому дана функція не утворює ФПС.
2. Булеві функції
Математичний апарат, який описує дії дискретних пристроїв, базується на алгебрі логіки, її ще називають по імені автора - англійського математика Джорджа Буля (1815 - 1864) булевою алгеброю. Практичне застосування алгебри логіки першим знайшов американський вчений Клод Шеннон у 1938 р. при дослідженні електричних кіл з контактними вимикачами.
Для формального опису цифрових автоматів використовується аппарат алгебри логіки. Логічною (булевою) змінною називається величина, яка може приймати тільки два значення 0 і 1. Сукупність різних значень змінних називаються набором.
Основним предметом булевої алгебри є висловлювання - просте твердження, про яке можна стверджувати: істинне воно (позначають символом 1) або хибне (позначають символом 0). Прості висловлювання позначають буквами, наприклад , які у цифровій техніці називають змінними (аргументами). У даний час головна задача алгебри логіки - аналіз, синтез і структурне моделювання будь-яких дискретних скінчених систем. Змінну із скінченим числом значень (станів) називають перемикальною, а з двома значеннями - булевою. Операція - це чітко визначена дія над одним або декількома операндами, яка створює новий об'єкт (результат). Булеві функції можуть залежати від однієї, двох і в цілому n змінних. Булева функція n аргументів може мати до наборів. Оскільки функції приймають тільки два значення, загальне число булевих функцій n аргументів дорівнює . Основними булевими операціями є заперечення (операція НЕ, інверсія), диз'юнкція (операція АБО, логічне додавання, об'єднання) і кон'юнкція (операція І, логічне множення).
Функції , де , називаються функціями логіки або булевими функціями. Всю множину булевих функцій n змінних позначимо:
Булеві функції від змінних можна задавати таблично або за допомогою формул. При табличному задаванні f задається так званою таблицею істинності (таблиця 2.1):
Таблиця 2.1
|
… |
||||||
|
0 |
0 |
… |
0 |
0 |
1 |
|
|
1 |
1 |
… |
0 |
1 |
1 |
|
|
… |
… |
… |
… |
… |
… |
|
|
1 |
1 |
… |
1 |
1 |
1 |
Якщо число змінних n, то таблиця істинності містить 2n рядків, які відповідають всім можливим комбінаціям змінних. Змінну x називають істотною змінною, якщо булева функція істотно залежить від , а саме . У випадку, коли , називають неістотною або фіктивною змінною.
Нехай задано деяку універсальну множину V та множини . Тоді:
З теорії множин відомо, що
, .
Аналогічні рівності виконують і для логічних функцій:
- тавтологія;
- протиріччя.
Тавтологія - це завжди істинний логічний вираз; протиріччя - завжди хибний логічний вираз, які б значення не набував би x. Венна для операцій та (рис. 2.1) Результат залито темно-сірим кольором.
а) б)
2.1.1 Булеві функції однієї та двох змінних
Якщо функція залежить від n аргументів, то кількість наборів аргументів - 2n, оскільки кожний аргумент може набувати двох значень - 0 і 1. Дві функції вважаються відмінними одна від другої, якщо вони набувають різних значень хоча б в одному наборі аргументів. Кількість різних функцій від n аргументів дорівнює , оскільки для задання функції необхідно вказати набір із констант , а число різних розрядних наборів дорівнює . Так, для маємо різних функцій, які наведені в таблиці 2.2
Таблиця 2.2
|
Змінна x |
0 |
1 |
|||
|
Назва функції |
Позначення |
Фіктивна |
|||
|
Нуль |
0 |
0 |
0 |
x |
|
|
Тотожність |
0 |
1 |
|||
|
Заперечення |
1 |
0 |
|||
|
Одиниця |
1 |
1 |
1 |
x |
Для функцій двох змінних - , маємо різних функцій, кожна із яких визначається 4-ма наборами аргументів. Таблиці істинності функцій наведені в таблиці 2.3. Функція з більшою кількістю змінних завжди може бути представлена функціями тільки двох змінних.
Таблиця 2.3
|
X1 |
0 |
0 |
1 |
1 |
Назва |
Алгебраїчний вираз |
|
|
X2 |
0 |
1 |
0 |
1 |
|||
|
f0 |
0 |
0 |
0 |
0 |
Нульова |
||
|
f1 |
0 |
0 |
0 |
1 |
Кон'юнкція (І) |
||
|
f2 |
0 |
0 |
1 |
0 |
Заборона х2 |
||
|
f3 |
0 |
0 |
1 |
І |
Повторення х1, |
||
|
f4 |
0 |
1 |
0 |
0 |
Заборона х1, |
||
|
f5 |
0 |
1 |
0 |
1 |
Повторення х2 |
||
|
f6 |
0 |
1 |
1 |
0 |
Нерівнозначність |
||
|
f7 |
0 |
1 |
1 |
1 |
Диз'юнкція (АБО) |
||
|
f8 |
1 |
0 |
0 |
0 |
Заперечення диз'юнкції, стрілка Пірса (АБО-НЕ) |
||
|
f9 |
1 |
0 |
0 |
1 |
Рівнозначність |
||
|
f10 |
1 |
0 |
1 |
0 |
Заперечення х2 |
||
|
f11 |
1 |
0 |
1 |
1 |
Імплікація від х2 до х1 |
||
|
f12 |
1 |
1 |
0 |
0 |
Заперечення х1 |
||
|
f13 |
1 |
1 |
0 |
1 |
Імплікація від х1 до х2 |
||
|
f14 |
1 |
1 |
1 |
0 |
Заперечення кон'юнкції, штрих Шеффера (І-НЕ) |
||
|
f15 |
1 |
1 |
1 |
1 |
Одинична |
Графічні позначення логічних елементів:
Рис
2.2 Еквівалентні формули
Одна і та ж булева функція може мати над даним базисом різні реалізації. Формули, що реалізують одну і ту ж функцію, називаються еквівалентними (рівносильними). Позначаються:
Відношення еквівалентності характеризується основними властивостями булевих операцій:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Всі властивості можуть бути перевірені за допомогою таблиць істинності.
За допомогою цих законів можна виконувати різні перетворення булевих функцій, дотримуючись такого порядку: першими виконуються операції в дужках; за їх відсутності першими виконуються операції заперечення (інверсії), потім кон'юнкції, потім диз'юнкції.
Отже, - булева алгебра.
2.3 Принцип двоїстості булевих
Функцію називають двоїстою до функції , якщо .
Наприклад: вони двоїсті, бо:
Якщо функція двоїста сама собі, тобто її називають самодвоїстою. Якщо у формулі F, що реалізує функцію f замінити знаки на знаки двоїстих функцій, то отримана формула F* буде реалізовувати функцію f* що двоїста функції f (принцип двоїстості).
В алгебрі Буля принцип двоїстості можна сформулювати наступним чином: для отримання формули F*, двоїстостої до формули F, треба у формулі F всюди замінити 0 на 1, 1 на 0, на , на .
3. Мінімізація булевих функцій
При проектуванні цифрових автоматів широко застосовуються методи мінімізації булевих функцій, які дозволяють отримати рекомендації для побудови економних схем цифрових автоматів.
Загальний задача мінімізації булевих функцій може бути сформульованою наступним чином: знайти вираз заданої функції в формі, яка б складала мінімально можливе число букв.
Потрібно зауважити, що в загальній постановці дана задача поки що не вирішена, але достатньо добре досліджена в класі ДКНФ.
Елементарною кон'юнкцією називають кон'юнкцією кінечного числа різних змінних, кожна з яких може мати або не мати заперечення.
ДНФ називають диз'юнкцією елементарних кон'юнкцій. Мінімальною ДНФ булевої функції називається ДНФ, яка включає найменше число букв (по відношенню до всіх інших ДНФ, які задають задану булеву функцію.
Булева функція називається імплікантою булевої функції , якщо для будь-якого набору змінних, на якому справедливо
Імпліканта булевої функції , яка є елементарною кон'юнкцією називається простою, якщо ніяка частина імпліканти не є імплікантою . Із приклада видно, що і є простими імплікантами функції ; - не є простими, так як їх частини є імплікантами .
Диз'юнкція будь-якого числа імплікант функції також є імплікантою цієї функції. Будь-яка булева функція є еквівалентна диз'юнкції всіх свої простих імплікант. Така форма предмтавлення функції називається скороченою диз'юнктивною нормальною формою (СДНФ).
СДНФ булевої функції називається тупиковою, якщо в ній відсутні зайві прості імпліканти. Видалення зайвих простих імплікант із СДНФ булевої фукції не є процесом однозначним, тобто булева фукція може мати декілька тупикових ДНФ.
Існує декілька методів мінімізації булевих фукцій, основні з них наведені нижче.
3.1 Метод послідовного застосування законів та тотожностей алгебри логіки
В основі даного методу лежить пошук виразів, які можна записати у більш простому виді. При цьому, як правило, найбільше використовуються наступні операції та закони логіки:
- операція склеювання;
- операція поглинання;
- дистрибутивний закон;
- ідемпотентність, з цього закону слідує, що кожний доданок в ДНФ можна групувати з іншим неодноразово.
Методом користуються лише в досить простих випадках, він носить елементи довільних розв'язків і являється досить громіздким.
3.2 Метод Квайна
Метод Квайна заснований на застосуванні двох основних співвідношень:
1) Співвідношеня склеювання
, де А - будь-який елементарний добуток.
2) Співвідношення поглинання
,
Справедливість обох співвідношень легко перевіряється. Суть методу полягає в послідовному виконанні всіх можливих склеювань а потім всіх поглинань, що приводить до скороченої ДНФ.
Метод застосовується і для досконалих ДНФ. Із співвідношення поглинання слідує, що будь-який елементарний добуток поглинається будь-якою його частиною.
Для доведення достатньо показати, що може бути отримана будь-яка проста імпліканта . Насправді, застосовуючи до р операцію розгортання (обернену операцію до операції склеювання)
по всіх бракуючих змінних початкової функції , отримуємо сукупність констатуент одиниці. При склеюванні всіх констатуент з отримаємо імпліканту р.
Це є очевидно, оскільки операція склеювання обернена операції розгортання. Множина констатуент обов'язково присутня в досконалій ДНФ функції , оскільки р - її імпліканта.
Таблиця 3.6
|
x1 |
x2 |
x3 |
x4 |
f4 |
|
|
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
0 |
1 |
1 |
|
|
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
1 |
|
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
1 |
Приклад. Нехай задана булева функція таблицею істинності (Табл. 2.6). Її ДНФ має вигляд
1 2 3 4 5 6
Перший етап. Виконуємо склеювання
1 - 2:
1 - 3:
2 - 4:
3 - 4:
4 - 6:
5 - 6:
Відмітимо, що результатом склеювання завжди є елементарний добуток, який являє собою спільну частину склеюваних констатуент. Далі виконуємо склеювання отриманих елементарних добутків. Склеюються тільки ті добутки, які мають однакові змінні:
Подальші склеювання не можливі. Виконуючи поглинання, отримаємо скорочену ДНФ:
.
Другий етап. Для отримання мінімальної ДНФ потрібно забрати зі скороченої ДНФ всі зайві прості імпліканти. Це робиться за допомогою спеціальної імплікантної матриці Квайна. У стрічки такої матриці записуються прості імпліканти булевої функції, а у стовпці - констатуенти одиниці, які є членами ДНФ булевої функції. Проста імпліканта поглинає деяку констатуенту одиниці, якщо та є її частиною. Відповідна клітинка імплікантної матриці на перетині стрічки і стовпця відмічаються хрестиком.
Мінімальні ДНФ будуються по імплікантній матриці наступним чином:
Таблиця 2.7
|
Прості імпліканти |
Констатуенти одиниці |
||||||
1) шукаються стовпці імплікантної матриці, які мають лише один хрестик. Прості імпліканти, які відповідать цим хрестикам, називаються базисними і складають так зване ядро булевої функції. Ядро обов'язково входить до мінімальної ДНФ;
2) розглядаються різні варіанти вибору сукупності простих імплікант, які накриють хрестиками решту стовпців імплікантної матриці і, вибирають варіанти з мінімальним сумарним числом букв в такій сукупності імплікант.
Ядром нашої функції є імпліканти і . Імпліканта - зайва, оскільки ядро накриває всі стовпці імплікантної матриці. Тому функція має єдину тупікову і мінімальну ДНФ:
.
Варто відмітити, що число N хрестиків в одній стрічці завжди є степінню числа 2. Більше того , де
k - число букв, що знаходяться в простій імпліканті,
n - число множників у констатуенті одиниці.
Також потрібно відмітити, що використовуючи різноманітні співвідношення, можна розширити область застосування методу Квайна за межі ДДНФ.
3.3 Метод Квайна - Мак-Класкі
Метод являє собою формалізований на етапі знаходження простих імплікант метод Квайна. Формалізація відбувається наступним чином:
1) Всі констатуенти одиниці з ДДНФ булевої функції f записуються їх двійковими номерами.
2) Всі номера розбиваються на групи. Ознакою утворення i-ої групи є i одиниць в кожному двійковому номері констатуенти одиниці.
3) Склеювання виконують тільки між номерами сусідніх груп. Номера, які склеюються, відмічаються будь-яким знаком.
4) Склеювання виконують всеможливі як і в методі Квайна. Невідмічені після склеювання номера являються простими імплікантами.
Знаходження мінімальних ДНФ далі проводиться по імплікантній матриці, як в методі Квайна. Більш детально розглянемо метод на прикладі розв'язання наступної задачі: мінімізувати методом Квайна-Мак-Класкі булеву функцію f, задану таблицею істинності (Табл. 2.6).
1) В ДДНФ функції f замінимо всі констатуенти одиниці їх двійковими номерами:
2) Утворимо групи двійкових номерів. Ознакою утворення i-ої групи є i одиниць в двійковому номері констатуенти одиниці.
Таблиця 2.8
|
Номер групи |
Двійкові номера констатуент одиниці |
|
|
0 |
- |
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
4 |
|
3) Склеїмо номера із сусідніх груп . Номера, які склеюються, викреслюємо. Склеїмо номера із сусідніх груп цієї таблиці. Склеюватися можуть тільки номера, які мають зірочки на однакових позиціях. Номера, які склеїлись, викреслюємо. Результати склеювання занесемо в таблицю 2.10.
4) Маємо три прості імпліканти *111, 111*, 00**1.
5) Будуємо імплікантну матрицю. По таблиці визначаємо сукупність простих імплікант - 0**1 і 111*, які відповідають мінімальній ДНФ.
Для встановлення буквенного вигляду простої імпліканти достатньо виписати добутки тих змінних, які відповідають двійковим цифрам, що збереглися:
.
Відмітимо, що розбиття констатуент на групи дозволяє зменшити число попарних порівнянь при склеюванні.
3.4 Метод діаграм Вейча
Якщо число змінних логічної функції мале () знаходження мінімальних форм можна проводити за допомогою спеціальних таблиць, які називають діаграмами Вейча або картами Карно.
Для булевої функції двох змінних діаграма Вейча має наступний вигляд:
Рис
Кожна клітинка відповідає набору змінних булевої функції в її таблиці істинності. Діаграма Вейча для трьох змінних має наступний вигляд:
Рис
Рис
Діаграма для чотирьох змінних являє собою квадрат, що розбитий на 16 малих квадратів ().
Для приведених діаграм характерно наступне:
1) Кожній клітинці діаграми відповідає свій набір.
2) Сусідні набори розташовані в стрічці або стовпці.
3) Сусідніми наборами є набори, які відрізняються однією компонентою.
4) Отриманий елементарний добуток по діаграмі - це добуток змінних, які приймають одне і те ж значення в обох клітинках.
5) Стовпці та рядки по краях діаграми також рахуються сусідніми.
Загальне правило склеювання на діаграмах Вейча:
Склеюванню підлягають прямокутні конфігурації, заповнені одиницями, які включають число клітинок, що є степінню числа 2 (тобто це число клітинок завжди повинно бути парним). Отриманий новий добуток визначається як добуток змінних, які не міняють свого значення на всіх склеюваних наборах.
Рис
Приклад. Нехай задана функція трьох змінних діаграмою Вейча.
Знайти мінімальну ДНФ булевої функції f
.
Розв'язання.
Рис
1 - , 2 - , 3 - .
За методом Вейча мінімальна нормальна форма функції має вигляд:
.
Отриманий результат можна перевірити по таблиці істинності і впевнитися, що МДНФ функції f дає всі значення вихідної функції. Зауважимо, що зовнішня загальна простота методу повертається складною програмою при реалізації алгоритму діаграм Вейча на комп'ютері.
4. Cинтез комбінаційних схем
4.1 Синтез функцій у базисі Буля на елементах з довільною кількістю входів
Рис. 4.1
Базис Буля (базис І, АБО, НЕ) складається з трьох функцій алгебри логіки (ФАЛ):
функція І (кон'юнкція, логічне множення, в аналітичному запису - &, *), кількість входів - більше 1;
функція АБО (диз'юнкція, логічне додавання, ОR, в аналітичному записі - «v», «+», «|»), кількість входів - більше 1;
функція НЕ (інверсія, в аналітичному записі - риска над символом, або "/" перед символом, або ''-" перед символом) , кількість входів - 1.
Умовні графічні позначення елементів І, АБО, НЕ наведені на рис. 4.1.
На виході F елемента І буде одиниця тільки тоді, коли на всіх його входах a,b,c,…,z є одиниця.
На виході F елемента АБО буде одиниця тоді, коли хоча б на одному з його входів a,b,c,…,z є одиниця.
На виході F елемента НЕ буде одиниця тоді, коли на його вході а є нуль.
Таблиця істиності задає значення ФАЛ при всіх можливих станах аргументів (змінних) цієї функції. Досконалі диз'юнктивні нормальні форми (ДДНФ) - це аналітичний вираз ФАЛ у вигляді диз'юнкції кон'юнкцій. При цьому кожна кон'юнкція містить усі змінні (аргументи) ФАЛ, а кількість термів дорівнює кількості одиничних значень функції у її таблиці істиності. ДДНФ визначає, коли дана ФАЛ набуває значення одиниці.
Для того, щоб утворити з таблиці істиності ДДНФ необхідно:
- визначити з таблиці істиності. скільки разів (N) функція набуває значення одиниці;
- написати рівняння:
,
де добуток (терм) містить усі аргументи функції і повторюється N разів. При цьому перший терм рівняння відповідає першому набору таблиці істиності, на якому ФАЛ набуває значення одиниці, другий - другому, і так далі, а останній, відповідно, останньому;
- розставити позначки інверсії змінних в кожному термі згідно із значенням цих змінних у відповідних наборах таблиці істиності: якщо змінна у відповідному наборі таблиці істиності має значення 0. то у термі вона повинна мати позначку інверсії (інверсне значення), якщо у набрі змінна має значення 1, то у термі змінна повинна бути без інверсії (пряме значення).
Приклад 4.1. ФАЛ задана таблицею істиності (таблиця 4.1). Скласти ДДНФ для даної функції.
Таблиця 4.1
Номернабору |
Аргументи |
Функція |
Терм |
|||
|
а |
b |
с |
f |
|||
|
0 |
0 |
0 |
0 |
0 |
||
|
1 |
0 |
0 |
1 |
0 |
||
|
2 |
0 |
1 |
0 |
1 |
||
|
3 |
0 |
1 |
1 |
1 |
||
|
4 |
1 |
0 |
0 |
1 |
||
|
5 |
1 |
0 |
1 |
0 |
||
|
6 |
1 |
1 |
0 |
0 |
||
|
7 |
1 |
1 |
1 |
1 |
Рішення: .
Функція набуває значення одниниці чотири рази, тому ДДНФ містить чотири терми.
Функціональна схема ФАЛ, заданої у вигляді ДДНФ, у базисі Буля складається з трьох послідовно з'єднаних частин:
- матриці інверторів, яка реалізує інверсні значення змінних;
- матриці елементів I, яка реалізує окремі терми ФАЛ;
- елемента АБО, на виході якого власне і реалізується ФАЛ.
Приклад 4.2. Синтезувати функціональну схему ФАЛ для ДДНФ Прикладу 4.1.
Результат синтезу наведений на рис. 4.2.
Рис
4.2 Реалізація функцій алгебри логіки на дешифраторах
Таблиця 4.2
|
№ |
Входи |
Виходи |
||
|
4 |
4 2 1 |
ВК |
7 6 5 4 3 2 1 0 |
|
01234567х |
0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1x x x |
111111110 |
0 0 0 0 0 0 0 10 0 0 0 0 0 1 00 0 0 0 0 1 0 00 0 0 0 1 0 0 00 0 0 1 0 0 0 00 0 1 0 0 0 0 00 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 0 |
Дешифратор - це схема, яка має n інформаційних входів і до виходів і використовується для
Рис.4.3 перетворення n-розрядного двійкового коду на вході в унітарний код на виході. Унітарний код складається з набору нулів і лише однієї одиниці (або навпаки). В ЕОМ дешифратори найчастіше використовуються для перетворення n-розрядного двійкового коду в унітарний код на виходах (кожному n-розрядному двійковому коду на вході відповідає сигнал 1 тільки на одному з виходів). Для прикладу наводиться таблиця істинності (табл. 4.2) дешифратора на 3 входи і його умовне графічне позначення (рис. 4.3). Інформаційні входи дешифратора позначаються вагою розрядів двійкового коду. Виходи дешифратора позначаються порядковими номерами, які відповідають номеру набору на інформаційних входах у табл. 4.2). Виходи дешифраторів можуть бути інверсними.
Таблиця 4.3
|
Входи |
Вихід |
|
|
аbс |
f |
|
000001010011100101110111 |
10110011 |
Додатковий вхід управління ВК (вибір кристалу) дозволяє або забороняє формування сигналів на виходах дешифратора.
Описані вище дешифратори називаються повними, оскільки кількість їхніх виходів дорівнює . Дешифратори, які мають меншу кількість виходів, називаються неповними.
На дешифраторах зручно реалізовувати ДДНФ, оскільки ДДНФ безпосередньо вказує на ті набори з , на яких функція приймає значення "1". Для схемної реалізації такої функції необхідно на інформаційні входи дешифратора подати вхідні змінні і з'єднати виходи дешифратора, які відповідають номерам набору, на яких функція приймає значення "1", з входами додаткового елемента АБО. На виході елемента АБО буде сформована потрібна функція.
Рис. 4.4
Приклад 4.3. Реалізувати функцію, яка задана табл. 4.3.
Розширення по входах схем, які реалізовані на дешифраторах.
Якщо потрібно дешифрувати більше сигналів, ніж є інформаційних входів у дешифратора, то необхідно використовувати вхід управління ВК і заводити на нього результат дешифрації тих розрядів, які безпосередньо не подані на інформапційні входи дешифратора. Приклад дешифрації 4 розрядів на дешифраторах з трьома інформаційними входами наведений на рис. 4.5.
Рис
Коли сигнал - працює верхній дешифратор D2, на його виходах формуються сигнали які відповідають наборам 0..7 вхідних змінних a,b,c,d. Коли - працює нижній дешифратор D3, на його виходах формуються сигнали які відповідають шістнадцятковим наборам 8..f вхідних змінних a,b,c,d. Таким чином, вхід ВК має найбільшу вагу, в наведеному прикладі вага входа ВК дорівнює 8. Окремо взяті дешифратори D2 і D3 в наведеному прикладі неповні.
4.3 Синтез комбінаційних схем на базі мультиплексорів
Мультиплексор - це комбінаційна багатовходова схема з одним виходом f Входи мультиплексора поділяються на інформаційні (k входів) та управління (n входів). Загалом, . Код, який надходить на входи управління, визначає один з інформаційних входів, сигнал з якого передається на вихід f. У табл. 4.4 показана таблиця істинності мультиплексора з трьома входами управління і 8 інформаційними входами, на рис. 4.6 показане умовне графічне позначення такого мультиплексора. Входи управління мультиплексора позначаються вагою розрядів двійкового коду. Інформаційні входи мультиплексора позначаються порядковими номерами, які відповідають номеру набору на вхід управління.
На мультиплексорах зручно реалізовувати ДДНФ, оскільки ДДНФ безпосередньо вказує на ті набори з , на яких функція приймає значення «1». Для схемної реалізації такої функції необхідно подати на входи управління мультиплексора змінні-аргументи у відповідності з їхнею вагою і з'єднати входи мультиплексора, номери яких відповідають наборам, на яких функція приймає значення "1", з логічною "1". На решту входів треба подати логічний "0". На виході мультиплексора буде сформована потрібна функція.
Таблиця 4.5
|
Сигнали (входи) |
Вихід |
|
a b c(4 2 1) |
f |
|
0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 |
10110 |
Подобные документы
Алгоритми переведення чисел з однієї позиційної системи числення в іншу. Перетворення і передавання інформації. Булеві функції змінних, їх мінімізація. Реалізація функцій алгебри логіки на дешифраторах. Синтез комбінаційних схем на базі мультиплексорів.
курсовая работа [3,2 M], добавлен 02.09.2011Побудова математичної логіки як алгебри висловлень і алгебри предикатів. Основні поняття логіки висловлювань та їх закони і нормальні форми. Основні поняття логіки предикатів і її закони, випереджена нормальна форма. Процедури доведення законів.
курсовая работа [136,5 K], добавлен 27.06.2008Функціональна повнота системи функцій алгебри логіки. Клас самодвоїстих функцій і його замкненість. Леми теореми Поста. Реалізація алгоритму В середовищі програмування С#, який визначає чи є система функцій алгебри логіки функціонально повна, вид повноти.
курсовая работа [388,6 K], добавлен 17.05.2011Ознайомлення із символікою та апаратом логіки висловлень. Сутність алгебри Жегалкіна. Дослідження питань несуперечності, повноти та незалежності логічних та спеціальних аксіом числення предикатів. Визначення поняття та характерних рис алгоритмів.
курс лекций [538,2 K], добавлен 02.04.2011Скорочені, тупикові диз'юнктивні нормальні форми. Алгоритм Квайна й Мак-Класки мінімізації булевої функції. Геометричний метод мінімізації булевої функції. Мінімізація булевої функції за допомогою карти Карно. Побудова оптимальних контактно-релейних схем.
курсовая работа [287,0 K], добавлен 28.12.2010Методи скінченних різниць або методи сіток як чисельні методи розв'язку інтегро-диференціальних рівнянь алгебри диференціального та інтегрального числення. порядок розв’язання задачі Діріхле для рівняння Лапласа методом сіток у прямокутної області.
курсовая работа [236,5 K], добавлен 11.06.2015Вивчення рівняння з однією невідомою довільного степеня та способів знаходження коренів таких рівнянь. Доведення основної теореми алгебри. Огляд способу Ньютона встановлення меж дійсних коренів алгебраїчних рівнянь. Відокремлення коренів методом Штурма.
курсовая работа [1,1 M], добавлен 06.10.2012Вивчення теорії наближених обчислень і чисельних методів лінійної алгебри. Опис прямих і ітераційних методів вирішення систем лінійних рівнянь, алгоритмізація і точність наближених обчислень функції. Чисельна інтеграція звичайних диференціальних рівнянь.
лекция [103,6 K], добавлен 06.02.2014Визначення основних понять і вивчення методів аналізу безкінечно малих величин. Техніка диференціального і інтегрального числення і вирішення прикладних завдань. Визначення меж числової послідовності і функції аргументу. Обчислення інтегралів.
курс лекций [570,1 K], добавлен 14.03.2011Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
курсовая работа [239,3 K], добавлен 10.06.2007
