12

1 Упражнение 2 Основни математически и езикови понятия д-р. Gábor Kallós 2017 2018

симетричен преходен

Благодарност Благодарност Това практическо упражнение надгражда до голяма степен върху следната книга Елементи на теорията на изчисленията (Прентис-Хол), Автори: Хари Р. Луис, Христос Х. Пападимитриу (Проф.); и теорията на цифровите изчисления, използвана в Университета на Панония (Веспрем). върху фолиото от практиките на предмета, Автори: д-р. Ищван Хекъл (лектор, ръководител на темата) и д-р. Máté Hegyháti Авторът би искал да ви благодари, че разрешихте използването на материалите и за многобройната помощ, която получихте по време на разработването на учебната програма.

Съдържание Набори, Операции Набори от мощности Подредени двойки Отношения Числа, Количествено съответствие Основни езикови понятия Азбука, думи, езици Операции с думи и езици 3

Проблеми (спец. Бинарни отношения) Решете дали отношението R 1, дадено от графиката по-долу, има изброените свойства! R 1 = < (a, a), (a, b), (a, c), (b, c), (c, a) >R 1 R1 рефлексивен ли е? О: Не, тъй като цикли b и c липсват R1 симетричен ли е? О: Не, защото няма ръбове (b, a) и (c, b) R1 антисиметричен ли е? О: Не, защото R 1 е преходен? Vá.: Не, защото a c b 9

Проблеми (спец. Бинарни отношения) Решете дали връзките, дадени от следващите графики, имат изброените свойства! (рефлексивен, симетричен, преходен) R 1 = 1 5 2 3 6 7 4 Рефлексивен N, симетричен N, преходен N R 2 = a b Рефлексивен Y, симетричен N, преходен Y c 10

Проблеми (спец. Бинарни отношения) Решете дали връзките, дадени от следващите графики, имат изброените свойства! (рефлексивен, симетричен, преходен) R 1 = рефлексивен Y, симетричен Y, преходен Y R 2 = рефлексивен Y, симетричен N, преходен Y a f a e b d d c c b 11