Which of the following compound propositions is a TAUTOLOGY?
((P -> Q) and P) -> Q is the Modus Ponens rule, which evaluates to True under all truth value assignments.
Let P and Q be two propositions. Which of the following is logically equivalent to P -> Q?
P -> Q is logically equivalent to ~P or Q, its contrapositive ~Q -> ~P, and the negation of (P and ~Q).
Consider the predicate formula: ∀x ∃y (P(x, y) -> Q(x)). What is its negation in Prenex Normal Form?
Negating ∀x ∃y (P(x,y) -> Q(x)) gives ∃x ∀y ~(~P(x,y) or Q(x)) = ∃x ∀y (P(x,y) and ~Q(x)).
What is the total number of distinct truth functions (boolean functions) of n variables?
For n variables, there are $2^n$ truth table rows. Each row can evaluate to 0 or 1, giving 2^{$2^n}$ distinct functions.
Which of the following set of connectives is NOT functionally complete?
{->, or} cannot express logical negation (NOT) because true operands under -> and or always yield true.