Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика icon

Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика


Скачать 79.66 Kb.
НазваниеМетодичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика
Размер79.66 Kb.
ТипМетодичні вказівки


МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

"КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"


Методичні вказівки

до виконання домашньої контрольної роботи

з кредитного модуля

«Математична логіка та теорія алгоритмів»


для студентів спеціальності 6.040301 Прикладна математика


Рекомендовано Вченою радою Фізико-технічного інституту


Київ

НТУУ «КПІ»

2013

Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» / Уклад. М.К.Мороховець. – К.: НТУУ «КПІ», 2013. – 30 с., 4 джерела.


^ Гриф надано Вченою радою Фізико-технічного інституту НТУУ «КПІ»

(Протокол № 3 від 27 березня 2013 р.)


Навчальне видання


Методичні вказівки

до виконання домашньої контрольної роботи

з кредитного модуля

«Математична логіка та теорія алгоритмів»


для студентів спеціальності 6.040301 Прикладна математика


Укладач Марина Костянтинівна Мороховець, канд.фіз.-мат.наук


Відповідальний редактор М.М. Савчук, д-р фіз.-мат. наук, проф.


Рецензент О.Є. Архипов, д-р техн. наук, проф.


ЗМІСТ

Мета та задачі домашньої контрольної роботи ……………………………...4

Короткі теоретичні відомості та приклади розв’язання задач………………4

Логічне слідування………………………………………………………4

Методи перевірки тотожної хибності й тотожної істинності................

формул логіки висловлень………………………………………….…..5

Метод перевірки суперечності й тавтологічності формул шляхом…...

зведення до диз’юнктивної та кон’юнктивної нормальної форми.......6

Метод Девіса й Патнема…………………………………………...........6

Метод резолюцій.......................................................................................8

Метод двійкових діаграм рішень.............................................................9

Приклади застосування методів перевірки тавтологічності та………..

суперечності формул логіки висловлень…..........................................11

Мова логіки першого порядку...............................................................11

Інтерпретації формул логіки першого порядку…...............................14

Пренексна нормальна форма формул логіки першого порядку........18

Перетворення формули у пренексну нормальну форму....................19

Сколемівська стандартна форма формули логіки першого порядку.....20

Підстановки та уніфікатори..................................................................22

Алгоритм уніфікації...............................................................................24

Правило резолюції для формул логіки першого порядку..................26

Вимоги до оформлення домашньої контрольної роботи.............................28

Графік виконання домашньої контрольної роботи.......................................28

Порядок виконання домашньої контрольної роботи....................................28

Оцінювання домашньої контрольної роботи.................................................29

Список рекомендованої літератури................................................................29

Додаток 1...........................................................................................................30

^ Мета та задачі домашньої контрольної роботи

З метою кращого засвоєння матеріалу курсу та набування навичок самостійної роботи студентам пропонується виконати домашню контрольну роботу (ДКР) за розділом «Математична логіка». Виконання завдань ДКР сприяє більш поглибленому вивченню студентами теоретичного матеріалу, формуванню вмінь використовувати знання для розв’язання практичних задач. При виконанні ДКР студент має продемонструвати володіння методами перевірки логічного слідування, також методами перевірки тотожної істинності (тотожної хибності) формул логіки висловлень та формул логіки першого порядку.

Домашня контрольна робота виконується студентом САМОСТІЙНО із забезпеченням необхідних консультацій з окремих питань з боку викладача.

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

^ Короткі теоретичні відомості та приклади розв’язання задач

Логічне слідування

Формула F називається логічним наслідком формул F1,…,Fn (позначається F1,…,Fn╞═F), якщо при кожній інтерпретації, при якій усі формули F1,…,Fn істинні, формула F також істинна. Говорять, що формули F1,…,Fn є посилками F, а формула F випливає з F1,…,Fn, або має місце логічне слідування формули F з формул F1,…, Fn.

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

Теорема 1. Нехай F1, F2, …, Fn, F – формули.

1) F1,F2…,Fn╞═ F тоді й тільки тоді, коли формула F1F2…FnF є тотожно істинною (тавтологією).

2) F1,F2,…,Fn╞═ F тоді й тільки тоді, коли формула F1F2…FnF тотожно хибна (суперечна).

Методи перевірки тотожної хибності й тотожної істинності формул логіки висловлень

Різноманітні задачі у математиці та у інших галузях можуть бути сформульовані як задачі встановлення того, чи випливає деяке твердження з заданої сукупності інших тверджень, тобто як задачі перевірки правильності міркування. Якщо твердження у міркуванні є висловленнями, то задачу перевірки правильності такого міркування можна звести до задачі перевірки логічного слідування формули логіки висловлень, що є перекладом твердження-висновку заданого міркування, з формул, що є перекладами висловлень-посилок цього міркування. Теорема 1, що сформульована вище, дає можливість замінити перевірку логічного слідування формули F з формул F1,…,Fn перевіркою тавтологічності (або суперечності) формули, побудованої з F1,…,Fn, F спеціальним чином. Для установлення тавтологічності (суперечності) деякої формули P логіки висловлень можна використати таблиці істинності й перевіряти істинносні значення формули P при кожній інтерпретації. Ми розглянемо інші методи перевірки тавтологічності та суперечності, які ґрунтуються на поданні формул у спеціальному вигляді, а саме у вигляді тієї чи іншої нормальної форми. Для подання формули у нормальній формі виконуються перетворення даної формули, які зберігають її істинносне значення при кожній інтерпретації.

^ Метод перевірки суперечності й тавтологічності формул шляхом зведення до диз’юнктивної та кон’юнктивної нормальної форми

