Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

А формула, имеющая вид:

(x) B(x),

равносильна формуле

B()  B() ...  B().

В таком случае произвольная формула U, отнесённая к полю {, ..., }, равносильна формуле , в которой все кванторы заменены операциями логического произведения и логической суммы. Если в U входили только предикаты A1..., An, зависящие от одного переменного, то  представляет собой формулу, образованную только операциями алгебры высказываний над выражениями Ai(xj), 1 ? i ? n, 1 ? j ? . Так как предикаты Ai(x) совершенно произвольны, то выражения Ai(xj) представляют собой совершенно произвольные высказывания. Формулу  тогда можно рассматривать как формулу алгебры высказываний, у которой Ai(xj) являются элементарными переменными высказываниями. Тогда вопрос о тождественной истинности U на поле , , ...,  оказывается эквивалентным вопросу о тождественной истинности , как формулы алгебры высказываний с переменными высказываниями Ai(xj).

Заметим, что формула алгебра высказываний  по существу не зависит от того, каковы элементы поля {, ..., }, а зависит только от их числа, так как если мы возьмём другое поле {¢, ..., ¢}, то в  произойдёт только перемена обозначений переменных высказываний Ai(xj) на Ai(xj¢). В силу этого мы можем сказать, что если  тождественно истинна, как формула алгебры высказываний, то формула U тождественно истинна на любом поле из p элементов, и обратно. С другой стороны, был получен конструктивный способ определять – является произвольная формула алгебры высказываний тождественно истинной или нет. Применяя этот критерий, мы можем установить, будет ли произвольная формула U, содержащая только предикаты от одного переменного, тождественно истинной на любом поле, содержащем p =  элементов. В таком случае в силу высказанного выше положения мы можем решить также и вопрос о том, будет формула 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=, а поэтому её можно отнести к формулам алгебры высказываний, у которой P() и Q() являются элементарными переменными высказываниями. Является ли формула  тождественно истинной?

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

			Q	(Q)P

Таким образом, формула (Q)P является выполнимой, следовательно,  является тождественно истинной формулой в алгебре высказываний  U также тождественно истинная формула на поле, содержащем  элементов. Это означает, что U тождественно истинна.

§3. Поиск доказательств в натуральном интуиционистском исчислении предикатов с e-символом и предикатом существования

Рекомендуем скачать другие рефераты по теме: сочинение изложение, курсовые работы бесплатно.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки