Нормальні форми логіки висловлювань

ЗАСТОСУВАННЯ ЛОГІКИ ВИСЛОВЛЮВАНЬ В ПРОГРАМНІЙ ІНЖЕНЕРІЇ

МЕТОДИЧНІ ВКАЗІВКИ

до практичних занять

з дисципліни „Комп’ютерна дискретна математика”

для студентів базового напряму

„Програмна інженерія”

Львів – 2013

Застосування логіки висловлювань в програмній інженерії.: Методичні вказівки до практичних занять з дисципліни „Комп’ютерна дискретна математика” для студентів базового напряму „Програмна інженерія” / Укл.: П. В. Сердюк, О.О. Нитребич. – Львів: Видавництво Національного університету „Львівська політехніка”, 2013. – 28 с.

Укладачі

Сердюк. П. В., к. т. н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Нитребич О. О., асист. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Відповідальний за випуск

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

Рецензенти

Гавриш В. І., к.ф.-м.н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”

Огородник Н. П., к.ф.-м.н., асис. кафедри теорії оптимальних процесів Львівського національного університету ім. І. Франка

Зміст

1. Вступ. 4

2. Нормальні форми логіки висловлювань. 4

3. Карти Карно. 11

4. Коди стійкі до перешкод. 15

5. Логічні побітові операції 18

6. Завдання до виконання. 22

7. Контрольні запитання. 27

ЛОГІКА

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

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

Вступ

Класична логіка висловлювань є основою сучасної символічної логіки, на базі якої створюються нові формально-логічні системи (логічні числення). Ідею логічного числення вперше сформулював німецький філософ, логік, математик Г. Ляйбніц. Історично першу систему логіки висловлювань, або алгебру логіки, створив англійський логік Дж. Буль, в якій використовували алгебраїчні методи для вирішення певних логічних задач. Подальший розвиток логіки висловлювань здійснювали логіки та математики - О. де Морган, Б. Шредер, Г. Фреге, Б. Рассел й ін.

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

Нормальні форми логіки висловлювань

Означення 2.1. Літерал – атомарна формула або її заперечення.

Приклад 2.1. – літерали. ▲

Означення 2.2. Елементарною диз’юнкцією називається диз’юнкція, що містить будь-яку кількість літералів, де кожна атомарна формула зустрічається лише один раз.

Приклад 2.2 – елементарні диз’юнкції однієї змінної;

– елементарні диз’юнкції двох змінних;

– елементарні диз’юнкції трьох змінних;

– не є елементарними диз’юнкціями. ▲

Означення 2.3. Простими імплікантами називаються елементарні диз’юнкції, що самі входять у задану функцію f, але ніяка їхня частина у функцію f не входить.

Приклад 2.3 Для функції f (p, q, r) = простими імплікантами будуть кон’юнкції та , а та не є ними, оскільки їхня частина уже входить у задану функцію. ▲

Означення 2.4. Формула f записана у кон’юнктивній нормальній формі (КНФ), якщо вона має вигляд () та всі () різні. У кон’юнктивній нормальній формі кожна з формул є елементарними диз’юнкціями.

Приклад 2.4. – приклад кон’юктивної нормальної форми, де – атомарні формули. , , – диз’юнкції відповідних літералів. ▲

Означення 2.5. k-кон’юнктивна нормальна форма – це кон’юнктивна нормальна форма, в якій кожна диз’юнкція містить рівно k літералів.

Приклад 2.5. Наступна формула записана в 2-КНФ:

.▲

Для того, щоб перевести формулу у кон’юнктивну нормальну форму необхідно виконати наступні перетворення:

1. Використати правила усунення імплікації та еквівалентності.

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

3. Використати закони дистрибутивності для диз’юнкції відносно кон’юнкції (p Ù(q Ú r) =(p Ù q) Ú (p Ù r)) для побудови кон’юнктивної нормальної форми.

Приклад 2.6. Звести до кон’юнктивної нормальної форми формулу .

1. Вилучення імплікації:

2. Застосування закону подвійного заперечення:

3. Використання закону дистрибутивності:

Отже, отримана є КНФ формули . ▲

Поиск по сайту: