Логическая модель. Логика высказываний. Основы логики высказываний

Нажмите для полного просмотра!

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №2

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №3

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №4

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №5

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №6

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №7

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №8

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №9

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №10

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №11

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №12

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №13

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №14

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №15

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №16

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №17

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №18

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №19

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №20

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №21

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №22

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №23

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №24

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №25

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №26

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №27

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №28

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №29

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №30

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №31

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №32

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №33

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №34

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №35

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №36

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №37

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №38

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №39

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №40

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №41

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №42

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №43

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №44

Логическая модель. Логика высказываний. Основы логики высказываний, слайд №45

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Логическая модель. Логика высказываний. Основы логики высказываний. Доклад-сообщение содержит 45 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЛОГИЧЕСКАЯ МОДЕЛЬ Логика высказываний Основы логики высказываний

Слайд 2

Описание слайда:

Употребление термина «логика» в словаре С.И. Ожегова имеет три основных значения: Употребление термина «логика» в словаре С.И. Ожегова имеет три основных значения: 1) наука о законах и формах мышления; 2) ход рассуждений или умозаключений; 3) разумность, внутренняя закономерность чего-либо. Таким образом, логику можно рассматривать с различных точек зрения. Логика будет рассматриваться как формализм для представления знаний. Как самостоятельная научная дисциплина логика сформировалась в силлогистике гениального мыслителя древности Аристотеля. . Особая роль принадлежит Эрбрану и Робинсону, предложившим автоматический метод доказательства теорем. После того как Р. Ковальски показал, как процесс логического доказательства преобразуется в традиционный процесс вычисления, логика перестала быть сугубо теоретической дисциплиной, став основой для создания языка программирования ПРОЛОГ и породив новое направление в программировании – логическое.

Слайд 3

Описание слайда:

простейшая математическая логика – логика высказываний, или логика нулевого порядка. Здесь основным понятием является высказывание – всякое повествовательное предложение, утверждающее что-либо о чем-либо, – и при этом можно сказать, истинно высказывание или ложно, но ни одно высказывание не может быть одновременно истинным и ложным. более общая система – логика первого порядка. Логика предикатов первого порядка позволяет выразить большее разнообразие утверждений благодаря тому, что в нее добавлены термы, предикаты и кванторы.

Слайд 4

Описание слайда:

В логике высказываний предполагается, что мир может быть описан элементарными предложениями, или высказываниями, и логическими связями между ними. Кроме этого, принято еще два допущения: В логике высказываний предполагается, что мир может быть описан элементарными предложениями, или высказываниями, и логическими связями между ними. Кроме этого, принято еще два допущения: 1) простому предложению или высказыванию можно приписать истинностное значение; 2) сложные предложения образуются путем видоизменения некоторого предложения с помощью слова «НЕ» (~ ) или путем связывания простых предложений с помощью слов «И» (∧ ); «ИЛИ» (∨ ); «ЕСЛИ, ТО» (→); «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» (↔). Эти пять слов называют сентенциональными, пропозициональными или логическими связками, каждая из них имеет свое название: « ~ » – отрицание; « ∧ » – конъюнкция; « ∨ » – дизъюнкция; « → » – импликация; « ↔ » – эквиваленция.

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

Для краткости «истина» обозначается как И, а «ложь» – Л. Высказывания обозначаются заглавными буквами или цепочкой букв. Например, Козьма Прутков считает: Для краткости «истина» обозначается как И, а «ложь» – Л. Высказывания обозначаются заглавными буквами или цепочкой букв. Например, Козьма Прутков считает: P: «Военные люди защищают отечество»; Q: «Ветер есть дыхание природы»; R: «Новые сапоги всегда жмут». Символы P, Q, R и др., которые используются для обозначения элементарных высказываний, называются атомарными формулами или атомами.

Слайд 8

Описание слайда:

Примеры сложных высказываний от Козьмы Пруткова: Примеры сложных высказываний от Козьмы Пруткова: «Чиновник умирает, а его ордена остаются на лице земли»; «Хочешь быть красивым, поступи в гусары». Примем следующие обозначения: M: чиновник умирает; L: ордена чиновника остаются на лице земли; B: хотеть быть красивым; G: поступать в гусары. Тогда два последних предложения могут быть записаны в виде формул как M ∧ L, B → G или правильнее G → B?

Слайд 9

Описание слайда:

