🗊Презентация Логика предикатов

Категория: Математика

Нажмите для полного просмотра!
Логика предикатов, слайд №1Логика предикатов, слайд №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Логика предикатов, слайд №46Логика предикатов, слайд №47Логика предикатов, слайд №48Логика предикатов, слайд №49Логика предикатов, слайд №50Логика предикатов, слайд №51Логика предикатов, слайд №52Логика предикатов, слайд №53Логика предикатов, слайд №54Логика предикатов, слайд №55Логика предикатов, слайд №56Логика предикатов, слайд №57Логика предикатов, слайд №58Логика предикатов, слайд №59Логика предикатов, слайд №60Логика предикатов, слайд №61Логика предикатов, слайд №62Логика предикатов, слайд №63Логика предикатов, слайд №64Логика предикатов, слайд №65Логика предикатов, слайд №66Логика предикатов, слайд №67Логика предикатов, слайд №68Логика предикатов, слайд №69Логика предикатов, слайд №70Логика предикатов, слайд №71Логика предикатов, слайд №72Логика предикатов, слайд №73Логика предикатов, слайд №74Логика предикатов, слайд №75Логика предикатов, слайд №76Логика предикатов, слайд №77Логика предикатов, слайд №78Логика предикатов, слайд №79Логика предикатов, слайд №80Логика предикатов, слайд №81Логика предикатов, слайд №82Логика предикатов, слайд №83Логика предикатов, слайд №84Логика предикатов, слайд №85Логика предикатов, слайд №86Логика предикатов, слайд №87Логика предикатов, слайд №88Логика предикатов, слайд №89Логика предикатов, слайд №90Логика предикатов, слайд №91Логика предикатов, слайд №92Логика предикатов, слайд №93Логика предикатов, слайд №94Логика предикатов, слайд №95Логика предикатов, слайд №96Логика предикатов, слайд №97Логика предикатов, слайд №98Логика предикатов, слайд №99Логика предикатов, слайд №100Логика предикатов, слайд №101Логика предикатов, слайд №102Логика предикатов, слайд №103Логика предикатов, слайд №104Логика предикатов, слайд №105Логика предикатов, слайд №106Логика предикатов, слайд №107Логика предикатов, слайд №108Логика предикатов, слайд №109Логика предикатов, слайд №110Логика предикатов, слайд №111Логика предикатов, слайд №112Логика предикатов, слайд №113Логика предикатов, слайд №114Логика предикатов, слайд №115Логика предикатов, слайд №116Логика предикатов, слайд №117

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


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

Слайд 1







§4. ЛОГИКА ПРЕДИКАТОВ
Описание слайда:
§4. ЛОГИКА ПРЕДИКАТОВ

Слайд 2






4.1 ОСНОВНЫЕ ПОНЯТИЯ ЛОГИКИ ПРЕДИКАТОВ
Описание слайда:
4.1 ОСНОВНЫЕ ПОНЯТИЯ ЛОГИКИ ПРЕДИКАТОВ

Слайд 3




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

Слайд 4




	Определение. Одноместным предикатом P(x) называется произвольная функция переменной x, определенная на множестве М и принимающая значение из множества         .
Описание слайда:
Определение. Одноместным предикатом P(x) называется произвольная функция переменной x, определенная на множестве М и принимающая значение из множества .

Слайд 5




	
	Определение. Предикатом Р называется n-местная функция, определенная на производном множестве М и принимающая в качестве значений элементы из двухэлементного множества      , где 0 и 1 интерпретируются как ложь и истина соответственно. 
	Выражение вида                            можно трактовать       так, что переменные                      связаны отношением Р.
Описание слайда:
Определение. Предикатом Р называется n-местная функция, определенная на производном множестве М и принимающая в качестве значений элементы из двухэлементного множества , где 0 и 1 интерпретируются как ложь и истина соответственно. Выражение вида можно трактовать так, что переменные связаны отношением Р.

Слайд 6




	Используя функциональную форму записи для предикатов, можно сказать, что предикатом  Р(х1, х2, …, хn) называется функция Р:Мn→ В , где В – двоичное множество, а М – произвольное множество.
Описание слайда:
Используя функциональную форму записи для предикатов, можно сказать, что предикатом Р(х1, х2, …, хn) называется функция Р:Мn→ В , где В – двоичное множество, а М – произвольное множество.

Слайд 7




	
	Таким образом, n-местный предикат,   это двузначная функция от n аргументов, определенная  на произвольном множестве М, принимающая значение 0 или 1 (которые интерпретируются как ложь и истина соответственно). 
	Область определения М называется предметной областью предиката, а  х1, х2, …, хn – предметными переменными.
Описание слайда:
Таким образом, n-местный предикат,  это двузначная функция от n аргументов, определенная на произвольном множестве М, принимающая значение 0 или 1 (которые интерпретируются как ложь и истина соответственно). Область определения М называется предметной областью предиката, а х1, х2, …, хn – предметными переменными.

Слайд 8



           Возможность описывать с помощью предикатов не только функции, но и отношения, определяется следующим:
           Возможность описывать с помощью предикатов не только функции, но и отношения, определяется следующим:
	а) если а1, а2, …, аn  –  элементы множества М, то каждому n - местному отношению R соответствует предикат Р такой, что 
Р (а1, а2, …, аn)=1   тогда и только тогда, когда 
(а1, а2, …, аn)  R ;
	б) всякий предикат Р(х1, х2, …  хn) определяет отношение R, такое, что (а1,а2…аn)R, если и только если   Р(а1, а2, … аn) = 1.  При этом R задает область истинности предиката Р.
Описание слайда:
Возможность описывать с помощью предикатов не только функции, но и отношения, определяется следующим: Возможность описывать с помощью предикатов не только функции, но и отношения, определяется следующим: а) если а1, а2, …, аn – элементы множества М, то каждому n - местному отношению R соответствует предикат Р такой, что Р (а1, а2, …, аn)=1 тогда и только тогда, когда (а1, а2, …, аn)  R ; б) всякий предикат Р(х1, х2, … хn) определяет отношение R, такое, что (а1,а2…аn)R, если и только если Р(а1, а2, … аn) = 1. При этом R задает область истинности предиката Р.

Слайд 9




	
	Предикат можно поставить в соответствие и непрерывной функции типа F:Мn→М. 
	Такой функции можно поставить в соответствие    (n + 1) - местный предикат Р  такой, что Р(а1,а2,…,аn,аn+1)=1, если и только если     f(а1,а2,…,аn)=аn+1 .
