• [IV] Tautology

  • 时间限制: 1000 ms 内存限制: 131072 K
  • 问题描述
  • WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:

    • p, q, r, s, and t are WFFs
    • if w is a WFF, Nw is a WFF
    • if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

    The meaning of a WFF is defined as follows:

    • p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
    • K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.
    Definitions of K, A, N, C, and E
    w x Kwx Awx Nw Cwx Ewx
    1 1 1 1 0 1 1
    1 0 0 1 0 0 0
    0 1 0 1 1 1 0
    0 0 0 0 1 1 1

    A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.

    You must determine whether or not a WFF is a tautology.

  • 输入
  • Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case.
  • 输出
  • For each test case, output a line containing tautology or not as appropriate.
  • 样例输入
  • ApNp
    ApNq
    0
  • 样例输出
  • tautology
    not
  • 提示
  • 来源
  • Show after the contest
  • 操作

显示春菜