Материал: discrete_mathematics

12.Побудувати скінченний автомат, що відшукує у вхідному тексті (слові) певний фрагмент, тобто автомат, що переходить у заключний стан тоді й тільки тоді, коли вхідне слово в алфавіті X = {a, b} завершується підсловом.

(а) abba; (б) bbbaba; (в) aabbaaa; (г) baabbba.

13.Довести такі рівносильні співвідношення для регулярних виразів:

(а) (a b)*ab(a b)* b*a* = (a b)*; (б) (ab)*a = a(ba)*;

(в) (a* b)* = (a b)*; (г) (a*b)*a* = a*(ba*)*;

(д) ((a bb)*aa)* = e (a bb)*aa; (е) (aa)*(e a) = a*;

(є) (a*bbb)*a* = a*(bbba*)*; (ж) a(ba a)*b = aa*b(aa*b)*.

14. Довести чи спростувати твердження про рівносильність таких регулярних виразів:

(а) (ab a)*a = a(ba a)*; (б) (ab a)*ab = (aa*b)*; (в) (a b)*b = (a*b)*;

(г) b(ab b)*a = aa*b(aa*b)*; (д) (a b)* = a*(ba*)*;

(е) a(a b)* b(a b)* e = (a b)*.

221

Розділ 6 СЕМАНТИЧНІ ЗАСАДИ ЛОГІКИ ПРЕДИКАТІВ

У попередніх розділах, які стосувались математичної логіки, увагу було зосереджено переважно на синтаксичних аспектах. Тепер детальніше розглянемо семантичні аспекти логіки.

6.1. Класи n-арних і квазіарних функцій

Основним поняттям логіки із семантичного погляду є поняття предиката, яке інтуїтивно можна тлумачити як відображення значень змінних у значення істинності.

Наприклад, розглянемо предикат, що задається виразом

якщо х > y та y > z, то х > z.

Тут вільними змінними є змінні х, y, z. Якщо такий предикат інтерпретується над множиною цілих чисел, то його значення слід обчислювати за наявності значень цих змінних. Нехай х має значення 17, y – 11, z – 3. Це означає, що визначено певний стан

змінних, який записуватимемо у вигляді [х 17, y 11, z 3].

Стан змінних також називають інтерпретацією, оцінкою або

розподілом змінних.

Таким чином, розглянутий предикат є відображенням множини станів змінних у значення істинності. Множину значень істинності позначають Bool = {1, 0} або Bool = {T, F}. Щоб зберегти однотипність позначень з іншими розділами посібника, уживатимемо позначення {1, 0}. Розглядаючи предикат як указану функцію, будемо називати стани змінних даними (з області визначення предиката).

Застосувавши предикат до даного (стану змінних)

отримуємо істиннісне значення 1.

Наведені міркування дають змогу формально означити поняття стану змінних. Нехай V – множина змінних (імен), M – множина предметних (базових) значень. Тоді довільна часткова

функція із V у M називають станом змінних, іменованими да ними, квазіарними даними, або просто даними. Множину та-

ких даних позначатимемо D = V → M = VM.

Якщо іменами є цілі числа, то квазіарне дане вигляду

[1 a1, 2 a2,… n an]

називатимемо n-арним даним. Такі дані зазвичай позначають у вигляді кортежа (a1, a2,… an). Кортеж є елементом декартового добутку M n. Відповідно квазіарні дані є елементами узагальненого часткового декартового добутку VM.

Уведені позначення дають змогу означити класи n-арних та квазіарних функцій. Функція, визначена на класі n-арних даних, називають n-арною, а функцію, визначену на класі квазіарних даних, – квазіарною.

Спеціальними класами таких функцій є предикати та ординарні функції. Предикат p: M n → Bool називають n-арним преди катом, а предикат q: VM → Bool – квазіарнимпредикатом. Функцію f: M n→ M називають n-арною ординарною функцією, а функцію g: VM → M – квазіарною ординарною функцією. Термін

ординарний часто пропускатимемо.

Розглянемо предикат над цілими числами, який задається виразом

якщо х > y та z > t, то х + z > y + t.

Із яких предикатів і функцій побудовано цей предикат? Бачимо, що тут фігурують бінарний предикат > та бінарна функція +. Однак якого типу є функції х+z та y+t ? Оскільки функції визначені над станами змінних, то вони є квазіарними. Ці квазіарні функції отримано підстановкою (суперпозицією) квазіарних функцій розіменування (узяття значення) змінних у бінарну функцію +. Функції розіменування позначатимемо ′х, ′y, ′z, ′t. Наприклад, на стані

