За заданою логічною схемою скласти логічний вираз. Логічні схеми та логічні вирази. Завдання синтезу логічних схем у булевому базисі

Логічній функції комп'ютера відповідає деяка схема з вентилів. Цей принцип дає такий підхід до створення комп'ютера:

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

Отриману функцію полегшують, використовуючи закони алгебри логіки.

Остаточно отриману функцію записуємо як схеми з вентилів.

Схема з вентилів реалізується фізично з електронних елементів.

Наведемо приклад реалізації 3-го етапу. Дана функція

Отримати логічну схему функції.

Формування логічної схеми слід розпочинати з урахуванням пріоритету операцій (див. п. «Визначення логічної (бульової) функції»), і навіть круглих дужок, які змінюють порядок виконання операцій. Як відомо, найвищий пріоритет мають операції усередині дужок (якщо вони є), потім операція інверсії (заперечення). Отже, для заданої функції спочатку потрібно сформувати елементи
і , а потім елемент
. Далі можна виконати складання отриманих елементів (
і
) і, в останню чергу, до отриманої суми додати змінну a. У результаті отримаємо таку схему (рис. 5):

Мал. 5. Схема реалізації функції (формула (28))

Можливе розв'язання та зворотної задачі, коли дана логічна схема, потрібно отримати логічну функцію. Наприклад, на рис. 6 дана логічна схема. Потрібно написати нею логічну функцію.

Мал. 6. Схема реалізації функції f ( x , y , z )

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

Так для схеми малюнку 6 в першу чергу виконуватися три операції: x∙y, і . Потім операція інвертування суми:
, Далі ще одна операція логічного складання результатів попередніх операцій:
. Останньою буде виконуватися операція інвертування результату логічного множення:
. Таким чином, потрібна функція має вигляд.

Конспект уроку
"Побудова логічних схем за допомогою базових логічних елементів"

10 клас

Тип уроку: лекція, самостійна робота.

Обладнання: проектор, картки із завданнями.

Форми роботи: колективна, індивідуальна.

Тривалість уроку: 45 хв.

Цілі уроку:

Освітні:

навчитися будувати логічні схеми для логічних функцій з допомогою основних логічних елементів;

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

Виховні:

прищеплення навичок самостійності у роботі, виховання акуратності, дисциплінованості.

Розвиваючі:

розвиток уваги, мислення, пам'яті учнів.

Хід уроку:

1. Організаційний момент (1 хв).
2. Перевірка пройденого матеріалу (5 хв).

Фронтальне опитування.

Перелічіть основні логічні операції.

Що таке логічне множення?

Що таке логічне додавання?

Що таке інверсія?

Що таке таблиця істинності?

Що таке суматор?

Що таке напівсуматор?

3. Вивчення нового матеріалу (20 хв).

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

Логічний елемент "І":

Логічний елемент «АБО»:

Логічний елемент «НЕ»:

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

приклад 1. побудувати логічну схему.

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

приклад 2. Виписати з логічної схеми відповідну їй логічну формулу:

Рішення:

4. Закріплення нового матеріалу (15 хв).

Для закріплення матеріалу учням лунають картки на два варіанти для самостійної роботи.

Варіант 1.

Рішення:

Рішення:

Варіант 2.

1. За заданою логічною функцієюпобудувати логічну схему та таблицю істинності.
Рішення:

2. Виписати із логічної схеми відповідну їй логічну формулу:

Рішення:

5. Постановка домашнього завдання. (3 хв).

За заданою логічною функцієюпобудувати логічну схему та таблицю істинності.

6. Підбиття підсумків уроку. (1 хв).

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

Література, еор:

Інформатика та інформаційні технології. Підручник для 10-11 класів, Н. Д. Угрінович - 2007 р.;

Практикум з інформатики та інформаційних технологій. Навчальний посібник для загальноосвітніх установ, Н. Д. Угрінович, Л. Л. Босова, Н. І. Михайлова - 2007р.

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

Рис 6.1 - Схематичне зображення логічних операцій

приклад.Для обчислення логічного виразу: 1 або 0 і 1 намалювати схему, що відбиває послідовність виконання логічних операцій. За схемою обчислити значення логічного виразу.

Тут наочно відображено те, що першою виконується операція і, потім або. Тепер у порядку ліворуч – праворуч припишемо до вихідних стрілок результати операцій:

