Презентация на тему: Тема 1. Математическая логика

Тема 1. Математическая логика
Классификация предикатов
Классификация предикатов
Классификация предикатов
Множество истинности предиката
Равносильность предикатов
Следование предикатов
Следование предикатов
Тема 1. Математическая логика
Тема 1. Математическая логика
Формулы логики предикатов
Интерпретация формулы на множестве М
Интерпретация формулы на множестве М
Двойной квантор существования
Разноименные кванторы
Разноименные кванторы
Законы де Моргана для кванторов
Применение кванторов к выражениям с конъюнкцией и дизъюнкцией
Доказательство 1:  x ( P ( x )  Q ( x ) )   x P ( x )   x Q ( x ) для конечного множества предметов
Доказательство 3:  x ( P ( x )  Q ( x ) )  (  xP ( x )   xQ ( x ) )
Опровержение обратной импликации  x ( P ( x )  Q ( x ) )  (  xP ( x )   xQ ( x ) )
Доказательство 4: (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) )
Опровержение обратной импликации (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) )
Импликация и кванторы
Тема 1. Математическая логика
Формулы: выполнимость
Формулы: тождественная истинность
Формулы: общезначимость
Пример тождественно ложной формулы
Тема 1. Математическая логика
Теорема о законах удаления квантора общности и введения квантора существования
Понятие равносильности формул
Тема 1. Математическая логика
Приведенная форма
Тема 1. Математическая логика
Предваренная нормальная форма
1/36
Средняя оценка: 4.2/5 (всего оценок: 2)
Код скопирован в буфер обмена
Скачать (95 Кб)
1

Первый слайд презентации: Тема 1. Математическая логика

Изображение слайда
2

Слайд 2: Классификация предикатов

Предикат Р ( х 1, х 2,..., х n ), заданный на множествах М 1, М 2,..., М n, называется: а) тождественно истинным, если при любой подстановке вместо переменных х 1, х 2,..., х n любых конкретных предметов a 1, a 2,..., a n из множеств М 1, М 2,..., М n соответственно он превращается в истинное высказывание Р ( a 1, a 2,..., a n ) ;

Изображение слайда
3

Слайд 3: Классификация предикатов

Предикат Р ( х 1, х 2,..., х n ), заданный на множествах М 1, М 2,..., М n, называется: б) тождественно ложным, если при любой подстановке вместо переменных х 1, х 2,..., х n любых конкретных предметов из множеств М 1, М 2,..., М n соответственно он превращается в ложное высказывание;

Изображение слайда
4

Слайд 4: Классификация предикатов

Предикат Р ( х 1, х 2,..., х n ), заданный на множествах М 1, М 2,..., М n, называется: в) выполнимым ( опровержимым ), если существует по меньшей мере один набор конкретных предметов a 1, a 2,..., a n из множеств М 1, М 2,..., М n соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат Р ( х 1, х 2,..., х n ) последний превратится в истинное ( ложное ) высказывание Р ( a 1, a 2,..., a n ).

Изображение слайда
5

Слайд 5: Множество истинности предиката

Множеством истинности предиката Р ( х 1, х 2,..., х n ), заданного на множествах М 1, М 2,..., М n, называется совокупность всех упорядоченных наборов ( a 1, a 2,..., a n ), в которых a 1  М 1, a 2  М 2, …, a n  М n, таких, что данный предикат обращается в истинное высказывание Р ( a 1, a 2,..., a n ) при подстановке х 1 = a 1, х 2 = a 2,..., х n = a n. Это множество будем обозначать Р +. Таким образом, Р + = {( a 1, a 2,..., a n ) : Р ( a 1, a 2,..., a n ) = 1}.

Изображение слайда
6

Слайд 6: Равносильность предикатов

