Базові поняття алгебри логіки 1 страница

Основними об’єктами алгебри логіки є елементарні висловлювання – висловлювання, про які однозначно можна сказати, що вони істинні або хибні.

Кожне елементарне висловлювання алгебри логіки повинно задовольняти двом вимогам:

1) Закон виключення третього. Висловлювання може бути або істинним, або хибним. Третього не дано.

2) Закон протиріччя. Висловлювання не може одночасно бути і істинним, і хибним.

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

Серед операцій алгебри логіки визначають наступні:

– операція заперечення;

( ) – операція кон’юнкції або логічного множення;

– операція диз’юнкції або логічного додавання;

– операція імплікації;

– операція еквівалентності або рівнозначності;

– операція Шеффера;

– операція Пірса;

– операція додавання за модулем два або операція нерівнозначності.

Таблиця істинності операцій алгебри логіки.

Пріоритетність логічних операцій (порядок їхнього виконання у формулі при відсутності дужок):

1. операція заперечення;

2. операція кон’юнкції;

3. операція диз’юнкції;

4. усі решта введених операцій зліва направо в порядку входження у формулу.

Розглянемо основні закони операцій алгебри логіки, застосовні до трьох змінних .

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

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

3.Дистрибутивний закон для кон'юнкції по відношенню до диз'юнкції

4.Дистрибутивний закон для диз'юнкції по відношенню до кон'юнкції

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

6.Закони де-Моргана (закони двоїстості)

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

8.Закони поглинання

9.Операції з константами 0 та 1.

10.Закон виключення третього

11.Закон суперечливості (протиріччя)

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

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

У алгебрі Жегалкіна виконуються закони:

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

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

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

4. Закони ідемпотентності для кон'юнкції