В результаті вийшла 1 , тобто. "ІСТИНА".

приклад.Дано вираз: не (1 і (0 або 1) і 1).

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

Рішення. Логічна схема з результатами обчислень виглядає так:

Імплікація та еквівалентність

Імплікація(Умовне висловлювання). У російській мові цієї логічної операції відповідають спілки якщо то; коли..., тоді; якщо ..., тоі т.п.

Вираз, що починається після спілок якщо, коли, якщо,називається основою умовного висловлювання.

Вираз, що стоїть після слів то, тоді,називається слідством. У логічних формулах операція імплікації позначається знаком "→". Імплікація – двомісна операція; записується так: А→В.

Еквівалентність.Мовний аналог - союзи якщо і тільки якщо; тоді і тільки тоді, коли...Еквівалентність позначається знайомий"≡" або "↔".

Порядок всіх п'яти логічних операцій зі спадання старшинства наступний: заперечення, кон'юнкція, диз'юнкція, імплікація, еквівалентність.

Перетворення логічних виразів

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

Основні формули перетворення логічних виразів:

2. (А & В) ≡ А Ст.

3. (А В) ≡ А & В.

4. (А → В) ≡А & В.

5. А→B ≡ A B.

6. А ↔ В ≡ (А & В) (А & В) ≡ (А В) & (А B).

7. А & (А B) ≡ А.

8. А А & В ≡ А.

9. А & (А В) ≡ А & В.

10. A А & В ≡ А Ст.

11. Закони комутативності:

А & В ≡ В & А;

А В ≡ В А.

12. Закони асоціативності:

(A B) З ≡ А (В С);

(А & В) & С ≡ А & (В & С).

13. Закони ідемпотентності:

А А ≡ А;

14. Закони дистрибутивності:

А & (В С) ≡ (А & В) (А&С);

А (В & С) ≡ (А В) & (А З).

15. А 1 ≡ 1;

16. А & 1 ≡ А;

17. А А ≡ 1;

18. А & 0 ≡ 0;

19. А & А ≡ 0.

6.3. Завдання на лабораторну роботу

Завдання розподіляються залежно від виданого викладачем mnкоду. Якщо m – число непарне, то ваш варіант 1, якщо парне – варіант 2.

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

Варіант 1.

1) хоча б одне із чисел X, Y, Z позитивно;

2) лише одне із чисел X, Y, Z не є позитивним.

3) тільки одне із чисел X, Y, Z більше 10

4) жодне з чисел X, Y, Z не дорівнює 104

Варіант 2.

1) хоча б одне із чисел X, Y, Z негативно;

2) лише одне із чисел X, Y, Z є негативним.

3) лише одне із чисел X, Y, Z не більше 10

4) кожне з чисел X, Y, Z дорівнює 0

Завдання 2.Визначте значення логічного виразу не (X>Z) іне (X=Y), якщо:

Варіант 1.

1) X = 3, Y = 5, Z = 2;

2) X = 5, Y = 0, Z = -8.

Варіант 2.

1) X = 9, Y = -9, Z = 9;

2) X = 0, Y = 1, Z = 19.

Завдання 3.Нехай a, b, c – логічні величини, які мають такі значення: а = істина, b = брехня, c = істина. Намалюйте логічні схеми для наступних логічних виразів та обчисліть їх значення:

Варіант 1.

1) а і b;

2) неа або b;

3) а або b іс;

4) (а або b) і(c або b).

Варіант 2.

1) а або b;

2) а і b абос;

3) неа або b іс;

4) не(а і b іс).

Завдання 4.Побудувати логічні схеми за логічним виразом:

Варіант 1. х 1 і (не x 2 абох 3).

Варіант 2. х 1 і x 2 або НЕ x 1 іх 3 .

Завдання 5.Виконайте обчислення за логічними схемами. Запишіть відповідні логічні вирази:

Варіант 1. Варіант 2.

Завдання 6.Дана логічна схема. Побудувати логічний вираз, що відповідає цій схемі.

Обчислити значення виразу для:

Варіант 1.

1) х 1 =0, х 2 =1;

2) х 1 =1, х 2 =1.

Варіант 2.

1) х 1 = 1, х 2 = 0;

2) х 1 =0, х 2 =0.

Завдання 7.Дана логічна схема. Побудувати таблицю істинності цієї схеми.

Завдання 8.Визначити істинність формули:

Варіант 1. ((a) .

Варіант 2. .

Завдання 9.Спростіть вираз:

Варіант 1. .

Варіант 2. .

6.4. Вимоги до змісту звіту

1. Ціль лабораторної роботи.

2. Завдання на лабораторну роботу. Mn – код.

3. Результати розв'язання завдань свого варіанта.

4. Висновки за отриманими результатами.

6.5. Контрольні питання

1. Що таке логічне висловлювання, константа, змінна, формула?

2. Які види логічних операцій розглядаються у лабораторній роботі?

3. Таблиці істинності для імплікації та еквівалентності?

4. Перерахуйте закони алгебри логіки?

Лабораторна робота №7
"СИСТЕМИ ЗЛІЧЕННЯ"

7.1. Мета роботи

Вивчення систем числення. Набуття навичок перекладу з однієї системи числення до іншої

7.2. Методичні вказівки

Розгорнутою формоюзапису числа називається запис у вигляді:

A q =±(a n-1 q n-1 + a n-2 q n-2 +…+ a 0 q 0 + a –1 q -1 + a -2 q -2 + …+ а -m q - m).

Тут А q – саме число, q – основа системи числення, а i – цифри даної системи числення, n – число розрядів цілої частини числа, m – число розрядів дробової частини числа.

приклад. Отримати розгорнуту форму десяткових чисел 32478; 26,387.

32478 10 = 3*10000 + 2*1000 + 4*100 + 7*10 + 8 = 3*10 4 + 2*10 3 + 4*10 2 + 7*10 1 + 8*10 0 .

26,387 10 = 2*10 1 + 6*10 0 + 3*10 -1 + 8*10 -2 + 7*10 -3 .

приклад. Отримати розгорнуту форму чисел 112 3 , 101101 2 , 15FC 16 , 101,11 2

112 3 =1*10 2 + 1*10 1 + 2*10 0 .

1011012 = 1*10 101 + 0*10 100 + 1*10 11 + 1*10 10 + 0*10 1 + 1*10 0 .

15FC 16 = 1 * 10 3 + 5 * 10 2 + F * 10 1 + С.

101,11 2 = 1*10 10 + 0*10 1 + 1*10 0 + 1*10 -1 + 1*10 -10 .

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

приклад. Усі числа з попереднього прикладу перевести до десяткової системи.

112 3 =1*3 2 + 1*3 1 + 2*3 0 = 9+3+2 = 14 10 .

101101 2 = 1*2 5 + 0*2 4 + 1*2 3 + 1*2 2 + 0*2 1 + 1*2 0 =32+8+4+1 = 45 10 ,

15FC 16 = 1 * 16 3 + 5 * 16 2 + 15 * 16 1 + 12 = 4096 + 1280 + 240 + 12 = 5628 10 .

101,11 2 = 1*2 2 + 0*2 1 + 1*2 0 + 1*2 –1 + 12 -2 = 4 + 1 + 1/2 + 1/4 = 5 + 0,5 + 0,25 = 5,75 10 .

4) Відповідь: l v 0 & l = 1.

Приклад 2

Побудуйте логічну схему, що відповідає логічному виразу

F = X & Y v (Y v X).

Обчислити значення виразу X = 1, Y = 0.

1) Змінних дві: X та Y;

2) Логічних операцій три: кон'юнкція та дві диз'юнкції: 14 3 2 X & Y v (Y v X).

3) Схему будуємо зліва направо відповідно до порядку логічних операцій:

3) Обчислимо значення виразу: F = l & 0 v (0 v 1) = 0

Виконайте вправу

Побудуйте логічну схему, що відповідає логічному виразу, і знайдіть значення логічного виразу:

A) F = A v B & C, якщо А = 1, = 1, С = 1.

Б) F = (A v B & C), якщо А = 0, = 1, С = 1.

B) F = A v B & C, якщо А = 1, = 0, С = 1.

Г) F = (А v) & (З v В), якщо А = 0, В = 1, С = 0.

Д) F = (А & & С), якщо А=0, В=0, С=1.

Е) F = (A & B & C) v (B & C vA), якщо А = 1, = 1, С = 0.

Ж) F = B&A v B&A, якщо А=0, В=0.

Закони логіки

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

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

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

приклад

Спростіть логічний вираз F= ((A v В) → (В v С)). Це логічне вираження потрібно призвести до нормальної форми, т.к. у ньому присутня імплікація та заперечення логічної операції.

1. Позбавимося імплікації та заперечення. Скористайтеся (8). Вийде: ((AvB)→(BvC))= (AvB)&(BvC).

2. Застосуємо закон подвійного заперечення (4). Отримаємо: (AvB)&(BvC)= (AvB)&(BvC)

3. Застосуємо правило дистрибутивності (15). Отримаємо:

(AvB)&(BvC)= (AvB)&Bv(AvB)&C.

4. Застосуємо закон комутативності (17) та дистрибутивності (15). Отримаємо: (AvB)&Bv(AvB)&C = A&BvB&BvA&CvB&C.

5. Застосуємо (16) і отримаємо: A&BvB&BvA&CvB&C=A&BvBvA&CvВ&С

6. Застосуємо (15), тобто винесемо за дужки В. Отримаємо:

A&BvBv A&Cv B&C=B&(Av1)v A&Cv В&С

7. Застосуємо (6). Отримаємо: В &(Avl)v A&Cv &С= Bv A&Cv &С.

8. Переставимо місцями доданки, згрупуємо і винесемо за дужки. Отримаємо:
BvA&CvB&C = B&(1vC)vA&C.

9. Застосуємо (6) і отримаємо відповідь:

Відповідь: F = ((A v) → (V v С)) = V v A & С.

Спростіть вираз:

1) F = (A & B) v (B v C).

2) F = (A→B) v (B→A).

3) F = A&C vA&C.

4) F = A vB v C v A v B v C.

5) F = (X & Y v (X & Y)).

6) F = X & (Y v X).

7) F = (X v Z) & (X v Z) & (Y v Z).

10) F = B & C & (AvA).

11) F = A&B&CvAvB

12) F = (AvB) & (BvA) & (CvB)

Спростіть вираз:

1. F = A&C vA&C.

2. F = A ↔ B v A&C

3. F=A& (B↔C)

4. F = (X v Y) & (Y ↔ X).

5. F= A vB vC v A v B v C.

6. F=(AvB) → (AvC)

7. F= А ↔ (V v C)

8. F = A&B → C&D.

9. F=(X & Y v (X & Y)).

10. F = (X v Y) & (Y v X).

11. F= A ↔ B &C

12. F = (A v B) & (B v A → B).

13. F= X&(Y v X).

14. F = A → B v A&C

15. F = X & Y v X.

16. F = ((X v Y) & (Z → X)) & (Z v Y).

17. F=(X v Z) & (X v Z) & (Y v Z).

18. F = А → (В v C)

19. F = A ↔ B v C

20. F = ((X v Y) & (Z v X)) & (Z → Y).

21. F= (B & (A→C))

22. F = A → B v A&C

23. F= А ↔ (V v C)

24. F = ((X v Y) & (Z v X)) & (Z v Y).

25. F=(A→B) v (B→A).

26. F = A&B&C&D.

27. F= А ↔(У v C)

28. F=A& (B→C).

29. F= A&(AvB)

30. F= А ↔ (V v C)

31. F = A → B v A &C

32. F = (A v B) & (B v A v B).

33. F= B&C& (AvA).

34. F= A&B v A&C

35. F = X & Y ↔ X.

36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).

37. F= A&B&CvAvB

38. F = (X → Y) & (Y v X).

39. F = A → B & C

40. F = (A ↔ B) & (B v A &B).

41. F =(AvB)&(BvA)& (CvB) .

42. F= A&B v A&C

43. F=A& (BvC)

44. F = (X → Y) & (Y ↔ X).

45. F= Av(A&B)

46. ​​F = A&B ↔ C&D.

47. F= А ↔(У v C)

48. F = (X & Y) v (Y & X).

Інструкція. При введенні з клавіатури використовуйте такі позначення: Наприклад, логічний вираз abc+ab~c+a~bc необхідно ввести так: a*b*c+a*b=c+a=b*c
Для введення даних у вигляді логічної схеми використовуйте цей сервіс.

Правила введення логічної функції

