سوال ۱۰۱ کنکور ارشد علوم کامپیوتر ۱۳۹۸ — می‌خواهیم تابع f را به‌صورت استقرایی روی گزاره‌ها (فرمول‌های منطق…

Question

می‌خواهیم تابع f را به‌صورت استقرایی روی گزاره‌ها (فرمول‌های منطق گزاره‌ای که با اتم‌های P₁، P₂، ... و ادوات منطقی ∧، ∨، ¬، → ساخته شده‌اند) طوری تعریف کنیم که برای هر A که در فرم نرمال عطفی باشد، f(A) تعداد نقیض اتم‌های به‌کار رفته در A را محاسبه کند. کدام مورد یک تعریف استقرایی درست برای این منظور می‌تواند باشد؟

Accepted Answer

∀ᵢ f(Pᵢ) = ۰، f(A ∧ B) = f(A ∨ B) = f(A) + f(B)، f(¬A) = ۱ + f(A)، f(A → B) = f(A) × f(B) + ۱

Answer

∀ᵢ f(¬Pᵢ) = ۱، f(A ∧ B) = f(A ∨ B) = f(A → B) = f(A) + f(B)، ∀ᵢ f(Pᵢ) = ۱، f(¬A) = ۱ + f(A)

Answer

∀ᵢ f(Pᵢ) = ۰، f(A ∧ B) = f(A ∨ B) = f(A → B) = ۱ + f(A) + f(B)، f(¬A) = ۱ + f(A)

Answer

∀ᵢ f(Pᵢ) = ۰، f(A ∧ B) = f(A ∨ B) = f(A → B) = max f(A), f(B) ، f(¬A) = ۱

What value must fff produce?

What value must $f$ produce?