Главная
 Сайт Андрея Зайчикова
Среда, 23 Июля 2003г. 
Карта сайта Поиск по сайту Написать письмо  
 .:Навигатор 
Новости
Библиотека
Статьи
Олимпиады
FAQ (ЧаВо)
Гостевая книга 
Ссылки
 .:Информация 

Выскажись!
Простым высказыванием называется простое повествовательное предложение, относительно которого можно сказать, что оно истинно или ложно. Примерами таких высказываний являются предложения:
1. Всероссийская олимпиада по информатике проводится весной (истинно).
2. 5 в квадрате меньше нуля (ложно).
Одно из слов простого высказывания на русском языке назовем определяющим, если в результате добавления перед ним частицы HЕ значение простого высказывания изменяется на противоположное. В первом примере таким словом является слово "весной", а во втором "меньше".
Сложным высказыванием назовем два и более простых высказывания, соединенные союзами И, ИЛИ, оборотами ЕСЛИ ..., ТО ... и ... ТОГДА И ТОЛЬКО ТОГДА, КОГДА ... . Hазовем эти союзы и обороты вместе с частицей HЕ логическими операциями, обозначив их следующим образом:
HЕ ...!...
... И ......&...
... ИЛИ ......|...
ЕСЛИ ..., ТО ......=>...
... ТОГДА И ТОЛЬКО ТОГДА, КОГДА ......<=>...
Значение сложного высказывания можно определить, используя таблицы истинности логических операций. Приведем таблицы истинности перечисленных операций, обозначив ложное значение нулем, а истинное -- единицей: 
A   !A
0   1
1   0

A   B   A&B   A|B   A=>B   A<=>B
0   0   0     0     1      1
0   1   0     1     1      0
1   0   0     1     0      0
1   1   1     1     1      1
В сложном высказывании операции имеют следующие приоритеты в порядке от высшего к низшему: !, &, |, =>, <=>. Hапример, в выражении A<=>!B=>C|D&E операции будут выполняться в таком порядке: (A<=>((!B)=>(C|(D&E)))). Здесь и далее в качестве имен высказываний будем использовать большие буквы латинского алфавита.
Рассмотрим следующую последовательность описаний.
а) Сначала идут описания простых высказываний вида:
<имя>=<простое высказывание>
В каждом <простом высказывании> определяющее слово заключается в круглые скобки.
б) Затем из описанных ранее высказываний с помощью логических операций строятся сложные высказывания по одному из следующих двух правил:
<имя>=!<имя>
<имя>=<имя><логическая операция><имя>
При использовании второго правила операция ! (HЕ) не может использоваться в качестве <логической операции>.
В указанной последовательности описаний имя каждого следующего высказывания обозначается не встречавшейся ранее буквой. Высказывание, построенное последним, назовем результирующим высказыванием.

Требуется: 1. Построить представление результирующего высказывания, использующее только имена простых высказываний, заменяя имя каждого сложного высказывания на его описание, заключив его в скобки.
2. Изменить полученное в пункте 1 логическое выражение так, чтобы операции ! (HЕ) стояли только перед именами простых высказываний, а не перед скобками, и истинность результирующего высказывания при этом не изменилась. Скобки можно как оставлять, так и раскрывать, используя приоритеты операций. Заметим, что в измененном логическом выражении возможно появление любых из перечисленных выше логических операций, отличных от имевшихся в исходном логическом выражении.
3. Построить результирующее высказывание на русском языке согласно полученному в пункте 2 выражению, опуская круглые скобки у определяющих слов в простых высказываниях и круглые скобки в логическом выражении.

Ввод:
В первой строке входного файла содержится число N, задающее количество описаний в последовательности. В последующих N строках записаны описания по определенным выше правилам, каждое описание -- в отдельной строке. Простые высказывания обозначаются буквами из диапазона от A до J и имеют длину не более 50 символов. Сложные высказывания обозначаются буквами из диапазона от K до T, пробелы в их определениях отсутствуют. В конце файла может содержаться одна или несколько пустых строк.

Вывод:
В выходном файле должны находиться 3 строки, каждая из которых является ответом на соответствующие пункты задания. Вторая строка должна содержать не более 50000 символов. В третьей строке слова, заменяющие логические операции, записываются заглавными русскими буквами и отделяются от простых высказываний пробелами. При отсутствии решения по какому-либо из пунктов задания соответствующая этому пункту строка должна быть пустой.

Пример: 

6
A=(шел) дождь
В=асфальт (мокрый)
C=(хочется) гулять
K=А&B
L=!К
М=L=>C

Результат:
((!(A&B))=>C)
((!A|!B)=>C)
ЕСЛИ HЕ шел дождь ИЛИ асфальт HЕ мокрый, ТО хочется гулять

Примечание:
Если в выходном файле вторая строка пустая, то ответ на пункт 3 оцениваться не будет.

 .:Реклама 
 
 © Андрей Зайчиков