Solve Timed Logical and Quantitative Reasoning Cases

Problem Description

Automated reasoning systems often evaluate statements under incomplete information. Given a set of ground-truth observations and logical rules, a proposition can be:

• "TRUE": It must be true in all valid interpretations.
• "FALSE": It must be false in all valid interpretations (its negation is proven true).
• "CANNOT_DETERMINE": It is true in at least one valid interpretation and false in at least one valid interpretation.

You are given:

1. facts: A list of strings representing propositions known to be unconditionally true. If a fact starts with !, its negated proposition is unconditionally false (for example, "!A" means proposition A is false).
2. rules: A list of conditional implication strings in the format "P -> Q", meaning "if proposition P is true, then proposition Q must be true". Note that rules also enforce their contrapositive: "!Q -> !P".
3. queries: A list of proposition strings to evaluate.

Each proposition token is a non-empty alphanumeric string without spaces (e.g., "HospitalA", "BedOccupied"). A token preceded by ! denotes the negation of that proposition. For any query variable X, determine if X is "TRUE", "FALSE", or "CANNOT_DETERMINE".

Assume there are no contradictory premises in facts and rules.

Function Interface

def evaluate_propositions(
    facts: list[str],
    rules: list[str],
    queries: list[str]
) -> list[str]:
    pass

Input & Output Format

• facts: list of strings, each either "X" or "!X".
• rules: list of strings, each of the form "X -> Y", where X and Y can each be either a variable or a negated variable (e.g., "!A -> B").
• queries: list of query proposition strings (without !).
• Returns: list of strings ("TRUE", "FALSE", or "CANNOT_DETERMINE"), corresponding to each query in queries in order.

Constraints

• 1 <= len(facts) <= 200
• 0 <= len(rules) <= 500
• 1 <= len(queries) <= 200
• Variable names consist of 1 to 20 alphanumeric characters.
• The premises are guaranteed to be mutually consistent.

Examples

Example 1

facts = ["NurseOnDuty", "!Admitted"]
rules = [
    "NurseOnDuty -> TriageOpen",
    "TriageOpen -> Staffed",
    "Admitted -> BedAssigned"
]
queries = ["TriageOpen", "BedAssigned", "NurseOnDuty", "Admitted"]

# Output: ["TRUE", "CANNOT_DETERMINE", "TRUE", "FALSE"]

Explanation: NurseOnDuty is true, which implies TriageOpen is true. !Admitted means Admitted is false. However, Admitted -> BedAssigned only specifies what happens if Admitted is true; since Admitted is false, BedAssigned could be true or false (CANNOT_DETERMINE).

Example 2

facts = ["!Discharged"]
rules = [
    "Stable -> Discharged"
]
queries = ["Stable"]

# Output: ["FALSE"]

Explanation: By contrapositive, Stable -> Discharged implies !Discharged -> !Stable. Since Discharged is false, Stable must be false.