Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

60 Следовательно, P(a)  Q(a)=И . Значит, т.к. P(a)=И , то и Q(a)=И . Так как в исчислении предикатов имеется бесконечное число областей, которые в свою очередь могут быть бесконечны, то, вообще говоря, имеется бесконечное число интерпретаций формулы исчисления предикатов. Следовательно, в отличие от исчисления высказываний, невозможно доказать общезначимость или противоречивость формулы оценкой формулы при всех возможных интерпретациях. В настоящее время разработаны и разрабатываются процедуры для проверки невыполнимости формул исчисления предикатов. 12. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму Предваренная нормальная форма В исчислении высказываний существуют две нормальные формы – конъюнктивная и дизъюнктивная. В исчислении предикатов также имеется нормальная форма, называемая предваренной нормальной формой. Определение. Формула F исчисления предикатов находится в предваренной нормальной форме тогда и только тогда, когда формула F имеет вид (Q 1 x 1 )…(Q n x n )(M), где каждое (Q i x i ), i 1 n ,  , есть или (  x i ) или (  x i ) , а M есть формула, не содержащая кванторов. (Q 1 x 1 )…(Q n x n ) называется префиксом, а M – матрицей формулы F .