Основні положення дискретної математики

Зміст

1. ТЕОРІЯ МНОЖИН

1.1 Поняття множини і підмножини

1.2 Графічна інтерпретація множин та операцій над ними

1.3 Властивості операцій

1.4 Тотожності та їх доказ

1.5 Відносини на множинах

1.6 Властивості відносин

1.7 Ставлення порядку

1.8 Ставлення еквівалентності

2 МАТЕМАТИЧНА ЛОГІКА. АЛГЕБРА ЛОГІКИ

3. Булева алгебра

3.1 Досконалі нормальні форми

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

3.1.2 Розкладання по змінним

3.1.3 Алгоритм перетворення формули в СДНФ

3.2 Досконала кон'юнктивні нормальна форма (СКНФ)

3.2.1 Алгоритм перетворення формули в СКНФ

4 числення висловів

4.1 Рівносильні формули і їх доказ

4.2 Рівносильні формули

4.3 Доказ равносильность

5. Булева функція

5.1 Повнота системи булевих функцій

6. Логіка предикатів

5.1 Операції над предикатами

5.2 Квантори

5.3 Формули

6. ТЕОРІЯ графів

6.1 Поняття суміжності

6.2 Матриця інцидентності і списки ребер

6.3 Матриця суміжності графа

6.4 Операції над членами графів

7 ОСНОВНІ ВИМОГИ ДО ВИКОНАННЯ КОНТРОЛЬНОЇ РОБОТИ

8. ЕКЗАМЕНАЦІЙНІ ПИТАННЯ

9. ЛІТЕРАТУРА

Додаток I

1. ТЕОРІЯ МНОЖИН

1.1 Поняття множини і підмножини

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

Безліч - сукупність об'єктів, що розрізняються нашою інтуїцією.

Об'єкти, що становлять безліч називаються елементами цієї множини.

Безлічі позначаються великими латинськими літерами, а елементи - маленькими латинськими літерами.

Якщо елемент а належить множині А, то будемо використовувати запис , В іншому випадку використовується запис .

Безліч, що містить кінцеве число елементів називається кінцевим. Якщо безліч не містить жодного елемента, воно називається порожнім. Якщо безліч містить всі елементи, присутні в задачі, то воно називається універсальним і позначається Е.

Безліч можна задати різними способами. Найпоширеніші це: перерахування елементів: ; Вказівку властивостей елементів: , (Після двокрапки вказані властивості х).

Безліч А називається підмножиною множини В тільки тоді, коли будь-який елемент множини А належить множині В. записується це так: якщо .

- Знак нестрогого включення (кажуть В містить або покриває А).

- Знак суворого включення.

- Не включення.

Очевидно: якщо і , То ці множини складаються з одних і тих самих елементів і А = В.

1.2 Графічна інтерпретація множин та операцій над ними

Для графічної інтерпретації множин використовують діаграми Венна, які мають такий вигляд:

Над множинами виконуються три двомісні операції:

• Перетин;

• Об'єднання;

• Різниця множин.

Перетином множин А і В (мультиплікативна операція) називається нове безліч С, яке включає в себе елементи належать і безлічі А і безлічі В.

А В

Приклад:

Об'єднанням множин А і В (адитивна операція) називається нове безліч С, що складається з елементів множини А і з елементів множини В.

А В

Приклад:

Різницею множин А і В називається нове безліч С, складається з елементів, що належать безлічі А і не належать безлічі В.

А \ В з А відняти В

Приклад:

.

Крім розглянутих двомісних операцій існує одна одномісна операція - доповнення. Доповненням безлічі М є безліч (Не М) = .

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

1.3 Властивості операцій

1. Асоціативність;

2. Комутативність;

3. Дистрибутивність.

Операція називається асоціативної, якщо виконується рівність:

.

Виконання цієї умови (властивості асоціативності) означає, що дужки у виразі можна не розставляти. Додавання і множення чисел - асоціативні операції, що й дозволяє не ставити дужки (приклад: a + b + c; abc) приклад неассоціатівное операції: зведення в ступінь (a ^{b) c} тут дужки необхідні.

Операція називається комутативної, якщо виконується умова: . Додавання і множення є комутативними (від зміни місць доданків сума не змінюється). Обчислення і розподіл - некомутативних, некомутативних так само є операція множення матриць.

Операція називається дистрибутивної, якщо виконується умова: .

1.4 Тотожності та їх доказ

При виконанні операцій над множинами часто доводиться доводити рівності, тобто тотожності. (Зокрема, умови наведені вище є тотожністю, які необхідно довести).

Довести, що M = N, де M і N - вирази з множинами.

Доказ проводиться в два етапи: 1) «в одну сторону», 2) "у зворотний бік».

1. Спочатку припустимо, що якийсь елемент х належить лівій частині рівності: цей запис звучить наступним чином:

«Якщо , То ».

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

Приклад № 1

Довести тотожність:

.

Рішення:

1. ;

2. .

1.5 Відносини на множинах

Відносини бувають одномісними, двомісними (бінарними) і n-місцевими. Одномісне ставлення-це просто підмножина. Ми зупинимося на бінарних відношеннях.

1. впорядкована пара (x, y) є сукупність двох елементів записаних в певному порядку.

