Логіка в інформатиці — це напрям досліджень та галузей знань, де логіка застосовується в інформатиці та штучному інтелекті. Використання логіки дуже ефективне в цих областях.Halpern J.Y., Harper R., Immerman N., Kolaitis Ph.G., Vardi M.Y., and Vianu V. On the unususal effectiveness of logic in computer science. — January, 2001 .
Умовно висловлюючись, можна сказати, що комп'ютер складається з матеріальної частини та математичного (програмного) забезпечення, або, використовуючи професійну лексику, з «заліза» і «взуття». І до того, і до іншого має саме безпосереднє відношення математична логіка, ні перше, ні друге без математичної логіки обійтися не можуть.
Область застосування Включаються такі основні застосування:
дослідження в логіці, викликані розвитком комп'ютерних наук. Наприклад, аплікативні обчислювальні системи, теорія обчислень і моделі обчислень;
формальні методи і логіка міркування про поняття. Наприклад, семантична мережаRoussopoulos N.D. A semantic network model of data bases. — TR No 104, Department of Computer Science, University of Toronto, 1976., семантична павутина;
булева логіка і алгебра для розробки апаратного забезпечення комп'ютерів;
розв'язання задач і структурне програмування для розробки прикладних програм і створення складних систем програмного забезпечення
доказове програмування — технологія розробки алгоритмів і програм із доказами правильності алгоритмів;
фундаментальні поняття і уявлення для комп'ютерних наук, які є природною областю для формальної логіки. Наприклад, семантика мов програмуванняScott D.S. The lattice of flow diagrams.-- Lecture Notes in Mathematics, 188, Symposium on Semantics of Algorithmic Languages.-- Berlin, Heidelberg, New York: Springer-Verlag, 1971, pp.~311-372.;
логіка знань і припущень. Наприклад, штучний інтелект;
мова Пролог і логічне програмування для створення баз знань та експертних систем і досліджень у сфері штучного інтелекту;
логіка для опису просторового положення і переміщення;
логіка в інформаційних технологіях. Наприклад, реляційна модель даних, реляційні СКБД, реляційна алгебра, реляційне численняCodd E. F. Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California, 1972.;
логіка обчислень з об'єктами. Наприклад, комбінаторна логіка, суперкомбінаториPeyton Jones S., Eber J.-M., Seward J. Composing contracts: an adventure in financial engineering. — ICFP 2000;
логіка для компілювання програмного коду та його оптимізації. Наприклад, категоріальна абстрактна машина;
логіка для еквівалентного перетворення об'єктів. Наприклад, лямбда-числення;
перевиклад логіки і математики в термінах, зрозумілих фахівцям в комп'ютерних наукахAsperti A, and Longo G. Categories, Types and Structures. Category Theory for the working computer scientist. — M.I.T. Press, 1991 (pp. 1-300).
Цей список продовжує поповнюватися.
Ефективність у комп'ютерних науках На відміну від природничих наук, комп'ютерні науки отримали великий стимул від широкої і безперервної взаємодії з логікою. Особливу роль у комп'ютерних науках відіграють доказові методи розробки алгоритмів і програм з доказами їхньої правильності.
Тестування програм може виявити наявність помилок у програмах, але не може гарантувати їх відсутність. Гарантії відсутності помилок в алгоритмах і програмах можуть дати тільки доведення їх правильності. Алгоритм не містить помилок, якщо він дає правильні розв'язки для всіх допустимих даних.
Серйозною проблемою для комп'ютерних наук та інформатики є наявність помилок в алгоритмах і програмах, що публікуються в підручниках і навчальних посібниках, а також невміння викладачів і вчителів інформатики виявляти і виправляти помилки в алгоритмах і програмах, складених учнями.
Єдиний шлях для подолання цих проблем-це вивчення систематичних методів складання алгоритмів і програм з одночасним аналізом їх правильності в рамках доказового програмування з самого початку навчання основам алгоритмізації і програмування.
Складність для викладачів і програмістів полягає в тому, що вони повинні вміти писати не тільки алгоритми і програми, а й доведення правильності своїх алгоритмів і програм.
В результаті програмісти пишуть програми з великим числом помилок, які вони не можуть ні виявити, ні виправити. Масоване тестування програм на ЕОМ приносить програмістам безперечну користь, проте не дає гарантій повного позбавлення від помилок.
Практика застосування та вивчення доказових методів програмування показала, що ця технологія цілком доступна студентам математичних факультетів, яким цілком під силу написання доказів правильності алгоритмів, після перевірки та тестування програм на ЕОМ.
Найбільший ефект в освоєнні технологій доказового програмування спостерігається в олімпіадах з інформатики та програмування, де переможцями та призерами стають ті студенти, які освоїли техніку тестування програм на ЕОМ і складання алгоритмів і програм без помилок.
Математична логіка та розвиток інформатики Інформатика як наука почала формуватися разом з створенням і бурхливим розвитком обчислювальної техніки. Її формування і визначення її предмета тривають дотепер. Інформатика — наука про зберігання, обробки і передачі інформації за допомогою комп'ютерів. Вона включає в себе великі розділи, які вивчають алгоритмічні, програмні та технічні засоби зберігання, обробки і передачі інформації. Математична логіка виявилася єдиною математичною наукою, методи якої стали найпотужнішими інструментами пізнання у всіх розділах інформатики. Тому скільки- серйозне вивчення інформатики немислимо без освоєння основ математичної логіки.
Щоб комп'ютер працював, він повинен бути оснащений програмним забезпеченням, тобто комплексом програм, що орієнтують комп'ютер на вирішення завдань того чи іншого класу. Слово «програма» має грецьке походження і означає «оголошення», «розпорядження». Уже саме поняття комп'ютерної програми, що передбачає чіткий алгоритмічний припис комп'ютера про порядок і характер дій, передбачає проникнення в програму, а також у процес її складання (в програмування) теорії алгоритмів.
Але при більш пильному розгляді процес проникнення логіки в програми і програмування виявляється значно більш глибоким і органічним. Не тільки один розділ теорії алгоритмів працює тут, але виключно дієвою виявляється саме істота математичної логіки — її мову, її аксіоматичні теорії, висновки і теореми в них, властивості цих теорій.
Фундаментальна основа програмування Теорія алгоритмів та математична логіка — фундаментальна основа програмування. У 30-ті рр. XIX ст. англійський математик Чарлз Беббідж висловив вперше ідею обчислювальної машини. І тільки сто років по тому логіки розробили чотири математично еквівалентні моделі поняття алгоритму. Саме в теорії алгоритмів було передбачено основні концепції, які лягли в основу принципів побудови і функціонування обчислювальної машини з програмним керуванням і принципів створення мов програмування. Ідею такої обчислювальної машини вперше змогли реалізувати болгарський учений С. Атанасов в 1940 р. і німецький вчений К. Цузе в 1942 р. Чотири головні моделі алгоритму породили різні напрямки в програмуванні.
Моделі поняття алгоритму Перша модель — це абстрактна обчислювальна машина (Алан Тюрінг, Р. Пост). Вона з'явилася абстрактним прообразом реальних обчислювальних машин. Дотепер всі обчислювальні машини в деякому сенсі базуються на ідеї Тюрінга: їх пам'ять фізично складається з бітів, кожен з яких містить або 0, або 1. Програмне управління успадкувало від цих абстрактних машин і програму, вміщену в «постійну пам'ять» (ідея помістити програму ЕОМ в основну пам'ять, щоб мати можливість змінювати її в ході обчислень, належить Джону фон Нейманом), а структура команди сучасної ЕОМ великою мірою нагадує структуру команди машини Тюрінга. У рамках теорії машин Тюрінга викристалізувалися найважливіші для комп'ютерних додатків логіки поняття: обчислювана функція, здійсненне завдання, нерозв'язна (алгоритмічно) задача. Зібрано велику кількість визначень абстрактних обчислювальних машин і показано, як кожне з них можна звести до іншого певним кодуванням входів і виходів. Друга модель — це рекурсивні функції, ідея яких сходить до гільбертівського аксіоматичного підходу. Від них успадкувало свої основні конструкції сучасне структурне програмування. Третій спосіб опису алгоритмів — нормальні алгоритми А. А. Маркова. Вони послужили основою мови Рефал і багатьох інших мов обробки символьної інформації. Четвертий напрямок в теорії алгоритмів — так зване λ-числення — базується на ідеях радянського логіка Р. Шейнфінкеля та американського логіка Гаскелла Каррі. Виявилося, що для визначення всіх обчислюваних функцій досить операцій так званої λ — абстракції і суперпозиції. Ідеї λ -числення активно розвиваються в мові Лісп, функціональному програмуванні і в багатьох інших перспективних напрямах сучасного програмування. Математична логіка стала бурхливо розвиватися на початку XX ст. на ґрунті здавалося б виключно далекої від додатків проблеми обґрунтування математики. Але саме ці дослідження поклали початок строгому визначенню алгоритмічних мов, показали їх колосальні можливості і принципові обмеження, розвинули техніку формалізації. Тому, коли в програмуванні було усвідомлено, що всяка програма є формалізацією, тоді ті що виникли тут математичні проблеми впали на ґрунт, ретельно підготовлений математичною логікою.
Опис комп'ютерних програм за допомогою математичної логіки Перші спроби застосувати в програмуванні розвинені логічні обчислення і методи формалізації зробив американський логік Г. Б. Каррі. У 1952 р. він зробив доповідь «Логіка програмних композицій», ідеї якої випередили свій час принаймні на чверть століття. Каррі розглянув задачу програмування, як завдання складання більших програм з готових шматків. Було введено дві базисні системи конструкцій: перша — послідовне виконання, розгалуження і цикл, друга — послідовне виконання і умовний перехід. Він охарактеризував логічні засоби, які можна використовувати для композиції програм з підпрограм в кожному з цих випадків.
Як відомо, комп'ютер є свого роду «ідеальним бюрократом»: він не сприйме програму, написану на не до кінця формалізованою мовою, і приступить до роботи лише після того, як все виражено в повній відповідності з детальними інструкціями. Тому в 1960-ті рр. на перший план вийшли завдання точного визначення формальних мов досить складної структури. Математична логіка, підтримувана ідеями програмування, успішно з ними впоралася, розробили опис синтаксису складних і багатих виражальними засобами формальних мов.
У середині 1960-х рр. практично одночасно з'явився ряд піонерських робіт у галузі опису умов, яким задовольняє програма. Радянський математик В. М. Глушков в 1965 р. ввів поняття алгоритмічної алгебри, що послужило прообразом алгоритмічних логік. Ф. Енгелер в 1967 р. запропонував використовувати мови з нескінченно довгими формулами, щоб висловити нескінченну безліч можливостей, що виникають при різних виконаннях програми. Але найбільшу популярність придбали мови алгоритмічних логік. Ці мови були винайдені практично одночасно американськими логіками Р. У. Флойдом (1967), С. А. Р. Гоаром (1969) і вченими польської логічної школи, наприклад А. Сальвіцкім (1970) та ін.