48. Понятя повних систем булевих функцій

Система мулевих ф-й назив. функціонально повною, якщо [Σ] = р₂ , якщо р₂ – множина всіх можливих булевих ф-й, що залежать від будь-якої к-ті змінних. Нехай дано 2 системи булевих ф-й Σ₁ та Σ₂ , при чому Σ₁ – функціонально повна. Якщо кожна ф-я системи Σ₁ може бути зобр. у вигляді суперпозиції функцій системи Σ₂ , то Σ₂ також буде ф-онально повною.

49.Теорема Поста про повноту.

Теорема. Не існує інших максимальних класів, крім Т₀ , Т₁ , S, M, L. Іншими словами, якщо деякий клас не міститься з цих п’яти, то він повний. Класами Поста назив. такі 5 множин булевих ф-й: 1) Т₀ – ф-я, що зберігає 0; 2) Т₁ – ф-я, що зберігає 1; 3) S – само двоїсті ф-ї; 4) M – монотонні ф-ї; 5) L – лінійні ф-ї. (Булева ф-я монотонна, якщо для будь-яких пар наборів значень змінних (а₁,…,а_n) і (b₁,…,b_n), для яких викон. співвідношення (а₁,…,а_n) ≤ (b₁,…,b_n) буде правильною і рівність f(а₁,…,а_n) ≤ f(b₁,…,b_n) ). Критерії повноти поста: Система булевих ф-й Σ є функціонально повною, якщо і тільки якщо вона містить хоча б одну ф-ю, що не зберігає 0, не зберігає 1, не само двоїста, не монотонна, не лінійна.

50.Правила дедуктивних висновків в логіці висловлювань.Дедуктивне міркування — це міркування, в якому між засновниками і висновком існує відношення логічного слідування.Міркування за схемою «доведення від протилежного» — це міркування, в якому істинність деякого висловлювання доводять на підставі того, що із заперечення цього висловлювання за допомогою інших міркувань виводять протиріччя.

53.Поняття предикату, квантору

Предикатом назив. ф-я Р(x₁,x₂…,x_n), змінні якої приймають значення з деякої множини n (1 або 0), яка назив. областю значеннь. К-ть аргументів – порядок предиката. Аргументи предиката назив. термами. Терма-конст. та терма-змінні назив. предметними константами або предметними змінними. Квантори. Нехай Р(х) – предикат. Висловлення «для всіх Х, які належать М» позн.

х Р(х) (квантор загальності).

54. Закони у логіці предикатів

55.Алгоритм зведення вільної форми алгебри логіки предикатів до внф.

Випередженою нормальною формою (ВНФ) назив. формула алгебри логіки, яка в своєму записі містить тільки операції заперечення, диз’юнкції та кон’юнкції, а знаки заперечення відносяться тільки до предикатних змінних або висловлювань. Алгоритм переходу до ВНФ: 1) усунути з формули операції «~», «→» : А~В = (А→В)(В→А); А→В = ¬ А v В. 2) внести знак заперечення безпосередньо до атома: 3) внести квантори в префікс.

56. Закони математичної логіки першого ступеня. Поняття множини істинності предиката.

Множиною істинності предиката Р(x₁,x₂…,x_n), заданого над множинами М₁,М₂…,М_n назив. сукупність всіх впорядкованих n-систем (а₁,а₂…,а_n)  М₁хМ₂ х…хМ_n , для яких даний предикат перетворюється в істинний вираз при підстановці. Позначається множина істинності Р⁺(а₁,а₂…,а_n)

57.Основні поняття теорії графів (порядок, степені вершин, порожній граф, мультиграф, псевдо граф, орієнтований та неорієнтований граф).

Упорядкована пара, що складається з множини V сукупності Е називається графом з множиною вершин В та множиною ребер Е. В залежності від типу ребрів розрізняють наступні види графів: мультиграф – граф без петель, в якому допускаються кратні ребра; Кратні ребра – це ребра, які з’єднують інцидентні пари вершин. Псевдограф - з петлями та кратними ребрами. Граф, в якому вершини поєднані орієнтованими дугами називається орієнтованим графом. Граф, який одночасно містить і петлі і дуги називається змішаним. Граф, в якому всі вершини пов’язані одна з одною називається повним графом.