2. Дві пари (x, y) і (x _1, y ₁₎ вважаються рівними тоді і тільки тоді x ₁ = х, y ₁ = y.

3. Прямим твором x y називається сукупність пар (x, y) таких, що .

Можна навести такі приклади бінарних відносин:

• Ставлення «мати загальний дільник відмінний від 1» виконується для пар (6,9); (4,2); (2,4); (4,4), але не виконується для пар (7,9), (4, 7).

• Ставлення «бути дільником», тобто x ділить y виконується для пар (2,4); (4,4), але не виконується для пар (4,2); (7,9).

• Ставлення виконується для пар (7,9), (7,7), але не виконується для пари (9,7).

1.6 Властивості відносин

1. Рефлексивність;

2. Симетричність;

3. Транзитивність.

Відношення позначається R і записується так: xRy (x і y перебувають у відношенні R).

Відношення R називається рефлективним, якщо для будь-якого має місце aRa. Головна діагональ його матриці містить лише одиниці.

Відношення R називається антірефлектівним, якщо для будь-якого не виконується aRa. Головна діагональ його матриці містить лише нулі. Відносини = - Рефлективні, а ставлення <- антірефлектівное.

Відношення R називається симетричним, якщо для пари (а, в) з aRb слід bRa, інакше кажучи для будь-якої пари ставлення виконується або в обидві сторони, або не виконується взагалі. Матриця даного відношення симетрична щодо головної діагоналі.

Відношення R називається транзитивним, якщо для будь-яких a, b, c з aRb і bR з слід aR з відносини = - Транзитивність, ставлення «перетинатися» - нетранзітівно. (Приклад: перетинається з перетинається з , Проте і не перетинаються).

Завдання № 2

Встановіть якими властивостями володіє кожне з відносин, заданих на R наступними висказивательную формами:

1. x + y = 2;

Рішення:

в даному випадку задані відносини + і .

Підставимо у вираз x + y = 2 конкретні значення: 1 +1 = 2, послідовно перевіримо кожне властивість:

Рефлективність: aR а = а + а = 1 +1 - умова виконується, отже дане відношення рефлективно.

Симетричність: з aRb слід bRa = з а + b слід b + а = з 1 +1 слід 1 +1 - умова виконується, отже дане відношення симетрично.

Транзитивність: з aRb і bR з слід aR з дана умова ми перевірить не можемо, тому що воно застосовується тільки для трьох або більше елементів.

1.7 Декартово твір множин

Декартовим твором - X Y множин X та Y називається безліч М виду

В круглих дужках позначена послідовність, тобто безліч, в якому зафіксовано порядок елементів.

Підмножина F X Y називається функцією, якщо для кожного елемента x X, знайдеться не більше одного елемента y Y виду (x, y) F; при цьому, якщо для кожного елемента х є один елемент y виду (x, y) F, то функція називається усюди (повністю) певної, в іншому випадку - частково певної (не доопределения).

Безліч Х утворює область визначення функції F.

Безліч Y утворює область значень функції F.

Часто замість (x, y) F пишуть у = F (х), при цьому елемент х називається аргументом або змінною, а у - значенням функції F.

Зіставимо з декартовим твором двох множин х = . і в = . прямокутну грати, вузли якої взаємно однозначно відповідають елементам декартова твори (мал. 5).

Підмножини декартова твори позначені штрихуванням відповідних елементів.

На рис.5 а) показано підмножина декартового добутку не є функцією.

На рис.5 б) показано підмножина декартового добутку, що є повністю визначеною функцією.

На рис. 5 в) показано підмножина декартового добутку, що є частково певною функцією.

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

Аналогічно поняттю декартова добутку двох множин можна визначити поняття декартова твори n-множин.

Декартовим твором множин М _1, М _2, ...., М _n називається безліч Елементами декартова твори є всілякі послідовності, кожна з яких складається з n елементів, причому перший елемент належить множині М _1, другий - безлічі М _2, n-ий - безлічі М _n.

Якщо безліч М _х у визначенні функції у = F (x) є декартовим твором множин М _х1, М _х2, ...., М _{х n,} то отримуємо визначення n-місній функції у = F (х _1, х _2, ...., х _n).

1.8 Функція як відношення

Функцією називається функціональна відповідність.

Якщо функція f встановлює відповідність між множинами А і В, то говорять, що функція f має тип А В, позначається f: А В. кожному елементу а зі своєї області визначення функція f ставить у відповідність єдиний елемент b з області значень. Позначається f (a) = b.

Елемент а називається аргументом функції, елемент b називається значенням функції на а.

Повністю певна функція f: A B називається відображенням А і В.

Областю визначення називається вираз D =

Функція називається ін'ектівной, якщо з відносин (x _1, y) f, (x _2, y) f x ₁ = x ₂

Функція називається сюр'ектівной, якщо для кожного у Y існує х Х.

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

1.9 Ставлення порядку

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

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

Елементи a, b порівнянні стосовно порядку, якщо виконується aRb або bRa. Безліч М, на якому задано відношення порядку називається повністю впорядкованим, якщо будь-які два елементи множини М порівнянні, в іншому випадку - частково упорядкованим.

Приклад: відносини для чисел є відносинами нестрого порядку, відносини <,> - відносини строгого порядку. Обидва відносини повністю впорядковують безліч. Відношення строгого включення задає строгий частковий порядок: .

Відношення еквівалентності

Відношення називається відношенням еквівалентності (еквівалентністю), якщо воно одночасно рефлективно, симетрично і транзитивній.

Приклади:

1. відношення рівності на будь-якому безлічі є відношенням еквівалентності;

2. твердження виду (a + b) (b - a) = a ² - b ² - формули з'єднані знаком рівності задають бінарне відношення. Таке ставлення називають ставленням равносильности. Воно відрізняється від рівності, тому що може виконуватися для різних формул.

3. Відношення подібності геометричних фігур, «бути сусідами по квартирі», «бути ровесниками» так само є відносинами еквівалентності.

Кожне відношення еквівалентності є в певному сенсі рівністю, наприклад, ставлення «бути ровесником» означає рівність віку.

Завдання № 3

Які з перерахованих відносин є відносинами еквівалентності, а які - відносинами порядку: <, (На множині дійсних чисел), передувати (на безлічі слів у словнику), бути однофамільцем (на безлічі учнів в даному вузі).

Рішення: необхідно перевірити кожне з властивостей відносин (аналогічно завданням № 2) і визначити еквівалентність або порядок відносин.

2. МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ

Модель є відображенням чого-небудь. У науці про природу моделювання використовується як метод пізнання.

2.1 Перетворення до моделі

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

2. Інформація про об'єкт, отримана в результаті експерименту на моделі повинна бути переносимо на об'єкт.

Існують різні моделі, які використовують у фізиці і математиці.

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

• модель повинна відображати характеристики та властивості об'єкта,

• модель повинна прогнозувати поведінку об'єкта,

• модель повинна бути більш простий, ніж оригінал, але з іншого боку вона повинна якомога повніше відображати властивості об'єкта.

2.2 Способи моделювання

1. Макетні. Широко застосовується в будівництві.

2. Фізичне. Основою для такого моделювання є теорія подібності.

3. Електричне моделювання.

4. Математичне моделювання.

Ми зупинимося на математичному моделюванні. Модель являє собою сукупність залежностей, що дозволяють прогнозувати задані свойсвта об'єкта. У математиці термін «модель» застосовується поряд із звичайним тлумаченням. Може означати, наприклад, теорію подібну іншої теорії. Математика використовує символічні моделі. Така модель охоплює певну безліч абстрактних об'єктів: це числа, вектори і т. д. І відносини між ними.

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

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

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

2.3 Алгебраїчні моделі

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

3. ТЕОРІЯ КОДУВАННЯ

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

Нехай А і В два кінцеві алфавіту.

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

І R - деяке безліч кінцевих слів в алфавіті А. Однозначне відображення безлічі R в деяке безліч слів в алфавіті В називається кодуванням множини R.

Образ З безлічі R при відображенні називається кодом безлічі R. Слова з С називаються кодовими словами, при цьому, якщо слово w з R відображається в слово v з С, то v називається кодом слова w. Слова з R називаються повідомленнями, алфавіт А - алфавітом повідомлень, алфавіт В - кодований алфавітом. Якщо кодує алфавіт В складається з двох букв (в цьому випадку будемо вважати, що ), То кодування і відповідний код З називається двійковим (з ними ми і будемо працювати).

