МІНІСТЕРСТВО ОСВІТИ І НАУКИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Застосування логіки висловлювань в програмній інженерії методичні вказівки
до практичних занять
з дисципліни „Комп’ютерна дискретна математика”
для студентів базового напряму
„Програмна інженерія”
|
|
Затверджено на засіданні кафедри програмного забезпечення Протокол № 14 від 18.04.2013 р. |
Львів – 2013
Застосування логіки висловлювань в програмній інженерії.:Методичні вказівки до практичних занять з дисципліни „Комп’ютерна дискретна математика” для студентів базового напряму „Програмна інженерія” / Укл.: П. В. Сердюк, О.О. Нитребич. – Львів: Видавництво Національного університету „Львівська політехніка”, 2013. – 28 с.
Укладачі
Сердюк. П. В., к. т. н., доц. кафедри програмного забезпеченння національного університету“Львівська політехніка”
Нитребич О. О., асист. кафедри програмного забезпеченння національного університету“Львівська політехніка”
Відповідальний за випуск
Федасюк Д. В., д-р тех. наук, проф., завідувач кафедрою програмного забезпечення, проректор з науково-педагогічної роботи національного університету “Львівська політехніка”
Рецензенти
Гавриш В. І., к.ф.-м.н., доц. кафедри програмного забезпеченння національного університету “Львівська політехніка”
Огородник Н. П., к.ф.-м.н., асис. кафедри теорії оптимальних процесів Львівського національного університету ім. І. Франка
Зміст
Зміст 3
1.Вступ 4
2.Нормальні форми логіки висловлювань 4
3.Карти Карно 11
4.Коди стійкі до перешкод 14
5.Логічні побітові операції 17
6.Завдання до виконання 21
7.Контрольні запитання. 26
ЛОГІКА
Мета роботи:Ознайомлення на практиці із застосуванням логіки висловлювань у програмній інженерії, навчитись будувати досконалі кон’юктивну та доз’юктивну форми, мінімізувати їх за допомогою карт Карно, а також навчитись працювати з кодами, стійкими до перешкод.
Теоретичні відомості.
Вступ
Класична логіка висловлювань є основою сучасної символічної логіки, на базі якої створюються нові формально-логічні системи (логічні числення). Ідею логічного числення вперше сформулював німецький філософ, логік, математик Г. Ляйбніц. Історично першу систему логіки висловлювань, або алгебру логіки, створив англійський логік Дж. Буль, в якій використовували алгебраїчні методи для вирішення певних логічних задач. Подальший розвиток логіки висловлювань здійснювали логіки та математики - О. де Морган, Б. Шредер, Г. Фреге, Б. Рассел й ін.
Багато сучасних досліджень у галузі логіки виникає з потреб розвитку програмування, зокрема, аплікативні обчислювальні системи, теорія обчислень і моделі обчислень, семантичні мережі, булева логіка і алгебра для розробки апаратного забезпечення комп'ютерів, штучний інтелект; експертні системи і т.д.
Нормальні форми логіки висловлювань
Означення 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-КНФ:
.▲
Для того, щоб перевести формулу у кон’юнктивну нормальну форму необхідно виконати наступні перетворення:
Використати правила усунення імплікації та еквівалентності.
Застосувати закон подвійного заперечення та закони де Моргана, щоб перенести знак заперечення безпосередньо до атомарних формул.
Використати закони дистрибутивності для диз’юнкції відносно кон’юнкції (p(qr)=(pq)(pr)) для побудови кон’юнктивної нормальної форми.
Приклад
2.6. Звести
до кон’юнктивної нормальної форми
формулу
.
Вилучення імплікації:
Застосування закону подвійного заперечення:
Використання закону дистрибутивності:
Отже,
отримана
є КНФ формули
.▲
Досконала кон’юнктивна нормальна форма
Нехай складне висловлювання задане таблицею істинності. Виберемо інтерпретації, у яких значення висловлювання є «хиба» (F). Для кожної такої інтерпретації побудуємо диз’юнкцію атомарних формул або їх заперечень: якщо значення атома – F, то він входить у кон’юнкцію без заперечення, в іншому випадку – з. Побудовану КНФ називають досконалою кон’юнктивною нормальною формою (ДКНФ).
Приклад
2.7. Нехай
формула
задана таблицею істинності (таблиця
2.1). Побудувати ДКНФ.
Таблиця 2.1
Таблиця
істинності для
|
p |
q |
r |
|
|
T |
T |
T |
F |
|
T |
T |
F |
T |
|
T |
F |
T |
T |
|
T |
F |
F |
T |
|
F |
T |
T |
F |
|
F |
T |
F |
T |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
Позначимо
всеможливі елментарні диз’юнкції трьох
змінних: g1=
,g2=
,g3=
,g4=
,g5=
,g6=
,g7=
,g8=
та побудуємо таблицю істинності для
всіхgi.
Таблиця 2.2
Таблиця істинності для елементарних диз’юнкцій
|
p |
q |
R |
g1 |
g2 |
g3 |
g4 |
g5 |
g6 |
g7 |
g8 |
|
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
F |
|
T |
T |
F |
T |
T |
T |
T |
F |
T |
T |
T |
|
T |
F |
T |
T |
T |
T |
T |
T |
F |
T |
T |
|
T |
F |
F |
T |
F |
T |
T |
T |
T |
T |
T |
|
F |
T |
T |
T |
T |
T |
T |
T |
T |
F |
T |
|
F |
T |
F |
T |
T |
F |
T |
T |
T |
T |
T |
|
F |
F |
T |
T |
T |
T |
F |
T |
T |
T |
T |
|
F |
F |
F |
F |
T |
T |
T |
T |
T |
T |
T |
Для отримання ДКНФ вибираємо інтерпретації, у яких f1 рівна FALSE (1, 5, 8 рядок).
Розглянемо
першу з вибраних трьох інтерпретацій.
Для заданої інтерпретації значення
атомарних формул
.
З таблиці 2.2 видно, що елементарною
диз’юнкцією, значення якої FALSE при
відповідних значеннях атомарних формул,
є g8=
– тобто значення атомарних формул
входять у диз’юнкцію із запереченням.
Аналогічно елементарною диз’юнкцією
для другої вибраної інтерпретації будеg7=
,
а для третьої –g1=
.
Отже,
формула
є ДКНФ для
.▲
Приклад 2.8. Побудувати висловлювання з елементів p, q , r, яке набуває значення F тільки у трьох випадках, коли r – істинне, а p і q – фальшиві, коли r і p – істинне, а q – фальшиве, p, r і q – фальшиві.
Таблиця 2.3
Таблиця істинності для f
|
p |
q |
r |
F |
|
F |
F |
F |
F |
|
F |
F |
T |
F |
|
F |
T |
F |
T |
|
F |
T |
T |
T |
|
T |
F |
F |
T |
|
T |
F |
T |
F |
|
T |
T |
F |
T |
|
T |
T |
T |
T |
Використаємо досконалу кон'юнктивну нормальну форму.
Для отримання ДКНФ вибираємо інтерпретації, у яких f1 рівна FALSE (1, 2, 6 рядок).
Розглянемо
першу з вибраних трьох інтерпретацій.
Для заданої інтерпретації значення
атомарних формул
,
отже, у відповідну елементрану диз’юнкцію
вони входять без заперечень, отже,
отримаємо
.
Аналогічно елементарною диз’юнкцією
для другої вибраної інтерпретації буде
,
а для третьої –
.
Отже,
наша формула f
=
.▲
Диз’юнктивна нормальна форма
Означення 2.6. Елементарною кон’юнкцією називається кон’юнкція, що містить будь-яку кількість літералів, де кожна атомарна формула зустрічається лише один раз.
Приклад
2.9 
– елементарні кон’юнкції однієї
змінної;
– елементарні кон’юнкції двох змінних;
– елементарні кон’юнкції трьох змінних;
–
не є елементарними кон’юнкціями.
Означення
2.7.
Формула f
записана у
диз’юнктивній нормальній формі (ДНФ),
якщо вона має вигляд 
(
)
та всі 
(
)різні.
У диз’юнктивній нормальній формі кожна
з формул 
єелементарними
кон’юнкціями.
Приклад
2.10.
–
приклад диз’юнктивної нормальної
форми, де
–
атомарні формули.
,
,
–
кон’юнкції відповідних літералів.
Означення 2.8. k-диз’юнктивна нормальна форма – це диз’юнктивна нормальна форма, в якій кожна кон’юнкція містить рівно k літералів.
Приклад 2.11. Наступна формула записана в 2-ДНФ:
.▲
Для того, щоб перевести формулу у диз’юнктивну нормальну форму необхідно виконати наступні перетворення:
Використати правила усунення імплікації та еквівалентності.
Застосувати закон подвійного заперечення та закони де Моргана, щоб перенести знак заперечення безпосередньо до атомарних формул.
Використати закони дистрибутивності для кон’юнкції відносно диз’юнкції (p(qr)=(pq)(pr)) для побудови диз’юнктивної нормальної форми.
Приклад
2.12. Звести
до диз’юнктивної нормальної форми
формулу
.
Вилучення імплікації:
Застосування закону де Моргана:
Використання закону подвійного заперечення:
Використання закону дистрибутивності:
Застосування закону асоціативності:
Використання закону ідемпотентності:
Отже,
отримана
є ДНФ формули
.▲
Досконала диз’юнктивна нормальна форма
Нехай складне висловлювання задане таблицею істинності. Виберемо інтерпретації, у яких значення висловлювання є «істина» (Т). Для кожної такої інтерпретації побудуємо кон’юнкцію атомарних формул або їх заперечень: якщо значення атома – F, то він входить у кон’юнкцію із запереченням, в іншому випадку – без. Побудовану ДНФ називають досконалою диз’юнктивною нормальною формою (ДДНФ).
Приклад
2.13. Нехай
формула
задана таблицею істинності (табл. 2.3).
Побудувати ДДНФ.
Таблиця 2.4
Таблиця
істинності для
|
P |
q |
r |
|
|
T |
T |
T |
F |
|
T |
T |
F |
F |
|
T |
F |
T |
T |
|
T |
F |
F |
F |
|
F |
T |
T |
F |
|
F |
T |
F |
T |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
Позначимо
всеможливі елментарні кон’юнкції трьох
змінних: g1=
,g2=
,g3=
,g4=
,g5=
,g6=
,g7=
,g8=
та побудуємо таблицю істинності для
всіхgi.
Таблиця 2.5
Таблиця істинності для елементарних кон’юнкцій
|
p |
q |
r |
g1 |
g2 |
g3 |
g4 |
g5 |
g6 |
g7 |
g8 |
|
T |
T |
T |
T |
F |
F |
F |
F |
F |
F |
F |
|
T |
T |
F |
F |
F |
F |
T |
F |
F |
F |
F |
|
T |
F |
T |
F |
F |
T |
F |
F |
F |
F |
F |
|
T |
F |
F |
F |
F |
F |
F |
F |
F |
T |
F |
|
F |
T |
T |
F |
T |
F |
F |
F |
F |
F |
F |
|
F |
T |
F |
F |
F |
F |
F |
F |
T |
F |
F |
|
F |
F |
T |
F |
F |
F |
F |
T |
F |
F |
F |
|
F |
F |
F |
F |
F |
F |
F |
F |
F |
F |
T |
Для отримання ДДНФ вибираємо інтерпретації, у яких f1 рівна TRUE (3, 6, 7 рядок).
Розглянемо
першу з вибраних трьох інтерпретацій.
Для заданої інтерпретації значення
атомарних формул
.
З таблиці 2.5 видно, що елементарною
кон’юнкцією, значення якої TRUE
при відповідних значеннях атомарних
формул, є g3=
– тобто значення атомарних формул
входять укон’юнкцію
без заперечення, а значення атомарної
формули
входить у кон’юнкцію із запереченням.
Аналогічно елементарною кон’юнкцією
для другої вибраної інтерпретації будеg6=
,
а для третьої –g5=
.
Отже,
формула
є ДДНФ для
.▲
Приклад 2.14. Побудувати висловлювання з елементівp,q,r, яке набуває значенняTтільки тоді, колиp– істинне, аrіq– фальшиві, або у випадку колиp- фальш, аq,r– істинні.
Таблиця 2.6
Таблиця істинності для f
|
p |
q |
r |
f |
|
F |
F |
F |
F |
|
F |
F |
T |
F |
|
F |
T |
F |
F |
|
F |
T |
T |
T |
|
T |
F |
F |
T |
|
T |
F |
T |
F |
|
T |
T |
F |
F |
|
T |
T |
T |
F |
Використаємо досконалу диз'юнктивну нормальну форму.
Для отримання ДДНФ вибираємо інтерпретації, у яких f1 рівна TRUE (4,5 рядок).
Розглянемо
першу з вибраних двох
інтерпретацій. Для заданої інтерпретації
значення атомарних формул
,
отже, у відповідну елементрану кон’юнкцію
вони входять без заперечень, а атомарна
формула
входить в відповідну елементарну
кон’юнкцію із запереченням, тому
отримаємо
.
Аналогічно елементарною кон’юнкцією
для другої вибраної інтерпретації буде
.
Отже,
формула
є ДДНФ для
.▲
!Увага Під час вибору досконалої форми запису логічної функції варто пам’ятати, що ДКНФ є більш доцільною, якщо число наборів, де функція дорівнює TRUE, перевищує число наборів, де функція дорівнює FALSE. У протилежному варто розглядати ДДНФ.