DWITE '11 R3 #5 - Tautology

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE, December 2011, Problem 5

XKCD Tautology Club

We define a propositional formula as follows:

  • \{a,b,\ldots,j\} are atomic propositions, representing either true or false.
  • If A and B are propositional formulae, then so are:
    • A \wedge B\wedge is boolean "and"
    • A \vee B\vee is boolean "or"
    • \neg A\neg is boolean "not"

For example, ((a \vee b) \wedge (\neg c \vee a)) is a propositional formula. A tautology is a propositional formula that equates to true for all possible value assignments to the atomic propositions. Our previous example ((a \vee b) \wedge (\neg c \vee a)) is not a tautology because for the assignments a = \text{false}, b = \text{false} and c = \text{true}, the formula evaluates to a false. However (a \vee \neg a) is a tautology because no matter what the atomic proposition is this equates to true; (true or not-true) == true, (false or not-false) == true.

The input will contain 5 test cases, each three lines (not more than 255 characters) with a propositional formula per line.

The output will contain 5 lines of output, each three characters long. Y for tautology, N for not tautology.

Sample Input

((a v b) ^ (~c v a))
(a v ~a)
~(a ^ ~a)
((a ^ b) v ~(c ^ ~c))

Note that ~ is used for \neg, ^ for \wedge, and v for \vee.

Sample Output


Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


There are no comments at the moment.