Символизация естественного языка средствами логики высказываний Операция конъюнкции в логике высказываний и союз «и» в повседневной речи употребляются в одном и том же смысле. Однако в обыденной речи не принято соединять союзом «и» два далеких по смыслу предложения (ироничное: «в огороде бузина, а в Киеве дядька»), в то время как в логике высказываний операция конъюнкции соединяет два любых высказывания. Операции конъюнкции соответствуют следующие выражения: А и В; не только А, но и В; В, хотя и А; А, а также В; как А, так и В; А вместе с В.

Слайд 10

Описание слайда:

ИЛИ В повседневной речи союз «или» употребляется в двух различных смыслах: исключающем и неисключающем, а операция дизъюнкции всегда употребляется в неисключающем смысле. Пример – Чай или кофе? Остаться дома или пойти в университет? (исключающий пример, хотя первый пример может допускать и кофе и чай)

Слайд 11

Описание слайда:

Употребление слов «если ..., то ...» в повседневной речи существенно отличается от применения в логике высказываний. В предложении «если А, то В» обыденной речи подразумевается, что В логически следует из А, в то время как в логике высказываний, не рассматривающей смысла предложений, этого не требуется. Кроме того, ложность предложения А в повседневной речи влечет либо ложность В, либо потерю смысла всего предложения «если А, то В». Таким образом, трансляция естественно-языкового предложения в предложение логики высказываний при кажущейся простоте таковой не является. Здесь требуется понять смысл предложения, а затем уже конструировать формулы логики высказываний

Слайд 12

Описание слайда:

Операции импликации (A → B) соответствуют следующие выражения естественного языка: В, если А; А влечет В; А является причиной В; В является следствием А; в случае А имеет место В; коль скоро А, то В; В, так как А; В, потому что А. «Если выглянет солнце, то станет тепло».

Слайд 13

Описание слайда:

Если B истинно, то истинность всего условного утверждения уже не зависит от истинности A. То есть истинное утверждение может быть обосновано с помощью любого утверждения. Пример: утверждение «если дважды два равно пяти, то снег белый» является истинным. Если B истинно, то истинность всего условного утверждения уже не зависит от истинности A. То есть истинное утверждение может быть обосновано с помощью любого утверждения. Пример: утверждение «если дважды два равно пяти, то снег белый» является истинным. Если A ложно, то истинность всего условного утверждения уже не зависит от истинности B. То есть с помощью ложного утверждения можно обосновать всё что угодно. Пример: утверждение «если дважды два равно пяти, то снег красный» является истинным. Если A является противоречивым (тождественно ложным) утверждением, то истинность всего условного утверждения уже не зависит от истинности B. То есть из противоречивого утверждения можно вывести всё что угодно. Пример: утверждение «если дважды два равно четырём и дважды два не равно четырём, то Луна сделана из зелёного сыра» является истинным. Если B является тавтологией (то есть утверждением, истинным при любом содержании; такие утверждения выражают логические законы), то истинность всего условного утверждения уже не зависит от истинности A. То есть логические законы следуют из любых утверждений. Пример: утверждение «Если снег белый, то дважды два равно четырём или дважды два не равно четырём» является истинным. «Если снег красный, то дважды два равно четырём или дважды два не равно четырём» является истинным.

Слайд 14

Описание слайда:

Эта особенность материальной импликации является прямым следствием двух основных допущений классической логики: Эта особенность материальной импликации является прямым следствием двух основных допущений классической логики: Всякое утверждение либо истинно, либо ложно, а третьего не дано; Истинностное значение сложного утверждения зависит только от истинностных значений входящих в него простых утверждений, а также от характера связи между ними, и не зависит от их содержания. В рамках этих двух допущений более удачное построение условных утверждений невозможно. Ясно, что материальная импликация плохо выполняет свою функцию обоснования. Подобное положение дел, отстаиваемое классической логикой, получило название «парадоксов материальной импликации».

Слайд 15

Описание слайда:

Операции эквиваленции (A ↔ B) соответствуют следующие выражения естественного языка: А, если и только если В; если А, то В, и обратно; А, если В, и В, если А; А эквивалентно В; А равносильно В.

Слайд 16

Описание слайда:

Формулы Правильно построенные формулы, или просто формулы, в логике высказываний определяются рекурсивно следующим образом: атом есть формула; если G – формула, то (~G) – формула; если G и H – формулы, то (G ∨ H), (G ∧ H), (G → H) и (G ↔ H) – формулы; других формул нет. Логическим связкам приписан следующий убывающий ранг: ↔, →, ∨, ∧, ~ . Таким образом, связка с большим рангом имеет большую область действия. Формула P ↔ ~Q ∨ R → S означает (P ↔ (((~Q) ∨ R) → S)).

