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



Скачать 84.59 Kb.
Дата22.12.2012
Размер84.59 Kb.
ТипДокументы
Основы логического программирования

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

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

  • Если 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.

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



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



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

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

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

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

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


Похожие:

Основы логического программирования Исчисление высказываний пропозициональная логика iconВопросы по курсу: Математическая логика и теория алгоритмов (2 курс)
Логика высказываний. Операции над высказываниями. Алгебра высказываний. Формулы логики высказываний. Логическая эквивалентность и...
Основы логического программирования Исчисление высказываний пропозициональная логика iconПрограмма курса " азы программирования"
Умение программировать развивает абстрактное, логическое и образное мышление детей. Средой программирования является qbasic. В интересной...
Основы логического программирования Исчисление высказываний пропозициональная логика iconПрограмма курса математическая логика для студентов 1-2 курсов
Секвенциальное исчисление высказываний. Вывод в исчислении. Теорема о подстановке
Основы логического программирования Исчисление высказываний пропозициональная логика iconПрограмма курса математическая логика для студентов 1-2 курсов
Секвенциальное исчисление высказываний. Вывод в исчислении. Теорема о подстановке
Основы логического программирования Исчисление высказываний пропозициональная логика iconПрограмма курса математическая логика для студентов 1-2 курсов
Секвенциальное исчисление высказываний. Вывод в исчислении. Теорема о подстановке
Основы логического программирования Исчисление высказываний пропозициональная логика iconМатематическая логика и теория алгоритмов
Логика высказываний: понятие пропозициональной переменной, логические связки и их аналог в естественном языке, правила записи сложных...
Основы логического программирования Исчисление высказываний пропозициональная логика iconВведение в лямбда-исчисление
Математические основы функционального программирования: лямбда-исчисление А. Черча и теория рекурсивных функций: основные понятия...
Основы логического программирования Исчисление высказываний пропозициональная логика iconЭкзаменационные вопросы по дисциплине: «Математическая логика и теория алгоритмов». Раздел основы математической логики
Логика высказываний: простые высказывания, логические связки, сложные высказывания
Основы логического программирования Исчисление высказываний пропозициональная логика iconИсчисление высказываний
Давая описание алгебры высказываний, мы пользовались логическими значениями высказываний (истина, ложь). Но понятия истинности и...
Основы логического программирования Исчисление высказываний пропозициональная логика iconМатематическая логика
Основными разделами математической логики является: логика высказываний, логика предикатов, металогика
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org