Xreferat.com » Рефераты по информатике и программированию » Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Лабораторна робота №1


Теоретичні відомості.

1. Алгебра логіки

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

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

Операції над логічними висловленнями:

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

І Операція, що виражається зв'язуванням "і", називається кон’юнкцією (лат. conjunctio - з'єднання) або логічним множенням і позначається точкою " " (може також позначатися знаками або &). Висловлення А·В істинно тоді і тільки тоді, коли обидва висловлення А и В істинні.

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

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

РІВНОСИЛЬНА Операція, що виражається зв'язуваннями "тоді і тільки тоді", "необхідно і досить",". рівносильно.", називається еквіваленцією або подвійною імплікацією і позначається знаком або ~. Висловлення істинне тоді і тільки тоді, коли значення А и В збігаються. За допомогою логічних змінних і символів логічних операцій будь-яке висловлення можна формалізувати, тобто замінити логічною формулою. В алгебрі логіки виконуються наступні основні закони, що дозволяють робити тотожні перетворення логічних виражень:

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


Закон Для АБО Для І
Комутативний

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Асоціативний

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Дистрибутивний

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Правила де Моргана

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Тавтології

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Поглинання

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Склеювання

Алгебра логіки як розділ математики


Операція над змінною з її інверсією

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Правила операцій з константами

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Закон подвійного заперечення

Алгебра логіки як розділ математики



Приклади


1.

Алгебра логіки як розділ математики

2.

Алгебра логіки як розділ математики

3.

Алгебра логіки як розділ математики

4.

Алгебра логіки як розділ математики

5.

Алгебра логіки як розділ математики

6.

Алгебра логіки як розділ математики

7.

Алгебра логіки як розділ математики

8.

Алгебра логіки як розділ математики

9.

Алгебра логіки як розділ математики


2. Перемикальні схеми

У комп'ютерах і інших автоматичних пристроях широко застосовуються електричні схеми, що містять сотні і тисячі перемикальних елементів: реле, вимикачів і т.п. Розробка таких схем досить трудомістка справа. Виявилося, що тут з успіхом може бути використаний апарат алгебри логіки.

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

Кожен перемикач має тільки два стани: замкнутий і розімкнутий. Перемикачеві Х поставимо у відповідність логічну перемінну х, що приймає значення 1 у тому і тільки в тому випадку, коли перемикач Х замкнути і схема проводить струм; якщо ж перемикач розімкнути, то х дорівнює нулеві.

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

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

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

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

СИНТЕЗ СХЕМИ по заданих умовах її роботи зводиться до наступних трьох етапів:

складанню функції провідності по таблиці істинності, що відбиває ці умови;

спрощенню цієї функції;

побудові відповідної схеми.

АНАЛІЗ СХЕМИ зводиться до

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

одержанню спрощеної формули.

Приклади.

1. Побудуємо схему, що містить 4 перемикачі x, y, z і t, таку, щоб вона проводила струм тоді і тільки тоді, коли замкнути контакт перемикача t і який-небудь з інших трьох контактів.

Рішення. У цьому випадку можна обійтися без побудови таблиці істинності. Очевидно, що функція провідності має вигляд F (x, y, z, t) = t · (x v y v z), а схема виглядає так:


Алгебра логіки як розділ математики


Приклад 2. Проаналізувати задану схему


Алгебра логіки як розділ математики


Розв’язок


Алгебра логіки як розділ математики

Алгебра логіки як розділ математики


В даному випадку будувати таблицю істинності не потрібно.

Приклад 3


Алгебра логіки як розділ математики


Розв’язок


Алгебра логіки як розділ математики


Спрощена перемикальна схема


Алгебра логіки як розділ математики


Таблиця істинності

z t F
0 0 0
0 1 1
1 0 1
1 1 1

3. Логічний елемент комп'ютера - це частина електронної логічної схеми, що реалізує елементарну логічну функцію.

Логічними елементами комп'ютерів є електронні схеми І, АБО, НЕ, І-НЕ, АБО-НЕ й інші (звані також вентилями), а також тригер.

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

Високий рівень звичайно відповідає значенню “істина" (“1”), а низький - значенню “неправда" (“0”).

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

Роботу логічних елементів описують за допомогою таблиць істинності.

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

Схема І

Схема І реалізує кон’юнкцію двох або більше логічних значень.

Одиниця на виході схеми І буде тоді і тільки тоді, коли на усіх входах будуть одиниці. Коли хоча б на одному вході буде нуль, на виході також буде нуль.

Зв'язок між виходом z цієї схеми і входами x і y описується співвідношенням: z = x · y

