Зміст
21 відносини: NP-повна задача, Квантор існування, Квантор загальності, Правило резолюцій, Пролог, Автоматизоване доведення теорем, Алгоритмічно нерозв'язна задача, Семантика стійких моделей, Теорія складності обчислень, Теорія моделей, Універсальна машина Тюрінга, Формальна специфікація, Математична логіка, Заперечення, ВЛВ-резолюція, Диз'юнкція (логіка), Доведення від супротивного, Інтуїціоністська логіка, Літерал (математична логіка), Логічна імплікація, Логічне програмування.
- Логіка в інформатиці
NP-повна задача
Діаграма Венна відношення між класами складності задач (у випадку вірності гіпотези P ≠ NP). NP-повна задача (NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.
Переглянути Диз'юнкт Горна і NP-повна задача
Квантор існування
У логіці предикатів, квантифікація існування — тип квантора, логічна константа, яка інтерпретується як «існує», «є принаймні один» або «для деяких».
Переглянути Диз'юнкт Горна і Квантор існування
Квантор загальності
У логіці предикатів, квантор загальності — тип квантора, логічної константи, яка інтерпретується як «для будь-якого» чи «для всіх».
Переглянути Диз'юнкт Горна і Квантор загальності
Правило резолюцій
Правило резолюцій — це правило висновування, що сходить до методу доказу теорем через пошук протиріч; використовується в логіці висловлювань і логіці предикатів першого порядку.
Переглянути Диз'юнкт Горна і Правило резолюцій
Пролог
Проло́г (Prolog, Prolog) — мова логічного програмування загального призначення, пов'язана зі штучним інтелектом та математичною лінгвістикою.
Переглянути Диз'юнкт Горна і Пролог
Автоматизоване доведення теорем
Автоматичне доведення (Automated theorem proving) — доведення, реалізоване на програмному рівні.
Переглянути Диз'юнкт Горна і Автоматизоване доведення теорем
Алгоритмічно нерозв'язна задача
В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після кінцевого числа кроків.
Переглянути Диз'юнкт Горна і Алгоритмічно нерозв'язна задача
Семантика стійких моделей
Поняття стійко́ї моде́лі (stable model), або набору відповідей, застосовується для визначення декларативних семантик для логічних програм із запереченням як відмовою.
Переглянути Диз'юнкт Горна і Семантика стійких моделей
Теорія складності обчислень
Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв.
Переглянути Диз'юнкт Горна і Теорія складності обчислень
Теорія моделей
Тео́рія моде́лей — розділ математичної логіки, який займається вивченням зв'язку між формальними мовами та їх інтерпретаціями, або моделями.
Переглянути Диз'юнкт Горна і Теорія моделей
Універсальна машина Тюрінга
Універсальна машина Тюрінга Універсальна машина Тюрінга(УМТ) це така машина Тюрінга(МТ) яка може замінити собою будь-яку машину Тюрінга.
Переглянути Диз'юнкт Горна і Універсальна машина Тюрінга
Формальна специфікація
Форма́льна специфіка́ція — математичний опис програмного забезпечення або обладнання, яке може бути використане для розробки реалізації.
Переглянути Диз'юнкт Горна і Формальна специфікація
Математична логіка
Математи́чна ло́гіка — розділ математики, що вивчає мислення за допомогою числень, застосовуючи математичні методи та спеціальний апарат символів.
Переглянути Диз'юнкт Горна і Математична логіка
Заперечення
Заперечення в логіці — унарна операція над судженнями, результатом якої є судження (у відомому сенсі) «протилежне» початковому.
Переглянути Диз'юнкт Горна і Заперечення
ВЛВ-резолюція
ВЛВ-резолю́ція (вибіркова лінійна резолюція з визначеними твердженнями), SLD-резолю́ція (SLD-resolution, Selective Linear Definite clause resolution) — це елементарне правило висновування, що застосовується в логічному програмуванні.
Переглянути Диз'юнкт Горна і ВЛВ-резолюція
Диз'юнкція (логіка)
Диз'юнкція (disjunctio — розділення) (операція OR) — двомісна логічна операція, що має значення «істина», якщо хоча б один з операндів має значення «істина».
Переглянути Диз'юнкт Горна і Диз'юнкція (логіка)
Доведення від супротивного
Доведення від супротивного (зведення до абсурду, Reductio ad absurdum) — один із поширених методів доведення тверджень в математичній логіці.
Переглянути Диз'юнкт Горна і Доведення від супротивного
Інтуїціоністська логіка
Інтуїтивна логіка (інколи конструктивна логіка) — система символічної логіки, яка відрізняється від класичної логіки, замінюючи традиційне поняття істини поняттям конструктивно доказової істини.
Переглянути Диз'юнкт Горна і Інтуїціоністська логіка
Літерал (математична логіка)
У математичній логіці літералом називають атомарну формулу, без 0 і 1, або її логічне заперечення.
Переглянути Диз'юнкт Горна і Літерал (математична логіка)
Логічна імплікація
Імплікація — логічна зв'язка «якщо …, то …», тобто оператор між множиною T формул та формулою B, що виконується, якщо кожна модель (або інтерпретація) T також є моделлю B.
Переглянути Диз'юнкт Горна і Логічна імплікація
Логічне програмування
IBM's Blue Gene/P масивно паралельний суперкомп'ютер Логі́чне програмува́ння — парадигма програмування, а також розділ дискретної математики, що вивчає методи і можливості цієї парадигми, засновані на виведенні нових фактів з даних фактів згідно із заданими логічними правилами.
Переглянути Диз'юнкт Горна і Логічне програмування
Див. також
Логіка в інформатиці
- Knowledge Interchange Format
- OBJ (мова програмування)
- Satisfiability Modulo Theories
- Інтуїціоністська логіка
- Аксіоматична семантика
- Аксіоми Пеано
- Алгоритмічно нерозв'язна задача
- Арифметика Пресбургера
- Відповідність Каррі — Говарда
- Денотаційна семантика
- Диз'юнкт Горна
- Зворотний вивід
- Карта Карно
- Комбінаційна логіка
- Логіка в інформатиці
- Нечітка логіка
- Операційна семантика
- Перевірка моделі
- Передумова (формальні методи)
- Припущення (програмування)
- Післяумова (формальні методи)
- Рерайтинг (математика)
- Секвенційна логіка
- Стан гонитви
- Типізоване лямбда-числення
- Уніфікація (інформатика)
- Формальна верифікація
- Функціональна повнота
Також відомий як Речення Горна, Подвійно-горнів диз'юнкт, Визначене твердження.