Слайд 17

Описание слайда:

Если G, H – две формулы, тогда истинность формул (~G) , (G ∨ H), (G ∧ H), (G → H), (G ↔ H) определяется по истинностным значениям атомов, входящих в эту формулу, по следующей таблице. Если G, H – две формулы, тогда истинность формул (~G) , (G ∨ H), (G ∧ H), (G → H), (G ↔ H) определяется по истинностным значениям атомов, входящих в эту формулу, по следующей таблице.

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Интерпретацию формулы, содержащей атомы A1, A2, ..., An, удобно представлять в виде Интерпретацию формулы, содержащей атомы A1, A2, ..., An, удобно представлять в виде I = {m1, m2, ..., mn}, где mj есть Aj или ~Aj. Если mj есть Aj, то атому Aj присвоено значение И, в противном случае Л. Например, в интерпретации {~P, Q} формула (P → Q) → P «ложна», а в интерпретации {P, ~Q} эта же формула «истинна». Формула, истинная при всех возможных интерпретациях, называется общезначимой формулой, или тавтологией. Формула, ложная при всех возможных интерпретациях, называется противоречивой (или невыполнимой). Общезначимую и противоречивую формулу обозначают обычно «■», «o» соответственно. Формула, которая не является общезначимой или противоречивой, называется необщезначимой, непротиворечивой или выполнимой

Слайд 20

Описание слайда:

Общезначимость и противоречивость формулы может быть определена с использованием таблицы истинности, но в силу экспоненциального роста размерности числа интерпретаций с ростом числа входящих в формулу атомов такой метод не всегда является приемлемым. Общезначимость и противоречивость формулы может быть определена с использованием таблицы истинности, но в силу экспоненциального роста размерности числа интерпретаций с ростом числа входящих в формулу атомов такой метод не всегда является приемлемым. Такое положение привело к необходимости разработки правил преобразования формул. Преобразования выполняются путем замены в преобразуемой формуле некоторой ее части на подформулу, эквивалентную заменяемой. Две формулы эквивалентны, если их истинностные значения совпадают при всех интерпретациях. Например, формула (P → Q) → P эквивалентна формуле P.

Слайд 21

Описание слайда:

Для ведения преобразований необходимо иметь минимальный запас эквивалентных формул. Ниже приведены десять законов преобразования, здесь F, G и H являются формулами, символ « = » – это знак эквивалентности. Для ведения преобразований необходимо иметь минимальный запас эквивалентных формул. Ниже приведены десять законов преобразования, здесь F, G и H являются формулами, символ « = » – это знак эквивалентности.

Слайд 22

Описание слайда:

Законы преобразования под номером три называются коммутативными законами; законы под номером четыре – ассоциативными законами; законы под номером пять – дистрибутивными законами; семь – закон идемпотентности; девять – законы дополнения; десять – закон двойного отрицания; одиннадцать – законы де Моргана. Законы преобразования под номером три называются коммутативными законами; законы под номером четыре – ассоциативными законами; законы под номером пять – дистрибутивными законами; семь – закон идемпотентности; девять – законы дополнения; десять – закон двойного отрицания; одиннадцать – законы де Моргана.

Слайд 23

Описание слайда:

ДНФ и КНФ В логике высказываний определены две нормальные формы: дизъюнктивная и конъюнктивная. Формула находится в дизъюнктивной нормальной форме, если она имеет следующий вид: F1 ∨ F2 ∨ ... ∨ Fn , где каждая подформула Fi – это конъюнкция атомов или отрицания атомов. Формула находится в конъюнктивной нормальной форме, если она имеет следующий вид: F1 ∧ F2 ∧ ... ∧ Fn , где каждая подформула Fi – это дизъюнкция атомов или отрицания атомов.

Слайд 24

Описание слайда:

Литера – это атом или отрицание атома. Дизъюнкт – это дизъюнкция литер. Литера – это атом или отрицание атома. Дизъюнкт – это дизъюнкция литер. Единичный дизъюнкт – это дизъюнкт, состоящий из одной литеры. Дизъюнкт, не содержащий никаких литер, называется пустым дизъюнктом. Формула, находящаяся в конъюнктивной нормальной форме, может быть представлена как множество входящих в форму дизъюнктов. Например, формула (P ∨ Q) ∧ (P ∨ R ∨ ~Q) ∧ (~Q ∨ P) ∧ ~P может быть представлена как множество {P ∨ Q, P ∨ R ∨ ~Q, ~Q ∨ P, ~P}.