Тавтологічність формули можна перевірити шляхом зведення її до кнф. Наприклад, (PQ)  Q  P = (PQ) Q  P = ((PQ) Q) P = (PQ)QP = (PQ)  Q P = (P Q P) (Q Q P) = 1 1 = 1. Отже, формула (PQ)  Q  P є тавтологією.

Суперечність формули можна довести шляхом перетворення її у днф. Наприклад, (PQ)QP = (PQ)QP = (PQP)(QQP) = 00 = 0. Отже, формула є суперечною.

Метод Девіса й Патнема

Метод Девіса й Патнема дає можливість перевіряти суперечність множини диз’юнктів. Він базується на чотирьох правилах.

1. ^ Правило тавтології. З множини диз’юнктів S вилучити усі тавтологічні диз’юнкти, якщо такі містяться у S. Позначимо множину диз’юнктів, що утворюється у результаті такого вилучення, через S. Якщо S=, то дати відповідь «S несуперечна» та завершити роботу, інакше перевірити суперечність S¢.

Зазначимо, що множина S суперечна тоді й тільки тоді, коли S¢ суперечна. Отже, однократне застосування правила тавтології до множини диз’юнктів S, що містить тавтологічні диз’юнкти, або дає відповідь на питання про суперечність S (якщо S=, то S – несуперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S¢, яка містить менше диз’юнктів, ніж S.

2. ^ Правило однолітерних диз’юнктів. Якщо в S існує одиничний диз’юнкт {L}, то спочатку побудувати множину S, вилучаючи з S ті диз’юнкти, що містять літеру L. Якщо S=, то дати відповідь «множина S несуперечна» й завершити роботу. Якщо S, то побудувати множину S, вилучаючи з диз’юнктів множини S усі входження літери L. Якщо S² містить порожній диз’юнкт, то дати відповідь «множина S суперечна» та завершити роботу, інакше перевірити суперечність S.

Зазначимо, що множина S суперечна тоді й тільки тоді, коли S суперечна. Таким чином, однократне застосування правила однолітерних диз’юнктів до множини диз’юнктів, що містить одиничний диз’юнкт, або дає відповідь на питання про суперечність S (якщо S=, то S – несуперечна, якщо S², то S суперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S², яка містить менше диз’юнктів, ніж S.

3. ^ Правило чистих літер. Назвемо літеру L, що входить у деякий диз’юнкт з S, чистою в S, якщо літера L не входить в жоден диз’юнкт з S. Якщо S містить літеру L, чисту в S, вилучити з S усі диз’юнкти, що містять L. Позначимо через S множину диз’юнктів, що залишилися. Якщо S=, то дати відповідь «S несуперечна» й завершити роботу, інакше перевірити суперечність S¢.

Зазначимо, що S суперечна тоді й тільки тоді, коли S¢ суперечна. Отже, однократне застосування правила чистих літер до множини диз’юнктів S, що містить чисту літеру, або дає відповідь на питання про суперечність S (якщо S=, то S несуперечна), або зводить задачу про суперечність S до задачі про суперечність множини диз’юнктів S¢, яка містить менше диз’юнктів, ніж S.

4. ^ Правило розщеплення. Вибрати літеру L, що має входження у який-небудь диз’юнкт з S. Подати множину S у вигляді (A1 L)…(AmL)(B1L)…(BnL)R, де m,nN+, Ai (i{1,…,m}), Bj (j  {1,…,n}), R не містять літер L та L. Побудувати множини S1 = A1…AmR та S2 = B1…BnR. Перевірити суперечність S1 та S2.

Зазначимо, що S суперечна тоді й тільки тоді, коли S1 й S2 суперечні. Застосування правила розщеплення дає можливість звести задачу про суперечність множини диз’юнктів S до сукупності двох задач (про суперечність S1 та про суперечність S2), кожна з яких простіша, ніж задача про суперечність S.

Метод Девіса й Патнема перевірки суперечності множини диз’юнктів S полягає у рекурсивному застосуванні до S правил 1-4 у зазначеному порядку.

^ Метод резолюцій

Правило резолюції. Нехай С1, С2 – диз’юнкти й С1=D1L, С2=D2L, де D1, D2 – диз’юнкції літер, можливо, порожні, L, L – контрарні літери. Будемо говорити, що диз’юнкт C=D1D2 утворюється за допомогою правила резолюції з диз’юнктів С1 та С2. Диз’юнкт С називається резольвентою диз’юнктів С1 та С2.

Теорема 2. Нехай С1, С2 – диз’юнкти, С – резольвента С1 та С2. Тоді С є логічним наслідком С1 та С2.

Будемо говорити, що порожній диз’юнкт c виводиться з множини диз’юнктів S (або існує вивід диз’юнкту c з множини диз’юнктів S) за допомогою правила резолюції, якщо існує така скінченна послідовність диз’юнктів С1,…,Сk, що Сk= c й кожен диз’юнкт Сi даної послідовності (1ik) є або диз’юнктом з множини S, або резольвентою таких диз’юнктів Cn, Cm даної послідовності, що n<і та m1,…,Сk, що задовольняє наведені умови, назвемо виводом порожнього диз’юнкту з множини диз’юнктів S за допомогою правила резолюції.

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

Теорема 3 (про повноту). Множина диз’юнктів S суперечна тоді й тільки тоді, коли існує вивід порожнього диз’юнкту  з S за допомогою правила резолюції.
^

Метод двійкових діаграм рішень


Нехай F, F0, F1 – формули. Розгалуженням називається вираз виду FF1,F0, який визначається так: FF1,F0=(FF1)(FF0). Формула F називається перевірним виразом,  – оператором розгалуження, F1,F0гілками розгалуження. Будемо називати розгалуження формулою.

З наведеного означення випливає, що логічні зв’язки , , , ,  можуть бути виражені через оператор розгалуження й логічні константи 0 та 1 таким чином, що: а) перевірні вирази є атомами, б) атоми зустрічаються лише у перевірних виразах. Дійсно, маємо: Р=(Р0,1); PQ=P(Q1,0),0; РQ=P(Q1,0),(Q0,1); PQ=P1,(Q1,0); PQ=P(Q1,0),1. Зазначимо також, що кожна формула F може бути записана у вигляді F1,0.

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