Два n -местных предиката Р ( х 1, х 2,..., х n ) и Q ( х 1, х 2,..., х n ), заданных над одними и теми же множествами М 1, М 2,..., М n, называются равносильными, если набор предметов (элементов) a 1  М 1, a 2  М 2, …, a n  М n превращает первый предикат в истинное высказывание Р ( a 1, a 2,..., a n ) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание Q ( a 1, a 2,..., a n ). Другими словами (на языке множеств истинности), предикаты Р ( х 1, х 2,..., х n ) и Q ( х 1, х 2,..., х n ) равносильны тогда и только тогда, когда их множества истинности совпадают Р + = Q +. Утверждение о равносильности двух предикатов Р и Q символически будем записывать так: Р  Q. Переход от предиката Р 1 к равносильному ему предикату Р 2 называется равносильным преобразованием первого.

Изображение слайда
7

Слайд 7: Следование предикатов

Предикат Q ( х 1, х 2,..., х n ), заданный над множествами М 1, М 2,..., М n, называется следствием предиката Р ( х 1, х 2,..., х n ), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Р ( х 1, х 2,..., х n ). Другими словами (в терминах множеств истинности), можно сказать, что предикат Q является следствием предиката Р тогда и только тогда, когда Р +  Q +. Утверждение о том, что предикат Q является следствием предиката Р, будем символически записывать так: Р  Q.

Изображение слайда
8

Слайд 8: Следование предикатов

Например, одноместный предикат, определенный на множестве натуральных чисел, « n делится на 3» является следствием одноместного предиката, определенного на том же множестве, « n делится на 6». Язык множеств истинности позволяет установить взаимосвязь между понятиями равносильности и следования предикатов: два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый из них является следствием другого.

Изображение слайда
9

Слайд 9

Теорема. Каждый тождественно истинный n -местный предикат является следствием любого другого n -местного предиката, определенного на тех же множествах. Каждый n -местный предикат является следствием любого тождественно ложного n -местного предиката, определенного на тех же множествах.

Изображение слайда
10

Слайд 10

Теорема. Пусть Р ( х 1, х 2,..., х n ) и Q ( х 1, х 2,..., х n ) — два n -местных предиката, определенные на одних и тех же множествах, такие, что Q ( х 1, х 2,..., х n ) есть следствие Р ( х 1, х 2,..., х n ). Тогда: а) если Р ( х 1, х 2,..., х n ) тождественно истинный (выполнимый), то и Q ( х 1, х 2,..., х n ) тождественно истинный (выполнимый); б) если Q ( х 1, х 2,..., х n ) тождественно ложный (опровержимый), то и Р ( х 1, х 2,..., х n ) тождественно ложный (опровержимый).

Изображение слайда
11

Слайд 11: Формулы логики предикатов

Алфавит символов, из которых составляются формулы: предметные переменные: х, у, z, x i, … ; нульместные предикатные переменные: P, Q, P i … ; n -местные предикатные переменные: R (,...,), S (,...,), R i (,..., ) с указанием числа свободных мест в них; символы логических операций:      ; кванторы: ,  ; вспомогательные символы: (, ) ( скобки, запятая ).

Изображение слайда
12

Слайд 12: Интерпретация формулы на множестве М

Интерпретация превращает формулу логики предикатов в высказывание. 1 или 2 этапа: 1) Вместо каждой предикатной переменной подставим конкретный предикат, определенный на некотором выбранном множестве М. Формула превратится в конкретный предикат, заданный над множеством М. Если формула логики предикатов не содержала свободных предметных переменных, то полученный конкретный предикат является нульместным, т.е. будет высказыванием (истинным или ложным). Второй этап не нужен.

Изображение слайда
13

Слайд 13: Интерпретация формулы на множестве М

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

Изображение слайда
14

Слайд 14: Двойной квантор существования

Аналогично формуле с кванторами общности можно показать, что  y  N  x  M Q ( x, y ) =  x  M  y  N Q ( x, y ). «для каждого y существует x » = «для каждого x существует y ». Вывод : одноименные кванторы коммутативны

Изображение слайда
15

Слайд 15: Разноименные кванторы

Что можно сказать о паре высказываний: 1)  y  N  x  M Q ( x, y ) и 2)  x  M  y  N Q ( x, y ) ? Возьмем для примера m = n = 2. Обозначим Q ( a i, b j ) = p ij. Тогда 1)  y  N  x  M Q ( x, y ) = ( p 11  p 21 )  ( p 12  p 22 ) = p 11 p 21  p 12 p 22 = q. 2)  x  M  y  N Q ( x, y ) = ( p 11  p 12 )  ( p 21  p 22 ) = p 11 ( p 21  p 22 )  p 12 ( p 21  p 22 ) = p 11 p 21  p 12 p 22  p 11 p 22  p 12 p 21. = q  r.

Изображение слайда
16

Слайд 16: Разноименные кванторы

Импликация q  ( q  r ) является тавтологией, а обратная – нет (например, ( 0  1 )  0 = 1  0 = 0). Следовательно, мы показали (для частного случая), что имеет место  y  N  x  M Q ( x, y )   x  M  y  N Q ( x, y ). Обратная импликация (  ) в общем случае не верна.

Изображение слайда
17

Слайд 17: Законы де Моргана для кванторов

 x  M P ( x ) =  x  M  P ( x ) « не для всех предметов из множества M имеет место P ( x ) » = « существует предмет из множества M, для которого имеет место  P ( x ) ».  x  M P ( x ) =  x  M  P ( x ) « не существует предмета из множества M, для которого имеет место P ( x ) » = « для всех предметов из множества M имеет место  P ( x ) ».

Изображение слайда
18

Слайд 18: Применение кванторов к выражениям с конъюнкцией и дизъюнкцией

Для краткости опустим указание на множество предметов M : 1)  x ( P ( x )  Q ( x ) )   x P ( x )   x Q ( x ) 2)  x ( P ( x )  Q ( x ) )   x P ( x )   x Q ( x ) 3)  x ( P ( x )  Q ( x ) )  (  x P ( x )   x Q ( x ) ) 4) (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) )

Изображение слайда
19

Слайд 19: Доказательство 1:  x ( P ( x )  Q ( x ) )   x P ( x )   x Q ( x ) для конечного множества предметов

 x ( P ( x )  Q ( x ) ) = ( P ( a 1 )  Q ( a 1 ) ) … ( P ( a m )  Q ( a m ) ) = ( P ( a 1 ) … P ( a m ) )  ( Q ( a 1 ) … Q ( a m ) ) =  x P ( x )   x Q ( x ) ∎ Подобным образом для  и .

Изображение слайда
20

Слайд 20: Доказательство 3:  x ( P ( x )  Q ( x ) )  (  xP ( x )   xQ ( x ) )

Пусть  x ( P ( x )  Q ( x ) ) = 1, т.е. существует (по крайней мере один) предмет a k, такой, что P ( a k )  Q ( a k ) = 1. По свойствам конъюнкции должно быть P ( a k ) = 1 и Q ( a k ) = 1. Иначе говоря,  xP ( x ) = 1 и  xQ ( x ) = 1, т.е.  x P ( x )   x Q ( x ) = 1. 1  1. ∎

Изображение слайда
21

Слайд 21: Опровержение обратной импликации  x ( P ( x )  Q ( x ) )  (  xP ( x )   xQ ( x ) )

Пусть  x P ( x )   x Q ( x ) = 1, т.е.  xP ( x ) = 1 и  xQ ( x ) = 1. Следовательно, существует предмет a k, такой, что P ( a k ) = 1 и существует предмет a l, такой, что Q ( a l ) = 1. Может быть, a k  a l. Может быть P ( a l ) = 0 и Q ( a k ) = 0. Тогда P ( a k )  Q ( a k ) = 0 и P ( a l )  Q ( a l ) = 0. Таким образом, в общем случае не исключена ситуация, когда  x ( P ( x )  Q ( x ) ) = 0, т.е. 1  0, что противоречит определению импликации. ∎

Изображение слайда
22

Слайд 22: Доказательство 4: (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) )

Пусть  x P ( x )   x Q ( x ) = 1. Тогда, по крайней мере, один из предикатов, например, P ( x ), истинен на всем множестве M. Следовательно, формула P ( x )  Q ( x ) истинна на всем множестве M и  x ( P ( x )  Q ( x ) ) = 1. Иначе говоря, 1  1. ∎

Изображение слайда
23

Слайд 23: Опровержение обратной импликации (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) )

Пусть P ( a k ) = 0 для некоторого предмета a k и P ( x ) = 1 для остальных предметов множества M. Пусть Q ( a l ) = 0 для предмета a l  a k и Q ( x ) = 1 для остальных предметов множества M. Тогда  x ( P ( x )  Q ( x ) ) = 1, но  x P ( x )   x Q ( x ) = 0. Иначе говоря, 1  0. ∎

Изображение слайда
24

Слайд 24: Импликация и кванторы

«всякий предмет, обладающий свойством P, обладает и свойством Q »:  x  M ( P ( x )  Q ( x ) ) Имеют место импликации:  x ( P ( x )  Q ( x ) )  (  x P ( x )   x Q ( x ) ),  x ( P ( x )  Q ( x ) )  (  x P ( x )   x Q ( x ) ), но обратные – неверны.

Изображение слайда
25

Слайд 25

Еще две тавтологии с импликацией:  x ( P ( x )  Q ( x ) )  (  x P ( x )   x Q ( x ) ), (  x P ( x )   x Q ( x ) )   x ( P ( x )  Q ( x ) ).

Изображение слайда
26

Слайд 26: Формулы: выполнимость

Определение. Формула логики предикатов называется выполнимой (опровержимой) на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат. Другими словами, формула выполнима (опровержима) на М, если существует истинная (ложная) ее интерпретация на М.

Изображение слайда
27

Слайд 27: Формулы: тождественная истинность

Определение. Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

Изображение слайда
28

Слайд 28: Формулы: общезначимость

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

Изображение слайда
29

Слайд 29: Пример тождественно ложной формулы

Пусть Р ( x ) – произвольный предикат. Формула  Р ( x )   y Р ( y ) является тождественно ложной. Доказательство. От противного: пусть на некотором множестве М имеется конкретный предикат А ( х ), такой, что данная формула превращается в выполнимый предикат (от x )  А ( x )   y А ( y ). Иначе говоря, найдется предмет a  М, такой, что высказывание  А ( a )   y А ( y ) истинно. Истинность конъюнкции дает истинность высказываний 1)  А ( a ) и 2)  y А ( y ). Из истинности 1 следует, что высказывание А ( a ) ложно, а из истинности 2 – что предикат А ( y ) тождественно истинный и, значит, для любого предмета из М в том числе и для a  М, высказывание А ( a ) истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.

Изображение слайда
30

Слайд 30

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

Изображение слайда
31

Слайд 31: Теорема о законах удаления квантора общности и введения квантора существования

Теорема. Следующие формулы логики предикатов являются тавтологиями: а) (  х Р ( х ))  Р ( у ); б) Р ( у )   х Р ( х ). Доказательство формулы а). От противного. Предположим, что формула а) не тождественно истинна. Это значит: существует такой предикат А ( х ), определенный на некотором множестве M, что предикат (от у ) (  х A ( х ))  A ( у ) опровержим, т.е. превращается в ложное высказывание при подстановке вместо у некоторого a  М : (  х A ( х ))  A ( a ) = 0. Последнее означает, что 1) (  х A ( х )) = 1 и 2) A ( a ) = 0. Из соотношения (1) заключаем, что предикат А ( х ) тождественно истинный. Но это противоречит соотношению (2). Следовательно, сделанное предположение неверно, и данная формула — тавтология. ∎

Изображение слайда
32

Слайд 32: Понятие равносильности формул

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

Изображение слайда
33

Слайд 33

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

Изображение слайда
34

Слайд 34: Приведенная форма

Определение. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции , , , причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Изображение слайда
35

Слайд 35

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

Изображение слайда
36

Последний слайд презентации: Тема 1. Математическая логика: Предваренная нормальная форма

Определение. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида ( K 1 х 1 )...( K m х m ) ( F ( х 1, х 2,..., х n ) ), где K i есть один из кванторов  или  ( i = 1,..., m ), m < n, причем формула F не содержит кванторов и является приведенной формулой. (Заметим, что кванторы в формуле могут отсутствовать вовсе.)

Изображение слайда