Поиск по сайту
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ реферат на тему: Логика предикатов с одним переменнымИ, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для каждого x из . В таком случае выражение R ((х), y, ..., u) имеет значение И для данных y, ..., u и для каждого x из M, так как (х) для любого x принадлежит .
Аналогичным образом можно показать, что выражения
() R ((х), y, ..., u) и () R (x, y, ..., u)
также равносильны.
Рассмотрим формулу U(, ..., ), которую можно представить в форме
( x1)( x2)...( xp) B(, ..., , x1, ..., xp).
B(, ..., , x1, ..., xp)
представляет собой предикат, определённый на поле M и зависящий от p переменных x1, ..., xp. Каждое из этих переменных входит в формулу B только через предикаты , ..., . С другой стороны, мы видели, что предикаты (х) и ((х)) равносильны. Поэтому если в формуле B(, ..., , x1, ..., xp) мы заменим xi на (хi), то получим равносильное выражение:
B(, ..., , x1, ..., xp) B(, ..., ,(x1), ..., (xp)).
Отсюда следует, что
( xp) B(, ..., , x1, ..., xp) ( xp) B(, ..., , (x1), ..., (xp)).
Далее можно заключить, что
( xp) B(, ..., , (x1), ..., (xp))
B(, ..., , (x1), ..., (xp-1), xp).
Рассуждая аналогичным образом, мы получим
( xp-1) ( xp) B(, ..., , x1, ..., xp-1 , xp)
B(, ..., , (x1), ..., (xp-2), xp-1, xp)
и, наконец, придём к следующему:
( x1)( x2)...( xp) B(, ..., , x1, ..., xp)
B(, ..., , x1, ..., xp).
Правая часть последней равносильности, согласно смыслу символа , представляет не что иное, как формулу
( x1)...( xp) B(, ..., , x1, ..., xp),
отнесённую к полю .
Таким образом, мы доказали, что формула U(, ..., ) сохраняет своё значение, если её отнести к полю , и теорема, таким образом, доказана.
С л е д с т в и е. Если формула U, содержащая только предикаты, зависящие от одного переменного, является тождественно истинной для всякого поля, не превышающего элементов, где n число предикатов в U, то формула U тождественно истинна (т. е. истинна для любого поля). В самом деле допустим, что U не является тождественно истинной формулой. В таком случае её отрицание выполнимо на некотором поле. Так как также удовлетворяет условиям теоремы, то найдётся поле, содержащее не более элементов, на котором формула выполнима. Следовательно, U не может быть истинной на этом поле, что противоречит условию. Итак, предположение, что U не является тождественно истинной, приводит к противоречию, что и требовалось доказать. П Р И М Е Р 1: Итак, пусть дана формула U, имеющая вид: (x)[P(x)( P(x))], отнесённая к некоторому полю L. Для того, чтобы установить тождественную истинность этой формулы, нам достаточно проверить, является ли она тождественно истинной на поле, содержащем ровно элементов (см. выше). В данном случае число предикатов (n) равно 2, т.е. L может быть представлено как { a1, a2, a3, a4 }. Легко видеть, что формула U равносильна: (x)[P(x)(Q(x)P(x))], которая, отнесённая к полю L, равносильна : [P()(Q()P())] [P()(Q()P())] [P()(Q()P())] [P()(Q() P())]. Таким образом, представляет собой формулу, образованную только операциями алгебры высказываний над выражениями P() и Q(), где i=, т.е. её можно рассматривать как формулу алгебры высказываний, у которой P() и Q() являются элементарными переменными высказываниями. Значит, ответив на вопрос о тождественной истинности , мы сможем сказать, является ли формула U тождественно истинной или нет. является тождественно истинной в алгебре высказываний U также тождественно истинная формула на поле, содержащем элементов. Это оэначает, что U тождественно истинна. П Р И М Е Р 2: Доказать, что формула U, отнесённая к некоторому полю L, представленная как [(х)( Q(x)) P(x)], является тождественно истинной. Для этого она должна быть тождественно истинной на поле, содержащем ровно элементов. В данном случае n = 2, т.е. L можно опять определить как { a1, a2, a3, a4 }. Применяя равносильные преобразования над U, можем заключить её равносильность формуле: (х)[(Q(x))P(x)], которая, отнесённая к полю L, равносильна : [(Q())P()] [(Q())P()] [(Q())P()] [(Q())P()]. Легко видеть, что , как и в предыдущем примере, представляет собой формулу, образованную только операциями алгебры высказываний над выражениями P() и Q(), где i=, а поэтому её можно отнести к формулам скачать реферат 1 2 3 4 Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ Внимание! Студенческий отдых и мегатусовка после сессии!
Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.
|
Обратная связь. |