2013年7月12日 星期五

11108 - Tautology


Problem D: Tautology

WFF 'N PROOF 是一個藉由骰子玩的邏輯遊戲,骰子的六面分別有可能有的字符 K, A, N, C, E, p, q, r, s, t。Well-formed formula (WFF) 定義為一個符合以下規則的字串:
  • p, q, r, s, t  都屬於 WFFs
  • 如果 w 屬於 WFF, 則 Nw 屬於WFF
  • 如果 wx 屬於 WFFs, 則 Kwx, Awx, Cwx, Ewx 也都屬於 WFFs.
WFF 字串的意思解釋如下:

  • p, q, r, s, t 是 0 (false) 或 1 (true) 的邏輯代數。
  • K, A, N, C, E 分別表示 and(&), or(|), not(!), implies(→), equals(==),真值表如下:
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

tautology (恆真式) 在 WFF 中,不管邏輯代數的值為何,計算出來值皆為 1 (true)。
例如
ApNp 是恆真式,p and (not p) 代入 p = 0 or p = 1 都是 1 (true)。
ApNq 不是恆真式,因為當 p = 0, q = 1 計算得到 0 (false)

寫程式判斷  WFF 是不是恆真式。


輸入有多組測資,每組只會有一行不超過 100 字元的 WFF。
最後一行以 0 結束程式。

對於每組測資,輸出 tautology not。

Sample Input

ApNp
ApNq
0

Possible Output for Sample Input

tautology
not

Gordon V. Cormack