Описание слайда:
Предикат можно поставить в соответствие и непрерывной функции типа F:Мn→М. Такой функции можно поставить в соответствие (n + 1) - местный предикат Р такой, что Р(а1,а2,…,аn,аn+1)=1, если и только если f(а1,а2,…,аn)=аn+1 .

Слайд 10




	Таким образом, в общем случае предикат Р – двоичная переменная, то есть переменное высказывание, истинность которого определяется значениями аргументов 
(х1, х2, …, хn) , а аргументы хi – чаще нелогические переменные. 
	После подстановки вместо хi  конкретных элементов множества М предикат  Р(а1,а2,…,аn)  перестает быть переменной и принимает одно из двух возможных значений (0 или 1).
Описание слайда:
Таким образом, в общем случае предикат Р – двоичная переменная, то есть переменное высказывание, истинность которого определяется значениями аргументов (х1, х2, …, хn) , а аргументы хi – чаще нелогические переменные. После подстановки вместо хi конкретных элементов множества М предикат Р(а1,а2,…,аn) перестает быть переменной и принимает одно из двух возможных значений (0 или 1).

Слайд 11




Примеры.
	1.Рассмотрим утверждение «x – целое число». Введем предикат I, обозначающий отношение  «быть целым числом», тогда в виде предикатного выражения утверждение может быть записано так : I(x).
	2. Рассмотрим утверждение x < y. Введем предикат S с двумя аргументами, первый из которых меньше второго, тогда S(x,y) соответствует введенному утверждению.
Описание слайда:
Примеры. 1.Рассмотрим утверждение «x – целое число». Введем предикат I, обозначающий отношение «быть целым числом», тогда в виде предикатного выражения утверждение может быть записано так : I(x). 2. Рассмотрим утверждение x < y. Введем предикат S с двумя аргументами, первый из которых меньше второго, тогда S(x,y) соответствует введенному утверждению.

Слайд 12




	3. Элементы  хi  множества М – города. 
Предикат  Р(х)  устанавливается таким образом: «х – это столица Франции». Тогда Р(Воронеж)=0, а  Р(Париж)=1.
	4. Задана функция  z=х+у, где х, у, z – действительные числа. Пусть  предикат Р(х,у,z) соответствует этой функции. 
Тогда Р(2, 3, 5)=1, а Р(7, 3, 8)=0.
Описание слайда:
3. Элементы хi множества М – города. Предикат Р(х) устанавливается таким образом: «х – это столица Франции». Тогда Р(Воронеж)=0, а Р(Париж)=1. 4. Задана функция z=х+у, где х, у, z – действительные числа. Пусть предикат Р(х,у,z) соответствует этой функции. Тогда Р(2, 3, 5)=1, а Р(7, 3, 8)=0.

Слайд 13




	Если вместо переменных в предикат подставить объекты                      , где М – множество, на котором определено Р, то значение              	   можно рассматривать как истинное или ложное.
Описание слайда:
Если вместо переменных в предикат подставить объекты , где М – множество, на котором определено Р, то значение можно рассматривать как истинное или ложное.

Слайд 14




	Пример(для предикатов определенных в предыдущем примере).
	Пусть в обоих случаях предикаты определены на множестве R – действительных чисел. Тогда
1) если x = 5, то предикат I(5) = 1;
    если x = 7.3; то I(7.3) = 0;
2) если x = 5;  y = 10.5, то S(5; 10.5) = 1;
    если x = 27.1;  y = 4.3, то S(27.1; 4.3) = 0.
Описание слайда:
Пример(для предикатов определенных в предыдущем примере). Пусть в обоих случаях предикаты определены на множестве R – действительных чисел. Тогда 1) если x = 5, то предикат I(5) = 1; если x = 7.3; то I(7.3) = 0; 2) если x = 5; y = 10.5, то S(5; 10.5) = 1; если x = 27.1; y = 4.3, то S(27.1; 4.3) = 0.

Слайд 15



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

Слайд 16




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

Слайд 17




	Определение. Предикат                        называется тождественно истинным, если его множество Ip образуют все возможные наборы, которые можно определить на множестве М.
Описание слайда:
Определение. Предикат называется тождественно истинным, если его множество Ip образуют все возможные наборы, которые можно определить на множестве М.

Слайд 18




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

Слайд 19




	 Пример. Рассмотрим предикаты I(x) и S(x,y) из предыдущих примеров. Пусть I и S определены на множестве R, тогда:
	1) при x = 3,  y =10 : I(3) = 1, S(3, 10) = 1, имеем I(3)&S(3, 10) = 1&1 = 1, 
	S(3, 10)  I(3) = 1  1 = 1;
	2) при x=7.5, y=11: I(7.5)=0,  S(7.5,11)=1, 	имеем I(7.5)&S(7.5,11)=0&1=0,  
	I(7.5)  S(7.5, 11) = 0  1 = 1;
Описание слайда:
Пример. Рассмотрим предикаты I(x) и S(x,y) из предыдущих примеров. Пусть I и S определены на множестве R, тогда: 1) при x = 3, y =10 : I(3) = 1, S(3, 10) = 1, имеем I(3)&S(3, 10) = 1&1 = 1, S(3, 10)  I(3) = 1  1 = 1; 2) при x=7.5, y=11: I(7.5)=0, S(7.5,11)=1, имеем I(7.5)&S(7.5,11)=0&1=0, I(7.5)  S(7.5, 11) = 0  1 = 1;

Слайд 20




	3) задана вычислительная процедура: «Повторять цикл, пока переменные х и у   не станут равными, либо прекратить вычисления после 100 повторений».
 	Область определения:
 х и у – действительные числа;  i – целое число, которое в каждом шаге увеличивается на единицу.  
Предикат Р задается условием: (x/=y)  (i<100)
При этом процедура может задаваться условием: «Повторять цикл, если Р=1» .
Описание слайда:
3) задана вычислительная процедура: «Повторять цикл, пока переменные х и у не станут равными, либо прекратить вычисления после 100 повторений». Область определения: х и у – действительные числа; i – целое число, которое в каждом шаге увеличивается на единицу. Предикат Р задается условием: (x/=y)  (i<100) При этом процедура может задаваться условием: «Повторять цикл, если Р=1» .

Слайд 21




	 Квантор всеобщности (). Пусть P(x) это предикат, определенный на множестве  М. Тогда под выражением      понимается высказывание, которое истинно для любого элемента             . 
Соответствующее этому высказыванию предложение можно сформулировать так: 
«Для любого х выражение Р(х) истинно».
Описание слайда:
Квантор всеобщности (). Пусть P(x) это предикат, определенный на множестве М. Тогда под выражением  понимается высказывание, которое истинно для любого элемента . Соответствующее этому высказыванию предложение можно сформулировать так: «Для любого х выражение Р(х) истинно».

Слайд 22




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

Слайд 23




	 Пример. Пусть предикат                 -  определен на множестве N.
Описание слайда:
Пример. Пусть предикат - определен на множестве N.

Слайд 24




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

Слайд 25




	Пример. Для выражения вида  

область действия кванторов определена следующим образом: 
для квантора         				  , 
для квантора                                              , 
для квантора                     .
Описание слайда:
Пример. Для выражения вида область действия кванторов определена следующим образом: для квантора  , для квантора  , для квантора  .

Слайд 26




 
	 Определение. Вхождение переменной x в формулу называется связанным , тогда и только тогда, когда оно совпадает с вхождением в квантор (x) или (y)  и находится в области действия квантора. 
	Вхождение переменной в формулу свободно , тогда и только тогда, когда оно не является связанным.
Описание слайда:
Определение. Вхождение переменной x в формулу называется связанным , тогда и только тогда, когда оно совпадает с вхождением в квантор (x) или (y) и находится в области действия квантора. Вхождение переменной в формулу свободно , тогда и только тогда, когда оно не является связанным.

Слайд 27




	 Определение. Переменная свободна в формуле, если хотя бы одно ее вхождение в эту формулу свободно. 
	Отметим, что переменная в формуле может быть свободной и связанной одновременно.
Описание слайда:
Определение. Переменная свободна в формуле, если хотя бы одно ее вхождение в эту формулу свободно. Отметим, что переменная в формуле может быть свободной и связанной одновременно.

Слайд 28




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

Слайд 29




 
	 Пример. 
    Р(х)  х свободная;
                              х связанная;
                           х связанная,  y свободная;
                           х и y связанные.
Описание слайда:
Пример. Р(х)  х свободная;  х связанная;  х связанная, y свободная;  х и y связанные.

Слайд 30




4.2 Логика предикатов как формальная система
Описание слайда:
4.2 Логика предикатов как формальная система

Слайд 31




Алфавит.
Правила построения формул.
Аксиомы. 
Правила вывода.
Описание слайда:
Алфавит. Правила построения формул. Аксиомы. Правила вывода.

Слайд 32



1. Алфавит. 
предметные переменные  x, y, z и т.п., которые принимают значение из множества М;
индивидные константы  a, b, c и т.п., то есть нульместные функциональные константы или константы предметной области;
функциональные константы  f, g, h и т.п., используются для обозначения функций;
высказывания  p, q, r и т.п.;
предикатные константы  P, R, H, Q и т.п.;
символы логических операций  &,       ,         и т.д.;
символы кванторных операций              ;
вспомогательные символы  ( , ).
Описание слайда:
1. Алфавит. предметные переменные  x, y, z и т.п., которые принимают значение из множества М; индивидные константы  a, b, c и т.п., то есть нульместные функциональные константы или константы предметной области; функциональные константы  f, g, h и т.п., используются для обозначения функций; высказывания  p, q, r и т.п.; предикатные константы  P, R, H, Q и т.п.; символы логических операций  &, , и т.д.; символы кванторных операций  ; вспомогательные символы  ( , ).

Слайд 33



2. Правила построения формул. 
	Термом является всякая переменная и всякая функциональная форма.
	Функциональная форма  это функциональная константа, соединенная с некоторым числом термов. 
	Если f  функциональная константа (n-местная) и                   - термы, то соответствующая форма записывается так
        
	Если n=0, то f превращается в индивидную константу.
Описание слайда:
2. Правила построения формул. Термом является всякая переменная и всякая функциональная форма. Функциональная форма  это функциональная константа, соединенная с некоторым числом термов. Если f  функциональная константа (n-местная) и - термы, то соответствующая форма записывается так Если n=0, то f превращается в индивидную константу.

Слайд 34




	Предикатная форма  это предикатная константа, соединенная с соответствующим числом термов. 
	Если Р  предикатная константа (m-местная константа) и                          термы, то соответствующая форма записывается так . 

	Если m = 0, то пишут Р, т.е.предикатная форма превращается в высказывание
Описание слайда:
Предикатная форма  это предикатная константа, соединенная с соответствующим числом термов. Если Р  предикатная константа (m-местная константа) и  термы, то соответствующая форма записывается так . Если m = 0, то пишут Р, т.е.предикатная форма превращается в высказывание

Слайд 35





	Атом  это предикатная форма или некоторое равенство (выражение вида s=t, где s и t  термы). 
	Для равенства характерно то же, что и для предикатной формы, т.е. о  нем можно сказать, что оно истинно или ложно.
Описание слайда:
Атом  это предикатная форма или некоторое равенство (выражение вида s=t, где s и t  термы). Для равенства характерно то же, что и для предикатной формы, т.е. о нем можно сказать, что оно истинно или ложно.

Слайд 36



Определение понятия формулы 
1. Атом есть формула.
2. Если А  формула, то          формула.
3. Если А и В  формулы,
то ,                                (А&В), (А~В)  формулы.
 4. Если А  формула и х  переменная, то          			формулы.
Описание слайда:
Определение понятия формулы 1. Атом есть формула. 2. Если А  формула, то  формула. 3. Если А и В  формулы, то , (А&В), (А~В)  формулы. 4. Если А  формула и х  переменная, то  формулы.

Слайд 37



 3. Определение аксиом. 
	Выбор системы аксиом  в исчислении предикатов может быть осуществлен по-разному. 
	Один из наиболее простых способов состоит в том, что берутся уже ранее определенные аксиомы из исчисления высказываний и дополняются еще двумя, связанными с использованием кванторов:
Описание слайда:
3. Определение аксиом. Выбор системы аксиом в исчислении предикатов может быть осуществлен по-разному. Один из наиболее простых способов состоит в том, что берутся уже ранее определенные аксиомы из исчисления высказываний и дополняются еще двумя, связанными с использованием кванторов:

Слайд 38



4. Правила вывода. 
	Правила вывода также полностью заимствуются из логики высказываний, кроме того, к ним добавляются еще два правила следующего вида:
 - правило введения квантора существования: 

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

Слайд 39




	Примеры.
	1. Утверждение: «Все слоны серые». 
	Вводимые предикаты: 
слон(x) – «x – слон»; 
цвет(x,y) – «x цвета y».
	Предикатное выражение:
Описание слайда:
Примеры. 1. Утверждение: «Все слоны серые». Вводимые предикаты: слон(x) – «x – слон»; цвет(x,y) – «x цвета y». Предикатное выражение:

Слайд 40




	2. Утверждение: «Для любого множества x существует множество y такое, что мощность y больше, чем мощность x».
	Вводимые предикаты: 
множество(x) – «x – множество»; 
мощность(x,u) – «мощность множества x равна u»; 
больше(x,u) – «значение x больше значения u».
	Предикатное выражение:
Описание слайда:
2. Утверждение: «Для любого множества x существует множество y такое, что мощность y больше, чем мощность x». Вводимые предикаты: множество(x) – «x – множество»; мощность(x,u) – «мощность множества x равна u»; больше(x,u) – «значение x больше значения u». Предикатное выражение:

Слайд 41



	3. Утверждение: «Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые сдвигались, тоже будут сдвинуты».
	3. Утверждение: «Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые сдвигались, тоже будут сдвинуты».
	Вводимые предикаты:
куб (x)– «x – куб»; 
сверху (x,y) – «x расположен сверху y»;  
скреплен (x,y) –  «x  скреплен с  y»;   
сдвинут (x) –  «x – сдвинут».
	Предикатное выражение:
Описание слайда:
3. Утверждение: «Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые сдвигались, тоже будут сдвинуты». 3. Утверждение: «Все кубики, находящиеся на кубиках, которые были сдвинуты или были скреплены с кубиками, которые сдвигались, тоже будут сдвинуты». Вводимые предикаты: куб (x)– «x – куб»; сверху (x,y) – «x расположен сверху y»; скреплен (x,y) – «x скреплен с y»; сдвинут (x) – «x – сдвинут». Предикатное выражение:

Слайд 42




4.3 Определение значения истинности предикатных формул
Описание слайда:
4.3 Определение значения истинности предикатных формул

Слайд 43




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

Слайд 44




	Пусть А(х), А(x,y) и В(х) –  предикаты, р –  высказывание, тогда правила имеют следующий вид:
Описание слайда:
Пусть А(х), А(x,y) и В(х) – предикаты, р – высказывание, тогда правила имеют следующий вид:

Слайд 45
Логика предикатов, слайд №45
Описание слайда:

Слайд 46
Логика предикатов, слайд №46
Описание слайда:

Слайд 47



	Пример. Доказать тождественную истинность заданного предикатного выражения 
	Пример. Доказать тождественную истинность заданного предикатного выражения
Описание слайда:
Пример. Доказать тождественную истинность заданного предикатного выражения Пример. Доказать тождественную истинность заданного предикатного выражения

Слайд 48




	Пример. Доказать тождественную ложность заданного предикатного выражения
Описание слайда:
Пример. Доказать тождественную ложность заданного предикатного выражения

Слайд 49




4.4 Метод резолюций для логики предикатов
Описание слайда:
4.4 Метод резолюций для логики предикатов

Слайд 50



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

Слайд 51



8888888888888888888888888888888888888888888888888888887
	Например, для создания               из                                  			  и              необходимо найти подстановку  «A вместо x», которая сделает идентичными W1(A) и W1(x). 
	Поиск подстановок термов на место переменных называется унификацией. 
	Унификация основывается на другом понятии – подстановка.
Описание слайда:
8888888888888888888888888888888888888888888888888888887 Например, для создания из и необходимо найти подстановку «A вместо x», которая сделает идентичными W1(A) и W1(x). Поиск подстановок термов на место переменных называется унификацией. Унификация основывается на другом понятии – подстановка.

Слайд 52






	Определение. Подстановочным частным случаем называется подстановка в некоторое выражение термов вместо переменных.
Описание слайда:
Определение. Подстановочным частным случаем называется подстановка в некоторое выражение термов вместо переменных.

Слайд 53




	Пример.
	Для выражения P(x, f(y), B) имеется четыре частных случая подстановки:
P(z, f(ω), B) – алфавитная, просто замена одних переменных на другие;
P(x, f(A), B) – константу подставили в функцию f;
P(g(z), f(A), B) – функциональное выражение вместо переменной x;
P(C, f(A), B) – основной частный случай, т.к. везде подставлены константы вместо переменных.
Описание слайда:
Пример. Для выражения P(x, f(y), B) имеется четыре частных случая подстановки: P(z, f(ω), B) – алфавитная, просто замена одних переменных на другие; P(x, f(A), B) – константу подставили в функцию f; P(g(z), f(A), B) – функциональное выражение вместо переменной x; P(C, f(A), B) – основной частный случай, т.к. везде подставлены константы вместо переменных.

Слайд 54




	Любую подстановку  можно представить с помощью множества упорядоченных пар вида  
S = {t1/v1, t2/v2, …, tn/vn}, 
где пара ti/vi  означает, что переменная vi заменяется на терм ti.
Описание слайда:
Любую подстановку можно представить с помощью множества упорядоченных пар вида S = {t1/v1, t2/v2, …, tn/vn}, где пара ti/vi означает, что переменная vi заменяется на терм ti.

Слайд 55




	
	При выполнении подстановки должны соблюдаться два правила:

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

Слайд 56




	Для предыдущего примера подстановки описанные с помощью введенного формализма, имеют следующий вид:
	1)  S1 = {z/x, ω/y};   
	2)  S2 = {A/y};   
	3)  S3 = {g(z)/x, A/y};   
	4)  S4 = {C/x, A/y}.
Описание слайда:
Для предыдущего примера подстановки описанные с помощью введенного формализма, имеют следующий вид: 1) S1 = {z/x, ω/y}; 2) S2 = {A/y}; 3) S3 = {g(z)/x, A/y}; 4) S4 = {C/x, A/y}.

Слайд 57




	Для обозначения подстановки часто используется следующая запись.
	 Если S – подстановка, а E – выражение, к которому она применяется, то пишут  ES . 
	Если подстановка S применяется к каждому элементу некоторого множества {Ei}, то множество подстановочных примеров обозначается {Ei}S.
Описание слайда:
Для обозначения подстановки часто используется следующая запись. Если S – подстановка, а E – выражение, к которому она применяется, то пишут ES . Если подстановка S применяется к каждому элементу некоторого множества {Ei}, то множество подстановочных примеров обозначается {Ei}S.

Слайд 58




	 Определение. Говорят, что множество E={E1, E2 , …, En } унифицируемо, если существует такая подстановка S, что 
	E1S = E2S = … =EnS. 
	В этом случае подстановка S называется унификатором для множества E, т.к. после ее применения множество склеивается в один элемент.
Описание слайда:
Определение. Говорят, что множество E={E1, E2 , …, En } унифицируемо, если существует такая подстановка S, что E1S = E2S = … =EnS. В этом случае подстановка S называется унификатором для множества E, т.к. после ее применения множество склеивается в один элемент.

Слайд 59




	 Пример. Пусть A={P(x, f(y), B), P(x, f(B), B)},
 рассмотрим подстановку S={C/x, B/y} , 
унифицируем и получаем  A = {P(A, f(B), B)} 
(в подстановке C необходимости не было).
Описание слайда:
Пример. Пусть A={P(x, f(y), B), P(x, f(B), B)}, рассмотрим подстановку S={C/x, B/y} , унифицируем и получаем A = {P(A, f(B), B)} (в подстановке C необходимости не было).

Слайд 60




	Унификация производится при следующих условиях:
1. Если термы – константы, то они унифицируемы тогда и только тогда, когда они совпадают.
2. Если в первом дизъюнкте терм – переменная, а во втором – константа, то они унифицируемы, при этом вместо переменной подставляется константа.
3. Если терм в первом дизъюнкте – переменная и во втором дизъюнкте терм тоже переменная, то они унифицируемы.
4. Если в первом дизъюнкте терм – переменная, а во втором – употребление функции, то они унифицируемы, при этом вместо переменной подставляется употребление функции.
5. Унифицируются между собой термы, стоящие на одинаковых местах в одинаковых предикатах.
Описание слайда:
Унификация производится при следующих условиях: 1. Если термы – константы, то они унифицируемы тогда и только тогда, когда они совпадают. 2. Если в первом дизъюнкте терм – переменная, а во втором – константа, то они унифицируемы, при этом вместо переменной подставляется константа. 3. Если терм в первом дизъюнкте – переменная и во втором дизъюнкте терм тоже переменная, то они унифицируемы. 4. Если в первом дизъюнкте терм – переменная, а во втором – употребление функции, то они унифицируемы, при этом вместо переменной подставляется употребление функции. 5. Унифицируются между собой термы, стоящие на одинаковых местах в одинаковых предикатах.

Слайд 61




	 Пример. 
	Рассмотрим дизъюнкты:
1)	Q(a, b, c) и Q(a, d, l). 
	Дизъюнкты не унифицируемы.

2)	Q(a, b, c) и Q(x, y, z). 
	Дизъюнкты унифицируемы. Унификатор – S=(a/x,b/y,c/z).
Описание слайда:
Пример. Рассмотрим дизъюнкты: 1) Q(a, b, c) и Q(a, d, l). Дизъюнкты не унифицируемы. 2) Q(a, b, c) и Q(x, y, z). Дизъюнкты унифицируемы. Унификатор – S=(a/x,b/y,c/z).

Слайд 62




	Если необходимо последовательно выполнить несколько подстановок: S1, S2, то можно записать 
 
	На этом действии базируется такое понятие, как композиция подстановок.
Описание слайда:
Если необходимо последовательно выполнить несколько подстановок: S1, S2, то можно записать На этом действии базируется такое понятие, как композиция подстановок.

