Question

Explain why each of the following are tautologies. That is, what expression(s) of predicate logic did we substitute into which tautologies of propositional logic?

a) (P(X) OR ((Y)) = (g(Y) OR p(x))
b) (p(X,Y) AND P(X,Y)) = P(X,Y)
c) (p(X) + FALSE) = NOT P(X)

Answer 1

Step-by-step explanation:

a) (P(X) OR ((Y)) = (g(Y) OR p(x))

This is a tautology because it is an instance of the commutative property of OR, which states that P OR Q is equivalent to Q OR P for any propositions P and Q. In this case, we can substitute P(X) for P and g(Y) for Q to get:

(P(X) OR g(Y)) = (g(Y) OR P(X))

b) (p(X,Y) AND P(X,Y)) = P(X,Y)

This is a tautology because it is an instance of the idempotent property of AND, which states that P AND P is equivalent to P for any proposition P. In this case, we can substitute p(X,Y) for P to get:

(p(X,Y) AND p(X,Y)) = p(X,Y)

c) (p(X) + FALSE) = NOT P(X)

This is a tautology because it is an instance of the law of excluded middle, which states that P OR NOT P is always true for any proposition P. In this case, we can substitute p(X) for P to get:

(p(X) OR FALSE) = NOT p(X)

Since OR with FALSE is always equivalent to the original proposition, this can be simplified to:

p(X) = NOT p(X) OR TRUE

And since NOT P OR TRUE is always true for any proposition P, this is a tautology.