Слайд 25

Описание слайда:

Вывод в логических моделях нулевого порядка ОПРЕДЕЛЕНИЕ. Пусть даны формулы F1, F2, ..., Fn и формула G. Формула G есть логическое следствие формул F1 , F2 , ..., Fn , если для всякой интерпретации, в которой формула F1 ∧ F2 ∧ ... ∧ Fn истинна, G также истинна. Формулы F1 , F2 , ..., Fn называются посылками, G – заключением. ТЕОРЕМА 1. Пусть даны формулы F1, F2, ..., Fn и формула G. Тогда G есть логическое следствие формул F1, F2, ..., Fn, если формула ((F1 ∧ F2 ∧ ... ∧ Fn) → G) общезначима. ТЕОРЕМА 2. Пусть даны формулы F1, F2, ..., Fn и формула G. Тогда G есть логическое следствие формул F1, F2, ..., Fn, если формула (F1 ∧ F2 ∧ ... ∧ Fn ∧ ~G) противоречива.

Слайд 26

Описание слайда:

Таким образом, вопрос о том, какие высказывания представляют собой логические следствия других высказываний, сводится к вопросу о том, какие высказывания общезначимы или противоречивы. Это, в свою очередь, дает возможность превратить ОПРЕДЕЛЕНИЕ и ТЕОРЕМЫ 1 и 2 в рабочий аппарат для логического вывода. Далее приведем восемь способов логического вывода в логике высказываний. В качестве примера рассматриваются следующие формулы: F1: P; F2: R; F3: Q ∧ R → ~R; G: ~ Q. Таким образом, вопрос о том, какие высказывания представляют собой логические следствия других высказываний, сводится к вопросу о том, какие высказывания общезначимы или противоречивы. Это, в свою очередь, дает возможность превратить ОПРЕДЕЛЕНИЕ и ТЕОРЕМЫ 1 и 2 в рабочий аппарат для логического вывода. Далее приведем восемь способов логического вывода в логике высказываний. В качестве примера рассматриваются следующие формулы: F1: P; F2: R; F3: Q ∧ R → ~R; G: ~ Q.

Слайд 27

Описание слайда:

Способ 1− вычисление истинностного значения. Здесь вывод основан на определении логического следствия и на истинностных таблицах

Слайд 28

Описание слайда:

Слайд 29

Описание слайда:

Способ таблиц истинности 3. В качестве аппарата для логического вывода может быть использована ТЕОРЕМА 2 и метод истинностных таблиц.

Слайд 30

Описание слайда:

Слайд 31

Описание слайда:

также алгебраический, только здесь использована ТЕОРЕМА 2, а для доказательства противоречивости формулы – десять законов эквивалентных преобразований. P ∧ R ∧ ((Q ∧ R) → ~R) ∧ Q = =P ∧ R ∧ (~(Q ∧ R) ∨~R) ∧ Q = =P ∧ R ∧ (~Q ∨ ~R ∨~R) ∧ Q = =P ∧ R ∧ (~Q ∨ ~R) ∧ Q = =P ∧ R ∧ ((~Q ∧ Q) ∨ (~R ∧ ~Q)) = =P ∧ R ∧ ~R ∧ ~Q = =P ∧о ∧ ~Q = о

Слайд 32

Описание слайда:

Способ 6 − алгоритм редукции. Этот способ позволяет доказывать общезначимость формул приведением их к абсурду. Этот способ удобен, когда формула содержит много импликаций. Пусть посылка (P ∧ Q) → R, а заключение P → (Q → R), тогда заключение является логическим следствием посылки, если формула ((P ∧ Q) → R) → (P → (Q → R)) является общезначимой. Предположим, что в некоторой интерпретации эта формула ложна. Это возможно только тогда, когда формула (P ∧ Q) → R истинна, а формула P → (Q → R) ложна. Формула P → (Q → R) ложна только тогда, когда P = И, Q = И, R = Л, что противоречит предположению (P ∧ Q) → R = И, следовательно, формула ((P ∧ Q) → R) → (P → (Q → R)) является общезначимой.

Слайд 33

Описание слайда:

Способ 7− алгоритм Девиса и Патнема. Данный алгоритм основан на использовании конъюнктивной нормальной формы, представленной как множество дизъюнктов S. Алгоритм состоит из четырех правил. 1. Правило тавтологии. Из множества дизъюнктов S вычеркиваются все тавтологичные дизъюнкты. 2. Правило однолитерных дизъюнктов. Если в множестве S есть единичный дизъюнкт C, то, вычеркнув из множества S дизъюнкт C, получим множество S'. Если S' пусто, то S выполнимо; иначе, вычеркнув из множества S' дизъюнкт ~C, получим множество S''. Множество S невыполнимо, когда невыполнимо S''. Если ~C является единичным дизъюнктом, то при его вычеркивании он превращается в противоречивую формулу 3. Правило чистых литер. Литера L в дизъюнкте из S называется чистой, если ~L не появляется ни в каком дизъюнкте из S. Если литера L чистая в S, то, вычеркнув из множества S все дизъюнкты, содержащие L, получим множество S'. Множество S невыполнимо, когда невыполнимо S'. 4. Правило расщепления. Если множество дизъюнктов S может быть представлено следующим образом: (A1∨ L) ∧ ... ∧ (An ∨ L) ∧ (B1∨ ~L) ∧... ∧ (B m∨ ~L) ∧ R, где Ai, Bj, R не содержат литер L и ~L, то получим два множества расщепления S' = A1 ∧ ... ∧ An ∧ R и S'' = B1 ∧ ... ∧ Bm ∧ R. Множество S невыполнимо, когда невыполнимы множества S' и S''.

Слайд 34

Описание слайда:

Используя алгоритм Девиса и Патнема, покажем, что формула (P ∨ Q) ∧ (P ∨ R) ∧ (~Q ∨ ~R) ∧ ~P ∧ U невыполнима. Используя алгоритм Девиса и Патнема, покажем, что формула (P ∨ Q) ∧ (P ∨ R) ∧ (~Q ∨ ~R) ∧ ~P ∧ U невыполнима. S = { P ∨ Q , P ∨ R, ~Q ∨ ~R, ~P, U }; правило 2, единичный дизъюнкт C = ~P; { Q, R, ~Q ∨ ~R, U } правило 2, единичный дизъюнкт C = Q; { R, ~R, U } правило 2, единичный дизъюнкт C = R. { O,U } Так как множество содержит невыполнимый дизъюнкт, то оно невыполнимо.

Слайд 35

Описание слайда:

Задача о влюбленном логике Задача о влюбленном логике Перед нами три девушки: Сью, Марция и Диана. Предположим, что юноша, занимающийся математической логикой, высказывает следующее. Я люблю, по крайней мере, одну из этих трех девушек. Если я люблю Сью, а не Диану, то я также люблю Марцию. Я либо люблю Диану и Марцию, либо не люблю ни одну из них. Если я люблю Диану, то я также люблю Сью. Требуется определить, любит ли автор высказываний Диану? Запишем формулами четыре высказывания и предполагаемое следствие: F1: C v M v D F2: С & ~ D => М F3: D & M v ~ D & ~ М F4: D => С G: D Формулу, построенную согласно теореме 2 о логическом следствии: (C v M v D) & (C & ~ D => M) & (D & M v ~ D & ~ M) & (D => С) & ~ D приведем к КНФ и получим интересующее нас множество дизъюнктов: S = {С v М v D, ~ С v М v D, M v ~ D, ~ М v D, ~ D v С, ~ D}.

Слайд 36

Описание слайда:

S = {С v М v D, ~ С v М v D, M v ~ D, ~ М v D, ~ D v С, ~ D}. Вычеркиваем одиночный дизьюнкт ~ D (правило 2)

Слайд 37

Описание слайда:

Способ 8 − метод резолюций. Данный метод является обобщением правила однолитерных дизъюнктов Девиса и Патнема и также основан на использовании конъюнктивной нормальной формы, представленной как множество дизъюнктов S. Обобщение правила связано с тем, что оно применяется к любой паре дизъюнктов, не обязательно единичных. Правило резолюций и формулируется следующим образом: Если в дизъюнкте C1 существует литера L, а в дизъюнкте C2 существует литера ~L, то, вычеркнув литеры L и ~L из C1 и C2, соответственно, построим дизъюнкцию оставшихся дизъюнктов, которая называется резольвентой дизъюнктов C1 и C2. Рассмотрим, например, дизъюнкты C1: P ∨ Q, C2: ~Q ∨ ~R ∨ U, резольвентой дизъюнктов C1 и C2 будет следующий дизъюнкт: P ∨ ~R ∨ U. Основное свойство резольвенты. Любая резольвента дизъюнктов C1 и C 2 является логическим следствием дизъюнктов C1 и C2. Для невыполнимого множества дизъюнктов применением метода резолюций можно получить пустой дизъюнкт