Позначимо F[0/P] (F[1/P]) формулу, що є результатом заміни у формулі F атома Р на 0 (1). Тоді формулу F, що містить атом Р, можна подати у вигляді

F=РF[1/P],F[0/P].

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

Двійковою діаграмою рішень (ДДР) називається ациклічний кореневий позначений орграф, у якому є одна чи дві кінцеві вершини (тобто вершини, напівстепені виходу яких дорівнюють нулю), що мають (різні) позначки 0 або 1, напівстепені виходу некінцевих вершин дорівнюють двом, на множині некінцевих вершин визначено функції var, low, high такі, що коли u – некінцева вершина, то її позначкою є var(u), а (u, low(u)) та (u, high(u)) – дуги, інцидентні вершині u. Областю значень функції var є деяка множина позначок, область значень функцій high, low – множина вершин ДДР.

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

(var(u)=var(v))(low(u)=low(v))(high(u)=high(v))u=v й low(u)high(u).

Визначимо рекурсивну процедуру побудови формули Fu, що визначається вершиною u деякої ПУДДР. Кінцева вершина визначає логічну константу, некінцева вершина u з позначкою Р визначає розгалуження, перевірним виразом якого є Р, а суміжні вершини визначають гілки розгалуження, тобто F0=0, F1=1, Fu=var(u)Fhigh(u),Flow(u).

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

Теорема 4. Для будь-якої формули F(A1,…,An) логіки висловлень існує єдина ПУДДР з лінійним упорядкуванням позначок A1…An, така що для кореневої вершини u Fu=F.

Н
Рис. 2
аведені результати забезпечують такий спосіб перевірки тавтологічності (суперечності) формули логіки висловлень. Побудуємо для даної формули F її нормальну форму розгалуження, вибравши певний лінійний порядок атомів (це можна зробити для будь-якої формули логіки висловлень). Потім за нфр побудуємо УДДР, при потребі здійснивши її приведення. Якщо результатом є діаграма, що складається з однієї кінцевої вершини, яка має позначку 1 (0), то формула F є тавтологією (суперечністю). Якщо побудована ПУДДР має некінцеві вершини, то формула F не є ні тавтологією, ні суперечністю, але має моделі.

^ Приклади застосування методів перевірки тавтологічності та суперечності формул логіки висловлень

Приклади застосування описаних методів для розв’язання задач докладно описано у електронному навчальному виданні [1], стор.37-63.

^ Мова логіки першого порядку

Будемо використовувати такі чотири типи символів:

1) символи індивідних констант: a, a1, a2,…, b, b1, b2,…, c, c1, c2,…, а також імена об’єктів (наприклад, Київ, 5, Марія і т.ін.);

2) символи предметних змінних: x, x1, x2,…, y, y1, y2,…z, z1, z2,…;

3) функціональні символи: f, f1, f2,…, g, g1, g2,…, h, h1, h2,…, а також звичайні слова, написані малими літерами (наприклад, плюс, факторіал), або спеціальні символи операцій (+, ); з кожним функціональним символом асоціюється ціле додатне число – арність функціонального символу; для позначення арності символів використовуються верхні індекси (наприклад, fn – n-арний функціональний символ);

4) предикатні символи: P, P1, P2,…, Q, Q1, Q2,…, R, R1, R2,… або звичайні слова, написані великими літерами (наприклад, МЕНШЕ, ПРАЦЮЄ), а також символи відношень (наприклад, , >, =).

Поняття терму визначається таким чином:

i) константа є термом;

ii) змінна є термом;

iii) якщо fn – n-арний функціональний символ й t1,…,tn – терми, то fn(t1,…,tn) – терм;

iv) інших термів немає.

Якщо P – n-арний предикатний символ й t1,…,tn – терми, то P(t1,…,tn) – атом, або елементарна формула.

Уведемо символи:  – квантор загальності,  – квантор існування. Якщо x – змінна, то (x) читається так: “для усіх x”, або “для будь-якого x”, або “для кожного x”, а (x) читається так: “існує x”, або “для деякого x”, або “хоча б для одного x”. Вирази (x), (x) називаються кванторними комплексами.

Запишемо, наприклад, за допомогою предикатів та кванторів такі твердження:

1) Кожне натуральне число є цілим числом.

2) Для кожного числа x існує таке число y, що yx.

Позначимо “x є натуральним числом” через N(x), “x є ціле число” через Z(x), “y більше x” через БІЛЬШЕ(y,x). Тоді наведені вище твердження можна записати такими формулами:

1) (x)(N(x) Z(x));

2) (x) (y) (БІЛЬШЕ(y,x)).

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

  • кожна елементарна формула є формулою;

  • якщо А – формула, то (А) – формула;

– якщо А, В – формули, x – змінна, то (А), (А)(В), (А)(В), (А)(В), (А)(В), (х)(А), (х)(А) – формули;

– інших формул немає.

У виразі (х)(А) ((х)(А)) формула А називається областю дії кванторного комплексу (х) (відповідно (х)), а змінна х з А – керованою квантором  (). Формули виду P(t1,…,tn), P(t1,…,tn), де P(t1,…,tn) – елементарна формула, будемо називати літерами.

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

Наприклад, обидва входження змінної х у формулу (x)(Р(х,z)  Q(w)) є зв’язаними, а входження змінних z та w є вільними.

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

Наприклад, у формулі (x)(Q(x,u,z)) змінна x зв’язана, оскільки обидва її входження зв’язані. Змінні u та z вільні, тому що усі входження u та z у формулу вільні. У формулі (z)(R(z,x))(x)(P(x)) змінна x є й зв’язаною, й вільною, адже перше входження змінної х у дану формулу є вільним, а друге та третє є зв’язаними.

Надалі будемо вважати, що у формулі (х)(F) ((x)(F)) змінна х вільна в F. Умовимося, що квантори мають менший ранг, ніж заперечення (). Отже, (х)F1   F2 означає (((х)(F1))  (F2)).

Запишемо, наприклад, за допомогою формули таке міркування. “Кожний студент прагне здобути знання. Петро – студент. Отже, Петро прагне здобути знання.” Спочатку уведемо предикатні символи. Позначимо “х є студент” через СТУДЕНТ(х), а “х прагне здобути знання” через ПРАГНЕ_ЗНАНЬ(х). Тоді твердження “Кожний студент прагне здобути знання” можна подати формулою:

(х)(СТУДЕНТ(х)ПРАГНЕ_ЗНАНЬ(х)),

твердження “Петро – студент” – формулою:

СТУДЕНТ(Петро),

а твердження “Петро прагне здобути знання” – формулою:

ПРАГНЕ_ЗНАНЬ(Петро).

Отже, міркування можна записати такою формулою:

(х)(СТУДЕНТ(х)ПРАГНЕ_ЗНАНЬ(х))СТУДЕНТ(Петро)

ПРАГНЕ_ЗНАНЬ(Петро).

Інтерпретації формул логіки першого порядку

Інтерпретація формули F логіки першого порядку – це упорядкована четвірка виду , де D – непорожня множина (предметна область, або область інтерпретації), а K,V,P – множини, що визначаються таким чином. Якщо формула F не містить констант, то К=, інакше побудуємо множину констант, що зустрічаються у F (позначимо її С), побудуємо відображення k: CD й покладемо К={k}. Якщо формула F не містить функціональних символів, то V=, інакше для кожного n-арного функціонального символу fn, що зустрічається у F, побудуємо відображення fn: DnD, й V є множина відображень, побудованих за усіма функціональними символами, що зустрічаються у F. Для кожного n-арного предикатного символу Pn, що зустрічається у F, побудуємо відображення виду Pn: Dn{0,1} (тобто n-арний предикат на множині D), й Р – множина предикатів, побудованих за усіма предикатними символами, що зустрічаються у F.

Іноді, щоб зосередити увагу на області D, будемо говорити про інтерпретацію формули на D.

Для кожної інтерпретації формули на області D формула може набути істинносне значення 0 або 1 згідно з такими правилами.

1. Якщо значення формул F й G відомі, то значення формул F, FG, FG, FG, FG обчислюються за таблицями істинності.

2. Формула (х)(F) набуває значення 1, якщо F набуває значення 1 для кожного x з D (тобто при заміні кожного входження змінної х у формулу F елементом множини D); у протилежному випадку вона набуває значення 0.

3. Формула (х)(F) набуває значення 1, якщо F набуває значення 1 хоча б для одного х із D; інакше вона набуває значення 0.

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

Розглянемо, наприклад, формулу F:

(х)(y)(P(х)(Q(y)R(f(х),c,y))).

У формулі F є одна константа (с), один унарний функціональний символ (f), два унарних предикатних символа (P та Q) й один тернарний предикатний символ (R). Визначимо інтерпретацію I таким чином. Покладемо D={1,2}; константі c поставимо у відповідність елемент 1 предметної області, функціональному символу f поставимо у відповідність відображення (збережемо для нього назву f), яке визначається так: f(1)=2, f(2)=1; предикатним символам P, Q, R поставимо у відповідність відображення (з тими ж назвами), поклавши P(1)=0, P(2)=1, Q(1)=1, Q(2)=0, R(1,1,1)=0, R(1,1,2)=0, R(1,2,1)=0, R(1,2,2)=0, R(2,1,1)=1, R(2,1,2)=1, R(2,2,1)=1, R(2,2,2)=1.

Якщо х=1, y=1, то P(x)Q(y)R(f(x),c,y)=P(1)Q(1)R(f(1),1,1)=011=1.

Якщо x=1, y=2, то P(x)Q(y)R(f(x),c,y)=P(1)Q(2)R(f(1),1,2)=001=1.

Якщо х=2, y=1, то P(x)Q(y)R(f(x),c,y)=P(2)Q(1)R(f(2),1,1)=110=0.

Якщо x=2, y=2, то P(x)Q(y)R(f(x),c,y)=P(2)Q(2)R(f(2),1,2)=100=0.

Бачимо, що при х=2 формула F не набуває значення 1 при жодному значенні у, отже F хибна при інтерпретації I на області {1,2}.

Формула F називається несуперечною, якщо існує така інтерпретація I, при якій F має значення 1. Якщо F істинна при інтерпретації I, то I називають моделлю формули F й говорять, що I задовольняє F.

Покажемо, наприклад, що формула F=P(a)((x)P(x)) несуперечна. Визначимо інтерпретацію I таким чином. Покладемо D={1,2}; константі а поставимо у відповідність елемент 1 предметної області; предикатному символу P поставимо у відповідність відображення (з тією ж назвою), поклавши Р(1)=0, Р(2)=1. Тоді (x)P(x) істинна при даній інтерпретації. Отже, маємо: F=Р(1)((x)P(x)) = 01=00=1. Оскільки існує інтерпретація, при якій формула F набуває значення 1, то F несуперечна. Побудована інтерпретація є моделлю формули F.

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

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

Покажемо, наприклад, що формула F = (х)P(х)(y)P(y) суперечна. Нехай I – деяка інтерпретація формули F, D – область інтерпретації. Якщо P(х) набуває значення 1 для кожного x з D, то ((y)P(y)) хибна при інтерпретації I, отже, й F хибна при I. Якщо хоча б для одного у із D P(y) набуває значення 0, то формула (х)P(х) хибна при I, отже, й F хибна при I.

Наведемо приклад тотожно істинної формули. Нехай F = (х)P(х)((y)P(y)). Нехай I – деяка інтерпретація формули F, D – область інтерпретації. Якщо P(х) набуває значення 1 для кожного x з D, то (х)P(х) істинна при інтерпретації I, отже, й F істинна при I. Якщо хоча б для одного у із D P(y) набуває значення 0, то формула ((y)P(y)) істинна при I, отже, й F істинна при I.

Формула F є логічним наслідком формул F1, F2,… Fn, якщо F істинна при кожній інтерпретації I, яка задовольняє F1F2…Fn.

Розглянемо, наприклад, формули

F1: (х)(P(х)Q(х)).

F2: P(a).

Покажемо, що формула Q(a) є логічним наслідком формул F1 та F2. Розглянемо довільну інтерпретацію I, яка задовольняє (х)(P(х)Q(х))P(a). При цій інтерпретації P(a) приймає значення 1. Припустимо, що I не задовольняє Q(a), тобто Q(a) не істинна при I. P(a)Q(a)=0, а тоді (х)(P(х)Q(х)) хибна при I, що суперечить припущенню. Отже, Q(a) має бути істинною при кожній інтерпретації, яка задовольняє (х)(P(х)Q(х))P(a). Це означає, що Q(a) є логічним наслідком формул F1 та F2.

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

^ Пренексна нормальна форма формул логіки першого порядку

Формула F логіки першого порядку подана (або знаходиться) у пренексній нормальній формі, якщо F має вигляд (Q1х1)…(Qnхn)M, де (Qixi) є (xi) або (xi) (i=1,…,n), а M є формулою, у якій немає кванторів. (Q1x1)…(Qnxn) називається префіксом, M – матрицею формули F.

Наприклад, формула (х)(y)(z)(Q(х,y)R(z)) знаходиться у пренексній нормальній формі, а формула (х)(P(х)(y)(R(y)Q(х,y))) – ні.

Уведемо позначення F[х], щоб відзначити, що формула F має вільну змінну x. Нехай G означає формулу, яка не має змінної х, Q означає  або . Наступні пари формул еквівалентні:

(Qх)F[х]G=(Qх)(F[х]G); (Qх)F[х]G=(Qх)(F[х]G); (1)

((x)F[x])=(x)(F[x]); ((x)F[х])=(x)(F[х]). (2)

Нехай F[х] та H[х] – формули, які мають змінну х. Виконуються такі співвідношення:

(x)F[x](x)H[x]=(x)(F[х]H[х]); (х)F[х](х)H[х]=(х)(F[х]H[х]).

Зауважимо, що

(x)F[x](x)H[x]  (x)(F[х]H[х]) й

(х)F[х](х)H[х]  (х)(F[х]H[х]).

Нехай z – змінна, що не входить у F[x] та H[х]. Тоді

(x)F[x](x)H[x] = (x)F[x](z)H[z] й

(х)F[х](х)H[х] = (х)F[х](z)H[z],

отже, використавши співвідношення (1), маємо

(x)F[x](x)H[x] = (x)(z)(F[х]H[z]),

(х)F[х](х)H[х] = (х)(z)(F[х]H[z]).

У загальному випадку маємо

(Q1x)F[x](Q2x)H[x] = (Q1x)(Q2z)(F[х]H[z]),

(Q1х)F[х](Q2х)H[х] = (Q1х)(Q2z)(F[х]H[z]).

Тут Q1, Q2 – це  або , а z не входить в F[х].

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

^ Перетворення формули у пренексну нормальну форму

  1. Використовуючи закони

F1  F2 = (F1F2)  (F2F1),

F1 F2 = F1  F2,

вилучити логічні зв’язки  та .

  1. За допомогою законів

(F) = F,

(F1  F2) = F1  F2, (F1  F2) = F1  F2,

((x)F[x])=(x)(F[x]); ((x)F[х])=(x)(F[х])

розмістити знаки заперечення безпосередньо перед атомами.

3. Здійснити перейменування зв’язаних змінних, якщо це необхідно.

4. Використовуючи закони

(Qх)F[х]G=(Qх)(F[х]G), (Qх)F[х]G=(Qх)(F[х]G),

(x)F[x](x)H[x]=(x)(F[х]H[х]),

(х)F[х](х)H[х]=(х)(F[х]H[х]),

(Q1x)F[x](Q2x)H[x] = (Q1x)(Q2z)(F[х]H[z]),

(Q1х)F[х](Q2х)H[х] = (Q1х)(Q2z)(F[х]H[z]),

винести квантори на початок формули.

Побудову пренексної нормальної форми завершено.

Приведемо, наприклад, формулу ((x)F1(x)(x)F2(x)) до пренексної нормальної форми: ((x)F1(x)(x)F2(x)) = ((x)F1(x)(x)F2(x)) = (x)F1(x)(x)F2(x) = (x)F1(x)(x)F2(x) = =(x)F1(x)(z)F2(z) = (x)(z)(F1(x)F2(z)).

^ Сколемівська стандартна форма формули першого порядку

Нехай формула F знаходиться у пренексній нормальній формі (Q1x1)…(Qnxn)M, де М є кон’юнктивна нормальна форма. Нехай Qi є квантор існування у префіксі (Q1x1)…(Qnxn), 1in. Якщо ліворуч від Qi у префіксі немає жодного квантора загальності, виберемо нову константу с, що не входить у М, замінимо усі входження змінної xi у М на с та викреслимо (Qixi) з префікса. Якщо Qs1,…,Qsm – список усіх кванторів загальності, що знаходяться у префіксі ліворуч від Qi, 1s1s2…smi, виберемо новий m-арний функціональний символ f, що відрізняється від функціональних символів формули М, та замінимо усі xi у М на терм f(xs1,xs2,…,xsm), а (Qixi) викреслимо з префікса. Такі дії виконаємо з усіма кванторами існування у префіксі. Формула, яка буде побудована в результаті, є сколемівська стандартна форма (або коротко стандартна форма) формули F. Константи та функції, що використані для заміни змінних, зв’язаних квантором існування, називаються сколемівськими функціями.

Побудуємо, наприклад, стандартну форму формули

(x1)(x2)(x3)(x4)(x5)(x6)(x7)М(x1,x2,x3,x4,x5,x6,x7).

Оскільки у даній формулі ліворуч від (x1) та (x2) немає кванторів загальності, замінимо змінні x1 та x2 новими константами а та b відповідно, а (x1) та (x2) вилучимо з префікса. Одержимо формулу

(x3)(x4)(x5)(x6)(x7)M(a,b,x3,x4,x5,x6,x7).

Ліворуч від (x5) міститься два квантори загальності, (x3) та (x4), а ліворуч від (x7) – три ((x3), (x4), (x6)), отже замінимо x5 термом f(x3,x4), а x7 – термом h(x3,x4,x6). У результаті маємо стандартну форму даної формули: (x3)(x4)(x6)M(a,b,x3,x4,f(x3,x4),x6,h(x3,x4,x6)).

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

Теорема 5. Нехай S – множина диз’юнктів, які представляють стандартну форму формули F. Тоді F суперечна тоді й тільки тоді, коли S суперечна.

Зауважимо, що несуперечна формула F та її стандартна форма S не завжди еквівалентні. Нехай, наприклад, F=(x)P(x). Стандартна форма формули F є S=P(a). Розглянемо таку інтерпретацію I з областю D={1,2}: константі a поставимо у відповідність елемент 1 предметної області й покладемо P(1)=0, Р(2)=1. Тоді F істинна при I, але S хибна при I, отже, FS.

Зазначимо також, що формула може мати більше однієї стандартної форми. Звичайно при побудові стандартної форми вибирають якнайпростіші сколемівські функції. Якщо маємо формулу виду F=F1…Fn, то можемо окремо побудувати множини диз’юнктів Si, де Si є стандартною формою формули Fi, i=1,…,n. Нехай S = S1…Sn. Неважко показати, що F суперечна тоді й тільки тоді, коли S суперечна.

^ Підстановки та уніфікатори

Під виразом будемо розуміти терм, множину термів, множину атомів, літеру, диз’юнкт, множину диз’юнктів. Вираз, що не містить змінних, будемо називати основним виразом. Підвиразом виразу Е назвемо вираз, що зустрічається в Е.

Підстановкою називається скінченна множина виду {t1/v1, …,tn/vn}, де vi – змінна, ti – терм, відмінний від vi, усі vi різні (i=1, … ,n). Елементи множини {t1/v1, …,tn/vn} називаються компонентами підстановки. Якщо t1,…,tn – основні терми (тобто не містять змінних), підстановка називається основною. Підстановка, що не містить елементів, називається порожньою й позначається .

Наприклад, множини {a/x, g(b)/y, f(x,y)/z}, {f(y,y)/x, z/y, f(x,z)/z} є підстановками, а {g(x)/u, b/y, z/u}, {x/x, g(a)/y, x/z} – ні.

Нехай ={t1/v1,…,tn/vn} – підстановка, Е – вираз. Прикладом Е називається вираз (позначається Е), що утворюється з Е шляхом заміни одночасно усіх входжень змінної vi (1  i  n) в Е на терм ti.

Нехай, наприклад, ={f(y)/x, a/y, u/z}, Е=Q(g(y),z,x). Тоді Е=Q(g(a),u,f(y)).

Нехай  = {t1/v1, … ,tn/vn},  = {u1/y1, … ,um/ym} – підстановки. Композицією  та  називається підстановка (позначається  або ), що утворюється із сукупності компонентів t1/x1,…,tn/xn, u1/y1,…,um/ym шляхом вилучення усіх тих компонентів tj/xj, для яких tj=xj, та усіх компонентів ui/yi, таких що yi{x1,…,xn}.

Нехай, наприклад,  = {t1/x1,t2/x2}={g(z)/x, w/z},  = {u1/y1,u2/y2,u3/y3} = {f(b)/x, a/z, z/w}. Тоді {t1/x1,t2/x2,u1/y1,u2/y2,u3/y3}={g(a)/x, z/z, f(b)/x, a/z, z/w}. Оскільки t2=x2, то маємо вилучити t2/x2 (тобто z/z) з множини. До того ж треба вилучити й u1/y1 та u2/y2 (тобто f(b)/x й a/z), бо y1 й y2 містяться серед {х1, х2}. Отже, маємо ={g(a)/x, z/w}.

Зазначимо, що сукупність підстановок з операцією композиції утворює напівгрупу з одиницею (), тобто () = () й == для усіх , , .

Уніфікатором множини виразів {E1,…,Ek} називається така підстановка , що E1=E2=…=Ek. Множина {E1,…,Ek} називається такою, що уніфікується, якщо для неї існує уніфікатор.

Нехай, наприклад, множина виразів Т = {Q(g(a),x), Q(y,f(a,b))}. Підстановка ={g(a)/y,f(a,b)/x} є уніфікатором T, оскільки Q(g(a),x)=Q(g(a),f(a,b))=Q(y,f(a,b)).

Найбільш загальним уніфікатором (нзу) множини виразів Т={E1,…,Ek} називається такий уніфікатор  цієї множини, що для будь-якого уніфікатора  множини Т існує така підстановка , що =.

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

Нехай, наприклад, W = {Q(x,a), Q(f(y),u)}. Тоді першою позицією, у якій не усі вирази з W мають однакові символи, є третя, оскільки усі вирази мають однакові перші два символи Q. Отже, множина розбіжностей складається з підвиразів, які починаються з третьої позиції, тобто це множина {x,f(y)}.

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

^ Алгоритм уніфікації

1. Покласти k=0, Wk=W, k=.

2. Якщо Wk – одноелементна множина, то припинити роботу: k є нзу для W; інакше знайти множину Dk розбіжностей множини Wk.

3. Якщо існують такі елементи vk та tk в Dk, що vk – змінна, що не входить в tk, то перейти до кроку 4, інакше припинити роботу: W не уніфікується.

4. Покласти k+1=k{tk/vk}, Wk+1=Wk{tk/vk}. (Зауважимо, що Wk+1=Wk+1.)

5. Збільшити k на одиницю та перейти до кроку 2.

Теорема 6. Якщо W – скінченна непорожня множина виразів, що уніфікується, то алгоритм уніфікації завершує роботу на кроці 2 й підстановка k є найбільш загальним уніфікатором множини W.

Знайдемо, наприклад, найбільш загальний уніфікатор для множини W={Q(x,a,f(y,g(b))),Q(b,y,u)}.

1. 0=, та W0=W. Оскільки W0 не є одноелементною множиною, то 0 не є найбільш загальним уніфікатором множини W.

2. Множина розбіжностей D0={x,b}. В D0 міститься змінна v0=х, яка не має входжень в t0=b.

3. Нехай 1=0{t0/v0}={b/x}={b/x},

W1=W0{t0/v0} = {Q(x,a,f(y,g(b))), Q(b,y,u)}{b/x} = {Q(b,a,f(y,g(b))),Q(b,y,u)}.

4. W1 – не одноелементна множина; множина розбіжностей множини W1 є D1={a,y}.

5. З D1 знайдемо v1=y та t1=a.

6. Обчислимо 2 та W2: 2=1{t1/v1}={b/x}{a/y}={b/x,a/y},

W2=W1{t1/v1}={Q(b,a,f(y,g(b))),Q(b,y,u)}{a/y}={Q(b,a,f(a,g(b))),Q(b,a,u)}

7. Бачимо, що W2 – не одноелементна множина. Множиною розбіжностей для W2 є D2={f(a,g(b)),u}. З D2 знаходимо v2=u та t2=f(a,g(b)).

8. Нехай 3=2{t2/v2}={b/x,a/y}{f(a,g(b))/u}={b/x,a/y,f(a,g(b))/u},

W3=W2{t2/v2}={Q(b,a,f(а,g(b))),Q(b,а,u)}{f(a,g(b))/u}={Q(b,a,f(a,g(b)))}.

9. W3 – одноелементна множина, отже, 3={b/x, a/y, f(a,g(b))/u} є нзу W.

Розглянемо ще один приклад. Визначимо, чи має нзу множина W={P(z,f(a)),P(c,f(z))}.

1. Покладемо 0=, W0=W.

2. W0 – не одноелементна множина; множиною розбіжностей W0 є D0={z,c}. Отже, v 0=z, t0=c.

3. Нехай 1=0{t0/v0}={c/z}={c/z},

W1=W0{t0/v0}={P(z,f(a)),P(c,f(z))}{c/z}={P(c,f(a)),P(c,f(c))}.

4. W1 – не одноелементна множина; множиною розбіжностей для W1 є D1={a,c}.

5. Множина D1 не містить змінних, отже виконання алгоритму уніфікації завершується, й ми робимо висновок, що W не уніфікується.

^ Правило резолюції для формул логіки першого порядку

Нехай дві або більше літер диз’юнкту С мають нзу . Склейкою диз’юнкту C називається диз’юнкт С. Якщо С – однолітерний диз’юнкт, то склейка називається одиничною.

Нехай, наприклад, С = Q(x,a) P(f(y),z)  Q(f(y),y). Перша та третя літери мають нзу ={f(a)/x, a/y}. Диз’юнкт C = P(f(а),z)  Q(f(а),а) – склейка C.

Нехай С1, С2 – диз’юнкти, що не мають жодної спільної змінної, L1, L2 – літери у відповідно С1 та С2. Якщо L1 та L2 мають нзу , то диз’юнкт (C1 \ {L1})(C2 \ {L2}) називається бінарною резольвентою С1 та С2. Літери L1 та L2 називаються такими, що відсікаються. С1 та С2 називаються диз’юнктами-посилками.

Нехай, наприклад, C1 = Q(f(x),y)P(z,b), C2 = R(f(x))Q(w,x). Оскільки x має входження у C1 та C2, замінимо змінну х у C2 на u. Нехай C2=R(f(u))Q(w,u). Виберемо L1=Q(f(x),y) та L2=Q(w,u). Оскільки L2=Q(w,u), то L1 та L2 мають нзу ={f(х)/w, y/u}. Отже,

(C1 \ {L1})  (C2 \ {L2}) = ({Q(f(x),y),P(z,b)}\{Q(f(x),y)})({R(f(y)), Q(f(x),y)}\{Q(f(x),y)})={P(z,b),R(f(y))} = P(z,b)R(f(y)).

Таким чином, P(z,b)R(f(y)) – бінарна резольвента диз’юнктів C1 та C2.

Резольвентою диз’юнктів-посилок С1 та С2 називається одна з таких резольвент:

- бінарна резольвента С1 та С2,

- бінарна резольвента С1 та склейки С2,

- бінарна резольвента С2 та склейки С1,

- бінарна резольвента склейки С1 та склейки С2.

Теорема 7. Множина диз’юнктів S суперечна тоді й тільки тоді, коли існує вивід порожнього диз’юнкту з S за допомогою правила резолюції.

Розглянемо, наприклад, таку сукупність формул:

F1: (x)(P(x)(Q(x)T(x))), F2: (x)(P(x)D(x)), F: (x)(D(x)T(x)).

Покажемо, що F є логічним наслідком F1 та F2. Перетворимо F1, F2 та F у стандартну форму. Маємо такі диз’юнкти:

(1) P(x)Q(x),

(2) P(x)T(x),

(3) P(a)

(4) D(a)

(5) D(х)T(x).

Виведення  за допомогою правила резолюції:

(6) Т(а) резольвента (3) та (2),

(7) Т(а) резольвента (5) та (4),

(8)  резольвента (7) та (6).

Отже, формула F є логічним наслідком формул F1 та F2.


^ Вимоги до оформлення домашньої контрольної роботи

Домашня контрольна робота виконується у звичайному шкільному зошиті, перша сторінка якого оформлюється за зразком додатку 1. Опис виконання першої частини завдання здійснюється за зразком [1], стор.37-63; виконання другої частини завдання здійснюється за прикладами, наведеними у попередньому розділі «Методичних вказівок».

^ Графік виконання домашньої контрольної роботи

Термін виконання ДКР – 3 тижні з моменту отримання завдання. За цей період проводиться консультація.

^ Порядок виконання домашньої контрольної роботи

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

Для підготовки до виконання ДКР слід скористатися конспектом лекцій та «Методичними вказівками», а також вивчити матеріал [1], стор. 4-36; [2], стор. 178-183, 195-200, 510-526. Для поглибленого вивчення теми можна скористатися додатковою літературою. ДКР виконується у зошиті та здається на перевірку викладачеві. Необхідно захистити ДКР згідно з графіком, який визначається викладачем.


^ Оцінювання домашньої контрольної роботи

Повне виконання, роботу захищено 24-27 балів,

повне виконання, роботу не захищено 10 балів,

неповне виконання, роботу не захищено 0 балів.

Максимальна кількість балів за виконання ДКР – 27.

Список рекомендованої літератури

Основна

1. Дискретний аналіз. Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та захистом інформації. Частина 2. Елементи математичної логіки. Укладач Мороховець М.К. – К.: НТУУ «КПІ», 2010. – 70 с.

2. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – 580 с.


Додаткова

1. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983. – 360 с.

2. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984. – 320 с.


ДОДАТОК 1

До методичних вказівок


^ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Фізико-технічний інститут

Кафедра математичних методів захисту інформації


ДОМАШНЯ КОНТРОЛЬНА РОБОТА


з дисципліни

МАТЕМАТИЧНА ЛОГІКА

ТА ТЕОРІЯ АЛГОРИТМІВ


Варіант №_______



Виконав:


студент ________ курсу групи______


___________________________________

(ПІБ студента)


Прийняв:

Викладач__________________________

(ПІБ викладача)


Кількість балів:

___________________________




20__



Похожие:

Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» / Уклад....
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання контрольної роботи з дисципліни "Основи математичного моделювання" для студентів спеціальності 090202
Вміщують робочу програму, конторольні питання для перевірки знань, методичні вказівки до виконання контрольної роботи та приклад...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання дипломної роботи для студентів спеціальності
Методичні вказівки до виконання дипломної роботи для студентів спеціальності 050201 «Менеджмент організацій». Полтава: Полтнту, 2011....
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання. Контрольної роботи з дисципліни "Економіка праці"
Завдання даної роботи – самостійне виконання студентами контрольних теоретичних питань і практичних завдань з метою засвоєння знань...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання курсової роботи затвердження теми курсової роботи
Написання курсової роботи з трудового права передбачено навчальним планом підготовки студентів із спеціальності "Правознавство"
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання курсового проекту за курсом
Методичні вказівки до виконання курсового проекту за курсом «Теплові електричні станції» (для студентів спеціальності 090510- теплоенергетика...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до контрольної роботи з дісципліни " Економіка І організація інноваційної діяльності" для студентів напрямку
Методичні вказівки розглянуті та рекомендовані до друку на засіданні кафедри «Економіка, організація і управління підприємством»...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до контрольної роботи з дісципліни " Економіка І організація інноваційної діяльності" для студентів напрямку
Методичні вказівки розглянуті та рекомендовані до друку на засіданні кафедри «Економіка, організація і управління підприємством»...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання самостійної роботи з дисципліни «Економіка підприємств» для студентів напряму «Економіка І підприємництво»
Методичні вказівки до виконання самостійної роботи з дисципліни «Економіка підприємств та фінанси» 050104 «Фінанси» усіх форм навчання...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання та оформлення дипломної роботи для студентів спеціальності 050107 "Економіка підприємства"
Економіка підприємства”; в них наведено мету і завдання дипломної роботи, вибір теми, поетапні процедури організації дипломування,...
Методичні вказівки до виконання домашньої контрольної роботи з кредитного модуля «Математична логіка та теорія алгоритмів» для студентів спеціальності 040301 Прикладна математика iconМетодичні вказівки до виконання курсового проекту з дисципліни «Технологія машинобудування» для студентів денної І заочної форм навчання з спеціальності
Методичні вказівки до виконання курсового проекту з дисципліни «Технологія машинобудування» для студентів денної і заочної форм навчання...
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы