Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Пояснительная записка'
Задания по контрольной работе составлены в соответствии с требованиями рабочей программы по дисциплине «Финансы, денежное обращение и кредит» и в соо...полностью>>
'Программа дисциплины'
Предметом дисциплины «Страноведение» является ознакомление студентов с географическим положением и природными условиями Германии, заповедниками, наци...полностью>>
'Документ'
В декабре 2011 г. защитила кандидатскую диссертацию по специальности 10.02.19 на тему «Организационный дискурс коммерческих фирм». С авторефератом ди...полностью>>
'Диссертация'
Защита состоится 26 ноября 2009 г. в 15 часов на заседании Диссертационного совета по политическим наукам Д212.141.20 при Московском государственном ...полностью>>

Основы логического программирования Исчисление высказываний

Главная > Документ
Сохрани ссылку в одной из сетей:

Основы логического программирования

Исчисление высказываний (пропозициональная логика) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка.

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемая индуктивно следующим образом:

  • Если P — пропозициональная переменная, то — формула.

  • Если A — формула, то — формула.

  • Если A и B — формулы, то , и — формулы.

  • Других соглашений нет.

Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками.

Приняты следующие соглашения о скобках:

  • Если опущены внешние скобки, то они восстанавливаются.

  • Если рядом стоят две конъюнкции или дизъюнкции (например, ), то в скобки заключается сначала самая левая часть.

  • Если рядом стоят разные связки, то скобки расставляются согласно приоритету: и .

Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0,1} (множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, определяемое индуктивно с использованием таблиц истинности.

Оценка отрицания задаётся таблицей:

Значение двуместных логических связок , и :

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

1

1

1

1

1

Тождественно истинные формулы (тавтологии)

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных.

Законы де Моргана:

1) ;

2) ;

Закон контрапозиции:

;

Законы поглощения:

1) ;

2) ;

Законы дистрибутивности:

1) ;

2) .

Вариантом аксиоматизации логики высказываний является следующая система аксиом:

;

;

;

;

;

;

;

;

;

;

.

Единственное правило вывода (Modus ponens):

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные.

Все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Логика первого порядка (исчисление предикатов, расширяющее логику высказываний) — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций, и предикатов.

Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов и предикатных символов .

Предикат (n-местный, или n-арный) — это функция с множеством значений {0,1} (или «ложь» и «истина»)

С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные так и предикатные символы арности 0. Первые выделяют в отдельное множество констант.

Кроме того используются следующие дополнительные символы

  • Символы переменных (обычно x,y,z,x1,y1,z1,x2,y2,z2, и т. д.),

  • Пропозициональные связки: ,

  • Кванторы: всеобщности и существования ,

  • Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из и образуют Алфавит логики первого порядка.

Более сложные конструкции определяются индуктивно:

  • Терм есть символ переменной, либо имеет вид , где f — функциональный символ арности n, а — термы.

  • Атом имеет вид , где p — предикатный символ арности n, а — термы.

  • Формула — это либо атом, либо одна из следующих конструкций: , где F,F1,F2 — формулы, а x — переменная.

Переменная x называется связанной в формуле F, если F имеет вид либо , или же представима в одной из форм , причем x уже связанна в H, F1 и F2.

Если x не связанна в F, ее называют свободной в F.

Формулу без свободных переменных называют замкнутой формулой, или предложением.

Теорией первого порядка называют любое множество предложений.

Система логических аксиом логики первого порядка состоит из аксиом исчисления высказываний дополненной двумя новыми аксиомами:

  • ,

  • ,

где A[t / x] — формула, полученная в результате подстановки терма t вместо переменной x в формуле A.

Правил вывода:

  • Modus ponens:

  • Правило обобщения (GEN):

Логика первого порядка обладает рядом полезных свойств, главными из них являются полнота и непротиворечивость.

Полнота - означает, что для любой формулы выводима либо она сама, либо ее отрицание (теорема Гёделя о полноте - устанавливает эквивалентность понятий доказуемости и общезначимости).

Непротиворечивость - означает, что ни одна формула не может быть выведена одновременно со своим отрицанием.

Пример формализации утверждений ЕЯ в логике первого порядка. Возьмем рассуждение «Каждый студент молод. Иванов — студент. Следовательно, Иванов молод». Обозначим «x есть студент» через СТУДЕНТ(x) и «x молод» через МОЛОД(x). Тогда утверждение «каждый студент молод» может быть представлено формулой: x(СТУДЕНТ(x) → МОЛОД(x)) утверждение «Иванов — студент» формулой СТУДЕНТ(Иванов), и «Иванов молод» формулой МОЛОД(Иванов). Утверждение может быть записано формулой:

(x(СТУДЕНТ(x) → МОЛОД(x)) СТУДЕНТ(Иванов)) → МОЛОД(Иванов)

5



Скачать документ

Похожие документы:

  1. Основные разделы программы Программирование на языке высокого уровня Операционные системы

    Документ
    Разработайте алгоритм для консольного приложения для следующей задачи: Дано уравнен6ие прямой Ax+By+C=0. Определить, принадлежит ли точка (X0, Y0) этой прямой.
  2. Основы Pascal. Типы данных. Структура программы на языке Pascal

    Документ
    При записи программы на языке программирования можно пользоваться лишь символами, предусмотренными алфавитом языка. Алфавит языка Паскаль составляют буквы, цифры и специальные символы (знаки операций и ограничители).
  3. Программа дисциплины Математическое программирование Семестры 5

    Программа дисциплины
    Сформировать фундаментальные основы знаний в области теории алгоритмов и структур данных, познакомить с математическими основами компьютерных наук, освоить программирование в различных парадигмах.
  4. Основы собриологии (лекции по антинаркотическому воспитанию) (1)

    Лекции
    Книга посвящена проблемам преодоления зависимостей и формированию здорового и трезвого образа жизни среди подростков и молодежи. Собриология - новая, развивающаяся наука о путях отрезвления народа.
  5. Основы собриологии (лекции по антинаркотическому воспитанию) (2)

    Лекции
    Книга посвящена проблемам преодоления зависимостей и формированию здорового и трезвого образа жизни среди подростков и молодежи. Собриология - новая, развивающаяся наука о путях отрезвления народа.

Другие похожие документы..