Спирина, М.С. Дискретная математика

235 Т а б л и ц а 5.5 Следствия и равносильности логики предикатов Равносильности для 3 Правила Равносильности для V 3x3yQ(x, у) <=> ЗуЗх Q(x, у) Правила перестановки кванторов VxVy (?(х, у) » VyVx Q(x, у) 3xVyQ(x, у) => Vy3xQ(x, у) Зх F(x) <=> VxF(x) Перенос отрицания с квантора на предикат Vx F(x) <=> Зх F(x) 3xF(x) <=> Vx F(x) Vx F(x) <=> 3xF(x) 3x(F(x) v Ф(х)) <=> 3xF(x) v ЗхФ(х) Правила дистрибутивности кванторов Vx ( F(x) л Ф(х)) <=> Vx F(x) л УхФ(х) 3x(F(x) л Ф(х)) => 3xF(x) л ЭхФ(х) V x ( /r(x) v Ф(х)) => Vx f(x ) v VxФ(x) 3x(M a f (x ) ) => M л 3 x / ’(x) Vx(A/ a F(x)) => M a Vx f(x ) Зх(Л/ v /"(x)) => Л/ v 3x F(x) \ /x(M v F(x)) => M v VxF(x)