Технологий В. П. Битюцкий Н. В. Папуловская Математическая логика. Исчисления высказываний и предикатов Методическое пособие по дисциплине \"Математическая логика и теория алгоритмов\" Екатеринбург 2005 удк icon

Технологий В. П. Битюцкий Н. В. Папуловская Математическая логика. Исчисления высказываний и предикатов Методическое пособие по дисциплине "Математическая логика и теория алгоритмов" Екатеринбург 2005 удк


1 чел. помогло.
Смотрите также:
Рабочей программы учебной дисциплины в...
Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов» Направление...
Учебная программа Дисциплины б5 «Математическая логика и теория алгоритмов» по направлению...
Учебная программа Дисциплины р2 «Математическая логика и теория алгоритмов» по специальности...
Рабочая учебная программа по дисциплине математическая логика и...
Рабочая учебная программа по дисциплине математическая логика и...
Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр и название...
Рабочая программа дисциплина Математическая логика и теория алгоритмов (наименование дисциплины...
Рабочая программа дисциплины математическая логика и теория алгоритмов, шифр ен. Ф. 01. 04...
Рабочая программа дисциплина ен. Ф. 01. 04 Математическая логика и теория алгоритмов направление...
Рабочая программа дисциплины «Математическая логика и теория алгоритмов»...
Программа дисциплины ен. Ф. 01...



Загрузка...
страницы:   1   2
скачать


Министерство образования Российской Федерации

Государственное образовательное учреждение высшего, профессионального образования

“УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ – УПИ’’



Кафедра
Автоматики и
Информационных
Технологий


В.П. Битюцкий Н.В.Папуловская


Математическая логика.

Исчисления высказываний и предикатов

Методическое пособие по дисциплине
"Математическая логика и теория алгоритмов"





Екатеринбург 2005

УДК


Составители: Валерий Петрович Битюцкий,
Наталья Владимировна Папуловская

Научный редактор – доц., канд.техн.наук Г.Б.Захарова


Математическая логика. Исчисления высказываний и предикатов

Методическое пособие по дисциплине «Математическая логика и теория алгоритмов» / В.П.Битюцкий, Н.В.Папуловская. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005, 34 с.


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


Подготовлено кафедрой
«Автоматика и информационные технологии»


© ГОУ ВПО «Уральский государственный

технический университет-УПИ», 2005

Содержание


Введение 5

1. Исчисление высказываний 6

1.1 Высказывания 6

1.2 Формулы 7

1.3. Выполнимые и общезначимые формулы 11

1.4 Алгебраический подход 12

1.5 Дизъюнкты и нормальные формы 13

1.6. Логический вывод 15

1.6.1. Прямой вывод 15

1.6.2. Доказательство «от противного» 15

1.6.3. Метод резолюций 16

1.6.4. Фразы Хорна 17

1.7. Примеры использования метода резолюций в логике высказываний 19

1.8. Непротиворечивость аксиом 21

1.9. Аксиоматизация логики высказываний 22

2. Исчисление предикатов 26

2.1 Предикаты 26

2.2. Применение логических связок 27

2.3. Кванторы 28

2.4. Свободные и связанные переменные. 29

2.5. Предикатные формулы 31

2.6. Предварённая нормальная форма 32

2.7. Сколемовская и клаузальная формы 34

2.8. Метод резолюций в логике предикатов 35

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

Литература 37

Введение


Слово «Логика» означает систематический метод рассуждений, но обычно под логикой понимают анализ методов рассуждений. Логика – наука о способах доказательств и опровержений, совокупность научных теорий, рассматривающих определённые способы доказательств и опровержений.

Для любой произвольной задачи возможны два разных способа её постановки. Можно определить, что нужно делать, например, поставить задачу так: «найти минимальный остов в заданном графе». Можно сформулировать, как решить задачу. Например: «в заданном графе выбрать минимальное по стоимости ребро и включить его в решение. Затем из оставшихся ребер снова взять минимальное ребро и включить в решение, если при этом не образуются циклы. Так делать пока число ребер не станет на единицу меньше, чем число вершин. Если описанный алгоритм сделать можно, получим решением остов графа, если нельзя, то в графе остова нет, и он не связан».

Сегодня все больше задач ставится для решения с помощью ЭВМ. Всё больше специалистов – не программистов привлекается к этому, и им, естественно, более подходит способ постановки задачи через ЧТО, а уж как решить, по какому алгоритму, пусть выбирает машина исходя, может быть, из особенностей конкретной задачи. Кроме того, все больше становится задач, для которых или алгоритма нет, или он чрезвычайно сложен, или требует данных, которых нет или они труднодоступны. Для них постановка через КАК невозможна.

Для того чтобы ставить и решать задачи на уровне ЧТО, необходимо описать ту предметную область, в которой должна решаться задача. Для нашего примера необходимо описать, что такое граф, остов и пр. Область знаний, которая занимается вопросами описания предметной области для решения различного рода задач, в том числе неформализуемых и плохо формализуемых, называется искусственным интеллектом, в рамках которого и создаются так называемые экспертные системы. Математическим инструментом для них служит математическая логика (матлогика).

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

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


Для рассмотренного примера, задача может быть сформулирована как доказательство истинности высказывания о том, что некоторый частичный граф является остовом.

Начало математической логики было положено в 1847г. работами Джорджа Буля «Математический анализ логики» С развитием математической логике в ней возникли свои специфические задачи. Появились различные системы математических логик: классическая, конструктивная, модальная, нечёткая, комбинаторная и др. Все эти теории объединяет стремление к каталогизации таких способов рассуждений, которые от истинных суждений-посылок приводят к истинным суждениям-следствиям. Каталогизация осуществляется, как правило, в рамках логических исчислений.

Рассматривается два уровня описания предметной области с разной степенью подробности – с помощью высказываний и с помощью предикатов.
^

1. Исчисление высказываний

1.1 Высказывания


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

Пусть есть множество высказываний, фраз, принимающих значение "истина" или "ложь". Примером могут быть фразы "сегодня холодно". "Идёт дождь", "Коля Петров учится в группе Р-23022", "Президент России поехал в Китай" и др. Будем называть их элементарными высказываниями и обозначать прописными буквами латинского алфавита. При этом отвлечёмся от конкретного смысла высказывания, оставим только его истинностное значение.

В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от значений «истинно» и «ложно». Не рассматривается и трёхзначная логика, со значениями, скажем «Да», «Нет», «Не знаю». Ответ отличный от «Да» должен быть «Нет». Древние философы называли этот принцип законом исключения третьего.

^ Высказывание – это утверждение, которое может быть только истинно или ложно. Его принято обозначать символами T (от True), или F (от False), или соответственно, 1 (для истинного значения) или 0 (для значения ложь).

Значение высказывания зависит от предметной области. Например, высказывание «число 15 – простое» будет истинным в восьмеричной и ложным в десятичной системе счисления. Поэтому весьма важно конкретизировать область на которой определено употребляемое высказывание.

1.2 Формулы


Из элементарных высказываний строятся более сложные высказывания с помощью логических связок "НЕ", "И", "ИЛИ", "ТО ЖЕ, ЧТО" (“ЭКВИВАЛЕНЦИЯ”), "ИЗ  СЛЕДУЕТ". ("  ВЛЕЧЁТ", "ПОТОМУ, ЧТО".). Эти связки называются сентенциональными. Связки логики высказываний представляют функции истинности или функции алгебры логики. В таб.1.1 представлены логические связки и их обозначения.

Таблица1.1

Название

Тип

Обозна­чение

Как читается

Другие обозначения

Отрицание

Унарный



не

s, not, не

Конъюнкция

Бинарный



и

,  , and, и

Дизъюнкция

Бинарный



или

, or, или

Импликация

Бинарный



влечёт

, 

Эквивалент-ность

Бинарный



эквивалентно

, 


Определение 1. Отрицанием высказывания p называется высказывание p (или p), которое истинно только тогда когда p ложно.
Пример
. Высказывание «Неправда, что идёт снег» является отрицанием высказывания «идёт снег».

Определение 2. Конъюнкцией высказываний p и q называется высказывание, которое истинно только тогда, когда p и q истинны., т.е. p = 1 и q = 1.

Пример. Чтобы успешно сдать экзамен, нужно иметь при себе зачётку и правильно ответить на вопросы. Для успешной сдачи экзамена нужно выполнить оба условия. Если обозначить как p –«иметь зачётку» и q – «правильно ответить на вопросы», то условием сдачи будет конъюнкция высказываний p & q.

Определение 3. Дизъюнкцией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны, т. е. p = 0 и q =0.

Примеры. (7 >3 или 4  1) =1;
(или sin2x имеет период 2, или 2 – рациональное число) = 0.

Определение 4. Импликацией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда p истинно, q ложно, т.е. p = 1 и q =0 (из p следует q).

Пример. Вышеприведённый пример с успешной сдачей экзамена можно записать как p&qr, где r – «успешно сдать экзамен».

Определение 5. Эквиваленцией высказываний p и q называется высказывание, которое истинно только и только тогда, когда значения высказываний p и q совпадают (p эквивалентно q).

Пример. «Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины». Если p – высказывание «иметь циклы нечетной длины», q – «граф двудольный», то начальная фраза примера запишется в виде q p .

Значения истинности для бинарных связок представлены в табл.1.2.

Таблица 1.2

p

q

p

p  q

p & q

 q

p q

0

0

1

0

0

1

1

0

1

1

1

0

1

0

1

0

0

1

0

0

0

1

1

0

1

1

1

1


С помощью связок можно получать составные высказывания, которым соответствует формула, например, (A & B)  (A v В). Такие высказывания называют сложными. Каждое сложное высказывание, как и элементарное принимает значение из множества {F, T}. В формулах используются скобки для определения порядка выполнения действий.

Пример. Пусть значения элементарных высказываний: p1 = 1, p2 = 0,
p3 = 1 и имеется составное высказывание:

((p1 p2)  p3)  (p2  p3 ).

Найти значение сложного высказывания.

Решение:

((p1 p2)  p3)  (p2  p3 )

0 0 1 1 0

0 1 1

1

Ответ: Значение сложного высказывания – 1.

Итак, словарь исчисления высказываний даёт возможность строить сложные высказывания из простых или элементарных, соединяя последние связками. Получаем формулы, которые являются объектами языка. Аналогия с естественными языками очевидна: фраза – это составное высказывание, построенное по определённым правилам.

Совокупность правил построения выглядит так:

  • Базис. Всякое высказывание является формулой.

  • Индукционный шаг. Если A и B формулы, то A, (AB), (A B), (AB), (A B) – формулы.

  • Ограничение. Формула однозначно получается с помощью правил, описанных в базисе и индукционном шаге.

Множество всех формул счётное (можно установить взаимно однозначное соответствие между ним и множеством натуральных чисел), разрешимое (можно достоверно выяснить, является ли данное высказывание формулой или нет).

Объектами изучения естественных и формальных языков являются синтаксис и семантика. Синтаксис позволяет распознать фразы среди наборов слов. Семантика придаёт определённое значение фразам. Высказывания либо истинны, либо ложны, значит семантическая область {T, F} или {1, 0}. Семантика есть набор правил интерпретации формул.

Интерпретация – это отображение i, сопоставляющее каждому элементарному высказыванию p некоторое значение истинности. Интерпретацию i заданную на множестве элементарных высказываний, можно распространить на множество формул посредством таблиц истинности.


Контрольные упражнения.

1. Найти значения следующих формул:

  1. (p1(p2p3))(p1p2p3), если p1 = 1, p2 = 0, p3 = 1

  2. ( p1 ( p2 ( p3  ( p1( p2 p3))))), если p1 = 0, p2 = 0, p3 = 1

  3. ( p1 p2 p3)  (p3( p2 p1)), если p1 = 1, p2 = 0, p3 = 0

  4.  (p1(p2 ( p3  p2 p3))), если p1 = 1, p2 = 1, p3 = 1

  5. ( p1 p2)  (p3(p2(p1p2p3), если p1 = 0, p2 = 0, p3 = 1

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

  1. Пётр ходит в кино только в том случае, когда там показывают комедию.

  2. Необходимое и достаточное условие для жизни растений состоит в наличии питательной почвы, чистого воздуха и солнечного света.

  3. Студент не может заниматься, если он устал или голоден.

  4. Если Иван выиграет в лотерею, он купит компьютер и будет праздновать всю ночь

  5. Если он не выиграет в лотерею или не купит компьютер, то праздновать всю ночь не будет

  6. Если Артёму нравятся фиолетовые галстуки, то он популярен и у него много друзей

  7. Если Игорь носит желтые ботинки, то он не модный и если он не модный, то у него странные друзья.

  8. Если он не удачлив, то он и не популярен

  9. Он удачлив и богат, следовательно, он популярен.

  10. Он читает научную литературу и любит фантастику, следовательно, он ученый-фантаст.

  11. Если он информатик, то он либо работает за компьютером, либо читает книги об ЭВМ.

  12. Если он или умеет писать или читать, то он грамотный человек.

  13. Для того, чтобы натуральное число a было нечётным, достаточно, чтобы оно было простым и большим двух.

  14. Необходимым условием сходимости последовательности S является ограниченность S.

  15. У меня быстродействующий компьютер и я закончу проект вовремя и сдам экзамен.

3. Сколько строк содержит таблица истинности высказывания, состоящего из n компонентов?
^

1.3. Выполнимые и общезначимые формулы


Формула семантически выполнима, или просто выполнима, если её можно интерпретировать со значением истина. Например:
(p & q)– выполнима.

Множество формул называют выполнимым (непротиворечи­вым), если найдется такая интерпретация, при которой все формулы истины. Если такой интерпретации не находится, то множество невыполнимо (противоречиво).

Существуют высказывания, которые истины в любой области. Примером может служить высказывание A v`A. Такие высказывания называются общезначимыми, тождествено-истинными или тавтологиями. Отрицание общезначимой формулы является невыполнимая формула или противоречие.

Иногда из вида высказывания не ясно, является ли оно тавтологией. Проверка состоит в вычислении значения истинности высказывания на всех наборах значений входящих в него элементарных высказываний. Если формула содержит k различных высказывания, тогда она допускает 2k интерпретаций. Рассмотрев все эти 2k интерпретаций, можно определить какая это формула.

Если A–формула, то запись ú= А означает, что А – тавтология.

Необходимо уметь:

  • Записывать в формальном виде любое сложное высказывание сформулированное фразами естественного языка.

  • Определять семантическую область составного высказыва­ния.

  • Определять, является ли данное высказывание тавтологией;

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

В логике истина-ложь не всякое предложение имеет смысл. Например, предложение "это предложение ложно" не может быть ни ложным, ни истинным. Существуют парадоксы, т.е. рассуждений, приводящих к противоречиям. Например, парадокс лжеца. Некто говорит «Я лгу». Если при этом он не лжёт, то произнесённое им есть ложь, и поэтому он не лжёт. Если же при этом он говорит правду, то произнесённое им есть истина, и поэтому он лжёт. В любом случае оказывается, что он лжёт и не лжёт одновременно.

Контрольные упражнения.

    1. Определить, является ли выражения тавтологией?

    1. r & (p®q) ®q

    2. p ÚØq & r Û p

    3. (p®q) Û Øp Ú q Ú r

    4. (Øp ® q) &(Øp ® Øq)) ® p

    5. (p ® q) & (q ® r) ® (p ® r)



2. Построить таблицы истинности для следующих выражений:

  1. r &(s&p)  p

  2. p  q  r

  3. ((p  q)  (q  r)  p)  (p  r)

  4. (p  q)  (s  p  s)

  5. p  (¬(ps) (sr)
^

1.4 Алгебраический подход


Семантика произвольной формулы исчисления высказываний полностью определяется её таблицей истинности. Разные формулы могут иметь одну и ту же семантику.

Для логических формул важно уметь обнаруживать эквивалентность двух различно представленных объектов.

Определение. Две формулы назовём равносильными, если для любых наборов значений переменных они принимают одинаковые значения.

А º В тогда и только тогда, когда ú= АÛ В.

Чтобы преобразовать логическую формулу в равносильную полезно знать «замечательные тождества», которые задают различные способы представления объекта.

^ Замечательные тождества.

I. Законы булевой алгебры. Математик Джордж Буль (1815–1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ.

  1. Закон двойного отрицания (инволюция): ØØA º A;

  2. Законы коммутативности: A & B º B & A,

  3. A Ú B º B Ú A;

  4. Законы ассоциативности: A & (B & C) º (A & B) & C,
    A Ú (B Ú C) º (A Ú B) Ú C;

  5. Законы дистрибутивности: A & (B Ú C) º (A & B) Ú (A & C),
    A Ú (B & C) º (A Ú B) & (A Ú C);

  6. Свойства констант: A &1= A, A & 0 = 0, A Ú 1 = 1, A Ú 0 = A.

  7. Закон идемпотентности: A & A º A; AÚ A º A.

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

Ø (A & B) º ØA Ú ØB;

Ø (A Ú B) º ØA & ØB.

III. Другие замечательные тождества.

Связь операций:

A Þ B º ØA Ú B,

A Û B º (A Þ B) & (ВÞА),
A & В º Ø(A Þ ØB),

A Ú В º ØA Þ B,

A Þ ØB º В Þ ØА.

  1. Закон контрапозиции: A Þ B º ØB ÞØA.

  2. Закон противоположности: A Û B º ØA Û ØB

Используя эти равносильности можно по данной формуле построить ей равносильные или эквивалентные.

Примеры.

  1. (A Ú A) & B Ú A º A & B Ú A º A& B Ú A & 1 º A& (B Ú 1) º A & 1º A.

  2. B(Ø A & B) º ØB Ú (Ø A & B) º (ØB Ú ØA)&(ØB v B) º(ØB Ú ØA) &1º º(ØB Ú ØA) º Ø (B & A).
^

1.5 Дизъюнкты и нормальные формы


Бывает полезно преобразовать заданную формулу в эквивалентную ей, имеющую вид «нормальной» или «канонической» формы.

Дизъюнктом называется дизъюнкция конечного числа высказываний, то есть формула вида

p1Ú p2 Ú…Ú pn или или Ú{pi | i=1,…,n}

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.

Теорема. Любая формула имеет логически эквивалентную ей КНФ.

^ Алгоритм нормализации:

Исключение связок эквивалентности и импликации;

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

Необходимое число раз применяются законы дистрибутивности (раскрыть все скобки).

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

Нормальная форма общезначима тогда и только тогда когда все ее дизъюнкты общезначимы.

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

Понятие дизъюнкта важно для практики. Описание задач и алгоритмов в терминах дизъюнктов составляет основу логического программирования.

Двойственным понятием к дизъюнкту является конъюнкт. Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция конечного числа конъюнктов. Можно показать, что любая формула приводима к логически эквивалентной ей ДНФ.


Контрольное задание. Привести формулы к КНФ

  1. r Û Ø(ps),

  2. (r & s)  (q & r);

  3. (pq) Þ (Øq  Øs),

  4. (r & q)Û (Øp Ú s)

  5. (p & r) (p Ú r)

  6. (p & (r Ú Øq)) Ú (Øp & r) Ú ((p Ú Øq) &Ør)
^

1.6. Логический вывод


Высказывание C есть логическое следствие высказываний H1, H2, ¼Hn, что записывается в виде
{ H1, H2, ¼, Hn}½= C,

если всякий раз, когда все Hi равны Тrue, значение C тоже равно Тrue. Здесь Hi могут быть формулами элементарных высказываний.

Говорят, что C следует из H={H1, H2, ¼, Hn}.

Выражения H1, H2, ¼, Hn называются посылками или аксиомами, а C – выводом из этих посылок или теоремой.

Фундаментальная проблема логики, называется проблемой вывода, состоит в следующем: определить, является ли формула С логическим следствием множества формул H. Решение этой задачи называют выводом теоремы из аксиом.

Выводу сопоставляется цепочка высказываний С1, С2,¼, Сk, где Сk = С, а каждое высказывание Сi либо является тавтологией, либо следует из аксиом и высказываний, предшествующих данному.
^

1.6.1. Прямой вывод


В прямом выводе используется знание семантики тех операторов, через которые строятся аксиомы. Так, если аксиома утверждает, что A&B, то из смысла этого утверждения следует, что истинными будут высказывния A и B, которые войдут в цепочку вывода. Если известно, что истинным являются высказывания {AvB, `A}, то истинным будет высказывание B именно исходя из смысла этих высказываний. В прямом выводе строится цепочка высказываний, обозначенная выше как C1, C2, …,Ck, которая и является выводом.

Пример. Доказать или опровергнуть следствие:

B®`A, A&D, BvC ½= D&C.

Пронумеруем аксиомы: B®`A (1), A&D (2), BvC (3).
Вывод. Из (2) Þ A (4), из (2) Þ D (5), из (4) и (1) Þ`B (6), из (6) и (3) ÞС (7), из (5) и (7) следует D&C. Здесь используется свойство связок И, ИЛИ и СЛЕДУЕТ. Действительно, A&B истинна, если истинны A и B одновременно (вывод 4 и 5) . Если A= T, то `A = F, значит B не может быть T, т.е. B=F (вывод 6). Если B=F и BvC истинно, то C должно быть равно T (вывод 7). Наконец, из (7) и (5) следует искомый вывод.
^

1.6.2. Доказательство «от противного»


Из определения вывода вытекает, что если {H1, H2, ¼, Hn}½= C, то справедливо утверждение, что (H1&H2&¼&Hn)½=C, или, что
½= (H1&H2& ¼&Hn)®C.

Принцип дедукции. Формула С является логическим следствием конечного множества H тогда и только тогда, когда H È {ØC} невыполнимо.

{H1, …Hn}ú= C Û {H1,… Hn,ØC}ú= 0.

На основе этого утверждение строится способ доказательства, который называется доказательством "от противного" или "reductio ad absurdum". В этом случае в множество аксиом добавляется высказывание, равное отрицанию того, что необходимо вывести. После этого нужно доказать, что из расширенного множества аксиом выводимо противоречие.

Пример. Требуется доказать или опровергнуть вывод
{`AvB, B ®C, AvD }½= CvD.

Обозначим`AvB (1), B®C (2), AvD (3). Введём ещё одно высказывание Ø(CvD)= `С&`D (4) (по правилу де Моргана). Тогда из (4)Þ`С (5), из (4)Þ`D (6), из (6) и (3) ÞA (7), из (7) и (1) ÞB (8), из (8) и (2) ÞС (9), из (8) и (9) ÞС& `С, то есть противоречие. Значит, верно, что CvD.

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

Ø(B ®C) = B & `С, следует тоже два утверждения: B и `С. Используя их необходимо построить противоречие.

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

Если формула имеет вид КНФ, то её можно рассматривать как множество дизъюнктов. Множество дизъюнктов невыполнимо тогда и только тогда, когда пустой дизъюнкт является логическим следствием из него. Невыполнимость множества S можно проверить, порождая логическое следствие до тех пор, пока не получим пустой дизъюнкт.
^

1.6.3. Метод резолюций


Для порождения логических следствий используется очень простая схема рассуждений. Пусть А, В, X – формулы. Предположим, что две формулы (AÚX) и (BÚØX) –истинны. Если X –истинна, то следовательно В истинна. Наоборот, если X ложна, то можно заключить, что А- истинна. В обоих случаях (AÚ В) истинна. Получается правило

^ {AÚX, BÚØX}ú= A Ú В,

можно записать в виде

{ØX vA, X vB}ú= A Ú В.

Это правило называется правилом резолюций.

Лемма. Пусть s1 и s2 –дизъюнкты нормальной формы S, l – высказывание. Если lÎs1 и ØlÎs2 , то дизъюнкт
r = (s1 \ {l})îþ(s2 \ l} ) является логическим следствием нормальной формы S.

Следствие. Нормальные формы S и S îþ{r} эквивалентны.

Замечание. Дизъюнкт r называется резольвентой дизъюнктов s1 и s2.


Алгоритм поверки на выполнимость.

        1. выбираем l, s1, s2, такие что lÎs1 и ØlÎs2.

        2. вычисляем резольвенту r;

        3. заменяем S на S îþ{r};

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

Пример. Проверим выполнимость множества

S={p Ú q, p Ú r, Øq ÚØr, Øp}

Дизъюнкты удобно пронумеровать:

    1. p Ú q

    2. p Ú r

    3. Øq ÚØr

    4. Øp

Вычисляем и добавляем резольвенты. В скобках указаны s1, s2

    1. q (1,4)

    2. r (2,4)

    3. Øq (3,6)

    4. 0 (5,7). Множество невыполнимо!
^

1.6.4. Фразы Хорна


В прямом методе вывод проводился исходя из свойств связок и из того, что предметная область описывалась через импликацию, конъюнкцию, дизъюнкцию и отрицание. Этот способ удобен для представления человеком – специалистом, потому что ему проще выражать свои знания через высказывания ЕСЛИ ТО . ("ЕСЛИ температура >39, слабость и покраснение, ТО необходимо принять лекарство, лечь в постель и пить большое количество воды." Робинсон предложил более удобную форму описания предметной области, позволяющий строить вывод с помощью ЭВМ.

Представим функцию импликации в виде минимальной ДНФ с помощью формулы;

A C  A v C

(A1&A2& &Am)B v C, Ей будет соответствовать формула (с учё-том правила де Моргана) A1 vA2 v vAm v B v C. Перенесём положительные литералы вперед и получим B v C v A1 vA2 v vAm. Такую формулу называют фразой Хорна, положительные литералы (B,C) называют альтернативными следствиями, негативные (A1,A2, ,Am )– необходимыми посылками.

Хорновский дизъюнкт называется точным, если он содержит одну позитивную литеру. Если он не содержит позитивных литер, то называется негативным.

Точный дизъюнкт выражает некоторое правило: негативные литеры соответствуют гипотезам (которые представлены высказываниями), а позитивные заключения.

Унитарный позитивный хорновский дизъюнкт представляет собой некоторый факт, т.е. заключение не зависящее от каких-либо гипотез.

Задача состоит в том, что надо проверить некоторую цель логически выведенную из множества фактов и правил.

Алгоритм построения резолюций для множества фраз Хорна упрощается.

Рассмотрим множество S фраз Хорна. Алгоритма построения резолюций:

При условии Ложь  S,

  • выбираем p и с, такие что:

  • p – унитарный позитивный дизъюнкт из S

  • c – дизъюнкт из S, содержащий p

  • вычисляем резольвенту r;

  • заменяем множество S на (S/{c]{r}).


Таким образом, на каждом этапе одна фраза Хорна заменяется другой, и некоторый атом удаляется из одного дизъюнкта. Отсюда следует, что выполнение алгоритма всегда завершается, какая бы стратегия ни была принята при выборе p и с. Если N – число атомов, первоначально присутствующих в S (c учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.

Существует два случая завершения алгоритма: либо порождён пустой дизъюнкт, тогда множество будет не выполнимым, либо получено множество S, не содержащее дизъюнктов для вычисления очередной резольвенты, тогда множество S будет выполнимым.


Показано, что любую предметную область можно представить в виде фраз Хорна. Для этого любую формулу в описании предметной области необходимо преобразовать в КНФ (конъюнктивную нормальную форму – конъюнкцию элементарных дизъюнкций) и далее каждую элементарную дизъюнкцию представить в виде фразы Хорна.

Пример. Пусть предметная область описана в виде
{A v (B & D), B C, A v D }. Представим её в виде фраз Хорна.

A v (B & D)  (A v B) & (A v D). Этому высказыванию соответствует две фразы Хорна (A v B) и (A v D).

BC B v C .

A v D – является фразой Хорна.

Итак, имеем предметную область, описанную фразами Хорна:
{A v B, A v D, B v C, A v D}
^

1.7. Примеры использования метода резолюций в логике высказываний


Метод резолюций применяется в качестве механизма доказательства при реализации принципа дедукции.

Для доказательства того, что некое заключение C является логическим следствием множества гипотез {H1, …Hn}, нужно применить резолюцию к множеству {H1,… Hn,ØC}. Эти гипотезы и отрицание заключения должны иметь вид дизъюнкций.

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

Например, выясним, является ли логически правильным следующее простое рассуждение. Студент пойдёт домой (p) или останется в университете (q). Он не останется в университете. Следовательно, студент пойдёт домой. (Буквами обозначены имеющиеся в этом рассуждении простые высказывания).

Запишем это рассуждение символически с помощью указанных в скобках букв: p Ú q, Øq, p. Истинность следствия будет определяться истинностью имеющихся высказываний, { p Ú q, Øq }ú= p.

Применим принцип дедукции: { p Ú q, Øq, Øp}ú= 0.

Невыполнимость множества докажем с помощью резолюций:

  1. p Ú q,

  2. Øq,

  3. Øp,

  4. p (1,2).

  5. 0.(ЛОЖЬ)

Можно считать, что данное рассуждение логически правильное.


Контрольные задания.

1. Выяснить, являются ли логически правильными следующие рассуждения. Доказательство провести методом прямого вывода, методом «от противного».

2. Выразить описание задачи через фразы Хорна и провести доказательства, используя метод резолюций.


1. Или Пётр и Иван братья, или они однокурсники. Если Пётр и Иван братья, то Сергей и Иван не братья. Если Пётр и Иван однокурсники, то Иван и Михаил также однокурсники. Следовательно или Сергей и Иван не братья, или Иван и Михаил однокурсники.

2. Если Перт не встречал Ивана, то либо Иван не был на лекциях, либо Пётр лжёт. Если Иван был на лекциях, то Пётр встречал Ивана, и Сергей был в читальном зале после лекций. Если Сергей был в читальном зале после лекций, то либо Иван не был на лекциях, либо Пётр лжёт. Следовательно, Иван не был на лекциях.

3. Наша футбольная команда либо выигрывает матч, либо проигрывает, либо сводит его к ничьей. Если матч выигран или проигран, то он не перенесён. Команда матч не выиграла и не свела его к ничьей. Следовательно, матч не перенесён и проигран

4. Если Джон не встречал этой ночью Смита, то либо Джон был убийцей, либо Джон лжет. Если Смит не был убийцей, то Джон не встречал Смита этой ночью, и убийство имело место после полуночи. Если же убийство имело место после полуночи, то либо Смит был убийцей, либо Джон лжет. Следовательно, Смит был убийцей.

5. Известно, что хроничные сепульки всегда латентны или бифуркальны.

Какие из следующих утверждений в этом случае истинны:

  1. сепульки не хроничны только в случае отсутствия у них свойства латентности;

  2. латентность сепулек не является необходимым условием их хроничности или бифуркальности;

  3. хроничность сепулек является достаточным условием их латентности или бифуркальности;

  4. для нехроничности сепулек необходимо отсутствие у них как бифуркальности, так и латентности.



^

1.8. Непротиворечивость аксиом


Множество аксиом H1, H2,  ,Hm называется непротиворечивым, если найдётся такой набор истинностных значений входящих в него элементарных высказываний, на котором все аксиомы истины. Иначе множество аксиом противоречиво.

Приведенное в примере 1 множество аксиом непротиворечиво, так как на наборе значений, где A=T, B=F, C=T и D=T, каждая аксиома принимает значение "истина".

Противоречием называется высказывание, которое ложно во всякой предметной области. Противоречие будем обозначать как A&A (это высказывание является и простейшим примером противоречия) или как 0.. Для более сложных высказываний проверку на то, является ли высказывание противоречием, приходится проверять так же, как проверяются высказывания на общезначимость, через построение таблицы, которая в этом случае должна быть равным F.

Если множество аксиом противоречиво, то высказывание A1&A2&&Am будет противоречием.

Каждый раз, когда в экспертной системе строится описание предметной области, его проверяют на непротиворечивость. Непротиворечивость достигается через уточнение высказываний

Кроме проверки множества аксиом на непротиворечивость, возникает задача проверки это множество на достоверность.

Пусть, например, в качестве аксиом выступают свидетельство людей, причастных к преступлению, и необходимо выявить, кто является преступником. Возникает вопрос, насколько можно доверять этим свидетельствам? Здесь можно использовать такой приём. Будем считать, что свидетельства людей, не совершивших преступление, истинны, а свидетельства преступников – ложны. Тогда каждое свидетельство породит две аксиомы, имеющие вид импликаций: ЕСЛИ A невиновен ТО его свидетельство верно, и ЕСЛИ A преступник ТО его свидетельство – ложно.

^

1.9. Аксиоматизация логики высказываний


Любая математическая система основывается на множестве аксиом, т.е. выражений, считающихся общезначимыми и множестве правил вывода, т.е. механизмов, позволяющих строить новые общезначимые выражения. Такие выражения называют теоремами. Доказательством теорем называется последовательность из аксиом, правил вывода и уже доказанных теорем, позволяющих получить новую теорему. Важно, что логические правила, которые используются для вывода новых теорем из аксиом и ранее доказанных в данной системе теорем, не порождали в качестве «теорем» ложные высказывания.

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

Необходимо предложить такие формализмы, которые бы определяли все процедуры и не требовали дополнительно никаких ссылок на смысловое содержание. В вышеприведённых примерах мы решали задачу вывода исходя из того, что известны понятия И, ИЛИ, ЕСЛИ ТО и др., которые использовались при выводе. Так, если аксиома определена как A&B, то, исходя из смысла этой операции, выводилась истинность высказываний A и B. В исчислении высказываний операция И определяется явно в виде двух аксиом: (A&B)A, (A&B)B. Это позволяет организовать вывод, не прибегая к рассмотрению смысла фраз.

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

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


H1, H2,…, Hn гипотезы

C заключение


Гипотезы представляют собой перечень высказываний или посылок. Умозаключение правильно, если всякий раз, когда H1, H2,… Hn истинны, то истинно и С. Правильность умозаключения можно проверить, построив таблицу истинности и показать, что всякий раз, когда гипотезы истинны, истинно и заключение.


Таблица 1.3

Силлогизм

Название силлогизма

PQ, P

Q

Modus Ponens

(способ спуска или
правило отделения)

PQ, Q

P

Modus Tollens

(доказательство от противного)

PQ, QR

PR

Транзитивность импликации

P v Q, P

Q

Дизъюнктивный силлогизм

P v Q,P(R&R)

Q

Исключающий выбор

PQ, RQ, P v R

Q

Простая конструктивная дилемма

PQ, RS, P v R

QvS

Сложная конструктивная дилемма

PQ, PS, Q vS

P

Простая деструктивная дилемма

PQ, RS, Q vS

P vR

Сложная деструктивная дилемма

P(R&R)

P

Сведение к абсурду


Рассмотрим пример использования правила вывода Modus Ponens . Пусть P и Q заданы следующим образом: P– «A является студентом УГТУ-УПИ», Q– «A посещает занятия»,

так что PQ: если A студент УГТУ-УПИ, то А посещает занятия.

Предположим, A – Петров Василий, и он посещает занятия. Нужно показать, что он – студент УГТУ-УПИ.

Правило Modus Ponens даёт

P®Q, P

Q

Если A студент УГТУ-УПИ, то А посещает занятия , A посещает занятия, значит A – студент УГТУ-УПИ.


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

PQ, R Q, R

P

Доказательство:

  1. PQ – гипотеза;

  2. R Q – гипотеза;

  3. R – гипотеза;

  4. Q – 2, 3, правило Modus Ponens;

  5. Q P – 1 и Закон контрапозиции: PQ º Q P;

  6. P – 4, 5 и правило Modus Ponens.



Контрольные задания.

Определите, какое из перечисленных умозаключений является правильным:

а) P v Q, P v S, S

P

b) P v Q, R v Q,P

R v P

c) PQ, PS, Q v S

P

d) (S & T), ZT

S Z

e) PQ, RQ, R

P

f) P v Q, R v Q,P, S

R v S

g) S v T, TR, S Z,

R v Z






Скачать 497,41 Kb.
оставить комментарий
страница1/2
Дата29.09.2011
Размер497,41 Kb.
ТипМетодическое пособие, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2
плохо
  2
отлично
  2
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх