ДРОГОБИЦЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ ІМЕНІ ІВАНА ФРАНКА
ЮРІЙ МАТУРІН
ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ І ТЕОРІЇ ...
55 downloads
218 Views
349KB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
ДРОГОБИЦЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ ІМЕНІ ІВАНА ФРАНКА
ЮРІЙ МАТУРІН
ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ І ТЕОРІЇ АЛГОРИТМІВ. ЧАСТИНА 1
НАВЧАЛЬНИЙ ПОСІБНИК ДЛЯ СТУДЕНТІВ ГАЛУЗІ ЗНАНЬ 0402 «ФІЗИКО-МАТЕМАТИЧНІ НАУКИ» , НАПРЯМУ ПІДГОТОВКИ 6.040201 «МАТЕМАТИКА»
Дрогобич - 2011
Юрій Матурін
2
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Рекомендовано до друку вченою радою Дрогобицького державного педагогічного університету імені Івана Франка (протокол № 3 від 17 березня 2011 р.) Матурін Юрій Петрович / ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ ТА ТЕОРІЇ АЛГОРИТМІВ. ЧАСТИНА 1: навчальний посібник для студентів галузі знань 0402 «Фізико-математичні науки», напряму підготовки 6.040201 "Математика" / Дрогобич, 2011. – 49 с. Даний посібник написано відповідно до програми навчальної дисципліни “Математична логіка та теорія алгоритмів” для студентів галузі знань 0402 “Фізико-математичні науки”, напряму підготовки 6.040201 "Математика", затвердженої вченою радою Дрогобицького державного педагогічного університету імені Івана Франка, містить виклад теоретичного матеріалу з даної дисципліни, приклади, що ілюструють теорію та завдання. Видається у двох частинах. Ця частина містить розділи «Алгебра висловлень» і «Булеві функції та релейно-контактні схеми». Посібник може бути використаний старшокласниками, які зацікавлені у поглибленому вивченні математики. Бібліографія 153 назв Автор: Матурін Ю. П., кандидат фізико-математичних наук, доцент кафедри математики та методики викладання математики Дрогобицького державного педагогічного університету імені Івана Франка. Рецензенти: Комарницький М.Я., доктор фізико-математичних наук, професор, завідувач кафедри алгебри і логіки Львівського національного університету імені Івана Франка; Дільний В.М., кандидат фізико-математичних наук, доцент кафедри математичного аналізу Дрогобицького державного педагогічного університету імені Івана Франка. Відповідальний за випуск: Галь Ю.М., кандидат фізико-математичних наук, доцент кафедри математики і методики викладання математики Дрогобицького державного педагогічного університету імені Івана Франка.
Юрій Матурін
3
Елементи математичної логіки і теорії алгоритмів. Частина 1
ЗМІСТ ВСТУП 4 1. АЛГЕБРА ВИСЛОВЛЕНЬ 7 1.1. Висловлення та операції над ними 7 1.2. Формули алгебри висловлень 9 1.3. Рівносильність формул алгебри висловлень 10 1.4. Логічне слідування на базі алгебри висловлень 13 1.5. Види теорем. Необхідна і достатня умови 14 1.6. Методи доведення теорем 15 1.7. Нормальні форми формул алгебри висловлень 15 1.7.1. Елементарні кон’юнкції [диз’юнкції] 15 1.7.2. Диз’юнктивні та кон’юнктивні нормальні форми (днф [кнф])16 1.7.3. Алгоритм зведення формули до рівносильної днф [кнф] 17 1.7.4. Алгоритм зведення днф [кнф] до досконалої днф [кнф] 17 2. БУЛЕВІ ФУНКЦІЇ ТА РЕЛЕЙНО-КОНТАКТНІ СХЕМИ 19 2.1. Означення булевих функцій 19 2.2. Таблиці основних булевих функцій 20 2.3. Деякі типи булевих функцій 21 2.4. Аналітичне задання булевих функцій 24 2.5. Замикання та замкненість множин булевих функцій 26 2.6. Повнота множин булевих функцій 27 2.7. Означення релейно-контактних схем 28 2.8. Реалізація булевих функцій 28 2.9. Спрощення релейно-контактних схем 30 2.10. Застосування релейно-контактних схем до побудови однорозрядного двійкового суматора 30 3. ЗАВДАННЯ 32 3.1. Запитання для самоконтролю 32 3.2. Вправи та задачі теоретичного характеру 33 3.3. Вправи та задачі розрахункового характеру 37 ІМЕННИЙ ПОКАЖЧИК 39 ПРЕДМЕТНИЙ ПОКАЖЧИК 41 БІБЛІОГРАФІЯ 42
א
Юрій Матурін
4
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
ВСТУП Таким чином, логіка та інтуїція відіграють кожна свою необхідну роль. Обидві вони неминучі. Логіка, яка єдина може гарантувати достовірність, є знаряддям доведення; інтуїція є знаряддям винахідництва. Анрі Пуанкаре
Математична логіка та теорія алгоритмів є фундаментальною математичною дисципліною, яка вивчає закони математичного мислення та загальні властивості алгоритмів. Ця наука виникла порівняно недавно. Вона нерозривно пов’язана з логікою і математикою. Засновником логіки вважається видатний давньогрецький філософ Аристотель. Він уперше систематизував доступні знання з логіки, обгрунтував форми та правила логічного мислення. Перші спроби перетворити логіку у галузь математичного знання зробив великий німецький учений і політичний діяч Готфрід Вільгельм Лейбніц (1646-1716). Проте суттєвого успіху в цьому напрямі вдалося досягнути (1847) англійському математику Джорджу Булю (1815 –1864), який побудував алгебру логіки, названу на його честь булевою. Головними розділами сучасної математичної логіки (її класичного варіанту) є логіка висловлень, що йде ще від Дж. Буля і яка не охоплює силогістику Аристотеля, і значно ширша логіка предикатів, яка містить силогістику як свою частину. Сучасного вигляду математична логіка набула в 1880-х роках у працях визначного німецького логіка, математика і філософа Готлоба Фреге (1848 – 1925). Популяризація його ідей Карнапом, Бертраном Расселом та Людвігом Вітгенштейном зробила Фреге відомим ще в 1930-тих. Революційний твір Фреге Begriffsschrift (Числення понять) (1879) започаткував нову еру в історії математичної логіки. У Begriffsschrift Фреге з абсолютно нових позицій переглянув ряд математичних проблем, включаючи належне трактування понять функції і змінних.
Юрій Матурін
5
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Він винайшов і аксіоматизував логіку предикатів завдяки своєму відкриттю кванторів, використання яких поступово поширилося на всю математичну науку. Ці досягнення заклали фундамент для створення теорії описів Бертрана Рассела, написання Principia Mathematica (Рассел, Уайтхед) і відкриття знаменитої теореми Геделя про неповноту. У минулому столітті почався бурхливий розвиток теорії моделей, найважливіші результати якої були отримані Тарським, Мальцевим і Робінсоном. Дана дисципліна покликана допомогти сформувати у студентів математичне мислення, яке є невід’ємною складовою підготовки майбутніх вчителів математики. Вона має величезне значення для фахівців цього напрямку, оскільки змістом її, за словами визначного сучасного математика Юрія Івановича Маніна, є вивчення самої мови математики. Таким чином, дисципліна є фундаментом для розуміння основ математичної науки. Парадокси Рассела та Рішара, БанахаТарського, Ейнштейна-Подольського-Розена, канторівська проблема континууму та багато інших проблем математики і фізики незаперечно довели, що даний предмет не просто застосовується до вирішення конкретних проблем математики і фізики, але й має глибокий філософський зміст. У наш час, коли розвиток інформаційних технологій набув небачених масштабів, ця дисципліна разом з дискретною математикою стала надійною основою для засвоєння комп’ютерних наук, оскільки комп’ютери працюють на основі елементів, які можна інтерпретувати за допомогою теоретичного апарату цих, близьких за змістом галузей математичної науки. Таким чином, математична логіка нерозривно взаємозв’язана з математикою, логікою, фізикою, комп’ютерними науками і філософією ( та відповідними навчальними дисциплінами). Основними завданнями, які стоять перед студентами при вивченні навчальної дисципліни є такі: - опанувати основи математичної логіки та теорії алгоритмів, що становлять зміст навчальної дисципліни; - набути умінь і навиків для розв’язування завдань з дисципліни; - навчитися самостійно здійснювати пошук літератури з предмету та суміжних дисциплін і працювати з нею;
Юрій Матурін
6
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
- зрозуміти застосування дисципліни до інших математичних дисциплін та майбутньої професійної діяльності; - виробити креативність та нешаблонність мислення при самостійній науково-пошуковій діяльності (самостійно розв’язувати задачі підвищеної складності, самостійно ставити собі задачі та розв’язувати їх); - виробити в собі критичне мислення та незалежність від «авторитетів»; - виховувати в собі справжню особистість з власною позицією з різноманітних проблем держави і суспільства, здатність її логічно обґрунтовувати і втілювати в життя. Даний посібник написано відповідно до чинної програми навчальної дисципліни “Математична логіка та теорія алгоритмів” для студентів галузі знань 0402 “Фізико-математичні науки”, напряму підготовки 6.040201 "Математика", затвердженої вченою радою Дрогобицького державного педагогічного університету імені Івана Франка, містить виклад теоретичного матеріалу з даної дисципліни, приклади, що ілюструють теорію та завдання. Видається у двох частинах. Ця частина містить розділи «Алгебра висловлень» і «Булеві функції та релейно-контактні схеми». Посібник рекомендуємо використовувати за наступною методикою: послідовно вивчати кожний теоретичний підрозділ за підрозділом, при цьому намагатися розв’язувати відповідні завдання (запитання для самоконтролю, вправи та задачі теоретичного характеру, вправи та задачі розрахункового характеру), здійснюючи пошук літератури та самостійну науково-пошукову діяльність використовуючи наведену бібліографію, керуючись вищенаведеними основними завданнями. Варто зауважити також, що в посібнику ми обмежуємося лише розглядом класичної математичної логіки – двозначної логіки, в якій є лише два значення істинності (1 – істинність, 0 – хибність), хоча останнім часом дуже багато результатів отримано в некласичному напрямку (квантова логіка, скінченнозначні та нескінченнозначні логіки та ін.). Книга розрахована як на студентів-математиків, так і на старшокласників, які поглиблено вивчають математику.
Юрій Матурін
7
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
1. АЛГЕБРА ВИСЛОВЛЕНЬ 1.1. Висловлення та операції над ними Висловлення належить до первісних понять і тому не означується. Введемо це поняття описово. Під висловленням ми розуміємо таке речення (твердження), яке є істинним (приписуємо такому висловленню значення 1) або хибним (0). Висловлення не може бути одночасно істинним і хибним. Значення істинності висловлень називають також істиннісними значеннями. Означення. Запереченням висловлення А називається таке висловлення А , яке є хибним тоді й тільки тоді, коли А є істинним. Це означення можна записати за допомогою таблиці: А
А
0 1
1 0
0 – хибне, а 1 – істинне значення. Інколи заперечення позначають, ще й так:
А (не А).
Означення. Диз’юнкцією висловлень А і В називається висловлення А ∨ В , яке є хибним тоді й тільки тоді, коли А і В є хибними. Це можна записати за допомогою таблиці: А
В
А∨ В
0
0
0
0
1
1
1
0
1
1
1
1
Диз’юнкцію інколи записують так: А або В.
Юрій Матурін
8
Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Означення. Кон’юнкцією висловлень А і В називається висловлення А ∧ В , яке є істинним тоді й тільки тоді, коли А і В істинні. Таблично це означення записують так: А В А∧ В 0
0
0
0
1
0
1
0
0
1
1
1
Кон’юнкцію ще позначають наступним чином: А і В. Означення. Імплікацією висловлень А і В називається висловлення А → В , яке є хибним тоді й тільки тоді, коли А є істинним, а В – хибним. Це можна записати у вигляді таблиці: А В А→ В 0
0
1
0
1
1
1
0
0
1
1
1
Інколи імплікацію записують так: якщо А, то В. Означення. Еквіваленцією висловлень А і В називається висловлення А ↔ В , яке є істинним тоді й тільки тоді, коли обидва висловлення А і В мають однакове значення істинності, тобто вони є одночасно істинними, або одночасно хибними. Таблично це записують так: А В А↔ В 0
0
1
0
1
0
Юрій Матурін
9
Елементи математичної логіки і теорії алгоритмів. Частина 1
1
0
0
1
1
1
א
1.2. Формули алгебри висловлень Означення. Змінні, єдиними можливими значеннями яких є висловлення, називаються пропозиційними змінними. Пропозиційні змінні (букви) будемо позначати малими латинськими літерами з індексами, або без них (у вправах будемо допускати вживання великих латинських букв). Будемо використовувати позначення А = 1 тоді і тільки тоді, коли А – істинне, а А = 0 тоді і тільки тоді, коли А – хибне. Означення. Формулою алгебри висловлень називається вираз одного з наступних виглядів: 1) пропозиційні букви; 2) А ; 3) ( А ∨ В ) ; 4) ( А ∧ В ) ;
5) ( А → В ) ;
6) ( А ↔ В ) , де А і В – формули алгебри висловлень. Приклади. 1) p, q, r – формули алгебри висловлень; 2) ( p → q ) , (q ∧ r ) , p – формули;
( ) 4) ( p ∧ ( p → q) ) – формула; 3) p ∧ ( p → q) – формула;
5) p – формула. Формули, що співпадають з пропозиційними буквами будемо називати атомарними. Усі інші формули називаються складними. Формули алгебри висловлень будемо позначати великими буквами латинського алфавіту. Дужки в формулах іноді будемо опускати,
Юрій Матурін
10 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
якщо не втрачається можливість їх відновлення. При цьому використовуємо наступну пріоритетність логічних дій у порядку її спадання: ∧, ∨, →, ↔ . Якщо формула U алгебри висловлень не містить у своєму записі пропозиційних змінних, відмінних від p1 , p2 ,... ps , то цю формулу іноді позначають через U ( p1 , p2 ,... ps ) . Означення. Формула алгебри висловлень U ( p1 , p2 ,... ps ) називається тотожноістинною формулою (тавтологією), якщо при будь-яких наборах істиннісних значень пропозиційних змінних p1 , p2 ,... ps , формула набуватиме істиннісне значення 1. Означення. Формула алгебри висловлень U ( p1 , p2 ,... ps ) називається тотожнохибною формулою (суперечністю), якщо при будь-яких наборах істиннісних значень пропозиційних змінних p1 , p2 ,... ps , формула набуватиме значення істинності 0. Означення. Формула алгебри висловлень, яка не є суперечністю, називається виконуваною, а формула, яка не є ні суперечністю, ні тавтологією, називається нейтральною. Приклади. 1) ( a → (b → a ) ) – тавтологія;
( ) 3) ( a → b ) – нейтральна і виконувана формула. 2) a ∧ a – суперечність;
1.3. Рівносильність формул алгебри висловлень Означення. Формули алгебри висловлень F ( x1 , x2 ,...xn ) і G ( x1 , x2 ,...xn ) називаються рівносильними (еквівалентними), якщо для будь-яких наборів значень істинності пропозиційних змінних x1 , x2 ,...xn ці формули набувають однакових значень істинності. Рівносильність формул позначають так: F ( x1 , x2 ,...xn ) ≡ G ( x1 , x2 ,...xn ) .
Юрій Матурін
11 Елементи математичної логіки і теорії алгоритмів. Частина 1
Позначення: 0 тавтологією.
א
– суперечність, 1 – тавтологія, ˫ Т – Т є
Теорема. Формули алгебри висловлень F і G є рівносильними тоді й тільки тоді, коли ˫ ( F ↔ G ) Основні рівносильності 1. x ∨ y ≡ y ∨ x ,
x∧ y ≡ y∧x
(комутативність); 2. ( x ∨ y ) ∨ z ≡ x ∨ ( y ∨ z ) ,
( x ∧ y) ∧ z ≡ x ∧ ( y ∧ z)
(асоціативність); 3. ( x ∨ y ) ∧ z ≡ ( x ∧ z ) ∨ ( y ∧ z ) ,
( x ∧ y) ∨ z ≡ ( x ∨ z) ∧ ( y ∨ z)
(дистрибутивність); 4. ( x ∧ y ) ∨ x ≡ x ,
( x ∨ y) ∧ x ≡ x
(поглинання); 5. ( x ∨ y ) ∧ ( x ∨ y ) ≡ x ,
( x ∧ y) ∨ ( x ∧ y) ≡ x (склеювання); 6. x → y ≡ x ∨ y ; 7. x ↔ y ≡ ( x → y ) ∧ ( y → x ) ; 8. x ≡ x (рівносильність подвійного заперечення); 9. x ∨ y ≡ x ∧ y ,
x∧ y ≡ x∨ y (рівносильності де Моргана); 10. x ∨ x ≡ x ,
x∧x≡ x
(рівносильності ідемпотентності);
Юрій Матурін
12 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
11. x ∨ x ≡ 1 (рівносильність виключення третього); 12. x ∧ x ≡ 0 (рівносильність непротиріччя) ;
x ∨ 1 ≡ 1, x ∧ 1 ≡ x, 13, 14. x ∧ 0 ≡ 0, – властивості констант; x ∨ 0 ≡ x 15. x → y ≡ y → x (рівносильність контрапозиції). Приклад.
( ( x → y ) ∧ ( z → x) ) ∨ ( z ∨ x ) ≡ z ∨ x
(за
рівносильностями 6, 8, 4). Властивості відношення рівносильності на множині формул алгебри висловлень 1. F ≡ F для будь-якої формули F (рефлексивність). 2. Якщо F ≡ G , то G ≡ F для будь-яких формул F і G (симетричність). 3. Якщо F ≡ G і G ≡ T , то F ≡ T для будь-яких формул F, G і T (транзитивність). Теорема. Відношення рівносильності на множині всіх формул алгебри висловлень є відношенням еквівалентності. Зауваження 1. Доведення рівносильностей 1-15 можна провести за допомогою таблиць істинності. Наприклад, доведемо одну з рівносильностей де Моргана. Доведення рівносильності 9 x 0
y 0
x
y
x∨ y
x∨ y
x∧ y
1
1
0
1
1
Юрій Матурін
13 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
0 1 1
1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 Зауваження 2. За допомогою основних рівносильностей можна спрощувати вигляд формул, якщо взяти до уваги наступне: якщо F1 ≡ F2 , F2 ≡ F3 ,..., Fn−1 ≡ Fn , то F1 ≡ Fn . Зауваження 3. Використовуючи рівносильності 1-15 можна отримати цілий ряд тавтологій. Наприклад, з рівносильності 8 маємо: x ↔ x . 1.4. Логічне слідування на базі алгебри висловлень Означення. Будемо говорити, що формула G ( x1 , x2 ,..., xn ) логічно слідує на базі алгебри висловлень з формул F1 ( x1 , x2 ,..., xn ),..., Fk ( x1 , x2 ,..., xn ) , якщо формула G набуває значення істинності 1 при будь-яких наборах істиннісних значень пропозиційних змінних x1 , x2 ,..., xn , при яких формули F1 ,..., Fk одночасно набувають значення істинності 1. Формули F1 ,..., Fk називаються посилками, а G – логічним висновком. Позначення. F1 ,..., Fk ˫ G. Теорема. Нехай F1 ,..., Fk , G – формули, причому G – тавтологія. Тоді F1 ,..., Fk ˫ G. Теорема. Нехай F1 ,..., Fk , G – формули. F1 ,..., Fk ˫ G тоді й тільки тоді, коли ˫ F1 ∧ ... ∧ Fk → G . Доведення Нехай Fi = Fi ( x1 , x2 ,..., xn ) , i = 1,..., k ; G = G ( x1 , x2 ,..., xn ) . (→) Нехай F1 ,..., Fk . Припустимо, що формула F1 ∧ ... ∧ Fk → G не є тавтологією. Тоді при деякому наборі істиннісних значень пропозиційних змінних x1 , x2 ,..., xn матимемо, що F1 ∧ ... ∧ Fk → G = 0 . Тоді при цьому ж наборі F1 ∧ ... ∧ Fk = 1 , G = 0 . Остаточно, при
Юрій Матурін
14 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
цьому ж наборі F1 = ... = Fk = 1 , G = 0 , що суперечить тому, що G є логічним висновком з формул F1 ,..., Fk . Отже, припущення не є правильним, тому формула F1 ∧ ... ∧ Fk → G є тавтологією. (←) Нехай F1 ∧ ... ∧ Fk → G – тавтологія (1). Розглянемо довільний набір істиннісних значень пропозиційних змінних x1 , x2 ,..., xn , при якому F1 = ... = Fk = 1 . Тоді при тому ж наборі істиннісних значень пропозиційних змінних F1 ∧ ... ∧ Fk = 1 . Враховуючи тепер (1), при тому ж наборі істиннісних значень пропозиційних змінних маємо, що G = 1 . Ми довели, що F1 ,..., Fk ˫ G. Теорему доведено. Наслідок. Нехай А і В – довільні формули алгебри висловлень. Тоді маємо, що A, A → B ˫ В. Доведення Згідно з попередньою теоремою ми повинні довести, що формула A ∧ ( A → B ) → B тотожноістинна. Справді, A ∧ ( A → B ) → B ≡ A ∧ ( A ∨ B) → B ≡ ( AA ∨ AB ) → B ≡ AB → B ≡ ≡ AB ∨ B ≡ ( A ∨ B) ∨ B ≡ A ∨ ( B ∨ B) ≡ A ∨ 1 ≡ 1. Наслідок доведено. 1.5. Види теорем. Необхідна і достатня умови Більшість теорем у математиці мають логічну структуру вигляду A→ B (1), яку словами можна записати так: якщо виконується А, то виконується В. При цьому кажуть, що А є достатньою умовою для В, а В – необхідна умова для А. У таких теоремах А називають умовою, а В – висновком. Розглянемо тепер теореми з наступними логічними структурами: B → A (2), B → A (3), A → B (4). Теорему (1) будемо називати прямою теоремою. Тоді теорема (2) називається оберненою до теореми (1); теорема (3) називається спряженою до теореми (1); теорема (4) називається протилежною до теореми (1).
Юрій Матурін
15 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
За законом контрапозиції маємо, що пряма та спряжена теореми є рівносильними. Зауважимо, що якщо пряма теорема має місце, то протилежна і обернена не завжди істинні. 1.6. Методи доведення теорем У математиці існують два основних методи доведення теорем, а саме: прямий метод та метод доведення від супротивного. Прямий метод доведення теореми грунтується на логічному слідуванні наступного вигляду: А → А1 , А1 → А2 ,..., Аn → Аn+1 (= B ) ˫ A → B . Метод доведення від супротивного використовується для доведення теореми A → B . Для цього припускають, що дана імплікація місця не має, отримують суперечність. Отже, імплікація A → B має місце. 1.7. Нормальні форми формул алгебри висловлень 1.7.1. Елементарні кон'юнкції [диз'юнкції] Означення. Елементарною кон'юнкцією [диз'юнкцією] називається вираз вигляду: x1* ∧ x2* ∧ ... ∧ xn* ( x1* ∨ x2* ∨ ... ∨ xn* ) ,
де xi* = xi або xi* = x i , ( i = 1,2,..., n ) , x1 , x2 ,...xn – пропозиційні змінні. Означення. Елементарна кон'юнкція [диз'юнкція] називається правильною, якщо кожна пропозиційна змінна входить до неї не більше ніж один раз, включаючи входження змінної під знаком заперечення. Приклади. a ∧ a – елементарна кон'юнкція, яка не є правильною; a ∨ a – елементарна диз’юнкція, яка не є правильною; a ∨ b ∨ a – елементарна диз’юнкція, яка не є правильною;
Юрій Матурін
16 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
a ∨ b – правильна елементарна диз’юнкція. Означення. Елементарна кон'юнкція [диз'юнкція] називається повною відносно пропозиційних змінних x1 , x2 ,...xn , якщо кожна з цих пропозиційних змінних входить до неї або із знаком заперечення, або без нього. Приклад. x1 ∧ x1 ∧ x2 – повна елементарна кон’юнкція відносно змінних x1 , x2 , яка не є правильною. 1.7.2. Диз’юнктивні та кон’юнктивні нормальні форми (днф [кнф]) Означення. Диз'юнктивною [кон'юнктивною] нормальною формою (днф [кнф]) називається диз'юнкція [кон'юнкція] декількох елементарних кон'юнкцій [диз'юнкцій]. Приклади. 1) x, x – кнф, днф; 2) x1 ∧ x2 – днф, кнф; 3) x1 ∨ x2 – днф, кнф;
(
)
4) x1 ∨ x2 ∧ x3 не є днф, але є кнф;
(
)
5) ( x1 ∨ x3 ) ∧ x2 ∨ x4 – кнф; 6) x1 ∧ x3 ∨ x2 ∧ x4 – днф.
F ( x1 , x2,..., xn ) Означення. Формула алгебри висловлень називається досконалою диз'юнктивною [кон'юнктивною] нормальною формою (дднф [дкнф]) відносно пропозиційних змінних x1 , x2,..., xn , якщо вона є диз'юнкцією [кон'юнкцією] декількох попарно різних правильних і повних відносно x1 , x2 ,..., xn елементарних кон'юнкцій [диз'юнкцій].
Юрій Матурін
17 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
1.7.3. Алгоритм зведення формули до рівносильної днф [кнф] 1. Позбуваємось у даній формулі імплікації та еквіваленції, x→ y ≡ x∨ y і використовуючи наступну рівносильність:
(
) (
)
x ↔ y ≡ x∨ y ∧ x∨ y . 2. В отриманій формулі в разі потреби досягаємо рівносильними перетвореннями того, щоби знак заперечення або був відсутній, або стосувався лише пропозиційних змінних. Для цього використовуємо наступні рівносильності: x ∨ y ≡ x y ; xy ≡ x ∨ y ; x ≡ x . 3. До отриманої формули в разі потреби застосовуємо дистрибутивну рівносильність кон'юнкції [диз'юнкції] відносно диз'юнкції [кон'юнкції].
(
)
Приклад. Звести формулу x ↔ x ∨ y до рівносильної днф.
(
)
(
) ( ( )) ≡ ( x ∨ x ∨ y )( x ∨ xy ) ≡
x ↔ x∨ y ≡ x∨ x∨ y x∨ x∨ y
(
)(
)
≡ x ∨ y x ∨ xy ≡ xx ∨ xxy ∨ y x ∨ y xy. 1.7.4. Алгоритм зведення днф [кнф] до досконалої днф [кнф] Якщо днф [кнф] не є суперечністю [тавтологією], то її можна звести рівносильними перетвореннями до дднф [дкнф]. 1. В разі необхідності в елементарних кон’юнкціях використовуємо наступні рівносильності: x ∧ y ≡ y ∧ x [ x ∨ y ≡ y ∨ x ]; x ∧ ( y ∧ z ) ≡ ( x ∧ y ) ∧ z [ x ∨ ( y ∨ z ) ≡ ( x ∨ y ) ∨ z ]; x ∧ x ≡ x [ x ∨ x ≡ x ]; x ∧ x ≡ 0 [ x ∨ x ≡ 1]; 0 ∧ x ≡ 0 [1 ∨ x ≡ 1]. 2. В разі потреби використовуємо рівносильність: 0 ∨ x ≡ x [1 ∧ x ≡ x ]. 3. В разі необхідності доповнюємо елементарні кон'юнкції пропозиційними змінними. Для цього використовуємо наступну рівносильність: k ≡ (k ∧ xi ) ∨ (k ∧ x i ) [ k ≡ (k ∨ xi ) ∧ (k ∨ x i ) ].
Юрій Матурін
18 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
4. Використовуємо рівносильність x ∨ x ≡ x [ x ∧ x ≡ x ], якщо в отриманій формулі є хоча би дві однакові елементарні кон'юнкції [диз'юнкції]. Ми отримали алгоритм зведення формули до рівносильної дднф [дкнф]. Він складається з двох виписаних алгоритмів. Приклад. Звести xy x ∨ x ∨ y до дднф. xy x ∨ x ∨ y ≡ x ∨ y ≡ xy ∨ x y ∨ yx ∨ y x ≡ xy ∨ x y ∨ x y .
Юрій Матурін
19 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
2. БУЛЕВІ ФУНКЦІЇ ТА РЕЛЕЙНО-КОНТАКТНІ СХЕМИ 2.1. Означення булевих функцій Означення. Булевою функцією від n змінних називається відображення f : Ω n → Ω , де Ω = {0,1} . Це є функція f ( x1 , x2 ,..., xn ) , де аргументи x1 , x2 ,..., xn набувають
значення з множини Ω = {0,1} , і значення самої функції належать також до Ω . Множину всіх булевих функцій від n змінних позначають через Pn . Дві функції f ( x1 , x2 ,..., xn ) і g ( x1 , x2 ,..., xn , xn+1 ,..., xn+k ) будемо вважати рівними, якщо виконується наступна умова ∀ ( a1 , a2 ,..., an , an+1 ,..., an+k ) ∈ Ω n+k :
f ( a1 , a2 ,..., an ) = g ( a1 , a2 ,..., an , an+1 ,..., an+k ) . Після цього ототожнення будемо розглядати множину всіх ∞
булевих функцій P := U Pn . n =1
Очевидно, що будь-яку булеву функцію можна задати однозначно за допомогою таблиці істинності. Кожній формулі алгебри висловлень у зрозумілий спосіб відповідає деяка булева функція, яка задається тою ж таблицею істинності. Приклад. Визначимо за допомогою таблиці функції f1 ( x1 , x2 , x3 ) ,
f 2 ( x1 , x2 , x3 ) :
x1
x2
x3
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
f1 ( x1 , x2 , x3 ) 1 0 1 0 0 0 0 0
f 2 ( x1 , x2 , x3 ) 0 1 1 0 0 1 0 0
Юрій Матурін
20 Елементи математичної логіки і теорії алгоритмів. Частина 1 n
א
Теорема. Кількість булевих функцій від n змінних дорівнює 22 . Доведення. Таблиця задання булевої функції від n змінних очевидно має 2n рядків. Тому значення булевих функцій виписуються в стовпці, що мають довжину 2n . Використовуючи комбінаторне правило добутку, звідси отримаємо, що всіх булевих функій від n змінних є n 214444 × 2× ... × 2 =3 22 . 4244444 2n разів
2.2. Таблиці основних булевих функцій Серед усіх булевих функцій виділяють деякі основні. Наведемо їх таблиці. Таблиці булевих функцій від однієї змінної (унарних функцій) x 0 1 Назва Позначення нуль 0 0 0 тотожна x 0 1 1 0 заперечення x одиниця 1 1 1 Таблиці булевих функцій від двох змінних (бінарних функцій) x
y
0
x∧ y
x⊕ y
x∨ y
x↓ y
0 0 1 1
0 1 0 1
0 0 0 0
0 0 0 1
0 1 1 0
0 1 1 1
1 0 0 0
x↔ y x→ y 1 0 0 1
1 1 0 1
Назви булевих функцій від двох змінних Назва нуль кон’юнкція
Позначення 0 x∧ y
x| y
1
1 1 1 0
1 1 1 1
Юрій Матурін
21 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
x⊕ y x∨ y
додавання за модулем 2 диз’юнкція стрілка Пірса еквіваленція імплікація штрих Шеффера одиниця
x↓ y x↔ y x→ y x| y 1
Очевидно, що тоді x = 1 − x , x ∨ y = max ( x, y ) , x ∧ y = min ( x, y ) , x, y ∈ Ω . 2.3. Деякі типи булевих функцій Означення.
Булева
функція
f * ( x1 , x2 ,..., xn )
називається
дуальною до булевої функції f ( x1 , x2 ,..., xn ) , якщо вона задається наступною формулою:
(
)
f * ( x1 , x2 ,..., xn ) := f x1 , x2 ,..., xn . Означення. Булева функція f ( x1 , x2 ,..., xn ) називається самодуальною, якщо вона дорівнює своїй дуальній функції. Означення. Кажуть, що булева функція f ( x1 , x2 ,..., xn ) зберігає 0
[1], якщо f ( 0,0,...,0 ) = 0 [ f (1,1,...,1) = 1 ].
Означення. Кажуть, що булева функція f ( x1 , x2 ,..., xn ) є монотонною, якщо виконується наступна умова: ∀a1 , a2 ,..., an , b1 , b2 ,..., bn ∈ Ω : a1 ≤ b1 & a2 ≤ b2 & ... & an ≤ bn → f ( a1 , a2 ,..., an ) ≤ f ( b1 , b2 ,..., bn ) . Означення. Кажуть, що булева функція f ( x1 , x2 ,..., xn ) є лінійною, якщо вона має наступний вигляд: f ( x1 , x2 ,..., xn ) = c0 ⊕ (c1 ∧ x1 ) ⊕ (c2 ∧ x2 ) ⊕ ... ⊕ (cn ∧ xn ) , де c0 , c1 , c2 ,..., cn ∈ Ω .
Юрій Матурін
22 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Тут використано асоціативність додавання за модулем 2. Будемо розглядати наступні множини (класи) булевих функцій: 1) T0 – множина всіх функцій, що зберігають 0; 2) T1 – множина всіх функцій, що зберігають 1; 3) T* – множина всіх самодуальних функцій; 4) T≤ – множина всіх монотонних функцій; 5) TL – множина всіх лінійних функцій. Приклади. 1) Розглянемо дуальну до даної функції f ( x1 , x2 , x3 ) . x1
x2
x3
f ( x1 , x2 , x3 )
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 0 1 1 0 1
f * ( x1 , x2 , x3 ) 0 1 0 0 1 0 0 0
Тут легко бачити, що значення дуальної булевої функції є запереченнями значень даної булевої функції, записаних в зворотному порядку. 2) Тепер розглянемо приклад самодуальної функції f ( x1 , x2 , x3 ) : x1
x2
x3
f ( x1 , x2 , x3 )
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 0 0 1 0 1 1 0
f * ( x1 , x2 , x3 ) 1 0 0 1 0 1 1 0
Юрій Матурін
23 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
3) Монотонні функції досить легко будувати, маючи елементарні уявлення про будову скінченних булевих алгебр (кожна така алгебра за відомою теоремою Стоуна є ізоморфною до алгебри всіх підмножин скінченної множини). Кожний ненульовий елемент такої алгебри є диз’юнкцією скінченного числа її атомів. Для функцій, залежних від трьох змінних, відповідна булева алгебра інтерпретується як сукупність вершин деякого куба (діаграма Гассе). Атомами цієї алгебри є впорядковані 3-ки, що складаються з двох 0 і однієї 1. Монотонна функція f ( x1 , x2 , x3 ) : x1
x2
x3
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
f ( x1 , x2 , x3 ) 0 1 0 1 0 1 0 1
4) Розглянемо лінійну функцію f ( x1 , x2 , x3 ) = 1 ⊕ x2 ⊕ x3 . Запишемо тепер її таблично: x1
x2
x3
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
f ( x1 , x2 , x3 ) 1 0 0 1 1 0 0 1
Означення. Будемо говорити, що змінна xi для булевої функції f ( x1 ,..., xi ,..., xn ) є фіктивною, якщо ∀ ( a1 ,..., ai−1 , ai+1 ,..., an ) ∈ Ω n−1 : f ( a1 ,..., ai −1 ,0, ai +1 ,..., an ) = f ( a1 ,..., ai −1 ,1, ai +1 ,..., an ) .
Юрій Матурін
24 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Наприклад, змінна x3 для функції f ( x1 , x2 , x3 ) =
(
)
= x1 ∨ x3 ∧ x3 ∨ x2 є фіктивною. 2.4. Аналітичне задання булевих функцій Означення. Будемо говорити, що булеву функцію f можна аналітично задати (представити) через булеві функції деякої множини G , якщо ця функція має один з наступних виглядів: 1) p , де p – змінна; 2) u (t1 , t2 ,..., tm ) , де u – функція від m змінних, що належить G , t1 , t2 ,..., tm – булеві функції, які можна аналітично задати (представити) через булеві функції множини G . Приклад. Нехай G = {g1 , g 2 } , g1 ( x1 , x2 ) = x1 ⊕ x2 , g 2 ( x1 ) = 1, f ( x1 , x2 , x3 ) = x3 ↔ x1 . Тоді f ( x1 , x2 , x3 ) = x3 ↔ x1 = x3 ⊕ x1 = g1 ( x3 , x1 ) = = 1 ⊕ g1 (1 ⊕ x3 ,1 ⊕ x1 ) = g1 (1, g1 (1 ⊕ x3 ,1 ⊕ x1 )) = g1 (1, g1 ( g1 (1, x3 ), g1 (1, x1 ))) = = g1 ( g 2 ( x1 ), g1 ( g1 ( g 2 ( x1 ), x3 ), g1 ( g 2 ( x1 ), x1 ))) . Отже, f можна аналітично задати через булеві функції множини G . Розглянемо наступне позначення: a, b = 0, a b := , де a, b ∈ Ω . a, b = 1 0, a ≠ b, Зрозуміло, що a b = , де a, b ∈ Ω , тобто a b = a ↔ b . 1, a = b Теорема 1. Будь-яку булеву функцію f ( x1 , x2 ,..., xn ) , яка тотожно не дорівнює 0, можна задати аналітично за допомогою кон’юнкції, диз’юнкції і заперечення, подавши її у вигляді дднф: f ( x1 , x2 ,..., xn ) =
∨)
( a1 ,a2 ,...,an
∈Ω n
(x
a1 1
)
∧ x2a2 ∧ ... ∧ xnan .
f ( a1 , a2 ,..., an ) =1
Доведення. Розглянемо довільний набір ( c1 , c2 ,..., cn ) ∈ Ω n . Тоді можливі наступні випадки:
Юрій Матурін
25 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
1) f ( c1 , c2 ,..., cn ) = 0 або 2) f ( c1 , c2 ,..., cn ) = 1 .
1) Нехай f ( c1 , c2 ,..., cn ) = 0 . Тоді для довільного набору
( a1 , a2 ,..., an ) ∈ Ωn , на якому f ( a1 , a2 ,..., an ) = 1 , ( c1 , c2 ,..., cn ) ≠ ( a1 , a2 ,..., an ) .
Отже, ∃k ∈ {1, 2,..., n}: ak ≠ ck . Звідси маємо, що ck k = 0 . Тому a
c1a1 ∧ c2a2 ∧ ... ∧ 0 ∧ ... ∧ cnan = 0 . Тоді
∨)
( a1 ,a2 ,...,an
∈Ω
(c
a1 1
n
)
∧ c2a2 ∧ ... ∧ cnan =
f ( a1 , a2 ,..., an ) =1
∨)
( a1 ,a2 ,...,an ∈Ω
n
0 = 0 = f ( c1 , c2 ,..., cn ) .
f ( a1 , a2 ,..., an ) =1
2) Нехай f ( c1 , c2 ,..., cn ) = 1 . Очевидно, що c1c1 ∧ c2c2 ∧ ... ∧ cncn = 1. Отже,
∨)
( a1 ,a2 ,...,an ∈Ωn f ( a1 ,a2 ,...,an )=1
(
(c
a1 1
)
∧ c2a2 ∧ ... ∧ cnan =
)
∨ c1c1 ∧ c2c2 ∧ ... ∧ cncn =
∨)
( a1 ,a2 ,...,an ∈Ωn f ( a1 ,a2 ,...,an )=1 ( a1 ,a2 ,...,an )≠( c1 ,c2 ,...,cn )
∨)
( a1 ,a2 ,...,an ∈Ωn f ( a1 ,a2 ,...,an )=1 ( a1 ,a2 ,...,an )≠( c1 ,c2 ,...,cn )
(c
(c
a1 1
a1 1
)
∧ c2a2 ∧ ... ∧ cnan ∨
)
∧ c2a2 ∧ ... ∧ cnan ∨
∨1 = 1 = f ( c1 , c2 ,..., cn ) . Теорему доведено.
Теорема 2. Будь-яку булеву функцію f ( x1 , x2 ,..., xn ) , яка тотожно не дорівнює 1, можна задати аналітично за допомогою кон’юнкції, диз’юнкції і заперечення, подавши її у вигляді дкнф: a a a f ( x1 , x2 ,..., xn ) = ∧ x1 1 ∨ x2 2 ∨ ... ∨ xn n . ( a1 ,a2 ,...,an )∈Ωn f ( a1 ,a2 ,...,an )=0
(
)
Ця теорема має доведення подібне до доведення попередньої теореми. Приклад. Булева функція f ( x1 , x2 , x3 ) задана таблицею істинності: x1 x2 x3 f ( x1 , x2 , x3 ) 0 0 0 0
0 0 1 1
0 1 0 1
1 0 1 0
Юрій Матурін
26 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 Побудуємо для неї дднф і дкнф. f ( x1 , x2 , x3 ) = x10 ∧ x20 ∧ x30 ∨ x10 x12 x30 ∨ x11 x20 x30 ∨ x11 x12 x30 = = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 (дднф);
(
) (
) (
) (
)
f ( x1 , x2 , x3 ) = x10 ∨ x20 ∨ x31 ∧ x10 ∨ x12 ∨ x31 ∧ x11 ∨ x20 ∨ x31 ∧ x11 ∨ x12 ∨ x31 =
(
) (
) (
) (
)
= x1 ∨ x2 ∨ x 3 ∧ x1 ∨ x 2 ∨ x3 ∧ x1 ∨ x2 ∨ x 3 ∧ x1 ∨ x 2 ∨ x 3 (дкнф). 2.5. Замикання та замкненість множин булевих функцій Означення. Замиканням множини G булевих функцій називається множина [G ] булевих функцій, яка складається з усіх тих і лише тих булевих функцій, які можуть бути аналітично представлені через функції самої множини G . Основні властивості замикання 1. G ⊆ [G ] ; 2. [[G ]] = [G ] ; 3. G1 ⊆ G2 → [G1 ] ⊆ [G2 ] ; 4. [G1 ] U [G2 ] ⊆ [G1 U G2 ] . Означення. Множина G булевих функцій називається замкненою, якщо вона дорівнює своєму замиканню ( G = [G ] ). Приклади замкнених множин булевих функцій 1) множина T0 всіх функцій, що зберігають 0; 2) множина T1 всіх функцій, що зберігають 1; 3) множина T* всіх самодуальних функцій; 4) множина T≤ всіх монотонних функцій; 5) множина TL всіх лінійних функцій.
Юрій Матурін
27 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Те, що дані множини є замкненими, доводиться нескладно. Пропонуємо читачам у вигляді вправи довести це. 2.6. Повнота множин булевих функцій Означення. Множина G булевих функцій називається повною, якщо всяку булеву функцію можна аналітично представити через функції цієї множини, тобто якщо P = [G ] . Теореми 1-2 підрозділу 2.4 показують, що множина {∨, ∧, −} є повною. Сформулюємо очевидне Твердження. Нехай G – повна множина булевих функцій. Якщо кожну функцію цієї множини можна аналітично представити через функції деякої множини K булевих функцій, то і множина K є повною. Приклади. Використаємо це твердження для отримання інших повних множин. 1) Множина {∨, −} є повною, оскільки a ∧ b = a ∨ b і {∨, ∧, −} – повна множина. 2) Множина {∧, −} є повною, оскільки a ∨ b = a ∧ b і {∨, ∧, −} – повна множина. 3) Множина {|} є повною. Справді, легко бачити, що a | b = a ∨ b . Далі, a = a | a і a ∨ b = (a | a ) | (b | b) . 4) Множина {↓} є повною. Справді, легко бачити, що a ↓ b = a ∧ b . Далі, a = a ↓ a і a ∧ b = (a ↓ a ) ↓ (b ↓ b) . Теорема (Пост). Множина G булевих функцій є повною тоді й тільки тоді, коли вона містить хоча б одну функцію, що не зберігає 0, хоча б одну функцію, що не зберігає 1, хоча б одну несамодуальну функцію, хоча б одну немонотонну функцію й хоча б одну нелінійну функцію: [G ] = P ↔ G ⊆ T0 ∨ G ⊆ T1 ∨ G ⊆ T* ∨ G ⊆ T≤ ∨ G ⊆ TL .
Юрій Матурін
28 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Доведення цієї теореми є досить громіздким і опускається. Приклади. 1) Розглянемо множину {∨, ∧}. Обидві функції цієї множини зберігають 0 і 1. Тому за теоремою Поста дана множина є неповною. 2) Множина {∨} також є неповною, оскільки неповною є попередня множина. 2.7. Означення релейно-контактних схем Тут у спрощеному варіанті введемо в розгляд поняття релейноконтактної схеми. Під релейно-контактною схемою (РКС) будемо розуміти сукупність перемикачів, які можуть працювати в двох станах: пропускати або не пропускати струм, що з’єднуються між собою провідниками (здебільшого будемо розглядати лише паралельне або послідовне поєднання). Таким чином, ми отримуємо певне електричне коло, по якому струм може протікати (стан 1) або не протікати (стан 0) в залежності від стану перемикачів. Розглядаємо два типи перемикачів: 1) — a — означає, що струм протікає, якщо a = 1 і не протікає, коли a=0 ; 2) — a — означає, що струм протікає, якщо a = 0 і не протікає, якщо a = 1. РКС будемо приписувати значення 1, якщо струм протікає і значення 0, якщо струм не протікає. Приклад. Розглянемо наступну РКС: a c
a
b 2.8. Реалізація булевих функцій Кожну РКС можна інтерпретувати як деяку булеву функцію.
Юрій Матурін
29 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Відповідну булеву функцію називають функцією провідності, що відповідає РКС. Розглянемо основні елементи РКС та їх очевидну інтерпретацію: a —— a ——
—— a ——
a
a
a∨b b a∧b
—— a —— b ——
Це дає можливість для кожної РКС записати відповідну функцію провідності. Повертаючись до прикладу, зобразимо функцію провідності аналітично: f ( a, b, c ) = ( a ∨ b ) ∧ c ∧ a . Навпаки, очевидно, що кожну булеву функцію можна реалізувати у вигляді РКС (див. теореми 1–2 п.2.4). Наприклад, f ( a, b, c ) = a ∨ b ∨ c d d ∨ a ∨ a .
(
a b
) (
)
d d a
c
a Означення. Будемо говорити, що дві РКС є рівносильні (еквівалентні), якщо вони мають рівні функції провідності.
Юрій Матурін
30 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Очевидно, що відношення рівносильності на множині всіх РКС є відношенням еквівалентності. 2.9. Спрощення релейно-контактних схем Для того, щоб спростити РКС, ми повинні записати відповідну функцію провідності – її аналітичний вираз, спростити його і по новому виразу будувати спрощену РКС, яка буде рівносильна попередній. Приклад. a
a
(1) b
b
(
)
f ( a, b ) = ( a ∨ b ) ∧ a ∨ b = a —— a ——
(2)
(1) рівносильна (2). 2.10. Застосування релейно-контактних схем до побудови однорозрядного двійкового суматора Знайдемо цифру i -го розряду суми двох цілих невід’ємних чисел, записаних у двійковій системі: xn ...x2 x1 x02 + yn ... y2 y1 y02 = zn+1 zn ...z2 z1 z02 . Для цього нам потрібне число pi , яке переноситься в i -ий розряд. xi
yi
pi
zi
pi +1
0
0
0
0
0
0
0
1
1
0
Юрій Матурін
31 Елементи математичної логіки і теорії алгоритмів. Частина 1
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
א
zi = x i y i pi ∨ xi yi p i ∨ xi y i p i ∨ xi yi pi , pi +1 = xi yi pi ∨ xi y i pi ∨ xi yi p i ∨ xi yi pi = yi pi ∨ xi pi ∨ xi yi = = ( yi ∨ xi ) pi ∨ yi xi , xi − y i − pi xi − yi − pi
zi
xi − y i − pi
xi − yi − pi xi
pi
pi +1
yi xi − yi Такими чином, маємо схеми, що реалізують додавання в одному розряді. Отже, ми отримали можливість побудови однорозрядного двійкового суматора за допомогою РКС.
Юрій Матурін
32 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
3. ЗАВДАННЯ 3.1. Запитання для самоконтролю 1. Наведіть приклади висловлень, які зустрічаються в математиці. 2. Сформулюйте означення логічних дій над висловленнями (заперечення, кон’юнкція, диз’юнкція, імплікація, еквіваленція). 3. Запишіть таблиці істинності для логічних дій над висловленнями. 4. Запишіть означення формули алгебри висловлень. 5. Сформулюйте означення тавтології, суперечності, виконуваної формули та нейтральної формули в алгебрі висловлень. 6. Наведіть приклади тавтологій, суперечностей, виконуваних та нейтральних формул. 7. Сформулюйте означення рівносильних формул алгебри висловлень. 8. Наведіть приклади рівносильних формул алгебри висловлень та поясність, чому вони рівносильні. 9. Сформулюйте означення логічного слідування на базі алгебри висловлень. 10. Наведіть приклади логічного слідування. 11. Сформулюйте теорему, що є оберненою до теореми Піфагора. Чи вона має місце? 12. Які методи доведення теорем ви знаєте? Відповідь поясніть. 13. Запишіть означення елементарної кон’юнкції та диз’юнкції. 14. Сформулюйте означення днф та кнф. 15. Сформулюйте означення дднф та дкнф. 16. Наведіть приклади днф, кнф, дднф, кнф. Відповідь поясніть. 17. Запишіть алгоритми для зведення формули алгебри висловлень до рівносильної днф і рівносильної кнф. У чому їх відмінність? 18. Запишіть означення булевої функції. 19. Наведіть приклади булевих функцій від однієї, двох та трьох змінних. 20. Запишіть таблиці для штриха Шеффера, стрілки Пірса та додавання за модулем 2. 21. Запишіть означення функції, яка є дуальною для даної булевої функції. 22. Наведіть приклади дуальних функцій. 23. Запишіть означення булевої функції, яка є самодуальною. 24. Наведіть приклади самодуальних функцій.
Юрій Матурін
33 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
25. Запишіть означення монотонної та лінійної функцій. 26. Наведіть приклади монотонних та лінійних функцій. 27. Запишіть означення функцій, що зберігають 0 і 1. 28. Наведіть приклади функцій, що зберігають 0 і 1. 29. Поясніть, що таке аналітичне задання булевої функції. 30. Сформулюйте та доведіть теореми про аналітичне зображення булевих функцій у вигляді дднф та дкнф. 31. Сформулюйте означення замикання множини булевих функцій. 32. Сформулюйте означення замкненої множини булевих функцій. 33. Сформулюйте і поясніть властивості замикання. 34. Сформулюйте означення повної множини булевих функцій. 35. Сформулюйте теорему Поста. 36. Наведіть приклади повних та неповних множин булевих функцій. 37. Сформулюйте означення РКС. 38. Наведіть приклади РКС. 39. Поясніть, як будь-якій булевій функції можна поставити у відповідність РКС. 40. Чи єдина РКС відповідає заданій булевій функції? Відповідь обґрунтуйте. 41. Поясніть побудову однорозрядного двійкового суматора. 3.2. Вправи та задачі теоретичного характеру 1. Чи існують такі висловлення A, B, C , щоб одночасно були виконані наступні умови: a). B → A = 1 , A → C = 0 , ( A → C ) ∧ B = 0 ; b). B → A = 0 , C → A = 1, A ∧ B ∧ C = 1 ; c). A ↔ C = 0 , A ∨ B ∨ C = 0 , A → C = 0 . 2. Доведіть теорему про оборотність системи двох імплікацій: якщо істинні висловлення A1 → B1 , A2 → B2 , A1 ∨ A2 , B1 ∧ B2 , то істинні також і висловлення B1 → A1 , B2 → A2 . 3. Доведіть теорему про оборотність системи m імплікацій: якщо істинні висловлення A1 → B1 ,…, Am → Bm , A1 ∨ ... ∨ Am , Bi ∧ B j , i ≠ j , i, j = 1,..., m , то істинні також і висловлення B1 → A1 ,…, Bm → Am . 4. Доведіть основні рівносильності, наведені в п. 1.3. 5. Доведіть, що наступні формули є тавтологіями:
Юрій Матурін
(
34 Елементи математичної логіки і теорії алгоритмів. Частина 1
(
א
))
a). P → Q ∧ Q → P ;
(( P → Q ) ∧ (Q → R )) → ( P → R ) ; c). ( ( P → Q ) ∨ R ) ↔ ( P → ( Q ∨ R ) ) .
b).
6. Доведіть, що якщо формули P, P → Q є тавтологіями, то формула Q також є тавтологією.
7. Доведіть, що якщо формули G ∧ H , F ∨ G є тавтологіями, то формула F → H також є тавтологією. 8. Чи має місце логічне слідування: a). P → Q, P → Q ˫ P ; b). P → Q, P ˫ Q ; c). P → Q, Q ˫ P . 9. Перетворити наступні формули алгебри висловлень у рівносильні, звівши число логічних дій до m : a). A → B ∧ AB ∨ B , m = 1; b). AB ∨ BC ∨ B , m = 1; c). AB ∨ AB ∨ AB , m = 1; d). ( A ∨ B )( B → A) ∨ AC , m = 0 ; e). ( A → B) → B , m = 1; f). ( A → B)( A ∨ BC )( A → C ) ∨ C , m = 1; g). A → B ∨ C → B ∨ B , m = 2 ; h). ( A ∨ B )( B → A) ∨ BC ∨ AB ∨ BC , m = 1; i). AB ∨ AB ∨ AB , m = 1; j). AC ∨ BC ∨ AB ∨ AC , m = 2 ; k). ( A ∨ ( B → C ))( A ∨ B ∨ C )( A ∨ C ∨ D) , m = 1; l). ABC ∨ ABC ∨ ABC , m = 2 ; m). (( B ∨ C ) → BCD) ∨ BD , m = 2 ; n). AB ∨ AC ∨ ( A → B ) ∨ A ∨ BC , m = 1; o). C → B ∨ BA ∨ BC → B , m = 1. 10. Звести наступні формули алгебри висловлень до рівносильних днф і кнф: a). ( A → B ) → ( B → A) ; b). ( A ↔ B ) ∨ A ;
Юрій Матурін
(
35 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
)
c). A ∨ B ∧ ( B → A) . 11. Звести наступні формули алгебри висловлень до рівносильних дднф і дкнф відносно пропозиційних змінних A1 , A2 , A3 : a). ( A1 ∧ A2 ) → A3 ;
( ) c). ( A ↔ A ) ∨ A .
b). A1 → A2 ↔ A3 ; 1
2
3
12. Знайдіть з точністю до рівносильності всі можливі формули F ( X , Y , Z ) від трьох змінних X , Y , Z , щоб мало місце наступне логічне слідування: X → Y ˫ ( X ↔ F ) ↔ (Y ∨ Z ) . 13. Чи має імплікація властивості комутативності та асоціативності? 14. Доведіть, що мають місце наступні рівності: a). x = x ⊕ 1 ; b). x ∨ y = x ⊕ y ⊕ ( x ∧ y ) ; c). x → y = ( x ∧ y ) ⊕ x ⊕ 1; d). x ↔ y = x ⊕ y ⊕ 1 ; e). ( x | y ) = ( x ∧ y ) ⊕ 1 ; f). ( x ↓ y ) = ( x ∧ y ) ⊕ x ⊕ y ⊕ 1; g). x → y = ( x | ( y | y ) ) .
15. Доведіть, що існує точно 2n+1 лінійних булевих функцій від n змінних. 16. Побудуйте таблиці для всіх лінійних булевих функцій від 2 змінних. 17. Для кожної булевої функції від однієї змінної знайдіть дуальну до неї функцію. 18. Для кожної булевої функції від двох змінних знайдіть дуальну до неї функцію. 19. Знайдіть усі самодуальні булеві функції від однієї та двох змінних. 20. Доведіть, що булева функція ( x ∧ y ) ⊕ ( x ∧ z ) ⊕ ( y ∧ z ) ⊕ y ⊕ z є самодуальною. 21. Доведіть, що функція pn ( x1 ,..., xn ) = x1 ⊕ ... ⊕ xn є самодуальною тоді й тільки тоді, коли n непарне. 22. Яка кількість усіх самодуальних булевих функцій від n змінних.
Юрій Матурін
36 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
23. Доведіть монотонність наступних булевих функцій: a). ( x ∧ y ∧ z ) ⊕ ( x ∧ y ) ⊕ ( x ∧ z ) ;
(
) (
)
b). ( x ∧ y ∧ z ) ∨ x ∧ y ∧ z ∨ x ∧ y ∧ z .
24. Доведіть, що всяка замкнена множина булевих функцій, що відмінна від множини всіх булевих функцій, є підмножиною однієї з наступних множин: T0 , T1 , T* , T≤ , TL . 25. Довести, що дані множини булевих функцій є повними: a).{→, −} ; b). {⊕, ∧,1} ; c). {⊕, ∨,1} ; d). {↔, ∧,0}; e). {→ / , −} , де a → / b = a → b; f). {→ / ,1} , де a → / b = a → b. 26. Довести, що дані множини булевих функцій є неповними: a). {→}; b). {⊕, ∨} ; c). {→, ↔} ; d). {↔,0} (Підказка: показати, що ↔ є лінійною функцією); e). {→,1} ; f). {↔,1}. 27. Побудувати РКС для наступних булевих функцій: a).
(( x ∧ y ∧ z ) ∨ ( x ∧ z )) ∨ y ;
b). x ⊕ ( y ↓ z ) ;
c). x ↔ ( y | z ) . 28. Дано функцію провідності РКС. Спростити її до m контактів. a). ( a ∧ b ∧ c ) ∨ a ∧ b ∧ c ∨ a ∧ b ∧ c , m = 3 ;
(
) (
)
( ) ( ) c). ( a ∧ b ∧ c ) ∨ ( a ∧ b ) ∨ ( b ∧ c ) ∨ b , m = 3 ; d). ( a ∨ b ∨ c ) ∧ ( a ∨ b ∨ d ) ∧ ( a ∨ b ∨ d ) ∧ ( a ∨ b ∨ c ) , m = 3 ; e). ( a ∨ b ) ∧ ( a ∨ c ) ∧ ( b ∨ c ) , m = 4 ; f). ( a ∨ b ) ∧ ( b ∨ c ) ∧ ( a ∨ c ) , m = 4 ; b). a ∨ b ∧ a ∨ b ∧ ( a ∨ ( b ∧ c ) ) , m = 2 ;
Юрій Матурін
37 Елементи математичної логіки і теорії алгоритмів. Частина 1
(
)
) (
)
א
g). ( a ∧ b ) ∨ ( b ∧ c ) ∨ a ∧ c , m = 4 ;
h). ( a ∨ b ∨ c ) ∧ ( b ∨ d ) ∧ ( a ∨ c ∨ e ) ∧ ( d ∨ e ) , m = 5 ;
(
) (
(
)
i). a ∨ b ∧ a ∨ c ∧ c ∨ b ∧ ( a ∨ c ) ∧ b ∨ c , m = 3 . 3.3. Вправи та задачі розрахункового характеру
1. Дано таблиці істинності для формул алгебри висловлень Y1 ( A1 , A2 ) , Y2 ( A1 , A2 ) , Y3 ( A1 , A2 ) . Записати відповідні дднф та дкнф, рівносильні до даних формул. A1
A2
0 0 1 1
0 1 0 1
Y1 ( A1 , A2 ) 1 0 1 0
Y2 ( A1 , A2 ) 0 1 0 1
Y3 ( A1 , A2 ) 0 0 0 1
2. Дано таблиці істинності для формул алгебри висловлень F ( A1 , A2 , A3 ) , G ( A1 , A2 , A3 ) . Записати відповідні дднф та дкнф, рівносильні до даних формул. A1
A2
A3
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
F ( A1 , A2 , A3 ) G ( A1 , A2 , A3 ) 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0
3. Дано наступні таблиці істинності для формул F1 ( A1 , A2 , A3 ) , F2 ( A1 , A2 , A3 ) , висловлень:
F3 ( A1 , A2 , A3 ) ,
G1 ( A1 , A2 , A3 ) , G2 ( A1 , A2 , A3 )
алгебри
Юрій Матурін
38 Елементи математичної логіки і теорії алгоритмів. Частина 1
A1 0 0 0 0 1 1 1 1
A2 0 0 1 1 0 0 1 1
A3 0 1 0 1 0 1 0 1
F1 1 0 1 0 1 1 0 0
F2 0 0 1 0 1 0 0 0
F3 0 1 1 0 1 1 0 1
G1 1 0 1 0 1 1 0 0
G2 1 0 0 0 1 1 0 0
При яких i має місце логічне слідування F1 , F2 , F3 ˫ Gi ? 4. Зобразіть аналітично булеві функції f1 ( x1 , x2 , x3 , x4 ), f 2 ( x1 , x2 , x3 , x4 ) , f 3 ( x1 , x2 , x3 , x4 ), f 4 ( x1 , x2 , x3 , x4 ) , які задані наступною таблицею: x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0
f2 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 0
f3 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1
f4 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
5. Знайдіть множини всіх фіктивних змінних для кожної булевої функції, визначеної в задачі 4.
א
Юрій Матурін
39 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
ІМЕННИЙ ПОКАЖЧИК Аристотель (384 до н.е. – 322 н.е.) – давньогрецький вченийенциклопедист, філософ і логік, засновник класичної (формальної) логіки 4 Банах, Стефан (1892 – 1945) – польський математик, один з творців функціонального аналізу та львівської математичної школи 5 Буль, Джордж (1815 – 1964) – англійський математик 4 Вітгенштейн, Людвіг (1889 – 1951) – англійський філософ, один із засновників аналітичної філософії і один із найяскравіших мислителів XX століття 4 Гассе, Гельмут (1898 – 1979) – німецький математик, працював у галузі алгебраїчної теорії чисел 23 Гедель, Курт (1906 – 1978) – австро-американський логік, математик та філософ науки 4 Ейнштейн, Альберт (1879 – 1955) – американський фізик, один з найвидатніших фізиків усіх часів і народів, творець теорії відносності, нобелівський лауреат, інтернаціоналіст, антифашист, гарячий прихильник ідеї відновлення Ізраїлю у ХХ столітті 5 Кантор, Георг (1845 – 1918) – німецький математик, великий учений, творець теорії множин, що стала наріжним каменем у математиці 5 Карнап, Рудольф (1891– 1970) – німецько-американський філософ та логік, провідний представник логічного позитивізму та філософії науки 4 Лейбніц, Готфрід Вільгельм (1646 – 1716) – провідний німецький філософ, логік, математик, мовознавець та дипломат 4 Мальцев, Анатолій Іванович (1909 – 1967) – радянський учений, основоположник Сибірської школи «Алгебра і Логіка», академік АН СРСР 4 Манін, Юрій Іванович (1937) – визначний російський математик, член-кореспондент РАН, член Королівської академії наук Нідерландів, Французької академії наук, Американської академії мистецтв і наук, почесний доктор університетів – Сорбонни, Університету Осло та Уорикського університету, один з основоположників некомутативної алгебраїчної геометрії і квантової інформатики 5 де Морган, Огастес (1806 – 1871) – англійський математик і логік, перший президент (1866) Лондонського математичного товариства 11
Юрій Матурін
40 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
Пірс, Чарльз Сандерс (1839 – 1914) – американський філософ, логік, математик, основоположник прагматизму та семіотики 21 Подольський, Борис Якович (1896 – 1966) – американський фізиктеоретик 5 Пост, Еміль Леон (1897 – 1954) – американський математик і логік, один із засновників багатозначної логіки 27 Рассел, Бертран (1872 – 1970) – англійський математик, філософ і громадський діяч 4 Рішар, Жуль (1862 – 1956) – французький математик 5 Робінсон, Абрахам (1818 – 1974) – американський математик, творець «нестандартного аналізу» 4 Розен, Натан (1909 – 1995) – американо-ізраїльський фізик-теоретик 5 Стоун, Маршал Гарві (1903 – 1989) – великий американський математик, який зробив значний вклад у розвиток дійсного та функціонального аналізів і в теорію булевих алгебр 23 Тарський (Тайтельбаум), Альфред (1901 – 1983) – американський математик, логік, засновник формальної теорії істинності 4 Уайтхед, Альфред Норт (1861 – 1947) – англійський математик, логік і філософ 4 Фреге, Готлоб (1848 – 1925) – німецький математик, логік і філософ 4 Шеффер, Генрі Моріс (1882 – 1964) – американський логік 21
Юрій Матурін
41 Елементи математичної логіки і теорії алгоритмів. Частина 1
ПРЕДМЕТНИЙ ПОКАЖЧИК атом булевої алгебри 23 булева алгебра 23 булева функція 19 висловлення 7 виконувана формула 10 дднф 16 дкнф 16 днф 16 диз’юнкція 7 додавання за модулем 2 21 дуальна функція 21 еквіваленція 8 замикання 26 замкненість 26 заперечення 7 імплікація 8 кнф 16 кон’юнкція 7 лінійна функція 21 логічні дії 7 логічне слідування 13 монотонна функція 21 повнота 27 рівносильність (еквівалентність) 10, 29 РКС 28 тавтологія 10 тотожноістинна формула 10 тотожнохибна формула 10 самодуальна функція 21 стрілка Пірса 21 суперечність 10 фіктивна змінна 23 формула алгебри висловлень 9 функція провідності 29 функція, що зберігає 0 [1] 21 штрих Шеффера 21
א
Юрій Матурін
42 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
БІБЛІОГРАФІЯ ОСНОВНА ЛІТЕРАТУРА Підручники та посібники з математичної логіки та теорії алгоритмів, рекомендовані студентам педагогічних ВНЗ 1. Беран Л. Упорядоченные множества / Л. Беран; пер. с чеш. — М.: Наука, 1981. — 68 с. 2. Варпаховский Ф.Л. Элементы теории алгоритмов / Ф.Л. Варпаховский. — М.: Просвещение, 1979. — 25 с. 3. Ефремов Г. О. Алгебра логики и контактные схемы / Г. О. Ефремов. — М.: Знание, 1969. — 32 с. 4. Игошин В. И. Математическая логика и теория алгоритмов / В. И. Игошин. — М.: Издательский центр «Академия», 2008. — 453 с. 5. Игошин В. И. Множества и графы / В. И. Игошин, Е.С. Петрова. — Саратов: СГПИ, 1981. — 37 с. 6. Иножарский В. К. Математическая логика и алгоритмы / В. К. Иножарский. — Орел, 1971. — 145 с. 7. Калбертсон Дж. Т. Математика и логика цифровых устройств / Дж. Т. Калбертсон; пер. с англ. — М.: Просвещение, 1965. — 267 с. 8. Калужнин Л. А. Что такое математическая логика? / Л. А. Калужнин. — М.: Наука, 1964. —152 с. 9. Криницкий Н.А. Алгоритмы вокруг нас / Н.А. Криницкий. — М.: Наука, 1984. — 223 с. 10. Лихтарников Л. М. Математическая логика: Курс лекций. Задачникпрактикум и решения / Л. М. Лихтарников, Т. Г. Сукачёва. — СПб.: Лань, 1999. — 288 с. 11. Математическая логика / Под ред. А. А. Столяра. — Минск: Вышэйшая школа, 1991. — 269 с. 12. Матросов В.Л. Теория алгоритмов / В.Л. Матросов. — М.: Прометей, 1989. — 188 с. 13. Матурін Ю.П. Елементи дискретної математики: Навчальний посібник / Ю.П. Матурін. –Дрогобич: Редакційно-видавничий відділ ДДПУ імені Івана Франка, 2009. – 60 с. 14. Мендельсон Э. Введение в математическую логику / Э. Мендельсон: Пер. с англ. —М.: Наука, 1976. — 320 с. 15. Михайлов А. В. Лекции по основам математической логики. Формальные системы первого порядка / А. В. Михайлов, Н.И. Рыжова, М.В. Швецкий. — СПб., 1998. — 164 с. 16. Мощенский В. А. Лекции по математической логике / В. А. Мощенский. — Минск: БГУ, 1973. — 160 с. 17. Нагель Э. Теорема Гёделя / Э. Нагель, Д. Ньюмен; пер. с англ. — М.: Знание, 1970. — 62 с.
Юрій Матурін
43 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
18. Непейвода Н. Н. Прикладная логика / Н. Н. Непейвода. — Ижевск, 1997. — 499 c. 19. Никольская И. Л. Математическая логика / И. Л. Никольская. — М.: Высшая школа, 1981. — 128 c. 20. Новиков П. С. Элементы математической логики / П. С. Новиков. — М.: Наука, 1973. — 400 с. 21. Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков. — СПб.: Питер, 1973. — 302 с. 22. Пензов Ю.Е. Элементы математической логики и теории множеств / Ю.Е. Пензов. — Саратов, 1968. — 143 с. 23. Современные основы школьного курса математики / Н.Я. Виленкин, К.И. Дуничев, Л.А. Калужнин, А.А. Столяр. — М.: Просвещение, 1980. — 240 с. 24. Столл P.P. Множества. Логика. Аксиоматические теории / P.P. Столл; пер. с англ. — М.: Просвещение, 1968. —232 с. 25. Столяр А.А. Элементарное введение в математическую логику / А.А. Столяр. — М.: Просвещение, 1965. —166 с. 26. Трахтенброт В.А. Алгоритмы и вычислительные автоматы / В.А. Трахтенброт. — М.: Советское радио, 1974. — 200 с. 27. Успенский В.А. Вводный курс математической логики / В.А. Успенский, Н.К. Верещагин, В. Б. Плиско. — М.: Физматлит, 2004. — 128 с. 28. Фрейденталь X. Язык логики / X. Фрейденталь; пер. с англ. — М.: Наука, 1969. —136 с. 29. Хромой Я.В. Математична логіка / Я.В. Хромой. — Київ: Вища школа, 1983. — 208 с. 30. Эдельман С. Л. Математическая логика / С. Л. Эдельман. — М.: Высшая школа, 1975. — 176 с. 31. Энгелер Э. Метаматематика элементарной математики / Э. Энгелер; пер. с нем. — М.: Мир, 1987. — 130 с. Збірники задач 1. Байиф Ж.-К. Логические задачи / Ж.-К Байиф; пер. с фр. — М.: Мир, 1983. — 173 с. 2. Гаврилов Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А.А. Сапоженко. — М.: Наука, 1977. — 370 с. 3. Гиндикин С. Г. Алгебра логики в задачах / С. Г. Гиндикин. — М.: Наука, 1972. — 289 с. 4. Гохман А. В. Сборник задач по математической логике и алгебре множеств / А. В. Гохман, М.А. Спивак, В. В. Розен. — Саратов: Саратовский университет, 1969. — 91 с. 5. Драбкина М. Е. Логические упражнения по элементарной математике / М. Е. Драбкина. — Минск: Высшая школа, 1965. — 160 с. 6. Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов / В. И. Игошин. — М.: Издательский центр «Академия», 2007. — 305 с.
Юрій Матурін
44 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
7. Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л.Л. Максимова. — М.: Физматлит, 2004. — 256 с. 8. Михайлов А. В. Упражнения по основам математической логики. Формальные системы первого порядка / А. В. Михайлов, Н.И. Рыжова, М.В. Швецкий. — СПб., 1997. — 127 с. 9. Хромой Я.В. Збірник вправ і задач з математичної логіки / Я.В. Хромой. — Київ: Вища школа, 1978. — 160 с. 10. Шапиро С. И. Решение логических и игровых задач / С. И. Шапиро. — М.: Радио и связь, 1984. — 155 с.
ДОДАТКОВА ЛІТЕРАТУРА Логіка 1. Аристотель. Сочинения: В 4 т / Аристотель. — М., 1976—1981. 2. Ахманов А. С. Логическое учение Аристотеля / А. С. Ахманов. — М. Изд.-во социально экономической литературы, 1960. — 302 с. 3. Бойко А. П. Занимательная логика (задачи и упражнения) / А. П. Бойко. — М.: Спектр -5, 1994. — 144 с. 4. Бойко А. П. Краткий курс логики / А. П. Бойко. — М., 1995. — 43 с. 5. Бочаров В. А. Аристотель и традиционная силлогистика / В. А. Бочаров. — М.: МГУ, 1984. — 133 с. 6. Гетманова А. Д. Логика / А. Д. Гетманова. — М.: Высшая школа, 1986. — 288 с. 7. Гетманова А.Д. Логика (10—11 классы) / А.Д. Гетманова, А. А. Никифоров, М. И. Панов. — М., 1995. — 256 с. 8. Горский Д. П. Логика / Д. П. Горский. — М.: Учпедгиз, 1963. — 292 с. 9. Горский Д. П. Краткий словарь по логике / Д. П. Горский, А.А. Ивин, А.А. Никифоров. — М.: Просвещение, 1991. — 207 с. 10. Зегет В. Элементарная логика / В. Зегет; пер. с нем. — М.: Высшая школа, 1985. — 256 с. 11. Ивин А. А. Строгий мир логики / А. А. Ивин. — М.: Педагогика, 1988. — 126 с. 12. Ивин А.А. Искусство правильно мыслить / А. А. Ивин. — М.: Просвещение, 1990. — 224 с. 13. Ивлев Ю. В. Курс лекций по логике / Ю. В. Ивлев. — М.: МГУ, 1988. — 159 с. 14. Игошин В. И. Логика с элементами математической логики / В. И. Игошин. — Саратов: Научная книга, 2004. — 143 с. 15. Кириллов В. И. Логика / В. И. Кириллов, А. А. Старченко. — М.: Высшая школа, 1987. — 270 с. 16. Логика / Под. ред. Г.А. Левина. — Минск, 1974. 17. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики / Я. Лукасевич; пер. с англ. — М.: ИЛ, 1959. — 290 с. 18. Мельников В.Н. Логические задачи / В.Н. Мельников. — Киев; Одесса: Вища школа, 1989. — 344 с. 19. Переверзев В. Н. Логистика: Справочная книга по логике / В. Н. Переверзев. — М.: Мысль, 1995. — 222 с. 20. Розен В.В. Дедуктивные умозаключения / В.В. Розен. — Саратов: Саратовский госуниверситет, 1990. — 51 с. 21. Смирнов В.А. Погружение силлогистики в исчисление предикатов // Логическая семантика и модальная логика. — М., 1967. — С. 254 —258. 22. Субботин А. Л. Теория силлогистики в современной формальной логике / А. Л. Субботин. — М.: Наука, 1965. — 124 с.
Юрій Матурін
45 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
23. Субботин А. Л. Традиционная и современная формальная логика / А. Л. Субботин. — М.: Наука, 1969. — 160 с. 24. Упражнения по логике / Под ред. В. И. Кириллова. — М.: Высшая школа, 1990. — 159 с. Логіка і наука. Основи математики 1. Босс В. Лекции по математике. Т.6: От Диофанта до Тьюринга / В. Босс. – Москва: КомКнига, 2006. — 208 с. 2. Босс В. Лекции по математике. Т.12: Контрпримеры и парадоксы / В. Босс. – Москва: КомКнига, 2009. — 216 с. 3. Вейль Г. Математика и логика: Пер. с англ. // Математика. Теоретическая физика. — М.: Наука, 1984. — С. 328—340. 4. Гетманова А. Д. О соотношении математики и логики //Логические исследования. — М.: АН СССР, 1959. — С. 194. 5. Гильдерман Ю.И. Вооружившись интегралом / Ю.И. Гильдерман. — Новосибирск: Наука, 1980. — 192 с. 6. Гончаров С. С., Ершов Ю.Л., Самохвалов К. Ф. Введение в логику и методологию науки (программа "Обновление гуманитарного образования в России"), М., Интерпракс, Н., ИМ СО РАН, 1994. — 255 с. 7. Зиновьев А. А. Основы логической теории научных знаний / А. А. Зиновьев. — М., 1967. — 261 с. 8. Йех Т. Теория множеств и метод форсинга / Т. Йех; пер. с англ. — М.: Мир, 1973. — 152 с. 9. Кац М. Математика и логика (ретроспектива и перспектива) / М. Кац, С.Улам; пер. с англ. — М.: Мир, 1971. — 252 с. 10. Колмогоров А. Н. К логическим основам теории информации и теории вероятностей // Проблемы передачи информации. — М., 1969. Т. 5. Вып. 3. — С. 3 — 7. 11. Копнин П. В. Логические основы науки / П. В. Копнин. — Киев: Наукова думка, 1968. — 284 с. 12. Коэн П.Дж. Теория множеств и континуум-гипотеза / П.Дж. Коэн; пер. с англ. — М.: Мир, 1969. — 347 с. 13. Куратовский К. Теория множеств / К. Куратовский, А. Мостовский; пер. с англ. — М.: Мир, 1970. — 416 с. 14. Кусраев А. Г. Булевы алгебры и булевозначные модели // Соросовский образовательный журнал. — 1997. — № 9. — С. 116—122. 15. Ледли Р., Ластед Л. Медицинская диагностика и методы выбора решений: Пер. с англ. // Математические проблемы в биологии. — М., 1966. — С. 141—198. 16. Логическая структура научного знания / Сб. статей под ред. П. В.Таванец. — М.: Наука, 1965. —350 с. 17. Беискашова Е. В. Идеи нестандартного анализа в истории науки и в преподавании // Математика в школе. — 1999. — № 3. — С. 76—79. 18. Применения логики в науке и технике / Сб. статей под ред. П. В. Таванец. — М., 1960. 19. Расёва Е. Математика метаматематики / Е. Расёва, Р. Сикорский; пер. с англ. — М.: Наука, 1972. — 592 с. 20. Рвачёв В.Л. Геометрические приложения алгебры логики / В.Л. Рвачёв. — Киев: Техника, 1967. — 212 с. 21. Сикорский Р. Булевы алгебры / Р. Сикорский; пер. с англ. — М.: Мир, 1969. — 376 с. 22. Смирнов В. А. Логические методы анализа научного знания / В.А. Смирнов. — М.: Наука, 1987. — 256 с. 23. Тарский А. Введение в логику и методологию дедуктивных наук / А. Тарский; пер. с англ. — М.: ИЛ, 1948. — 163 с. 24. Успенский В.А. Что такое нестандартный анализ? / В.А. Успенский — М.: Наука, 1987. — 128 с.
Юрій Матурін
46 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
25. Формальная логика и методология науки / Сб. статей под ред. П.В. Таванец. — М., 1964. 26. Френкель А. Основания теории множеств / А. Френкель, И. Бар-Хиллел; пер. с англ. — М.: Мир, 1966. — 557 с. Фундаментальні посібники з математичної логіки 1. Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств / Н.К. Верещагин, А. Шень. — М.: МЦНМО, 2002. — 128 с. 2. Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления / Н.К. Верещагин, А. Шень. — М.: МЦНМО, 2002. — 128 с. 3. Верещагин Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции / Н.К. Верещагин, А. Шень. — М.: МЦНМО, 2002. — 192 с. 4. Гильберт Д. Основы теоретической логики / Д. Гильберт, В. Аккерман; пер. с нем. — М.: ИЛ, 1947. — 153 с. 5. Гильберт Д. Основания математики. Логические исчисления и формализация арифметики / Д. Гильберт, П. Бернайс; пер. с англ. — М.: Наука, 1979. — 557 с. 6. Гладкий А. В. Математическая логика / А. В. Гладкий. — М.: Российский государственный гуманитарный университет, 1998. — 479 с. 7. Гудстейн Р.Л. Математическая логика / Р.Л. Гудстейн; пер. с англ. — М.: ИЛ, 1961. — 166 с. 8. Ершов Ю.Л. Математическая логика / Ю.Л. Ершов, Е.А. Палютин. — М.: Наука, 1979. — 337 с. 9. Ершов Ю.Л., Тайманов А.Д., Тайцлин М.А. Элементарные теории // Успехи математических наук. 1965. — Т. 20. — № 4. — С. 37—108. 10. Карри Х. Основания математической логики / Х. Карри; пер. с англ. — М.: Мир, 1969. — 566 с. 11. Кейслер Г. Теория непрерывных моделей / Г. Кейслер, Ч. Чэн; пер. с англ. — М.: Мир, 1977. — 184 с. 12. Клаус Г. Введение в формальную логику / Г. Клаус; пер. с нем. — М.: ИЛ, 1960. — 507 с. 13. Клини С. Введение в метаматематику / С. Клини; пер. с англ. — М.: ИЛ, 1957. — 527 с. 14. Клини С. Математическая логика / С. Клини; пер. с англ. — М.: Мир, 1973. — 241 с. 15. Колмогоров А.Н. Введение в математическую логику / А.Н. Колмогоров, А. Г. Драгалин. — М.: МГУ, 1982. — 120 с. 16. Кондаков Н.И. Логический словарь-справочник / Н.И. Кондаков. — М.: Наука, 1975. — 720 с. 17. Линдон Р. Заметки по логике / Р. Линдон; пер. с англ. — М.: Мир, 1968. — 128 с. 18. Манин Ю. И. Доказуемое и недоказуемое / Ю. И. Манин. — М.: Советское радио, 1979. — 88 с. 19. Марков А. А. Элементы математической логики / А. А. Марков. — М.: МГУ, 1984. — 80 с. 20. Маслов С. Ю. Теория дедуктивных систем и ее применения / С.Ю. Маслов. — М.: Радио и связь, 1986. — 134 с. 21. Слупецкий Е. Элементы математической логики и теории множеств / Е. Слупецкий, Л. Борковский; пер. с пол. — М.: Прогресс, 1965. — 367 с. 22. Смальян Р. Теория формальных систем / Р. Смальян; пер. с англ. — М.: Наука, 1981. — 208 с. 23. Справочная книга по математической логике: В 4 ч.: Пер. с англ.; Под ред. Дж. Барвайса. — М., 1982— 1983. 24. Чёрч А. Введение в математическую логику / А. Чёрч; пер. с англ. — М.: ИЛ, 1960. — 485 с. 25. Шенфилд Дж. Математическая логика / Дж. Шенфилд; пер. с англ. — М.: Наука, 1975. — 265 с.
Юрій Матурін
47 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
26. Яблонский С. В. Функции алгебры логики и классы Поста / С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев. — М.: Наука, 1966. — 120 с. Теорія алгоритмів 1. Булос Дж. Вычислимость и логика / Дж. Булос, Р. Джеффри; пер. с англ. — М.: Мир, 1994. — 397 с. 2. Ершов Ю.Л. Теория нумераций / Ю.Л. Ершов. — М.: Наука, 1977. — 208 с. 3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций / Н. Катленд; пер. с англ. — М.: Мир, 1983. — 255 с. 4. Криницкий Н.А. Алгоритмы вокруг нас / Н.А.Криницкий. — М.: Наука, 1977. — 224 с. 5. Макаренков Ю.А. Что такое алгоритм? / Ю.А. Макаренков, А.А. Столяр — Минск: Народная асвета, 1989. — 128 с. 6. Мальцев А. И. Алгоритмы и рекурсивные функции / А. И. Мальцев. — М.: Наука, 1986. — 367 с. 7. Манин Ю.И. Вычислимое и невычислимое / Ю.И. Манин. — М.: Советское радио, 1980. — 129 с. 8. Марков А. А. Теория алгорифмов / А. А. Марков, Н.М. Нагорный. — М.: Наука, 1984. — 217 с. 9. Машина Тьюринга // Квант. 1992. № 7. 10. Машины Тьюринга и вычислимые функции: Пер. с нем. / Г.-Д. Эббинхауз, Ф.-К. Ман, К.Якобс и др. — М.: Мир, 1972. — 264 с. 11. Минский М. Вычисления и автоматы / М. Минский; пер. с англ. — М.: Мир, 1971. — 366 с. 12. Нагель Э. Теорема Гёделя / Э. Нагель, Дж. Р. Ньюмен; пер. с англ. — М.: Знание, 1970. — 62 с. 13. Петер Р. Рекурсивные функции / Р. Петер; пер. с нем. — М.: ИЛ, 1954. — 264 с. 14. Роджерс X. Теория рекурсивных функций и эффективная вычислимость / X. Роджерс; пер. с англ. — М.: Мир, 1972. — 624 с. 15. Семенов А.Л., Успенский В. А. Математическая логика в вычислительных науках и вычислительной практике // Вестник АН СССР. — 1986. — № 7. — С. 93 — 103. 16.Трахтенброт Б.А. Алгоритмы и вычислительные автоматы / Б.А. Трахтенброт. — М.: Советское радио, 1974. — 200 с. 17. Успенский В. А. Лекции о вычислимых функциях / В. А. Успенский. — М.: Наука, 1960. — 491 с. 18. Успенский В. А. Машина Поста / В. А. Успенский. — М.: Наука, 1988. — 100 с. 19. Успенский В. А. Теорема Гёделя о неполноте / В. А. Успенский. — М.: Наука, 1982. — 114 с. 20. Успенский В. А. Теория алгоритмов: основные открытия и приложения / В. А. Успенский, А.Л. Семенов. — М., 1987. — 288 с. 21. Цейтлін Г.О. Алгебра логіки та конструювання програм. Елементи дискретної математики / Г.О. Цейтлін. — Київ: Наукова думка, 1994. —84 с. Книги, рекомендовані для школярів 1. Бизам Д. Игра и логика (85 логических задач) / Д. Бизам, Я. Герцег; пер. с венг. — М.: Мир, 1975. — 358 с. 2. Бизам Д. Многоцветная логика (175 задач) / Д. Бизам, Я. Герцег; пер. с венг. — М.: Мир, 1978. — 448 с. 3. Гжегорчик А. Популярная логика / А. Гжегорчик; пер. с пол. — М.: Наука, 1972. — 112 с. 4. Депман И. Я. Первое знакомство с математической логикой / И. Я. Депман. — Л.: Знание,
Юрій Матурін
48 Елементи математичної логіки і теорії алгоритмів. Частина 1
א
1965. — 57 с. 5. Жоль К. К. Логика в лицах и символах / К. К. Жоль. — М.: Педагогика — Пресс, 1993. — 256 с. 6. Касаткин В. Н. Элементы кибернетики — школьнику: Сборник упражнений и задач / В. Н. Касаткин, А.Ф. Верлань, И. А. Переход. — Киев: Радянська школа, 1974. — 112 с. 7. Кольман Э. Занимательная логика / Э. Кольман, О. Зих; пер. с чеш. — М.: Наука, 1966. — 127 с. 8. Кутасов А. Д. Элементы математической логики / А. Д. Кутасов. — М.: Просвещение, 1977. — 63 с. 9. Кэррол Л. История с узелками / Л. Кэррол; пер. с англ. — М.: Мир, 1973. — 408 с. 10. Либер А. Е. Двоичная булева алгебра и ее приложения / А. Е. Либер. — Саратов: Саратовский университет, 1966. — 80 с. 11. Мадер В. В. Школьнику об алгебре логики / В. В. Мадер. — М.: Просвещение, 1993. — 128 с. 12. Мадер В. В. Тайны ряда N / В. В. Мадер. — М.: Просвещение, 1995. — 91 с. 13. Хаваш К. Так — логично! / К. Хаваш; пер. с венг. — М.: Прогресс, 1985. — 272 с. 14. Шевченко В.Е. Некоторые способы решения логических задач / В.Е. Шевченко. — Киев: Выща школа, 1979. — 80 с. 15. Яглом И.М. Необыкновенная алгебра / И.М. Яглом. — М.: Наука, 1968. — 76 с.
Юрій Матурін
49 Елементи математичної логіки і теорії алгоритмів. Частина 1
Навчально-методичне видання ЮРІЙ МАТУРІН
ЕЛЕМЕНТИ МАТЕМАТИЧНОЇ ЛОГІКИ І ТЕОРІЇ АЛГОРИТМІВ. ЧАСТИНА 1 НАВЧАЛЬНИЙ ПОСІБНИК ДЛЯ СТУДЕНТІВ ГАЛУЗІ ЗНАНЬ 0402 «ФІЗИКО-МАТЕМАТИЧНІ НАУКИ», НАПРЯМКУ ПІДГОТОВКИ 6.040201 «МАТЕМАТИКА»
א
