JNTU MCA I MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (October/ November - 2020 - R15)

A Well-Formed Formula (WFF) in predicate calculus is defined recursively as follows:

1. Any atomic formula (a predicate symbol applied to a sequence of terms) is a WFF.
2. If P is a WFF, then ¬P is a WFF.
3. If P and Q are WFFs, then (P ∧ Q), (P ∨ Q), (P → Q), and (P ↔ Q) are WFFs.
4. If P is a WFF and x is a variable, then (∀x)P and (∃x)P are WFFs.
5. A string is a WFF if and only if it can be constructed by a finite number of applications of the above rules.

Examples:

• WFF: (∀x)(P(x) → Q(x))
• Not a WFF: (∀x)P ∨ Q(x) (missing parentheses or scope definition) or P(x, y) ∧ (missing operand).

To show that B is tautologically implied by ( ( A ∧ B ) → ( C ∧ ¬C ) ) ∨ ¬A, we must show that the implication (( ( A ∧ B ) → ( C ∧ ¬C ) ) ∨ ¬A) → B is a tautology. Using the resolution method, we negate the implication and check for unsatisfiability:

1. Negated expression: (( ( A ∧ B ) → ( C ∧ ¬C ) ) ∨ ¬A) ∧ ¬B
2. Simplify the implication (P → Q ≡ ¬P ∨ Q): (¬(A ∧ B) ∨ (C ∧ ¬C)) ∨ ¬A
3. Apply De Morgan's Law: (¬A ∨ ¬B ∨ (C ∧ ¬C)) ∨ ¬A
4. Simplify using associativity and idempotency: (¬A ∨ ¬B ∨ (C ∧ ¬C))
5. Now consider the full conjunction: (¬A ∨ ¬B ∨ (C ∧ ¬C)) ∧ ¬B
6. Since (C ∧ ¬C) is a contradiction (False), the expression simplifies to: (¬A ∨ ¬B ∨ False) ∧ ¬B
7. This reduces to: (¬A ∨ ¬B) ∧ ¬B
8. Using the distributive law: (¬A ∧ ¬B) ∨ (¬B ∧ ¬B)
9. Which simplifies to: (¬A ∧ ¬B) ∨ ¬B
10. By absorption law: ¬B

Since the negation of the implication is not a contradiction (it is true when B is false), the original statement does not tautologically imply B. However, if we assume the premise is true, then (¬A ∨ ¬B) must be true. If A is true, B must be false; if A is false, the premise is satisfied regardless of B. Thus, B is not tautologically implied.