Логика предикатов лк 4

1. Примеры выполнимых, невыполнимых и общезначимых формул:

Пусть формула задана в виде: x yP ( x, y ), где предикат Р х, у
означает sin x cos y и определен на области M E E , где
E 0 0 ,44 0 (символ a, b означает, что рассматриваемая
переменная x принимает значения от a до b, то же и для y). Ясно,
что в этом случае формула x yP ( x, y ) тождественно истинная в
области M, а поэтому и выполнима в этой области.
Если же предикат sin x cos y рассматривать в другой
области, например M E1 E1 , где E1 46 0 ,224 0 , то формула
x yP ( x, y ) является тождественно ложной. Поскольку
рассматриваемая формула не является тождественно истинной на
всякой области, то она и не общезначима.

2. Рассмотрим другой пример:

Пусть заданы предикаты: P(x)– “число кратно 7”, Q(y) – “число кратно 3” и
P ( x ) Q ( y ) , определенные в области M E E , где E {1,2,3,...}. На какой области
формула x y( P( x) Q( y)) выполнима, невыполнима и является ли она общезначимой?
Так как для предиката P(x) I p {7,14,21,...,7n,...}, а для предиката Q(y)
I Q 3,6,9,...,3n,... , то для предиката P ( x ) Q ( y ) I p Q {21,42,63,...,21n,...}. А это означает,
что существуют такие x I pи x I Q, что среди натуральных чисел N всегда
найдется такое число, при котором будет истинна формула x y ( P( x) Q( y )) . Это
число I P Q . Например, для чисел 7 I p и 3 I Q существует число 21 I P Q(это же
число принадлежит и каждому в отдельности множеству I P и I Q ). Следовательно,
рассматриваемая формула является истинной на множестве I P Q , т.е. она
выполнима в этой области (на этом множестве), а следовательно, и в области M.
Кроме того, какие бы числа x и y мы ни взяли соответственно из I P и I Q , для
них всегда найдется такое число из I P Q , что будет истинна формула x y ( P( x) Q( y )),
т.е. эта формула тождественно истинная в этой области.
Если же предикат P ( x ) Q ( y ) мы будем рассматривать в области M 1 E1 E1,
где E1 {1,2,...,20}, то формула x y ( P( x) Q( y )) является тождественно ложной.
Действительно, среди пар чисел множества M1 не найдется ни одной такой пары
чисел, для которой были бы истинны предикаты P ( x ) Q ( y ) . Следовательно, на
множестве M1 формула является тождественно ложной, а значит, и невыполнимой.
И, наконец, эта формула необщезначима, так как не является тождественно
истинной на всякой области.

3.

Интерес представляют общезначимые формулы, так как они
являются логическими законами. Такой простейшей формулой
является формула x( P( x) P( x)). Причем, независимо от
конкретного смыслового содержания предиката P(x), эта формула
является тождественно истинной в любой области M.
Действительно, x( P ( x) P ( x)) x(1) . 1
Если квантор всеобщности применить к конъюнкции
любого предиката P(x) и его отрицанию, т.е. x( P( x) P( x)), то
получим тождественно ложную формулу в любой области M.
Действительно, x( P ( x) P ( x)) x(0) 0.
В то же время x(0) 1 значит, формула x( P( x) P( x))
является логическим законом.

4. Пример:

Рассмотрим еще один пример, показывающий, как с
помощью равносильных преобразований устанавливается
общезначимость формул логики предикатов:
x( P( x) Q( x)) xP( x) xQ( x) x( P( x) Q( x)) xP( x) xQ( x)
x P( x) Q( x) xP( x) xQ( x) x( P( x) Q( x)) xP( x) xQ( x)
x( P( x) Q( x)) xQ( x) xP( x) xP( x) Q( x) Q( x)) xP( x)
x( P( x) Q( x)) (Q( x) Q( x)) xP( x) xP( x) Q( x) xQ( x)
xP( x) xQ( x) xP( x) 1 xQ( x) 1
Таким образом, мы получили заданную формулу, которая
является тождественно истинной для любых двух одноместных
предикатов и в любой области (поскольку область заранее не
оговаривалась). Значит, формула общезначима.

5. 3.8. Применение языка логики предикатов в математике и технике.

Как было показано в разделе 1 на соответствующих
примерах, алгебра логики является основным теоретическим
средством для построения цифровых автоматов и, в частности,
электронных цифровых вычислительных машин.
Именно благодаря алгебре логики стало возможным
появление в 1945 г. первой электронной ЭВМ ЭНИАК.
Логика предикатов пока такого широкого применения не
нашла. Тем не менее, в самой математике она применяется для
компактной записи определений, теорем и доказательств, а в
технике может быть той благодатной почвой, на основе которой
строятся системы искусственного интеллекта.

6.

Рассмотрим некоторые примеры использования языка логики
предикатов в математике. Предварительно введем соглашение о том,
что для большей ясности после кванторов и в соответствующей
переменной в некоторых случаях будем указывать область ее
определения, а также будем применять символ эквивалентности .
Тогда определение предела числовой последовательности на
языке логики предикатов запишется так:
lim a n 0 n0 n N (n n0 a n a )
n
Здесь использован трехместный предикат: P( , n, n 0 ) – ( n n0 a n a )
Определение возрастающей функции можно записать так:
x1 E x 2 E( x1 x 2 f ( x1 ) f ( x 2 ))
Здесь использован двухместный предикат P( x1 , x 2 ) -
( х1 х2 f x1 f ( x2 ))

7.

Рассмотрим записи некоторых теорем на языке логики
предикатов:
x E ( P( x) Q( x)) ; (1)
x E (Q( x) P( x)) ; (2)
x E ( P ( x) Q( x)) ; (3)
x E (Q( x) P ( x)) . (4)
Две теоремы, у которых условие первой является
заключением второй, а условие второй является заключением
первой, называются взаимно обратными друг другу. Так, теоремы
(1) и (2), а также (3) и (4) – взаимно обратные теоремы. При этом
если одну из них называют прямой теоремой, то вторая
называется обратной.
Две теоремы, у которых условие и заключение одной
являются отрицанием соответственно условия и заключения
другой, называются взаимно противоположными.

8.

Значительный интерес представляет построение утверждения,
отрицающего справедливость некоторой теоремы, если она может быть
записана в таком виде:
x E P x Q x
Очевидно, что для опровержения этой теоремы необходимо
доказать справедливость противоположного утверждения:
x E ( P( x) Q( x)) x E ( P( x) Q( x)) x E ( P( x) Q( x))
Следовательно, чтобы доказать, что теорема x E ( P( x) Q( x))
неверна, достаточно указать такой элемент x E, для которого предикат
P(x) истинен, а предикат Q(x) – ложен. Другими словами, нужно
привести контрпример, опровергающий теорему x E ( P( x) Q( x))

9.

Как уже говорилось, алгебра логики сыграла решающую роль в
создании цифровых ЭВМ. Первые ЭВМ могли выполнять только
арифметические действия над числами. Но человеку этого было мало. И
уже практически сразу встал вопрос: а нельзя ли сделать ЭВМ
усилителем интеллектуальных способностей человека? Иными словами,
нельзя ли создать мыслящую машину?
Чтобы решить эту глобальную проблему, человек должен был
научить машину понимать естественный язык, чтобы он мог на нем
общаться с машиной. Но чтобы этого достигнуть, процесс должен быть
не односторонним (когда машину пытаются заставить понимать
естественный язык), а двухсторонним (когда в естественном языке
находят такие его особенности и законы, которые позволили бы
формировать его и сделать науку о языке – лингвистику – не
описательной, а точной).

10.

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