5. Закон поглинання (зведення подібних членів при додаванні за модулем два

6. Операції з константами 0 та 1.

Наведемо еквівалентності, що дозволяють перетворити будь-яку формулу алгебри логіки у формулу алгебри Жегалкіна чи відповідно у формулу алгебри Буля:

Наведемо декілька прикладів розв'язування задач з алгебри логіки.

Приклад 1. Побудувати таблиці істинності формули .

Розв’язування. На підставі таблиці істинності для бінарних логічних операцій побудуємо відповідні таблицю істинності для заданої формули .

Таблиця істинності формули

Приклад 2. Мінімізувати формулу алгебри логіки, що задана в попередньому завданні.

Розв’язування. Скористаємося побудованою вище таблицею істинності формули . Побудуємо для кожного її істинного значення відповідну елементарну кон'юнкцію і об'єднаємо їх операцією диз’юнкція (отримаємо відповідну ДДНФ).

= .

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

.

Подальший аналіз одержаного виразу свідчить про мінімальний рівень складності виразу , тобто це і є мінімальна ДНФ.

Приклад 3. Побудувати еквівалентну формулу у алгебрі Жегалкіна для формули, що задана в попередньому завданні.

Розв’язування. Скористаємося наступними співвідношеннями між операціями алгебри логіки: ; ; , отримаємо

4. Основні елементи теорії графів.

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

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

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

Дуга є інцидентною до вершин та , якщо ці вершини є початковою та кінцевою його вершинами.

Вершини є інцидентними дузі, якщо дана дуга їх з’єднує.

Дві вершини та називаються суміжними, якщо вони з’єднані одною дугою.

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

Вершина, не інцидентна жодному ребру, називається ізольованою вершиною.

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

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

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

Кількість дуг, що входить у дану вершину називається напівстепенем входу.

Сума напівстепеня входу та напівстепеня виходу називається степенем вершини.

Дуга, початкова та кінцева вершини якої співпадають, називається петлею.

Граф, що складається лише з ізольованих вершин, називається нуль-графом.

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

Граф називається неорієнтованим, якщо кожне ребро його не орієнтоване, і орієнтованим, якщо орієнтовані всі його ребра. Деколи у графі деякі ребра є орієнтованими, а інші – ні, тоді такий граф називають графом змішаного типу.

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

Довжиною шляху називають кількість дуг, що його утворює.

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

Довжиною контура називають кількість дуг, що його утворює.

Шлях називається елементарним, якщо всі вершини, які він містить, є різними.

Контур називається елементарним, якщо всі вершини, які він містить, за винятком початкової та кінцевої, є різними.

Шлях називається простим, якщо всі дуги, які він містить, є різними.

Контур називається простим, якщо всі дуги, які він містить, є різними.

Граф, у якому для будь-якої пари його вершин існує шлях, що їх з'єднує, називається зв’язним.

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

Вагою (довжиною) шляху називається кількість (або сума всіх ваг) дуг, що його утворюють.

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

Частковим графом графу G називається граф, що містить частину дуг основного графа і всі вершини, що належать основному графу G.

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

Способи задання графа

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

2. Граф можна задати через відображення, визначивши множину його вершин та множину відображень кожної із вершин:

, , , , .

3. Граф можна задати через К-список (підмножину декартового добутку множини вершин графа самої на себе).

.

4. Найбільш математичним способом задання графа вважають його задання через матрицю суміжності чи матрицю інцидентності.

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

Матрицею інцидентності, відповідної до заданого графа, називають прямокутну матрицю, кількість рядків якої дорівнює кількості вершин графа, а кількість стовпців – кількості його дуг. Елементами матриці є числа 0, 1 і -1, причому елемент матриці дорівнює 0 у випадку, коли дуга не інцидентна вершині , елемент матриці дорівнює 1 у випадку, коли дуга входить у вершину і елемент матриці дорівнює -1 у випадку, коли дуга виходить із вершини .

Для того, щоб дати характеристику графа (незалежно від способу його задання) необхідно вказати:

– множину вершин даного графа;

– ізольовані вершини, вершини входу та виходу (якщо вони існують);

– тип графа (щодо орієнтованості);

– вказати чи заданий граф є повним;

– вказати чи заданий граф є зв’язним;

Наведемо деякі основні задачі в теорії графів.

1.Знаходження найкоротшого шляху у графі.

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

Спершу вершині присвоїмо індекс (0), а всім суміжним із нею вершинам присвоїмо індекс (1). Всім вершинам, що суміжні із вершиною, якій присвоєно індекс (1), і які ще не мають індексу, присвоюємо індекс (2). Таким чином, здійснюємо послідовну індексацію суміжних вершин до моменту, поки вершині не буде присвоєно деякий індекс. Припустимо, що вершина отримала індекс (k). Це означає, що довжина найкоротшого шляху, що з’єднує вершину із вершиною дорівнює k, а сам шлях є шляхом, що проходить вершинами, індекси яких відповідно дорівнюють 0,1,2,…,k. Для встановлення послідовності вершин, що утворили найкоротший шлях (а таких однакової довжини може бути більше одного), вибираємо проіндексовані вершини, суміжні з вершиною , індекс яких рівний . Тоді для вершин індексу шукаємо суміжні з індексом . Цей процес продовжуємо доти, поки не потрапимо у початкову вершину . Встановлена послідовність вершин, записана в інвертованому порядку і буде цим найкоротшим шуканим шляхом або шляхами.

2. Знаходження оптимального шляху у зваженому графі (шляху мінімальної ваги).

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

Спершу проводимо початкову індексацію вершин: вершині присвоїмо індекс (0), а всім вершинам даного графа надамо індекс . Отже, всі всі вершини графа є проіндексованими. Якщо вершини та є суміжними і проіндексовані відповідно та , а для їх індексів виконується нерівність: , де – вага дуги , тоді вершині присвоюємо індекс . Таким чином, здійснюємо процес переіндексації вершин, тобто корекцію проводимо для всіх індексів, для яких це можливо, до тих пір, поки всі проставлені індекси не стануть мінімально можливими. Якщо вершина одержить відмінний від індекс, який залишається незмінюваним, тоді значення становить довжину найкоротшого шляху в зваженому графі, а встановлення послідовності вершин цього мінімального шляху здійснюється аналогічно до вказаного у першому пункті способу.

Якщо індекс вершини залишається незмінюваним, рівним , то це означає, що шляху із вершини у вершину немає.

3.Знаходження числа шляхів або контурів заданої довжини.

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

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

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

Приклад 1. Охарактеризувати граф, заданий матрицею суміжності

.

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

1. Множина вершин даного графа .

2. Вершина h є ізольованою, оскільки в матриці суміжності цій вершині відповідають нульовий рядок і стовпець. Вершинами входу є вершини та g, оскільки у матриці суміжності цим вершинам відповідає нульовий рядок, а стовпець не нульовий. Вершина виходу – k, оскільки рядок, відповідний цій вершині, у матриці суміжності не нульовий, а стовпець – нульовий.

3. Оскільки матриця суміжності несиметрична – граф є графом змішаного типу. Існують строго напрямлені дуги такі як , а також існують двонаправлені дуги, такі як і .

4. Оскільки у графі є ізольована вершина, то граф не є повним і не є зв’язним.

Приклад 2. Граф, що заданий у попередньому завданні записати через відповідні множини відображень.

Розв’язування. Множина вершин даного графа .

Запишемо множину відображень для кожної вершини графа:

; ; ; ; ; ; ; ; ; .