(читається як "x і y"). Операція кон’юнкції на структурних схемах позначається знаком "&" (читається як "амперсенд"), що є скороченим записом англійського слова and.


Алгебра логіки як розділ математики


Схема АБО

Схема АБО реалізує диз'юнкцію двох або більш логічних значень. Коли хоча б на одному вході схеми АБО буде одиниця, на її виході також буде одиниця.

Умовна позначка на структурних схемах схеми АБО з двома входами представлене на мал.5.2 Знак "1" на схемі - від застарілого позначення диз'юнкції як ">=1" (тобто значення диз'юнкції дорівнює одиниці, якщо сума значень операндів більше або дорівнює 1). Зв'язок між виходом z цієї схеми і входами x і y описується співвідношенням: z = x v y (читається як "x або y").


Алгебра логіки як розділ математики

Схема НЕ


Схема НЕ (інвертор) реалізує операцію заперечення. Зв'язок між входом x цієї схеми і виходом z можна записати співвідношенням z =, x де читається як "не x" або "інверсія х".

Якщо на вході схеми 0, то на виході 1. Коли на вході 1, на виході 0.


Алгебра логіки як розділ математики

Схема І-НЕ


Схема І-НЕ складається з елемента І и інвертора і здійснює заперечення результату схеми І. Зв'язок між виходом z і входами x і y схеми читається як "інверсія x і y".


Алгебра логіки як розділ математики

Схема АБО-НЕ


Схема АБО-НЕ складається з елемента АБО й інвертора і здійснює заперечення результату схеми АБО. Зв'язок між виходом z і входами x і y схеми читається як "інверсія x або y".


Алгебра логіки як розділ математики


2. Завдання до лабораторної роботи

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


Алгебра логіки як розділ математики


Проаналізувати наступні перемикальні схеми


Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики


Скласти перемикальні схеми функцій


Алгебра логіки як розділ математики

Алгебра логіки як розділ математики

Алгебра логіки як розділ математики


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


Лабораторна робота №2


Синтез схем

Теоретичні відомості

1. Основні етапи побудови схеми

Цифрові електронні схеми на логічних елементах застосовуються в якості схем керування для різних задач контролю і регулювання технологічних об’єктів. Під синтезом схеми розуміють її проектування (розробку).

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

2. Нормальні форми запису

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

Повна кон’юнкція-операція логічного множення, в якій беруть участь всі наявні вхідні змінні або їх інвертовані значення. Наприклад, якщо є змінні А і В, то одержуються 4 повні кон’юнкції:


Алгебра логіки як розділ математики


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


Алгебра логіки як розділ математики


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

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

Приклад:

Перевести нормальну форму І в нормальну форму АБО


Алгебра логіки як розділ математики

Алгебра логіки як розділ математики


За нормальною формою АБО можна синтезувати задану таблицю істинності.

Приклад

Спростити нормальну форму АБО


Алгебра логіки як розділ математики


Спочатку спрощують кон’юнкції 1 і 2


Алгебра логіки як розділ математики


Аналогічно спрощують 3 і 4


Алгебра логіки як розділ математики


Тоді


Алгебра логіки як розділ математики

Алгебра логіки як розділ математики


Нормальна форма може бути переведена на елементи І-НЕ або АБО-НЕ. Для переведення на І-НЕ здійснюють подвійне заперечення, а потім використовують формули де Моргана.


Алгебра логіки як розділ математики


Схема, що реалізує рівняння, представлена на рисунку:


Алгебра логіки як розділ математики


3. Метод карт Карно.

Карти Карно служать для наочного представлення і спрощення нормальної форми АБО. Карти Карно можуть бути представлені у вигляді таблиць істинності для повних кон’юнкцій. Карти Карно завжди мають кількість полів рівну кількості можливих повних кон’юнкцій.1 в полі карти Карно означає наявність повної кон’юнкції.

Приклад

Занести в карту Карно нормальну форму АБО


Алгебра логіки як розділ математики


Алгебра логіки як розділ математики


Представлена на карті Карно нормальна форма АБО може бути спрощена за певних умов.


Алгебра логіки як розділ математики


„Сусідні” повні кон’юнкції можна об’єднувати в групи.

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

Приклад

Максимально спростити за допомогою карти Карно нормальну форму АБО


Алгебра логіки як розділ математики


Спочатку повні кон’юнкції заносяться в карту


Алгебра логіки як розділ математики


Утворюються 2 групи по 2 поля. Спрощений вираз виглядає


Алгебра логіки як розділ математики


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


Алгебра логіки як розділ математики