Слайд 38

Описание слайда:

Метод резолюций основан на проверке того, содержит ли исходное множество дизъюнктов пустой дизъюнкт: если множество содержит пустой дизъюнкт, то это множество невыполнимо, в противном случае проверяется, можно ли получить пустой дизъюнкт из исходного множества. Такой процесс проверки называется выводом. Выводом из конечного множества дизъюнктов S называется конечная последовательность C1, C2, ..., Cn дизъюнктов, всякий элемент Ci которой или принадлежит множеству S, или является резольвентой дизъюнктов, предшествующих данному элементу Ci. Вывод пустого дизъюнкта из S называется опровержением или доказательством невыполнимости S. Метод резолюций основан на проверке того, содержит ли исходное множество дизъюнктов пустой дизъюнкт: если множество содержит пустой дизъюнкт, то это множество невыполнимо, в противном случае проверяется, можно ли получить пустой дизъюнкт из исходного множества. Такой процесс проверки называется выводом. Выводом из конечного множества дизъюнктов S называется конечная последовательность C1, C2, ..., Cn дизъюнктов, всякий элемент Ci которой или принадлежит множеству S, или является резольвентой дизъюнктов, предшествующих данному элементу Ci. Вывод пустого дизъюнкта из S называется опровержением или доказательством невыполнимости S.

Слайд 39

Описание слайда:

Основа метода (~C or K) and (C or P) Если С = 1 то K Если С=0 то P Фактически нужно проверить P or K

Слайд 40

Описание слайда:

Используя метод резолюций, проведем вывод и покажем, что формула (P ∨ Q) ∧ (P ∨ R) ∧ (~Q ∨ ~R) ∧ ~P ∧ U невыполнима. Запишем множество дизъюнктов S = { P ∨ Q , P ∨ R, ~Q ∨ ~R, ~P, U } следующим образом: Используя метод резолюций, проведем вывод и покажем, что формула (P ∨ Q) ∧ (P ∨ R) ∧ (~Q ∨ ~R) ∧ ~P ∧ U невыполнима. Запишем множество дизъюнктов S = { P ∨ Q , P ∨ R, ~Q ∨ ~R, ~P, U } следующим образом: 1) P ∨ Q; 2) P ∨ R; 3) ~Q ∨ ~R; 4) ~P; 5) U; 6) из п.п. 2, 3 получим резольвенту P ∨ ~Q; 7) из п.п. 1, 6 получим резольвенту P; 8) из п.п. 4, 7 получим резольвенту Ǿ. Так как есть логическое следствие множества дизъюнктов S, то S невыполнимо.

Слайд 41

Описание слайда:

Доказать невыполнимость конечного множества дизъюнктов S можно с помощью следующего алгоритма. Доказать невыполнимость конечного множества дизъюнктов S можно с помощью следующего алгоритма. Шаг 1. Если множество S содержит пустой дизъюнкт, то останов с сообщением «Множество невыполнимо». Шаг 2. Если возможно найти резольвенту, то вычислить резольвенту R, иначе останов с сообщением «Множество выполнимо». Шаг 3. S:= S ∪ { R }. Перейти на шаг 1. Приведенный алгоритм – недетерминированный, на шаге 2 возможно вычисление различных резольвент, некоторые резольвенты могут оказаться ненужными и вычисляться несколько раз, а алгоритм без надлежащих проверок может зациклиться.

Слайд 42

Описание слайда:

Алгоритмы доказательства выводимости A → B, построенные на основе этого метода, применяются во многих системах искусственного интеллекта, а также являются фундаментом, на котором построен язык логического программирования «Пролог».

Слайд 43

Описание слайда:

«Яблоко красное и ароматное.» «Если яблоко красное, то яблоко вкусное.» Докажем утверждение «яблоко вкусное». Введем множество формул, описывающих простые высказывания, соответствующие вышеприведенным утверждениям. Пусть X1 — «Яблоко красное», X2 — «Яблоко ароматное», X3 — «Яблоко вкусное». Тогда сами утверждения можно записать в виде сложных формул: X1 ∧ X2 — «Яблоко красное и ароматное.» X1 → X3 — «Если яблоко красное, то яблоко вкусное.» Тогда утверждение, которое надо доказать, выражается формулой X3. Итак, докажем, что X3 является логическим следствием (X1 ∧ X2) и (X1 → X3).

Слайд 44

Описание слайда:

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