# UVa 10847

Jump to navigation
Jump to search

## 10847 - Basic Tautologies[edit]

## Summary[edit]

Write a program to check whether given expression is a valid Reverse Polish Notation formula under given constraints, and if it is a tautology.

## Explanation[edit]

The truth tables given in the problem statement use {0, 1} for the truth values, but it is more natural here to use -1 for false, and +1 for truth. Then the operator "=" becomes just the usual multiplication, and "-" is multiplication by -1.

The expression is a tautology, if it evaluates to +1 regardless of the variables' values, and this can only happen when these two conditions are satisfied:

- the minus sign occurs an even number of times,
- each of the variables occurs an even number of times.

## Input[edit]

3 aa= aa=- ab

## Output[edit]

tautology formula incorrect