В одній групі можуть бути об’єднані 2, 4 чи 8 повних кон’юнкцій.

Приклад

Записати і максимально спростити нормальну форму АБО, задану в карті Карно


Алгебра логіки як розділ математики


Можуть бути утворені 2 групи з 4 клітинок. Спрощене рівняння


Алгебра логіки як розділ математики


Карта Карно для 4 змінних:

Алгебра логіки як розділ математики


Варіанти мінімізації:

Алгебра логіки як розділ математикиАлгебра логіки як розділ математики

Алгебра логіки як розділ математики


Приклад

Скласти схему, що задовольняє заданій таблиці істинності


Алгебра логіки як розділ математики


Карта Карно

Алгебра логіки як розділ математики


Схема

Алгебра логіки як розділ математики


Завдання до лабораторної роботи


1. Побудувати схему перемикача "2 з 3" на елементах АБО-НЕ

Перемикач "2 з 3" - на виході 1, коли 2 з 3 входів встановлені в 1.

2. Побудувати схему контролю парності

Схема контролю парності - 1 на виході тоді, коли парне число входів дорівнює 1.

Лабораторна робота № 3


АЛГОРИТМИ ЛІНІЙНОЇ СТРУКТУРИ, РЕАЛІЗОВАНІ НА С++

Теоретична частина

У загальному мова програмування базується на двох основних поняттях - дані і алгоритми. Дані-це інформація, яку обробляє програма. Алгоритми - методи, які використовує програма. Мова С++ є процедурною, тобто основний акцент в ній робиться на алгоритмах. Це означає, що спочатку визначається послідовність дій, а потім ці дії реалізуються з допомогою мови програмування. Програма містить набір процедур, які комп’ютер повинен виконати для досягнення необхідного результату. Програмування на С++ є структурним. Програми проектуються за принципом "зверху вниз", ідея якого полягає у розбитті великої задачі на менші і такі, що легко розв’язуються.

Дані в С++ бувають прості і складені. Прості типи наведено в таблиці.


Типи даних:

Тип Розмір, байт Діапазон Опис
char signed char 1 Від - 128 до 127 Символьний тип. Містить один символ або рядок символів. Кожен символ представляється одним байтом. Компілятор розрізняє як окремі наступні типи: char, signed char і unsigned char
unsigned char 1

Від

до 255

Символьний тип. Кожен символ представляється одним байтом (значення в діапазоні від 0 до 255)
short signed short 2 Від - 32768 до 32767 Цілий тип. Скорочене позначення типу short int. Довжина цього типу поза залежністю від використовуваного компілятора завжди більше або дорівнювати довжині значення типу char і менше або дорівнює довжині значення типу int
Unsigned short 2 Від 0 до 65535 Беззнаковий цілий тип
int signed int 42 Від - 2147483648 до 2147483647 Цілий тип. Довжина цього типу поза залежністю від використовуваного компілятора завжди більше або дорівнює довжині значення типу short int
unsigned int 4 Від 0 до 4294967259 Беззнаковий цілий тип
intn n/8
Цілий тип, розмір у бітах якого визначається значенням п, і може бути рівним 8, 16, 32 або 64 бітам
long signed long 4 Від - 2147483648 до 2147483647 Цілий тип. Скорочене позначення типу long int
unsigned long 4 Від до 4294967259 Беззнаковий цілий тип
float 4 Від 3.4Е-38 до 3.4Е+38 Тип даних із плаваючою крапкою

До складених типів належать покажчики, масиви, перерахування, об’єднання, структури, класи. Більш детально вони будуть розглянуті в наступних лабораторних роботах.

Програмування включає в себе наступні етапи

Скориставшись текстовим редактором, написати текст програми і зберегти її в файлі. Цей файл буде вихідним кодом програми.

Допустимі розширення імен вихідного коду


Алгебра логіки як розділ математики


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

Зв’язати об’єктний код програми з об’єктними кодами функцій, використаних в програмі (додатковим кодом) і скомпонувати їх у єдину програму. Файл, який містить цю програму, називається виконуваним кодом.

Програми на С++ мають наступну структуру

Директиви препроцесора

#include

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

Блок опису вхідних змінних

Заголовок функції main () і її тіло у фігурних дужках{}. Тіло функції містить інструкції для комп’ютера. Кожна завершена функція називається оператором і завершується крапкою з комою. Слово, що стоїть перед назвою функції, називається типом функції (фактично, це тип результату, одержаного при виконанні функції). У круглих дужках після назви функціі мітиться список аргументів (параметрів) функції.

Оператор return, що завершує виконання функції main ()

Нижче наведено приклад програми, що здійснює

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: