Логика высказываний и предикатов


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
1 Классическая логика. З аконы логики предикатов Для нульместных и одноместных предикатов справедливы следующие равносильные формулы и клаузы: ∀ x (A(x)&B)≡ ( ∀ x A(x))& B ( 3 ) ∃ x (A(x) & B)≡ ( ∃ x A(x)) & B ( 4 ) ∀ x (A(x) V B)≡ ( ∀ x A(x)) V B ( 5 ) ∃ x (A(x) V B)≡ ( ∃ x A(x)) V B ( 6 ) ( ∀ x A(x) �= B)≡ ∃ x (A(x) �= B) ( 7 ) ∀ x (A(x) �= B)≡ ∃ x A(x) �= B ( 8 ) ( B �= ∀ x A(x) ) ≡ ∀ x ( B �= A(x) ) ( 9 ) ( B �= ∃ x A(x) ) ≡ ∃ x ( B �= A(x) ) ( 10 ) - ∀ x A(x)≡ ∃ x ( - A(x) ) ( 11 ) - ∃ x A(x)≡ ∀ x ( - A(x)) ( 12 ) ∀ x (A(x)&B(x))≡ ( ∀ x A(x))& ( ∀ x B(x)) ( 13 ) ∃ x (A(x)VB(x))≡ ( ∃ x A(x))V ( ∃ x B(x)) ( 14 ) ∃ x (A(x)& B(x)) |= ( ∃ x A(x))& ( ∃ x B(x)) ( 15 ) ( ∀ x A(x))V( ∀ x B(x)) |= ∀ x (A(x)VB(x)) ( 16 ) Теорема 1. 5 . В формулах (7), (8) отсутствует равносильность. Доказательство Докажем, что левые части в формулах (7), (8) не являются следствиями соответствующих правых частей. Чтобы показать это, возьмем следующую интерпретацию M ( M ) :  M - множество натуральных чисел,  A ( x ) =" x - четное число",  B ( x ) =" x - нечетное число". Тогда формула ( ∃ x ∈ M A ( x ))& ( ∃ x ∈ M B ( x ) ) - истинна, а формула ∃ x ∈ M ( A ( x )& B ( x )) - ложна. При этой же интерпретации формула ∀ x ∈ M ( A ( x ) VB ( x )) - истинна, а 2 формула ( ∀ x ∈ M A ( x )) V ( ∀ x ∈ M B ( x )) - ложна. Что и требовалось доказать. Для двуместных предикатов справедливы следующие равносильные формулы: ∀ x ∀ y Р( x , у ) ≡ ∀ y ∀ x Р( x , у ) , (17) ∃ x ∃ у Р( x , у ) ≡ ∃ у ∃ x Р( x , у ) , (18) т.е. одинаковые кванторы при двуместных предикатах можно перестав л ять мес тами. Д ля перестановк и кванторов ∃ и ∀ справедлива следующая клауза : ∃ х ∀ y Р( х , y ) |= ∀ y ∃ х Р( х , y ) . (19) Теорема 1. 6 . В формуле (19) отсутствует равносильность. Доказательство Докажем, что левая часть в формуле (19) не явля е тся следствием правой част и . Чтобы показать это, возьмем следующую инте рпретацию M ( M ) :  M 1 =" множество шляп" ,  M 2 =" множество людей",  M= { M 1 , M 2 }  Р( х , y ) = «шляпа x пришлась человеку y впору» Тогда формула ∀ "человека y " ∃ "шляпа х " Р(х, y ) = «шляпа x пришлась человеку y впору» - истинна, а формула ∃ "шляпа х " ∀ "человека y " Р( х , y ) = «шляпа x пришлась человеку y впору» - ложна. Что и требовалось доказать. И стинн ыми являются следующие к л а уз ы : 3 Таблица 1 Истинные клаузы 1. ∀ х ∀ y Р( х , y ) |= ∀ х ∃ y Р( х , y ) 2. ∀ х ∀ y Р( х , y ) |= ∃ х ∀ y Р( х , y ) 3. ∀ х ∀ y Р( х , y ) |= ∃ х ∃ y Р( х , y ) 4. ∃ х ∀ y Р( х , y ) |= ∃ х ∃ y Р( х , y ) 5. ∀ х ∃ y Р( х , y ) |= ∃ х ∃ y Р( х , y ) 6. ∃ х ∀ y Р( х , y ) |= ∀ y ∃ х Р( х , y ) 7. ∀ х ∀ y Р( х , y ) |= ∀ х Р( х , х ) 8. ∃ х Р( х , х ) |= ∃ х ∃ y Р( х , y ) 9. ∀ х ∀ y Р( х , y ) |= Р( a , b ) 10. Р( a , b ) |= ∃ х ∃ y Р( х , y ) 11. ∀ y Р( a , y ) |= ∀ y ∃ х Р( х , y ) 12. ∀ y Р( a , y ) |= ∃ х ∀ y Р( х , y ) 13. ∀ х Р( х , b ) |= ∃ y ∀ х Р( х , y ) 14. ∀ х Р( х , b ) |= ∀ х ∃ y Р( х , y ) 15. ∀ х ∃ y Р( х , y ) |= ∃ y Р( a , y ) 16. ∃ y ∀ х Р( х , y ) |= ∃ y Р( a , y ) 17. ∃ х ∀ y Р( х , y ) |= ∃ х Р( х , b ) 18. ∀ y ∃ х Р( х , y ) |= ∃ х Р( х , b ) Сколемовские функции и сколемизация формул Формула логики предикатов имеет нормальную форму , если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам. Например, для формулы ( ∃ x A ( x ) - � ∀ y B ( y ) ) - � C ( x ) нормальной формой будет ( ∃ x A ( x ) & ∃ y ( - B ( y ) ) ) V C ( x ) Формулу А ( х 1 , х 2 ,...,х п ) с помощью формул ( 3 ) - (16) можно привести к 4 равно сильной формуле в предваренной форме (ПНФ) , в которой кванторы ∀ , ∃ не перемешиваются, а встречаются группами и все «вынесены вле во», т.е. либо к виду ∃ x 1 ∃ x 2 ... ∃ x n ∀ y 1 ∀ y 2 ... ∀ y n ∃ z 1 ∃ z 2 ... ∃ z n B ( x 1 , x 2 , ... , x n , y 1 , y 2 , ... , y n , z 1 , z 2 , ... , z n ) либо к виду ∀ u 1 ∀ u 2 ... ∀ u n ∃ v 1 ∃ v 2 ... ∃ v n ∀ w 1 ∀ w 2 ... ∀ w n B ( u 1 , u 2 ,..., u n , v 1 , v 2 ,..., v n , w 1 , w 2 ,..., w n ) , где в формуле В нет кванторов. Легко добиться, чтобы последними стояли кванторы существования. Для этого используется тожде ство: B ( x 1 , x 2 ,..., x n , z 1 , z 2 ,..., z n )≡ ∃ u ( B ( x 1 , x 2 ,..., x n , z 1 , z 2 ,..., z n )& T ( u )) где T ( u ) — произвольная общезначимая формула. Пример. Н ормальной форм а ∀ x ∃ y A ( x , y ) & ∀ x ∃ z ( - B ( x , z ) ) приводится к ПНФ ∀ x ∃ y ∃ z ( A ( x , y ) & ( - B ( x , z ) ) ) Следующий алгоритм всякую формулу логики предикатов позволяет перевести в ПНФ. 1. Исключить логические операции импликации и эквивалентности. 2. Перенос операции отрицания непосредственно к пропозициональным переменным с помощью раскрытия скобок. 3. Переименование связанных переменных. 4. Вынесение кванторов с помощью законов логики предикатов. Пример . П рименим этот алгоритм к формуле ∀ x (( ∃ y A ( x , y ) - � ∀ y ( - B ( x , y ) ) - � C ( x ) ) . 1. ∀ x ( ∃ y A (x , y ) & ∃ y B(x, y ) V C (x) ) 2. Операция отрицания отсутс т вует . 3. Переименовываем x на z . У первой ссылки ∃ y A ( x , y ) заменяем y на v . Во второй ссылке о ставляем y . Получим ∀ x ( ∃ v A ( x , v ) & ∃ y B ( x , y ) V C ( x ) ) 4. Выносим кванторы ∀ x ∃ v ∃ y ( A ( x , v ) & B ( x , y ) V C ( x ) )


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.

Приложенные файлы

  • pdf 10ML&TA_Rudakov
    Сколемовские функции
    Размер файла: 824 kB Загрузок: 0
  • pdf 01ML&TA_Rudakov
    Логика, математическая логика, классическая логика
    Размер файла: 443 kB Загрузок: 0
  • pdf 02ML&TA_Rudakov
    Высказывания и операции
    Размер файла: 563 kB Загрузок: 0
  • pdf 03ML&TA_Rudakov
    Формулы и булевы функции
    Размер файла: 489 kB Загрузок: 0
  • pdf 04ML&TA_Rudakov
    Логические законы
    Размер файла: 572 kB Загрузок: 0
  • pdf 05ML&TA_Rudakov
    Клаузы
    Размер файла: 584 kB Загрузок: 0
  • pdf 06ML&TA_Rudakov
    Силлогизмы
    Размер файла: 767 kB Загрузок: 0
  • pdf 07ML&TA_Rudakov
    Метод резолюций
    Размер файла: 654 kB Загрузок: 0
  • pdf 08ML&TA_Rudakov
    Предикаты
    Размер файла: 563 kB Загрузок: 0
  • pdf 09ML&TA_Rudakov
    Интерпретации формул
    Размер файла: 676 kB Загрузок: 0

Добавить комментарий