деревья строго не судите издержки текстовой графики
рисовать их надо не так...

{/Exist} квантор существования
{/All} квантор всеобщности
{/belong} принадлежит

Коллоквиум часть 1

Также небольшое отступление (не касается конкретно этой работы): при доказательстве законов эквивалентности можно (но не нужно! делайте как удобнее - это не является ошибкой) не рассматривать очевидные значения некоторых идентификаторов. Достаточно лишь дописать что при данном значении данного идентификатора левая и правая часть уравнения имеют такое-то значение и всё выражение либо истинно, либо неопределенно.
Написал коряво, поэтому поясню на примере:
В случае задачи 13:
P = ((e1&&(e2||e3)) = (e1&&e2)||(e2&&e3))
Очевидно, при e1 = U левая и правая часть выражения не определены, а потому и P = U.
Далее рисуется таблица истинности со всеми возможнами значениями e1, e2 и e3, кроме e1 = U, которая на треть меньше обычной. Вот так%). Главное при этом способе не забыть написать, почему вы не указали некоторое значение некоторого идентификатора в таблице %).

#! /usr/bin/env ruby

n = gets.to_i

bot = 10**(n - 1)
top = 10**n - 1

for k in bot .. top
puts k if k == k*k%(10**n)
end

Добавлено (26.09.2007, 23:35)
---------------------------------------------
оно должно быть понятнее,так что если что,лечше пользоваться этим

Выложено решение коллоквиума 50 летней давности)))
Имеются в наличии решение задач нашего коллоквиума....
За правильность и фиговый подчерк не отвечаю...бугагага
коллоквиум

Добавлено (12.10.2007, 21:29)
---------------------------------------------
Можно ли упростить?
((a<>b) or (b>0)) and ((a=b) or (a>0))
<> - не равно

В принципе, можно показать, что это равносильно просто (a > 0) - делается элементарно, рассмотрением трех случаев (двух для доказательства, что при предусловии a > 0 предикат всегда истиннен и ещё одного для доказательства что при a <= 0 предикат всегда ложен). Кто-нибудь знает, можно ли упростить это выражение какими-нибудь элементарными преобразованиями, чтобы было более очевидно, откуда взят ответ (а возможно ещё быстрее и короче)?

Добавлено (12.10.2007, 22:00)
---------------------------------------------
Сори, понял, что ты спрашиваешь уже про другую задачу - ту же, про которую спрашиваю и я %))) В общем, я упрощаю до a > 0, но делается это не очень красиво (т.к. непонятно, откуда я выдумал этот ответ), но (надеюсь) правильно. Вот рассуждения:
Докажем, что A = ((a != b ИЛИ b > 0) И (a = b ИЛИ a > 0)) равносилен (a > 0). Для этого покажем что предикат истиннен тогда и только тогда, когда a > 0 и ложен, когда !(a > 0).
1) Пусть a > 0. Тогда, очевидно A = ((a != b ИЛИ b > 0) И (a = b ИЛИ a > 0)) = ((a != b ИЛИ b > 0) И (a = b ИЛИ T)) = ((a != b ИЛИ b > 0) И T) = (a != b ИЛИ b > 0).
Рассмотрим два случая:
a) a != b. В этом случае A = (a != b ИЛИ b > 0) = (T ИЛИ b > 0) = T
b) a = b. В этом случае A = (a != b ИЛИ b > 0) = (F ИЛИ b > 0) = (b > 0) = T, т.к. если a > 0 и a = b, то b > 0.
Таким образом в случае, когда a > 0 предикат A = T. Покажем, что он истиннен только в этом состоянии, для этого найдем все его возможные значения при a <= 0:
2) Пусть a <= 0. Тогда, очевидно A = ((a != b ИЛИ b > 0) И (a = b ИЛИ a > 0)) = ((a != b ИЛИ b > 0) И (a = b ИЛИ F)) = ((a != b ИЛИ b > 0) И (a = b)) = ((a != b И a = b) ИЛИ (b > 0 И a = b)) = (F ИЛИ (b > 0 И a = b)) = (b > 0 И a = b) = F, т.к. если a <= 0 и a = b, то заведомо b <= 0
Т.к. во всех возможных случаях при a <= 0 A = F, а при a > 0 A = T, то предикат A эквивалентен предикату (a > 0).

В общем даже и не знаю, существуют ли более простые варианты упрощения...

Коллоквиум часть 3

e->id->(C(x,y))
значит (C(x,y)) - предикат с переменными любого типа, он же - выражение логического типа. Значит, и ({/Exist}x (C(x,y))) - тоже предикат и переменная логического типа, взятая в скобки.
e->id->({/Exist}x (C(x,y)))
значит ({/Exist}x (C(x,y))) - предикат с переменными любого типа. Значит, и ({/All}y ({/Exist}x (C(x,y)))) - тоже предикат и переменная логического типа, взятая в скобки.
e->(e=>e)->(id1=>e)->(id1=>id2)->((A^B)=>id2)->((A^B)=>({/All}y ({/Exist}x (C(x,y)))))
((A^B)=>({/All}y ({/Exist}x (C(x,y))))) - это предикат в расширенном смысле. Если мы уберем лишне скобки и сохраним смысл, он им же и останется: (A^B)=>{/All}y {/Exist}x C(x,y).
Это предикат. Доказано.

2.
S -> 1T | 0S | E(epsilon)
T -> 0T | E(epsilon)

L(G) = {E(epsilon), 0* 1 0*}
Грамматика задает язык состоящий из пустой цепочки и всех цепочек
состоящих из некоторого числа(даже нулевого) 0,
затем одной 1 и затем некоторого числа(даже нулевого) 0.

разве эта грамматика не может задать цепочку вида 0* ? (то есть S -> 0S -> 00S -> 00)

Я б поставил в противоположную от вашей... то есть из того, что все элементы массива неположительны следует, что найдутся 2 корня уравнения и только два.

Добавлено (Сегодня, 00:33)
---------------------------------------------
100% 29 не верен.... там достаточное условие, а не необходимое.

Мы на паре 30 делали. Там тоже было необходимое условие

Добавлено (Сегодня, 00:34)
---------------------------------------------
y0ma, похоже на правду. Я пока этого варианта придерживаться буду

И по поводу номера 6.
Как будет правильно
S-> 0S|1S|2S|3S|4S|5S|6S|7S|8S|9S|AS|BS|CS|DS|ES|FS|EPSILON
или
S-> 0S|1S|2S|3S|4S|5S|6S|7S|8S|9S|AS|BS|CS|DS|ES|FS|0eps|1eps|2eps|3eps|4eps|5eps|6eps|7eps|8eps|9eps|Aeps|Beps|Ceps|Deps|Eeps|Feps

Или может какие другие варианты есть?

#6
В начале обязательно должно быть 0x, после чего не менее одного символа:
S->0x1T|0x2T|0x3T|0x4T|0x5T|0x6T|0x7T|0x8T|0x9T|0xaT|0xbT|0xcT|0xdT|0xeT|0xfT
T->1T|2T|3T|4T|5T|6T|7T|8T|9T|aT|bT|cT|dT|eT|fT|0T| E