значення змінних ′х, ′y, ′z дорівнюють відповідно 17, 11, 3, значення змінної ′t не визначено. Позначатимемо це таким чином:

Тут символ ↓ означає, що значення функції визначено, а сим-

вол ↑ – що воно не визначено.

Позначаючи підстановку квазіарних предикатів (функцій) у n- арний предикат як SPn , отримуємо, що предикат х > y подають як SP2 (>,′x,′ y). Відповідно подають також інші предикати. Тут SPn − операціянадквазіарнимипредикатами. Їїзадаютьформулою

SP2 ( p, g1,..., gn )(d) = p(g1 (d),..., gn (d)),

де p – n-арний предикат, g1,…,gn – квазіарні ординарні функції, d – номінативне дане.

Яким чином побудовано предикат, що заданий виразом

якщо х > y та y > z, то х > z?

Очевидно, що його побудовано із квазіарних предикатів

SP2 (>,′x,′ y), SP2 (>,′ y,′z) та SP2 (>,′x,′z)

за допомогою спеціальної операції над предикатами, яку називають імплікацією й позначають символом →. Операції подібного типу називатимемо композиціями предикатів, а відповідне подання предиката – композиційною формулою (інколи вживають також назви композиційний терм, операторний терм, семантич нийтерм). Остаточно отримуємо таку композиційну формулу:

SP2 (>,'x,'y) & SP2 (>,'y,'z) → SP2 (>,'x,'z).

Приклад 6.1.

1. Обчислити предикат

SP2 (>,'x,'y) & SP2 (>,'y,'z) → SP2 (>,'x,'z).

на номінативному даному d = [х 17, y 11, z 3 ].

Спираючись на означення композицій суперпозиції, обчислюємо спочатку

SP2 (>,'x,'z)(d) = >('x(d),'z(d)) = >(17,3) =1.

За означенням композиції імплікації отримуємо, що

SP2 (>,'x,'z) & SP2 (>,'y,'z)→ SP2 (>,'x,'z)(d ) =1.

2. Обчислити вказаний предикат на номінативному даному d = [х 1, y 11, z 3].

224

Спочатку обчислюємо

SP2 (>,'x,'z)(d) = > ('x(d),'z(d)) = > (1,3) = 0.

Оскільки консеквент хибний, то обчислюємо антицедент. Для цього обчислюємо значення

SP2 (>,'x,'y)(d) = > ('x(d),'y(d)) = > (1,11) = 0,

SP2 (>,'y,'z)(d) = > ('y(d),'z(d)) = > (11,3) =1.

Звідси

SP2 (>,'x,'y) & SP2 (' >,'y,'z)(d ) = 0,

(SP2 (>,'x,'y) & SP2 (' >,'y,'z) → SP2 (>,'x,'z))(d ) =1.◄

Для функцій вводимо композицію суперпозиції квазіарних ординарних функцій у n-арну функцію:

SFn ( f , g1,..., gn )(d ) = f (g1 (d),..., gn (d)),

де f – n-арна функція, g1,…, gn – квазіарні ординарні функції, d – номінативне дане.

Приклад 6.2. Написати композиційну формулу для предиката, що поданий виразом

якщо х > y та z > t, то х + z > y + t,

та обчислити його значення на номінативному даному d = [х 17, y 11, z 5, t 3].

Указаний вираз можна задати композиційною формулою

SP2 (>,'x,'y) & SP2 (' >,'y,'z) → SP2 (>, SF2 (+,'x,'z),SF2 (+,'y,'t).

Обчислюємо

SP2 (>, SF2 (+,'x,'z),SF2 (+,'y,'t)(d) = > (SF2 (+,'x,'z)(d),SF2 (+,'y,'t)(d)) =

=> (+ ('x(d),'z(d)),+ ( y(d))) = > (+(17,5),+ (11,3) => (22,14)) =1.

Це означає, що

SP2 (>,'x,'y) & SP2 (' >,'y,'z) → SP2 (>, SF2 (+,'x,'z),SF2 (+,'y,'t))(d) = 1. ◄

Підсумовуючи розглянуті приклади, доходимо висновку, що семантика логіки предикатів спирається на дві алгебри (алгебричні системи): алгебру предметних значень із n-арними операціями та алгебру квазіарних предикатів і функцій з композиціями як операцій.

225