Код називається рівномірним або блоковим, якщо всі кодові слова мають однакову довжину.

Блочний двійковий код, в якому кожне кодове слово має довжину n, являє собою підмножину вершин n-мірного куба.

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

b = b _1, b _2, b ₃

b = 000

b = 001

b = 010

b = 011

b = 100

b = 101

b = 110

b = 111

Кожній вершині куба привласнена кодова комбінація за принципом: якщо проекція на вісь дорівнює нулю, то в комбінації ставиться нуль, а якщо проекція дорівнює одиниці, то в комбінації ставиться одиниця. Порядок проекцій повинен бути одним і тим же: b _1, b _2, b _3. Довжина ребра куба дорівнює одиниці. D - це довжина між сусідніми розрядами або кодова відстань.

Даний спосіб кодування позначимо (2,3). У цій ситуації неможливо ні виявити помилку ні виправити її.

Нехай дозволеними кодами є 000 і 111, тоді кількість можливих кодів - 8, кількість дозволених кодів - 2, відстань між дозволеними кодами = 3.

Для того щоб визначити кодова відстань між двома комбінаціями двійкового коду досить підсумувати ці комбінації за модулем 2 і підрахувати число одиниць в отриманій комбінації. Приклад:

000

111

. 111 число одиниць = 3. Значить d = 3.

Отримуємо повідомлення з однією помилкою в розряді. Тоді віднесемо помилковий код до тієї вершини, яка відстає на одиницю. Замість неправильний код запишемо координату вершини (0,0,0), отримаємо виправляється код тоді можливі три ситуації:

1. (3,3) коли кількість повідомлень = 8, кількість кодів = 8. У цьому випадку помилковий код буде збігатися з одним з повідомлень і тому помилку виявити неможливо.

2. (2,3) кількість повідомлень = 4, кількість кодів = 8, тоді отримаємо 4 дозволених коду, які збігаються з вершинами (рис. 8).

Помилку виявити можна, але виправити не можна.

3. (1,3) помилку можна і виявити і виправити.

Якщо ми хочемо побудувати код, який може виявити n помилок, то відстань між кодовими словами d = k + 1.

Якщо ми хочемо виправляти помилку, то відстань повинна бути d = 2 s +1

Якщо ми хочемо побудувати код одночасно виявляє і виправляє помилку, то мінімальна кодова відстань повинна бути

d = k + s +1.

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

10110 - передана кодова комбінація

10010 - 1-я прийнята комбінація

10100 - 2-я прийнята комбінація

00110 - 3-я прийнята комбінація

10110 - накопичена комбінація

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

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

3.1 Коди з виявленням помилок

Маємо кодове слово а = а _1, а _2, ..., а _m; складаємо інше кодове слово з додаванням символу - b = b _1, b ₂ ... b _m, b _{m +1}

a _i = b _i

b _{m +1} = ... ... ... ..

отримаємо на вході непарний код, він є завжди помилковим. Помилку виявити можна але виправити не можна. Даний код відповідає розробленому прикладу (2,3)

3.2 Коригувальні коди

а = а _1, а _2, ..., а _m

b = a ₁ a ₁ a _1, a ₂ a ₂ a _2, ... a _m a _m a _m

a _i = b _i, довжина коду 3 _m

а ₂ а ₂ а ₂

якщо 0 0 0, то помилки немає

якщо 1 1 1, то помилки немає

якщо 0 1 1, то помилка є

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

Аксіоми відстані:

d (a, b) 0

d (a, b) = 0, якщо a = b

d (a, b) = d (b, a)

d (a, b) + d (b, c) d (a, c)

3.3 Групові коди

Розглянемо безліч двійкових кодів із заданою операцією (додавання по модулю).

Запишемо таблицю істинності для операції «складання по модулю»

a + (b + c) = (a + b) + c

a + b = b + a

a + a = 0, (a ^-1 = a)

a +0 = a

На безлічі кодів задана група (В, +, 0) в свою чергу безліч прийнятих повідомлень С утворюють групу (С, +, 0). Для розглянутого прикладу безліч кодів b = c = . Очевидно, що безліч b є підгрупою безлічі С.

3.4 Класи

• класи.

Суміжних класом В і С називається безліч В + С, де С - фіксований елемент, а b пробігає усі значення безлічі В. для прикладу побудуємо лівий суміжний клас.

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

Вісім лівих суміжних класів:

b c

000 +000 = 000 000 +111 = 111

001 +000 = 001 001 +111 = 110

010 +000 = 010 010 +111 = 101

011 +000 = 011 011 +111 = 100

100 +000 = 100 100 +111 = 011

101 +000 = 101 101 +111 = 010

110 +000 = 110 110 +111 = 001

111 +000 = 111 111 +111 = 000

Стовпці цієї таблиці є розбиття множини С. Відомо, що розбиття визначає певне відношення еквівалентності, тоді процес декодування можна робити таким чином: допустимо, що отримано повідомлення З _i = 011. Таким чином теорія груп може розглядатися математичною основою теорії кодування.

ЛІНІЙНА АЛГЕБРА

Вектор (0, 0,, 0) з усіма координатами рівними нулю, називається нульовим. Це єдиний n-мірний вектор, для якого виконуються умови:

Якщо r ^/ , То r ^/ + = R ^/

Якщо r ^/ , То r ^/ - = R ^/

Якщо r ^/ , То r ^/ - r ^/ =

Якщо r ^/ , То 0 * r ^/ =

Якщо а , То а * =

Реляційна алгебра

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

Операція вибору є процедуру побудови «горизонтального» підмножини, тобто підмножини кортежів (рядків), що володіють заданими властивостями.

Приклад: за допомогою операції вибору побудуємо відношення R ^/ ₅ (розклад іспитів професора Іванова). Результатом операції вибору є рядки, в яких домен (стовпець) D ₃ представлений значенням професор Іванов: це 1,6,8-я рядка.

Таб.1

Для визначення проекцій відносин безліч в реляційної алгебри розбивається на дві підмножини в разі бінарного відносини і на n підмножин у разі n-арного відносини:

,

Проекцією П _р (R ₂ / A) бінарного відношення R _2, R ₂ на А називається безліч елементів .

Проекцією П _р (R ₂ / A _{i 1,} A _{i 2,} ... A _in) n-арного відносини називається безліч кортежів (а _{i 1,} a _{i ​​2,} ..., a _im), де , Кожен з яких є частиною елемента n-арного відносини R _n. операція проекції визначає побудову «вертикального» підмножини відносини, тобто безліч підмножини кортежів, одержуваного вибором одних доменів і виключення інших доменів.