1. Замість символу v (диз'юнкція, АБО) використовуйте знак + .
2. Перед логічною функцією не треба вказувати позначення функції. Наприклад, замість F(x,y)=(x|y)=(x^y) необхідно ввести просто (x|y)=(x^y) .
3. Максимальна кількість змінних дорівнює 10 .

Проектування та аналіз логічних схем ЕОМ ведеться за допомогою спеціального розділу математики – алгебри логіки. В алгебрі логіки можна виділити три основні логічні функції: "НЕ" (заперечення), "І" (кон'юнкція), "АБО" (диз'юнкція).
Для створення будь-якого логічного пристрою необхідно визначити залежність кожної з вихідних змінних від діючих вхідних змінних така залежність називається функцією перемикання або функцією алгебри логіки.
Функція алгебри логіки називається повністю певною якщо задані все 2 n її значення, де n – число вихідних змінних.
Якщо визначено в повному обсязі значення, функція називається частково визначеної.
Пристрій називається логічним, якщо його стан описується за допомогою алгебри функції логіки.
Для представлення функції алгебри логіки використовують такі способи:

• словесне опис – це форма, що використовується початковому етапі проектування має умовне уявлення.
• опис функції алгебри логіки як таблиці істинності.
• опис функції алгебри логіки у вигляді виразу алгебри: використовується дві алгебраїчні форми ФАЛ:
  а) ДНФ – диз'юнктивна нормальна форма- Це логічна сума елементарних логічних творів. ДНФ виходить із таблиці істинності за наступним алгоритмом або правилом:
  1) у таблиці вибираються ті рядки змінних для яких функція на виході =1.
  2) для кожного рядка змінних записується логічний твір; причому змінні =0 записуються з інверсією.
  3) отриманий твір логічно підсумовується.
  Fднф = X 1 * Х 2 * Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
  ДНФ називається досконалою, якщо перемінні мають однаковий ранг чи порядок, тобто. до кожного твіру обов'язково повинні включатися всі змінні у прямому або інверсному вигляді.
  б) КНФ – кон'юнктивна нормальна форма– це логічний добуток елементарних логічних сум.
  КНФ може бути отримана з таблиці істинності за таким алгоритмом:
  1) вибираємо набори змінних для яких функція на виході = 0
  2) для кожного набору змінних записуємо елементарну логічну суму, причому змінні = 1 записуються з інверсією.
  3) логічно перемножуються одержані суми.
  Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  КНФ називається досконалоюякщо всі змінні мають однаковий ранг.

Рисунок1- Схема логічного устрою

Усі операції алгебри логіки визначаються таблицями істинностізначень. Таблиця істинності визначає результат виконання операції для всіх можливіх логічних значень вихідних висловлювань. Кількість варіантів, що відображають результат застосування операцій, залежатиме від кількості висловлювань у логічному виразі. Якщо кількість висловлювань у логічному вираженні N, то таблиця істинності міститиме 2 N рядків, оскільки існує 2 N різних комбінацій можливих значень аргументів.

Операція НЕ – логічне заперечення (інверсія)

• якщо вихідний вираз істинний, то результат його заперечення буде хибним;
• якщо вихідний вираз хибний, то результат його заперечення буде істинним.

Операція АБО - логічне додавання (диз'юнкція, об'єднання)

Операція І – логічне множення (кон'юнкція)

Операція «ЯКЩО-ТО» - логічне слідування (імплікація)

Операція "А тоді і тільки тоді, коли В" (еквівалентність, рівнозначність)

Операція «Додаток за модулем 2» (XOR, що виключає або, сувора диз'юнкція)

Пріоритет логічних операцій

• Дії у дужках
• Інверсія
• Кон'юнкція (&)
• Диз'юнкція (V), що виключає АБО (XOR), сума за модулем 2
• Імплікація (→)
• Еквівалентність (↔)

Досконала диз'юнктивна нормальна форма

1. Кожне логічне доданок формули містить всі змінні, що входять у функцію F(x 1 x 2 x x n).
2. Усі логічні доданки формули різні.
3. Жоден логічний доданок не містить змінну та її заперечення.
4. Жоден логічний доданок формули не містить одну й ту саму змінну двічі.

Досконала кон'юнктивна нормальна форма

1. Всі елементарні диз'юнкції містять усі змінні, що входять до функції F(x 1 ,x 2 ,...x n).
2. Усі елементарні диз'юнкції різні.
3. Кожна елементарна диз'юнкція містить один раз змінну.
4. Жодна елементарна диз'юнкція не містить змінної та її заперечення.