Слайд 63




	
	Если S  и S' являются двумя множествами подстановок, то их композиция S  и S'      (пишется S S' ) получается после применения S' к элементам S и добавления результата к S. 
	Композиция подстановок – это метод, с помощью которого объединяются подстановки унификации.
Описание слайда:
Если S и S' являются двумя множествами подстановок, то их композиция S и S' (пишется S S' ) получается после применения S' к элементам S и добавления результата к S. Композиция подстановок – это метод, с помощью которого объединяются подстановки унификации.

Слайд 64




	Определение. Композиция подстановок g и s есть функция gs, определяемая следующим образом:
 (gs) [t]=g[ s[t]],
 где t – терм, 
g и s  – подстановки, 
а s[t] – терм, который  получается из t путем применения к нему подстановки s.
Описание слайда:
Определение. Композиция подстановок g и s есть функция gs, определяемая следующим образом: (gs) [t]=g[ s[t]], где t – терм, g и s – подстановки, а s[t] – терм, который получается из t путем применения к нему подстановки s.

Слайд 65




	 Пример. Пусть задана последовательность подстановок 
		{x/y,w/z}, {v/x}, {A/v, f(B)/w}, 
они эквивалентны одной подстановке 			{A/y,f(B)/z}. 
Последняя подстановка была выведена путем компоновки  {x/y,w/z} и  {v/x}  для получения {v/y,w/z} и компоновки результата с {A/v, f(B)/w} для получения  {A/y,f(B)/z}.
Описание слайда:
Пример. Пусть задана последовательность подстановок {x/y,w/z}, {v/x}, {A/v, f(B)/w}, они эквивалентны одной подстановке {A/y,f(B)/z}. Последняя подстановка была выведена путем компоновки {x/y,w/z} и {v/x} для получения {v/y,w/z} и компоновки результата с {A/v, f(B)/w} для получения {A/y,f(B)/z}.

Слайд 66




	Основное требование алгоритма унификации состоит в том, что унификатор должен быть максимально общим, т.е. для любых двух выражений должен быть найден   наиболее общий унификатор (НОУ).
Описание слайда:
Основное требование алгоритма унификации состоит в том, что унификатор должен быть максимально общим, т.е. для любых двух выражений должен быть найден наиболее общий унификатор (НОУ).

Слайд 67




	 Определение. Если s – произвольный унификатор выражения E, а g – наиболее общий унификатор  этого набора выражений, то в случае применения s к E будет существовать еще один унификатор s' такой, что  Es= Egs', где g и s', – композиции унификация, примененные к выражению E.
Описание слайда:
Определение. Если s – произвольный унификатор выражения E, а g – наиболее общий унификатор этого набора выражений, то в случае применения s к E будет существовать еще один унификатор s' такой, что Es= Egs', где g и s', – композиции унификация, примененные к выражению E.

Слайд 68





	 Определение. Множество рассогласований непустого множества дизъюнктов {E1,…, En} получается путем выявления первой (слева) позиции, на которой не для всех дизъюнктов из E стоит один и тот же символ, и выписывания из каждого дизъюнкта терма, который начинается с символа, занимающего данную позицию. 
	Множество термов и есть множество рассогласований в E.
Описание слайда:
Определение. Множество рассогласований непустого множества дизъюнктов {E1,…, En} получается путем выявления первой (слева) позиции, на которой не для всех дизъюнктов из E стоит один и тот же символ, и выписывания из каждого дизъюнкта терма, который начинается с символа, занимающего данную позицию. Множество термов и есть множество рассогласований в E.

Слайд 69




	 Пример. 
	Рассмотрим дизъюнкты:
 {P(x, f(y, z)), P(x, a), P(x, g(h(k(x))))}.
	Множество рассогласований состоит из термов, которые начинаются с пятой позиции, и представляет собой множество 
{f(x, y), a, g(h(k(x)))}.
Описание слайда:
Пример. Рассмотрим дизъюнкты: {P(x, f(y, z)), P(x, a), P(x, g(h(k(x))))}. Множество рассогласований состоит из термов, которые начинаются с пятой позиции, и представляет собой множество {f(x, y), a, g(h(k(x)))}.

Слайд 70




Алгоритм унификации

	Пусть E – множество дизъюнктов,
	 D – множество рассогласований, 
	k – номер итерации, 
	gk – наиболее общий унификатор на k-й итерации.
Описание слайда:
Алгоритм унификации Пусть E – множество дизъюнктов, D – множество рассогласований, k – номер итерации, gk – наиболее общий унификатор на k-й итерации.

Слайд 71




	 Шаг 1. 
	Пусть 	k=0, 
		  	gk=e (пустой унификатор),
		  	Ek=E.
Описание слайда:
Шаг 1. Пусть k=0, gk=e (пустой унификатор), Ek=E.

Слайд 72




	 Шаг 2. 
	Если для Ek не существует множества рассогласований Dk, то алгоритм завершает работу и gk – наиболее общий унификатор для E. 
Иначе найдем множество рассогласований Dk.
Описание слайда:
Шаг 2. Если для Ek не существует множества рассогласований Dk, то алгоритм завершает работу и gk – наиболее общий унификатор для E. Иначе найдем множество рассогласований Dk.

Слайд 73




	Шаг 3.
	Если существуют такие элементы vk и tk в Dk, что vk – переменная, не входящая в терм tk, то перейдем к шагу 4. 
	В противном случае алгоритм завершает работу и E не унифицируемо.
Описание слайда:
Шаг 3. Если существуют такие элементы vk и tk в Dk, что vk – переменная, не входящая в терм tk, то перейдем к шагу 4. В противном случае алгоритм завершает работу и E не унифицируемо.

Слайд 74




	Шаг 4.
	Пусть gk+1=gk { tk / vk}, заменим во всех дизъюнктах Ek переменную vk. на терм tk
Описание слайда:
Шаг 4. Пусть gk+1=gk { tk / vk}, заменим во всех дизъюнктах Ek переменную vk. на терм tk

Слайд 75






	Шаг 5.
        k=k+1. Перейти к шагу 2.
Описание слайда:
Шаг 5. k=k+1. Перейти к шагу 2.

Слайд 76




	Пример.
	Рассмотрим дизъюнкты: 
		E={P(f(a), g(x)), P(y, y)}.
Итерация 1.
Шаг 1. E0=E, k=0, g0=e.
Шаг 2. D0={f(a),y}.
Шаг 3. v0=y, t0=f(a).
Шаг 4. g1={f(a)/y}, E1={P(f(a), g(x)), P(f(a), f(a))}. Переход на шаг 2.
Описание слайда:
Пример. Рассмотрим дизъюнкты: E={P(f(a), g(x)), P(y, y)}. Итерация 1. Шаг 1. E0=E, k=0, g0=e. Шаг 2. D0={f(a),y}. Шаг 3. v0=y, t0=f(a). Шаг 4. g1={f(a)/y}, E1={P(f(a), g(x)), P(f(a), f(a))}. Переход на шаг 2.

Слайд 77




Итерация 2.
Шаг 2. D1={g(x),f(a)}.
     
Шаг 3. Так как нет переменной в множестве рассогласований D1, то, следовательно, алгоритм унификации завершается,  множество E – не унифицируемо.
Описание слайда:
Итерация 2. Шаг 2. D1={g(x),f(a)}. Шаг 3. Так как нет переменной в множестве рассогласований D1, то, следовательно, алгоритм унификации завершается, множество E – не унифицируемо.

Слайд 78




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

Слайд 79




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

Слайд 80




	Пусть задано следующее предикатное выражение:

	Его следует привести к множеству предложений. 
	На каждом шаге будем приводить пример, который демонстрирует результат применения действий соответствующего шага к заданному выражению.
Описание слайда:
Пусть задано следующее предикатное выражение: Его следует привести к множеству предложений. На каждом шаге будем приводить пример, который демонстрирует результат применения действий соответствующего шага к заданному выражению.

Слайд 81




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

Слайд 82




	Шаг 2. Используя правила де Моргана, выполняют преобразования, обеспечивающие применение операции отрицания только к литералам. 
	Пример.
Описание слайда:
Шаг 2. Используя правила де Моргана, выполняют преобразования, обеспечивающие применение операции отрицания только к литералам. Пример.

Слайд 83




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

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

Слайд 84




	 Шаг 4. Исключение кванторов существования.  	Рассмотрим формулу                                
 
	В этой формуле получается, что все выражение выполняется для  любого y и некоторого x, который, возможно, зависит от y. 
	Эту зависимость можно обозначить явно с помощью некоторой функции g(y), отображающей каждое значение y в то x, которое существует. 
	Такая функция называется сколемовской функцией.
Описание слайда:
Шаг 4. Исключение кванторов существования. Рассмотрим формулу В этой формуле получается, что все выражение выполняется для любого y и некоторого x, который, возможно, зависит от y. Эту зависимость можно обозначить явно с помощью некоторой функции g(y), отображающей каждое значение y в то x, которое существует. Такая функция называется сколемовской функцией.

Слайд 85




	Если заменить на эту формулу переменную  x, то квантор существования можно убрать и переписать  выражение в новом виде
Описание слайда:
Если заменить на эту формулу переменную x, то квантор существования можно убрать и переписать выражение в новом виде

Слайд 86



		
		
	Пример.
	Привести к сколемовской форме следующую формулу: 

можно заменить переменную x на константу a, 
переменную u  на двухместную f(y, z), 
переменную w  на трехместную функцию g(y, z, v). 
Таким образом, получаем следующую форму:
Описание слайда:
Пример. Привести к сколемовской форме следующую формулу: можно заменить переменную x на константу a, переменную u  на двухместную f(y, z), переменную w  на трехместную функцию g(y, z, v). Таким образом, получаем следующую форму:

Слайд 87




	 Шаг 5. Преобразование выражения в предваренную (префиксную) форму. Так как в формуле кванторы существования отсутствуют, то все кванторы общности можно переместить в начало формулы. 
	Формула в таком виде называется формулой в предварительной форме, цепочка кванторов перед ней  префиксом, а следующее за ним бескванторное выражение – матрицей.
	Пример.
Описание слайда:
Шаг 5. Преобразование выражения в предваренную (префиксную) форму. Так как в формуле кванторы существования отсутствуют, то все кванторы общности можно переместить в начало формулы. Формула в таком виде называется формулой в предварительной форме, цепочка кванторов перед ней  префиксом, а следующее за ним бескванторное выражение – матрицей. Пример.

Слайд 88




	 Шаг 6. Приведение матрицы выражения к форме КНФ.  Известно, что любая логическая функция может быть представлена в форме КНФ. Для этого чаще всего используется метод эквивалентных  преобразований.
	Пример. 
	Из алгебры логики известны следующие равенства
Описание слайда:
Шаг 6. Приведение матрицы выражения к форме КНФ. Известно, что любая логическая функция может быть представлена в форме КНФ. Для этого чаще всего используется метод эквивалентных преобразований. Пример. Из алгебры логики известны следующие равенства

Слайд 89



			
			
	Применим их к полученному после шага 5 выражению:
Описание слайда:
Применим их к полученному после шага 5 выражению:

Слайд 90




	 Шаг 7.  Исключение кванторов общности. Так как в выражении остались кванторы общности, а их порядок несущественен, то можно эти кванторы опустить, то есть удалить у формулы префикс.
	Пример.
Описание слайда:
Шаг 7. Исключение кванторов общности. Так как в выражении остались кванторы общности, а их порядок несущественен, то можно эти кванторы опустить, то есть удалить у формулы префикс. Пример.

Слайд 91




	Шаг 8. Переход от выражения в виде КНФ к множеству предложений.  Для этого требуется убрать все операции конъюнкции, а каждый дизъюнкт представить как отдельное предложение, т.е. перейти от  выражения вида           к выражению        	  , в котором каждый элемент  предложение.
	Пример.
Описание слайда:
Шаг 8. Переход от выражения в виде КНФ к множеству предложений. Для этого требуется убрать все операции конъюнкции, а каждый дизъюнкт представить как отдельное предложение, т.е. перейти от выражения вида к выражению , в котором каждый элемент  предложение. Пример.

Слайд 92




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

	Пример.
Описание слайда:
Шаг 9. Переименование переменных. Символы переменных должны быть изменены так, чтобы каждый появлялся не более чем в одном предложении. Этот процесс называется разделением переменных. Пример.

Слайд 93



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

Слайд 94




	 Пример.
	Рассмотрим дизъюнкты:
C1: P(x)  Q(x),
C2: 
Так как аргументы предиката Р в C1 и C2. различны, то невозможно построить на их основе резольвенту, но если подставить f(a) вместо x в C1 и a вместо x в C2, то исходные дизъюнкты примут вид.
C1’: P(f(a)) Q(f(a)),
C2’:
Описание слайда:
Пример. Рассмотрим дизъюнкты: C1: P(x) Q(x), C2: Так как аргументы предиката Р в C1 и C2. различны, то невозможно построить на их основе резольвенту, но если подставить f(a) вместо x в C1 и a вместо x в C2, то исходные дизъюнкты примут вид. C1’: P(f(a)) Q(f(a)), C2’:

Слайд 95



	Следовательно, можно получить резольвенту    
	Следовательно, можно получить резольвенту    
                                 C3’: Q(f(a)) R(a).
	В общем случае, подставив f(x) вместо x в C1,  получим 
                                C1’’: P(f(x)) Q(f(x)). 
	Предикат P(f(x)) в C1’’ и предикат в C2 позволяют получить резольвенту 
                              C3: Q(f(x)) R(x).
Описание слайда:
Следовательно, можно получить резольвенту Следовательно, можно получить резольвенту C3’: Q(f(a)) R(a). В общем случае, подставив f(x) вместо x в C1, получим C1’’: P(f(x)) Q(f(x)). Предикат P(f(x)) в C1’’ и предикат в C2 позволяют получить резольвенту C3: Q(f(x)) R(x).

Слайд 96




	 Определение. Если два или более предиката (с одинаковым знаком) дизъюнкта C имеют наиболее общий унификатор g, то Cg  называется склейкой C.
Описание слайда:
Определение. Если два или более предиката (с одинаковым знаком) дизъюнкта C имеют наиболее общий унификатор g, то Cg  называется склейкой C.

Слайд 97




	Пример.
	Рассмотрим дизъюнкт 
		C= P(x)  P(f(y))  
 В этом дизъюнкте первый и второй предикаты имеют наиболее общий унификатор g={f(y)/x}. 
	Следовательно, 
		Cg=P(f(y))  
есть склейка C.
Описание слайда:
Пример. Рассмотрим дизъюнкт C= P(x)  P(f(y))  В этом дизъюнкте первый и второй предикаты имеют наиболее общий унификатор g={f(y)/x}. Следовательно, Cg=P(f(y))  есть склейка C.

Слайд 98




	 Определение. Пусть C1 и C2 – два дизъюнкта, которые не имеют никаких общих переменных. Пусть L1 и L2 – два предиката в C1 и C2. Если L1 и L2 имеют наиболее общий унификатор g, то дизъюнкт (C1g\L1g)  (C2g\L2g) называется резольвентой C1 и C2.
Описание слайда:
Определение. Пусть C1 и C2 – два дизъюнкта, которые не имеют никаких общих переменных. Пусть L1 и L2 – два предиката в C1 и C2. Если L1 и L2 имеют наиболее общий унификатор g, то дизъюнкт (C1g\L1g)  (C2g\L2g) называется резольвентой C1 и C2.

Слайд 99




	Пример.
	Пусть C1= P(x)   Q(x) и C2=	 R(x). 
	Так как x входит в C1 и C2, то заменим переменную в C2 и пусть C2= 	      R(y). 
	Выбираем L1= P(x) и L2=     
 L1 и L2 имеют наиболее общий унификатор g={a/x}. 
Следовательно, Q(a)  R(y) – резольвента C1 и C2.
Описание слайда:
Пример. Пусть C1= P(x)  Q(x) и C2=  R(x). Так как x входит в C1 и C2, то заменим переменную в C2 и пусть C2=  R(y). Выбираем L1= P(x) и L2= L1 и L2 имеют наиболее общий унификатор g={a/x}. Следовательно, Q(a)  R(y) – резольвента C1 и C2.

Слайд 100




	Пример.
Описание слайда:
Пример.

Слайд 101




	Переформулируем теперь уже известный алгоритм метода резолюций применительно к логике предикатов.
Описание слайда:
Переформулируем теперь уже известный алгоритм метода резолюций применительно к логике предикатов.

Слайд 102




	Шаг 1. Если в S есть пустой дизъюнкт, то множество S не выполнимо и алгоритм завершает работу, иначе переходим к
 шагу 2.
Описание слайда:
Шаг 1. Если в S есть пустой дизъюнкт, то множество S не выполнимо и алгоритм завершает работу, иначе переходим к шагу 2.

Слайд 103




	 Шаг 2. Найти в исходном множестве S такие дизъюнкты или склейки дизъюнктов C1 и C2, которые содержат унифицируемые литералы L1C1 и L2C2.
	Если таких дизъюнктов нет, то исходное множество выполнимо и алгоритм завершает работу, иначе переходим к шагу 3.
Описание слайда:
Шаг 2. Найти в исходном множестве S такие дизъюнкты или склейки дизъюнктов C1 и C2, которые содержат унифицируемые литералы L1C1 и L2C2. Если таких дизъюнктов нет, то исходное множество выполнимо и алгоритм завершает работу, иначе переходим к шагу 3.

Слайд 104




	 Шаг 3. Вычислить резольвенту C1 и C2, добавить ее в множество S и перейти к шагу 1.
Описание слайда:
Шаг 3. Вычислить резольвенту C1 и C2, добавить ее в множество S и перейти к шагу 1.

Слайд 105




	 Пример 1. Докажем с помощью метода резолюций справедливость следующих рассуждений.
Каждый член демократической партии голосует за президента и не любит коммунистов.
Некоторые демократы являются предпринимателями.
Следовательно, существуют предприниматели, которые не любят коммунистов
Описание слайда:
Пример 1. Докажем с помощью метода резолюций справедливость следующих рассуждений. Каждый член демократической партии голосует за президента и не любит коммунистов. Некоторые демократы являются предпринимателями. Следовательно, существуют предприниматели, которые не любят коммунистов

Слайд 106




 	Введем следующие предикаты:
C(x) – "x – член демократической партии";
W(x) – "x – голосует за президента "; 
R(x) - "x – не любит коммунистов ";
P(x) – "x – является предпринимателем".
	h1 = x(C(x)W(x)&R(x)), 
	h2 = x(C(x)&P(x)),
	S = x(P(x)&R(x)).
Описание слайда:
Введем следующие предикаты: C(x) – "x – член демократической партии"; W(x) – "x – голосует за президента "; R(x) - "x – не любит коммунистов "; P(x) – "x – является предпринимателем". h1 = x(C(x)W(x)&R(x)), h2 = x(C(x)&P(x)), S = x(P(x)&R(x)).

Слайд 107




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

Слайд 108




	 Пример 2. Докажем с помощью метода резолюций справедливость следующих рассуждений.
Некоторые руководители с уважением относятся ко всем программистам. 
Ни один руководитель не уважает бездельников. 
Следовательно, ни один программист не является бездельником.
Описание слайда:
Пример 2. Докажем с помощью метода резолюций справедливость следующих рассуждений. Некоторые руководители с уважением относятся ко всем программистам. Ни один руководитель не уважает бездельников. Следовательно, ни один программист не является бездельником.

Слайд 109




 	Введем следующие предикаты:
	C(x) – "x – руководитель";
	P(x) – "x – программист";
	B(x) – "x – бездельник";
	U(x,y) – "x уважает y".
Описание слайда:
Введем следующие предикаты: C(x) – "x – руководитель"; P(x) – "x – программист"; B(x) – "x – бездельник"; U(x,y) – "x уважает y".

Слайд 110




	Тогда посылки, записанные в виде предикатных выражений будут выглядеть так:



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

Слайд 111




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

Слайд 112
Логика предикатов, слайд №112
Описание слайда:

Слайд 113




	 Пример 3. Докажем с помощью метода резолюций справедливость следующих рассуждений.
Если родитель мужчина, то это отец.
Если ребёнок мужчина, то это сын. 
Иван  мужчина. 
Сидор мужчина. 
Иван родитель Сидора. 
Следовательно, Иван отец и Сидор сын
Описание слайда:
Пример 3. Докажем с помощью метода резолюций справедливость следующих рассуждений. Если родитель мужчина, то это отец. Если ребёнок мужчина, то это сын. Иван мужчина. Сидор мужчина. Иван родитель Сидора. Следовательно, Иван отец и Сидор сын

Слайд 114




 	Введем следующие предикаты:
C(x) – "x – сын";
О(x) – "x – отец "; 
R(x,y) - "x – родитель y ";
M(x) – "x – мужчина".
Константы: D – Иван, B – Сидор.
	h1 = xy(R(x, y)&M(x)O(x)), 
	h2 = xy(R(x, y)&M(y)C(y)),
 	h3 = M(D), 	
	h4 = M(B),	 
	h5 = R(D,B), 
	S = O(D)&C(B)).
Описание слайда:
Введем следующие предикаты: C(x) – "x – сын"; О(x) – "x – отец "; R(x,y) - "x – родитель y "; M(x) – "x – мужчина". Константы: D – Иван, B – Сидор. h1 = xy(R(x, y)&M(x)O(x)), h2 = xy(R(x, y)&M(y)C(y)), h3 = M(D), h4 = M(B), h5 = R(D,B), S = O(D)&C(B)).

Слайд 115




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

Слайд 116





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

Слайд 117






	 Определение. Клаузальной формой называется такая сколемовская форма, матрица которой имеет вид КНФ.
 	Любая сколемовская форма допускает эквивалентную ей клаузальную форму.
Описание слайда:
Определение. Клаузальной формой называется такая сколемовская форма, матрица которой имеет вид КНФ. Любая сколемовская форма допускает эквивалентную ей клаузальную форму.



Похожие презентации
Mypresentation.ru
Загрузить презентацию