Приклад: проекція П _р (R ₅ / D _2,, D ₃₎ породжує безліч пар, кожна з яких визначає дисципліну і екзаменатора.

Таб. 2

R 2	D 3	D 3
	теорія автоматів	пр. Іванов
	математична статистика	пр. Петров
	фізика	пр. Сидоров
	алгоритмічні мови	пр. Іванов

однакові рядки в таблиці об'єднані в одну.

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

Приклад: знайдемо по двом заданим таблиць (таб.3.а, _таб.3. Б) результат операції з'єднання по домену D ₁ (таб.3.в)

Таб. 3.а

Таб.3б

Таб.3в

Аналогічно можна визначити операцію з'єднання не тільки за умовою «рівності», а й за іншими умовами порівняння: <,>. Визначимо наприклад операцію з'єднання за умовою> з'єднання за умовою> відносини R _а по атрибуту х і відносини R _b по атрибуту у (атрибути х, у є атрибутами одного і тог ж домена загального для відносин R _а, R _b ), Х> у називається безліч всіх кортежів , Таких, що - Конкатенація кортежу а _i, що належить R _b, де х - частина а _i, у - частина b _i і х> у.

Запит до реляційної БД буде виконаний тим швидше, чим менше операцій над відносинами він містить Таким чином становить практичний інтерес розглянута вище завдання спрощення подання безлічі через введені операції.

2 МАТЕМАТИЧНА ЛОГІКА. АЛГЕБРА ЛОГІКИ.

У булевой алгебрі розглядається двоелементною безліч В, елементи якого позначаються як 0 і 1 і розглядають їх як формальні символи, які не мають арифметичного значення. Найбільш поширена інтерпретація двійкових змінних - логічна: «так» - «ні», «істина» - «брехня».

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

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

Логічна функція f (x _{1, ...} x _n) - це функція приймає значення 0,1. Безліч всіх логічних функцій позначається Р _2, безліч всіх логічних функцій від n-змінних позначається Р ₂ (n). Будь-яка логічна функція може бути задана таблицею, в лівій частині якої перераховані всі набори змінних, а в правій частині - значення функції на цих наборах.

Мінлива х _i у функції f (x _{1, ...} x _i, x _i, x _{i +1,} ..., x _n) називається несуттєвою (або фіктивної), якщо f (x _{1, ...} x _i, 0, x _{i +1} , ..., x _n) = f (x _{1, ...} x _i, 1, x _{i +1,} ..., x _n) при будь-яких значеннях інших змінних, тобто якщо зміна значення x _i в будь-якому наборі значень x _{1, ...} x _i не змінює значення функції. Кажуть, що функція g отримана з функції f видаленням фіктивної змінної і навпаки, причому ці функції вважаються рівними.

Приклад: f (x ₁ x ₂ x ₃ x ₄₎ = g (x _1, x ₂₎ означає, що при будь-яких значеннях x ₁ і x ₂ f = g незавасімо від значення x _3. Видаляють фіктивні змінні оскільки вони не впливають на значення функції і є з цієї точки зору зайвими.

Розглянемо приклади логічних функцій:

1. Одна мінлива Х має 4 логічних функції, які наведені в таблиці 1.

Таб.1.

Функції F ₀ і F ₃ - константи 0 і 1 відповідно;

Функція F ₁ (х) = х, тобто функція F ₁ повторює х;

Функція F ₂ (х) є запереченням х (логічна операція НЕ) і позначається .

Всі перераховані функції є унарний (для однієї змінної) функціями.

2. Дві змінні мають 16 логічних функцій (таблиця 2).

Таб. 2

Всі функції в таблиці 2 є бінарними (для двох змінних).

Функції F ₀ і F ₁₅ - константи 0 і 1;

Функція F ₁ (х _1, х ₂₎ називається кон'юнкція х ₁ і х _2, позначається: &, , Але найчастіше значок кон'юнкції опускають, аналогічно знаку множення. Вона рівна одиниці тільки тоді коли х ₁ і х ₂ = 1. В інших випадках вона рівна 0. Це функція логічного «І» або функція логічного множення.

Функція F ₇ (х _1, х ₂₎ називається диз'юнкція х ₁ і х _2, позначається +, . Вона рівна 1, якщо хоча б одна змінна дорівнює 1. Це функція логічного "АБО" або функція логічного складання.

Функція F ₆ (х _1, х ₂₎ - додавання за модулем 2, позначається . Вона рівно 1 коли значення її аргументів різні і рівно 0 коли значення її аргументів рівно, тому ця функція називається нерівнозначні.

Функція F ₉ (х _1, х ₂₎ - еквівалентність (рівнозначність), позначається « ». Вона рівно 1 коли аргументи рівні і рівно 0 коли аргументи різні.

Функція F ₁₃ (х _1, х ₂₎ - імплікація, позначається . Звучить ця функція так: "якщо х _1, то х ₂ ".

Функція F ₈ (х _1, х ₂₎ - стрілка Пірса, позначається

Функція F ₁₄ (х _1, х ₂₎ - штрих Шеффера, позначається х _1, х ₂

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

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

Завдання № 4

Побудувати таблицю істинності для формули:

Таб. 3

3. Булева алгебра

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

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

1. Асоціативність

2. Комутативність

3. Дистрибутивність кон'юнкції щодо диз'юнкції

4. Дистрибутивність диз'юнкції відносно кон'юнкції

5. Ідемпотентность

6. Подвійне заперечення

7. Властивості констант

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

9. Закон суперечності

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

В алгебрі логіки ці закони називаються рівносильними.

3.1 Досконалі нормальні форми

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

Введемо позначення:

; А ^А = 1; Х ^А = 1, якщо Х = А, Х ^А = 0, якщо Х А.

Формула Х ^А _{1 ... ...} Х ^А _n, де А = - Будь-який двійковий набір, а серед змінних Х i можуть бути збігаються називається елементарною кон'юнкцією.

Всяка диз'юнкція елементарних кон'юнкція називається діз'юнктівной нормальною формою (ДНФ).

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

Наприклад: 1) (Значок кон'юнкції в даному випадку опущений).

1), 4) - правильні елементарні кон'юнкції;

2) - мінлива х входить один раз сама і другий раз під знаком заперечення;

3. - Мінлива y входить тричі: один раз сама і два рази під знаком заперечення.

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

Наприклад: з перелічених у попередньому прикладі кон'юнкція повною є тільки 4) щодо змінних x, y, z, t; а щодо змінних x, y, z повною є тільки 1).

Досконалої діз'юнктівной нормальною формою (СДНФ) щодо змінних х ₁ ... .. х _n називається діз'юнктівная нормальна _форма, в якій немає однакових елементарних кон'юнкція і всі елементарні кон'юнкції правильні і повні щодо змінних х ₁ ... .. х _n

1. Розкладання по змінним

Теорема 1. Будь-яка логічна функція може бути представлена ​​в СДНФ:

, (1)

де m , А диз'юнкція береться за всіма 2 ^m наборам значень змінних х _1, ... х _m. Функція f розкладена по перших n-змінним. Дане рівність називається розкладанням по змінним. х _1, ... х _m. Наприклад при n = 4, m = 2 розкладання має вигляд:

теорема доводиться підстановкою в обидві частини рівності (1) довільного набору (b _1, ..., b _m, b _{m +1,} ..., b _n) всіх n-змінних.

При m = 1 з (1) отримуємо розкладання функції з однією змінною:

(2)

Очевидно, що аналогічне розкладання справедливо для будь-якої з n - змінних.

Інший важливий випадок коли n = m. При цьому всі змінні в правій частині (1) отримують фіксовані значення та функції в кон'юнкції правій частині стають рівними 0 або 1, що дає:

, (3)

де диз'юнкція береться по всіх наборів (b ₁ ... b _n), на яких f = 1. При f = 0 безліч кон'юнкція в правій частині порожньо. Таке розкладання називається досконалою діз'юнктівной нормальною формою. СДНФ функції f містить рівно стільки кон'юнкція, скільки одиниць виходить в таблиці істинності f. Кожному одиничному набору (b _1, ..., b _n) відповідає кон'юнкція всіх змінних, в якій x _i взято з запереченням, якщо b _i = 0 b, і без заперечення, якщо, b _i = 1. Таким чином існує взаємно однозначна відповідність між таблицею істинності функції f і її СДНФ, і, отже, СДНФ для всякої логічної функції єдина. Єдина функція не має СДНФ - це константа 0.

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

Теорема 2. Будь-яка логічна функція може бути представлена ​​у вигляді булевої формули.

Дійсно, для будь-якої функції, крім константи 0, таким поданням може служить її СДНФ. Константу 0 можна представити булевой формулою:

3.1.3 Алгоритм перетворення формули в СДНФ

Рівність (3) дає можливість знаходити СДНФ для функції з її таблиці істинності

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

Таб. 4.

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

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

• імплікація

• еквівалентність

• перенесення заперечення: з властивостей: і можна зробити наступні перетворення:

2 крок. Перетворимо функцію так, щоб всі кон'юнкції виконувалися раньшн, ніж диз'юнкції. Досягти цього можна за допомогою властивості дистрибутивності кон'юнкції щодо диз'юнкції: .

Наприклад:

3 крок. Якщо в ДНФ є кілька однакових елементарних кон'юнкція, то ми залишаємо тільки одну (використовуючи властивість ідемпотентності: ).

4 крок. Робимо все елементарні кон'юнкції правильними шляхом одним з таких перетворень:

• якщо в елементарну кон'юнкцію входить деяка змінна разом зі своїм запереченням, то ми видаляємо цю кон'юнкцію з ДНФ (використовуючи властивість ).

• Якщо деяка змінна входить в елементарну кон'юнкцію кілька разів, причому або у всіх функціях з запереченням або у всіх випадках без заперечення, то ми залишаємо тільки одне входження (використовуючи властивість ідемпотентності: хх = х).

5 крок. Робимо все елементарні кон'юнкції повними. Якщо в деяку кон'юнкцію не входить змінна y, то необхідно розглянути равносильное вираз і знову застосувати крок 2. Якщо відсутніх змінних кілька, то потрібно додати кілька кон'юнктивні членів виду .

6 крок. Після застосування 5-го кроку можуть знову з'явиться однакові кон'юнкції. Тому на шостому кроці застосовують крок 3.

Завдання № 5.

Знайти СДНФ для наступної формули:

=

1. крок. Перетворимо формулу так, щоб у ній були операції тільки кон'юнкції, диз'юнкції і заперечення.

Використовуючи властивість , Одержимо

використовуючи властивість , Одержимо

=

2. крок. Перетворимо формулу так, щоб кон'юнкція виконувалася раніше диз'юнкції.

Використовуючи властивість дистрибутивності отримаємо

=

3. крок. Всі кон'юнкції вийшли правильними, робимо їх повними

4. крок. Однакових кон'юнкція немає, отже залишаємо їх усі.

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

(Наприкінці прикладу опущений знак кон'юнкції)

3.2 Досконала кон'юнктивні нормальна форма (СКНФ)

Формула виду , Називається елементарною диз'юнкцією.

Всяка кон'юнкція елементарних диз'юнкцій називається, кон'юнктівной нормальною формою

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

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

Досконалої кон'юнктівной нормальною формою щодо змінних х ₁ ... х _n , Називається КНФ, в якій немає однакових елементарних диз'юнкцій і всі елементарні диз'юнкції правильні і повні щодо змінних х ₁ ... х _n.

Теорема 3: всяку функцію f можна представити у СКНФ

, (4)

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

1. Алгоритм перетворення формули в СКНФ

Перетворення формули в СКНФ проводиться аналогічно перетворенню формули в СДНФ. Відмінність полягає в тому, що утворювати потрібно не кон'юнкції, а диз'юнкції.

Знаходити СКНФ для функції також можна за її таблиці істинності, але диз'юнкції беруться за тими розділами, де функція = 0. Із запереченням береться та змінна, значення якої = 1.

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

Таб. 5

Ця функція має наступну СКНФ:

.

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

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

• імплікація

• еквівалентність

• перенесення заперечення: з властивостей: і можна зробити наступні перетворення:

2 крок. Перетворимо функцію так, щоб всі диз'юнкції виконувалися раніше, ніж кон'юнкції. Досягти цього можна за допомогою властивості дистрибутивності диз'юнкції відносно кон'юнкції:

.

Наприклад:

3 крок. Якщо в КНФ є кілька однакових елементарних диз'юнкцій, то ми залишаємо тільки одну (використовуючи властивість ідемпотентності: ).

4 крок. Робимо все елементарні кон'юнкції правильними шляхом одним з таких перетворень:

• якщо в елементарну диз'юнкцію входить деяка змінна разом зі своїм запереченням, то ми видаляємо цю диз'юнкцію з КНФ (використовуючи властивість ).

• Якщо деяка змінна входить в елементарну кон'юнкцію кілька разів, причому або у всіх функціях з запереченням або у всіх випадках без заперечення, то ми залишаємо тільки одне входження (використовуючи властивість ідемпотентності: х х = х).

5 крок. Робимо все елементарні диз'юнкції повними. Якщо в деяку диз'юнкцію не входить змінна y, то необхідно розглянути равносильное вираз і знову застосувати крок 2. Якщо відсутніх змінних кілька, то потрібно додати кілька диз'юнктивних членів виду .

6 крок. Після застосування 5-го кроку можуть знову з'явиться однакові диз'юнкції. Тому на шостому кроці застосовують крок 3.

Завдання № 5

Знайти СКНФ для формули:

=

1. крок. Перетворимо формулу так, щоб у ній були операції тільки кон'юнкції, диз'юнкції і заперечення.

Використовуючи властивість , Одержимо

=

використовуючи властивість , Одержимо =

2. крок. Перетворимо формулу так, щоб диз'юнкція виконувалася раніше, ніж кон'юнкція.

Використовуючи властивість дистрибутивності отримаємо

3. крок. Робимо диз'юнкції правильними

4. крок. Робимо диз'юнкції повними

5. крок. Застосовуємо крок 2. Отримуємо

6. крок. Отримали дві однакові диз'юнкції, залишаємо одну з них

отримали досконалу кон'юнктивні нормальну форму. (Наприкінці прикладу опущений знак кон'юнкції)

4 числення висловів

4.1 Рівносильні формули і їх доказ

Алгебра висловлювань також як і булева алгебра використовує два елементи: «істина», «брехня». В алгебрі висловлювань розглядаються питання, пов'язані з утворенням складних висловлювань. Якщо, у нас є кілька висловлювань, то за допомогою логічних зв'язок (кон'юнкції, диз'юнкції, імплікації і еквівалентності) і за допомогою операцій з них можна утворювати різні, нові висловлювання. При цьому вихідні висловлювання називаються простими, а новоутворені висловлювання називаються складними.

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

• на вулиці світить сонце, і в аудиторії йдуть заняття;

• на вулиці світить сонце, або в аудиторії йдуть заняття;

• якщо на вулиці світить сонце, то в аудиторії йдуть заняття. і. т. д.

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

Розглянемо деякі визначення.

Алфавіт - будь непорожня множина.

Символ - елемент алфавіту.

Довільна кінцева послідовність символів, називається, словом або виразом.

Вираз називається формулою, якщо воно задовольняє наступним вимогам:

1. будь-яка висказивательную змінна є формула;

2. якщо X і Y - формули, то вирази

... Y

теж є формулами.

Упорядкований набір висказивательную змінних називається списком.

Оцінений зі списку - це зіставлення кожної змінної її істинного значення.

1. Рівносильні формули

Нехай X і Y - формули алгебри висловлень, а х ₁ ... .. х _n - Набір простих висловлювань, що входять хоча б в одну з формул. Формули X і Y будемо називати рівносильними, якщо при всіх значеннях істинності х ₁ ... .. х _n значення істинності збігаються. равносильность позначається ., Але знак = помилкою не буде.

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

Перелічимо основні равносильности:

1. Подвійне заперечення ;

2. Комутативність

3. Дистрибутивність

4. Асоціативність

11. Ідемпотентность

12. Властивості констант

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

14. Закон суперечності \

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

4.3 Доказ равносильность

Доказ равносильность можна здійснити двома способами:

• за допомогою таблиці істинності;

• за допомогою міркувань.

Приклад (Завдання № 6): доведемо равносильность

а) за допомогою таблиці.

Таб. 6

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

б) за допомогою міркувань.

1. припустимо істинність лівій частині

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

3. оцінку списку підставимо в праву частину равносильности

4. встановимо істинність для правої частини

5. всі повторимо справа наліво.

I.

х = І чи І

якщо х = І І, І,

якщо і z = І

II.

і

х = І чи y = И и х = І чи z = І

якщо х = І І

якщо y = И и z = І = І

(І - «істина», тобто присвоюється справжнє значення)

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

Правила переходу від одних равносильность до інших

Нехай , А С - довільна формула

1. 

2. 

3. 

4. 

5. 

6. З А С В

Правила рівносильних перетворень

Нехай , А С - довільна формула. Нехай х - формула, яка входить до С. тоді Са - формула, яка виходить заміною у формулі З формули х на А.С b - виходить з Із заміною x на b, тоді Са = С b.

До цього моменту було визначено поняття равносильности формул алгебри висловлень.

Поняття равносильности функцій алгебри логіки визначається аналогічно.

Нехай f і g - функції алгебри логіки, x _{1, ...,} x _n - Сукупність аргументів, що входять хоча б в одну з цих функцій, кажуть, що f і g - рівносильні, якщо при всіх значеннях x _{1, ...,} x _n значення f і g - збігаються.

Тавтології

Дана формула А х ₁ х ₂ х _3.

Формула А називається тотожно істинною, якщо на будь-якому списку змінних вона приймає значення «Істина».

Тавтологія - це твердження, яке завжди істинно, інакше її визначають як закон.

Формула називається тотожно хибною, якщо на будь-якому списку змінних вона приймає значення «Брехня».

Протиріччя - це твердження, яке завжди помилково. Таблиця істинності для суперечності завжди приймає значення «Брехня».

Наприклад

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

Формула А називається опровержімий, якщо перебуває такий набір змінних, що вона приймає значення «Брехня».

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

Основні тавтології

Доказ тверджень

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

5. Булева функція

5.1 Повнота системи булевих функцій

Булевой називається довільна n-місцева функція , Де .

Ці функції нам зустрічалися в темі «Математична логіка» при складанні 16-ти функцій для двох змінних.

Повна система булевих функцій позначається Е має наступний вигляд:

f ₁ (x _1, x _2, ... x _k1)

f ₂ (x _1, x _2, ... x _k2)

... ... ... ... ....

F _e (x _1, x _2, ... x _ke)

Система функцій (Е), називається повною, якщо будь-яка її булева функція може бути виражена за допомогою f _1, f _2, ... f _e через суперпозицію.

Суперпозиція - це функція f ^*, яка отримана з функції f за допомогою наступних перетворень:

• заміна змінної. f (x _1, x _2, x _j, ..., x _n) f ^* = f (x _1, x _2, x _{j -1,} y, x _{j +1,} ..., x _n)

• підстановка замість х _j деякої функції з системи (1).

f ^* = f _i (x _1, x _2, x _{j -1,} f _e (x _1, x _2, ... x _ke) x _{j +1,} ..., x _ki).

Приклад: система функцій (Е ₁₎ завжди повна, т. к. кожна функція цієї системи може бути представлена ​​у вигляді СДНФ, отже СДНФ є суперпозицією, через яку може бути виражена будь-яка з функцій системи;

Система функцій (Е ₂₎ також є повною, оскільки відсутня функція ( ) Може бути виражена через інші дві за правилом де Моргана і подвійного заперечення: .

Завдання № 7

Довести повноту системи:

.

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

отже дана система є повною.

6. Логіка предикатів

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

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

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

Предикатом Р (х ₁ ... х _n), називається функція P: M ⁿ B, де М-прізвольное безліч, а В - двійкове безліч .

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

М називається предметною областю предиката, а елементи цієї множини (х ₁ ... х _n) М, називаються предметними змінними.

Якщо предикат залежить від n аргументів, то це буде n-місний предикат.

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

Розглянемо приклади предикатів:

1. Р ^{0: 2} 2 +3 ² 5 ² - вислів

Р ^1: х ² +3 ² 5 ² - одномісний предикат

Р ^2: х ² + y ² 5 ² - двомісний предикат

Іноді використовують більш простий запис: x> y - це двомісний предикат, предметною областю якого можуть служити будь-яку безліч дійсних чисел. Висловлення 6> ​​6 - істинно, а 7> 7 - помилково. Різні підстановки чисел замість однієї предметної змінної дають різні n - місцеві предикати: x> 5, x> 0, 7> y і т. д.

2. «Пряма Р проходить через точки А і В» - тримісний предикат, у якого предметними областями двох змінних (А і В) є множини точок, а предметною областю третин змінної Р є безліч прямих.

6.1 Операції над предикатами

Над предикатами можна робити ті ж операції, що і над висловлюваннями: .

Приклади:

Р ¹ (х): х ділиться на 2

Q ¹ (х): х ділиться на 3

Р ¹ (х) Q ¹ (х):

Р ¹ (х) Q ¹ (х):

Р ¹ (х) Q ¹ (х): або на 2 і на 3 або ні на 2 і ні на 3

Р ¹ (х) Q ¹ (х): : Не ділитися на 2 або ділитися на 3

Р ¹ (х): х не ділиться на 2.

6.2 Квантори

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

Нехай Р (х) - предикат, визначений на М, т. е. . Тоді під висловом «для всіх х з М Р (х) істинно» ми розуміємо висловлювання, яке є істинним, якщо Р (х) істинно для будь-якого х. Висловлення записане в лапках позначається , Безліч М не входить в позначення, але має бути зрозуміло з контексту. Знак , Називається квантором спільності.

А під висловом «існує такий х їх М, що Р (х) істинно» ми розуміємо висловлювання, яке є істинним, якщо знайдеться хоча б один х такий, що Р (х) є істинним. Висловлювання в лапках позначається . Знак , Називається квантором існування.

Перехід від Р (х) до або до називається зв'язуванням змінної х (або квантифікації). Змінна, на яку навішали квантор, називається зв'язаною, незв'язана мінлива називається вільною.

Квантор спільності відповідає зв'язування словами «для всіх», квантор існування - словом «існує».

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

Приклад кванторів:

Нехай Р (х) - предикат, х - парне число, тоді вислів - Істинно на будь-якому безлічі парних чисел і помилково на безлічі, що містить хоча б одне непарне число. Висловлення - Істинно на будь-якому безлічі, що містить хоча б одне парне число і помилково на будь-якому безлічі непарних чисел.

6.3 Формули

Алфавіт числення предикатів містить такі символи:

• х _1, х _2, ... х _n - предметні змінні;

• P ^t _1, P ^t _{2, ...,} P ^t _n - предикати, де t - кількість місць;

• - Операції;

• - Квантори;

• () - Дужки.

Послідовність перерахованих символів називається формулою.

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

1. Якщо в області М для формули F існує така підстановка констант замість усіх змінних, що F стає істинним висловлюванням, то формула f називається здійсненною в області М. Якщо існує область М, де f здійсненна, то f називається просто здійсненним.

Приклад: .

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

Приклад: формула тотожно істинна для всіх М, що складаються з одного елемента, а формула тотожно істинна.

Дві (або більше) формули називаються еквівалентними, якщо при будь-яких підстановках констант вони приймають однакові значення. Зокрема всі тотожно істинні (тотожно хибні) формули еквівалентні. Відзначимо, що якщо F ₁ і F ₂ еквівалентні, то формула F 1 F _2, - тотожно істинна.

Приклад (Завдання № 8):

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

Будь-яке натуральне число, що ділиться на 12 ділитися на 2, 4, 6.

Рішення:

Введемо на натуральному ряді предикати:

А (х) - ділитися на 12 (тобто А (х) = 1 тоді і тільки тоді, коли х ділитися на 12),

В (х) - ділитися на 2 (тобто В (х) = 1 тоді і тільки тоді, коли х ділитися на 2),

С (х) - ділитися на 4 (тобто С (х) = 1 тоді і тільки тоді, коли х ділитися на 4),

D (х) - ділитися на 6 (тобто D (х) = 1 тоді і тільки тоді, коли х ділитися на 6).

.

7. ТЕОРІЯ графів

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

Записується граф наступним чином: G (V, E).

Елементи безлічі V називаються вершинами графа G. Елементи безлічі Е - ребрами графа G. Вершини і ребра графа G називають його елементами і часто записують і .

7.1 Поняття суміжності

Нехай v _1, v ₂ - вершини, е ₁ - з'єднує їх ребро. Тоді вершина v ₁ і ребро е ₁ - інцидентні, вершина v ₂ і ребро е ₁ також інцидентні. Два ребра інцідентние одній вершині (е _1, е ₂ інцидентні v ₂₎ називаються суміжними. А також дві вершини інцідентние одному ребру (v _1, v ₂ інцидентні е ₁ називаються суміжними.

Приклад: зазвичай граф зображують діаграмою: вершини - крапками (або кружками), ребра - лініями. Зобразимо граф, який має 4 вершини та 5 ребер.

Приклад: Завдання: виписати всі суміжні і несуміжні вершини і ребра.

Рішення:

Таб. 7

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

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

Вершини в орієнтованому графі називаються вузлами.

Розглянемо деякі види графів:

• Якщо ребро з'єднує вершину саму з собою, то такий елемент графа називається петлею, а містить його граф називається графом з петлею (або псевдографом):

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

• Безліч ребер Е може бути порожнім:

• Лінії, що зображують ребра графа можуть перетинатися, але точки перетину не є вершинами:

• Граф може бути нескінченним:

Кожному неориентированном графу можна поставити у відповідність орграф з тим же безліччю вершин замінивши лише ребра неорієнтованого графа на спрямовані дуги орграфа. Таке відповідність називається канонічним.

7.2 Матриця інцидентності і списки ребер

Поставити граф - значить описати безлічі його вершин і ребер, а також ставлення інцидентності. Коли граф кінцевий для опису його вершин і ребер достатньо їх занумерувати. Відношення інцидентності визначають матрицею _ij, що має m рядків і n стовпців. Стовпці відповідають вершинам графа, рядки - ребрах графа. Якщо ребро е _i інцидентне вершині v _j, то _ij = 1, в іншому випадку _ij = 0. Це матриця інцидентності для неорієнтованого графа.

Приклад (Завдання № 9)

Позначимо вершини римськими цифрами, а ребра - арабськими. Матриця інцидентності для даного графа виглядає наступним чином:

У матриці інцидентності орграфа _ij = -1, Якщо вершина v _j - початок дуги a _{i; ij} = 1, якщо v _j - кінець дуги a _i; якщо a _i - Петля, а v _j - інцидентна їй вершина, то _ij = А, де а - будь-яке число відмінне від 0, 1, -1. В інших випадках _ij = 0.

Приклад (Завдання № 10): побудуємо орієнтований граф і матрицю інцидентності для неї:

З матриці інцидентності ми бачимо, що в кожному рядку є тільки два елементи (або один, якщо ребро є петлею) відмінних від 0. Тому такий спосіб завдання графа порахували неекономічним. Відношення інцидентності можна задати так само за допомогою списків ребер графа. Кожен рядок цього списку відповідає ребру, в ній записують номери вершин, інцидентних йому. Для неорієнтованого графа порядок вершин в рядку довільний, а для орграфа першому записують номер вершини початку дуги, а другим - номер вершини кінця дуги.

Складемо списки ребер для даних графів:

Таб. 8 списків ребер неорієнтованого графа

Таб. 9 Списки ребер орграфа

Кожен рядок списку ребер відповідає рядку матриці з тим же номером ребра.

7.3 Матриця суміжності графа

Матриця суміжності - це квадратна матриця _ij, рядкам і стовпцям якої відповідають вершини графа. Для неорієнтованого графа _ij рівно кількості ребер, інцидентних i-ої та j-ої вершин. Для орграфа _ij рівно кількості ребер з початком в i-ої вершини і кінцем j-ої вершини. Таким чином матриця суміжності неорієнтованого графа симетрична, а орграфа - необов'язково.

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

Матриця суміжності неорієнтованого графа

Матриця суміжності орграфа.

7.4 Операції над членами графів

1. Доповнення Н частини Н визначається безліччю всіх ребер графа G, не належать Н.

2. Об'єднання Н ₁ Н ₂ визначається:

;

.

3. Перетин Н ₁ Н ₂ частин Н ₁ і Н ₂ графа G визначається:

;

.

8 Основні ВИМОГИ ДО ВИКОНАННЯ КОНТРОЛЬНОЇ РОБОТИ

Контрольна робота в обов'язковому порядку повинна містити титульний лист (див. додаток I), умову задачі і докладний опис її рішення. Опис рішення повинно містити: використовувані при вирішенні формули і властивості; їх назва (якщо таке є); методи або способи вирішення завдання; результати обчислень; висновки.

9. ЕКЗАМЕНАЦІЙНІ ПИТАННЯ

1. Множини і підмножини. Основні поняття. Графічне представлення множин та операцій над ними.

2. Множини і підмножини. Основні поняття. Властивості операцій над множинами. Тотожності. Порядок докази тотожностей.

3. Відношення на множинах. Декартовій твір.

4. Відносини на множинах. Одномісні, бінарні, n - місцеві відносини.

5. Відносини на множинах. Властивості відносин.

6. Функція як відношення на множинах. Відношення порядку. Відношення еквівалентності.

7. Математичне моделювання. Поняття моделі. Етапи приведення до моделі. Способи моделювання.

8. Алгебраїчні моделі. Загальні поняття. Алгебраїчні моделі з однією визначальною операцією.

9. Алгебраїчні моделі. Загальні поняття. Алгебраїчні моделі з двома визначальними операціями.

10. Алгебраїчні моделі. Загальні поняття. Алгебраїчні моделі, що містять більше одного класу математичних об'єктів.

11. Теорія кодування. Загальні поняття. Показати побудова тризначного двійкового коду на прикладі куба. Описати всі можливі ситуації.

12. Теорія кодування. Загальні поняття. Кодові відстані. Методи виявлення помилок.

13. Теорія кодування. Загальні поняття. Групові коди.

14. Лінійна алгебра. Загальні поняття. Лінійні підпростору.

1. Реляційна алгебра. Поняття домену, кортежу. Операції вибору, проекції, об'єднання.

2. Математична логіка. Загальні поняття алгебри логіки. Функції алгебри логіки і їх таблиці істинності.

3. Булева алгебра. Загальні поняття. Властивості операцій і елементів булевої алгебри.

4. Булева алгебра. Диз'юнктивні нормальні форми. Досконалі диз'юнктивні нормальні форми.

5. Булева алгебра. Алгоритм перетворення формули в досконалу діз'юнктівную нормальну форму.

6. Булева алгебра. Кон'юнктивні нормальні форми. Досконалі кон'юнктивні нормальні форми.

7. Обчислення висловлювань. Загальні поняття. Поняття равносильной формули.

8. Обчислення висловлювань. Равносильности. Способи докази равносильности.

9. Обчислення висловлювань. Правила рівносильних перетворень. Тавтології. Основні поняття.

10. Обчислення висловлювань. Тавтології. Методи доказу тотожною істинності. висловлювань.

25. Аксіоматична система в обчисленні. Основні поняття. Виведені формули. Правила виводу.

26. Булеві функції. Повнота системи булевих функцій. Теорема Поста.

27. Булеві функції. Замкнені класи. Контактні схеми.

28. Логіка предикатів. Основні поняття. Операції над предикатами.

29. Логіка предикатів. Основні поняття. Квантори. Обчислення предикатів.

30. Формальні граматики. Класифікація граматик. Породжують граматики.

31. Мови. Властивості мов. Операції над мовами. Аналіз граматик і мов.

32. Теорія алгоритмів. Поняття алгоритмічної можливості розв'язання. Рекурсивні функції.

33. Теорія кінцевих автоматів. Машини Тьюрінга. Форми подання алгоритмів.

34. Теорія графів. Основні поняття.

35. Елементи комбінаторики. Основні поняття.

ЛІТЕРАТУРА

1. Кузнкцов О.П., Адельсон - Бєльський Г.М. Дискретна математика для інженера - 2-е іеданіе перероблене і доплнения М.: Вища школа 1988р .- 480с.

2. Горбатов В.А. Основи дискретної математики: навчальний посібник для студентів вузів - М.: Вища школа, 1986р-311с.

3. Нікольська І Л. Математична логіка: Підручник М.: Вища школа 1981р.-127с.

4. Єршов Ю.А., Палютін Е.А. Математична логіка: навчальний посібник для вузів 2-е видання виправлене і доповнене-М.: Наука 1987р .- 336с.

5. Кліні С.К. Математична логіка М.: Мир 1973р.

6. Новиков П.С. Елементи математичної логіки. М.: Наука 1973р.

7. Оре О. Теорія графів М.: Наука 1968р.

8. Зиков А.А. Теорія кінцевих графів. Новосибірськ: Наука 10969г.

9. Гаврилов Г.П., Сапоженко А.А. Збірник завдань з дискретної математики М.: Наука 1977р .- 368с.

10. Гіндікін С.П. Алгебра логіки в задачах М.: Наука 1972р.

11. Лавров І.А., Максимова Л.Л. Завдання з теорії множин, математичної логіки, теорії автоматів М.: Наука 1975р.

ДОДАТОК I

Оформлення титульного аркуша