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

Основы математической логики

Из аристотелевской логики вытекает математическая логика — наука о правильном построении умозаключений, т.е. цепочек суждений, которые доказываются (вытекают) одна из другой. В отличие от классической математики, которая оперирует с переменными, которые могут принимать бесконечное число значений, математическая логика чаще всего оперирует с бинарными переменными, принимающими значения истина или ложь. Таким образом, если некоторая предметная область (домен) описывается п логическими переменными, то максимально возможное число состояний равно 2". Ограниченное число состояний домена делает возможным доказательство на основе таблиц истинности, которые хорошо знакомы тем, кто изучал дискретную математику, в которой булевы функции определяются исключительно с помощью таблиц истинности.

В интеллектуальных системах чаще всего находят применение две разновидности логики: пропозициональная логика и логика первого порядка.

Пропозициональная логика (логика нулевого порядка) —

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

Логика первого порядка — логика, также оперирующая с бинарными высказываниями (предикатами), которые имеют один или более аргументов. Число аргументов предиката называется его арностью. Принципиальное отличие логики первого порядка от пропозициональной логики состоит в том, что предикат представляет собой множество экземпляров, которые определяются значениями аргументов. Следовательно, здесь уже невозможно обойтись булевыми связками, а необходимо использовать кванторы существования (3) и всеобщности (V).

Рассмотрим классический пример, используемый практически во всех учебниках: если яблоко красное и ароматное, то оно вкусное. Для тех, кто изучал булеву алгебру, очевидно, что данное правило содержит конъюнкцию входных переменных. Определим переменные A, R и Т, которые отвечают соответственно за аромат, цвет и вкус, и составим таблицу истинности, используя функцию конъюнкции (табл. 1.1).

Таблица 1.1

Конъюнкция T=AaR

А — яблоко ароматное

R — яблоко красное

Т — яблоко вкусное

0

0

0

0

1

0

1

0

0

1

1

1

Но вытекает ли из исходного утверждения, что зеленое или желтое яблоко не может быть вкусным? Нет, потому что помимо конъюнкции в данном утверждении используется импликация X —> Y (если X то У, где X — антецедент, У — консеквент). Таблица истинности для импликации выглядит следующим образом (табл. 1.2).

Таблица 1.2

Таблица истинности для импликации

X

У

У

0

0

1

0

1

1

1

0

0

1

1

1

Из табл. 1.2 вытекает, что импликация ложна в единственном случае — если антецедент истинен, а консеквент ложен. Иными словами, из истинности консеквента не следует истинность антецедента. Если подставить в правило импликации конъюнкцию А л R (яблоко ароматное и красное), то мы получим табл. 1.3.

Таблица 13

Таблица истинности для импликации А л R —> Т

А

R

Т

А л R —> Т

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

А

R

т

AaR^T

1

0

1

1

1

1

0

0

1

1

1

1

Докажем с помощью этой таблицы истинности следующее утверждение. Пусть А = 1, R - 1, А л R —» 7. Требуется доказать, что 7 = 1.

Доказательство. Поскольку А - 1 и R - 1, фильтруем таблицу истинности (см. табл. 1.3), оставляя в ней только строки, в которых А = 1 и R = 1. Остаются две последние строки, которым соответствуют значения 7 = 0 и 7 = 1. Импликация Д л 7? —> 7 истинна только в последней строке, где 7=1. Утверждение доказано (если яблоко ароматное и красное, то оно вкусное).

Рассмотрим теперь другой пример. Дано: Л = 1,7? = О, А л R—>Т. Докажем, что 7’= 1 (если яблоко ароматное, но не красное, то оно вкусное).

Доказательство. Отфильтруем табл. 1.3, оставив в ней только строки, в которых А = 1,7? = 0 (пятая и шестая строки). Импликация А л R —»• 7 истинна для обеих комбинаций переменных: = 1, 7? = 0, 7= 0) и (Л = 1, 7? = 0, 7= 1). Следовательно, ароматное, но не красное яблоко может быть вкусным, а может и не быть.

Таким образом, поиск доказательства в пропозициональной логике сводится к таблице истинности.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >