У розділі логіка висловлювань розглядаються булеві функції, тобто функції, що приймають тільки два значення: істина або брехня. Булеві функції можна поділити на класи функцій (групи функцій), щодо певної ознаки. Клас булевих функцій називається замкнутим, якщо комбінація функцій з даного класу міститься в ньому ж. Під комбінацією булевих функцій будемо розуміти функцію, що складається з інших булевих функцій, з'єднаних знаками логічних операцій.
Існує кілька замкнутих класів функцій:
1) Клас функцій, що зберігають нуль:.
2) Клас функцій, що зберігають одиницю:.
3) Клас S самодвоїстих функцій складають функції, на протилежних наборах приймають протилежні значення.
4) Клас лінійних функцій L складають функції, які представляються полиномом Жегалкина першого ступеня.
5) Клас М монотонних функцій: для довічних векторів і. де. . вводиться наступне відношення часткового порядку. Вважається що . якщо для. Клас M визначається наступним чином:
Перевірка приналежності булевої функції замкнутим класам здійснюється по таблиці істинності. Перевірка приналежності булевої функції класу L здійснюється шляхом побудови полінома Жегалкина.
Функція алгебри логіки називається монотонною. якщо для будь-яких n мірних довічних наборів, з того, що. випливає, що
Теорема про монотонних функціях: будь-яка булева функція в сигнатурі алгебри логіки, яка не містить заперечень, є монотонною функцією. для будь-якої монотонної функції алгебри логіки, відмінної від 0 і 1, знайдеться рівносильна їй булева функція без заперечень.
Приклад 1.Определить, чи є функція монотонної.
- не містить заперечень, є монотонною.
Функція називається двоїстої функцією до функції. Функція називається самодвоїстих. якщо.
Самодвоїстих є функції
Перевірку на самодвоїстих функції можна здійснювати по таблиці істинності, для чого в останньому стовпці: перший 0 або 1 замінюють на 1 або 0, ставлять на останнє місце, якщо на останньому місці стоїть 1 або 0, перевірку ведуть далі - порівнюють другий рядок і передостанню, і так далі до середини. Якщо ж вийшли два однакових значення хоча б на двох симетричних відносно середини рядках останнього стовпця таблиці істинності, то функція не є самодвоїстих.
Приклад 2. Визначити, чи є функціясамодвойственной.
Побудуємо двоїсту функцію до вихідної:
Якщо двоїста функція до вихідної дорівнює вихідної, то вихідна функція самодвоїстих.
Система булевих функцій називається функціонально повною. якщо будь-яка булева функція представляється суперпозицією (складною функцією) функцій даної системи.
Теорема Поста про функціональну повноту. для того щоб система функцій була повною, необхідно і достатньо, щоб вона цілком не містилася ні в одному з наступних замкнутих класів T0. T1. L, M і S.
Для перевірки функціональної повноти системи булевих функцій будується так звана таблиця Посту, в якій зазначається приналежність функцій замкнутим класам. Якщо в кожному стовпчику таблиці Поста є хоча б один мінус, система повна, в іншому випадку - ні.
Приклад 1.Проверіть функціональну повноту системи булевих функцій.
Перевіримо приналежність замкнутим класам функції. Побудуємо таблицю істинності цієї функції:
система функцій Á утворює повну систему, так як для кожного з класів Посту в системі є функції, які не належать цьому класу. система функцій Á є базисом, так як повна і при видаленні однієї з функцій система стає неповною.
Приклад 4.Визначите, чи є повною система функцій F = і утворює вона базис.
x Ù Øy
x Ù Øy
для x Ù Øy:
4) Так як f (0,0) = f (1,1), отже, функція f (x Ù Øy) монотонна;
5) поліном жегалкіна: x + xy.
4) Так як f (0,0) 5) поліном жегалкіна: x + y + xy. Система функцій неповна. Приклад 5.Определіть, чи є повною система функцій: Складаємо таблицю істинності для кожної з цих п'яти функцій (для f2 і f4 таблицю можна скласти окремо). Предикати і квантори Нехай А - безліч об'єктів довільної природи (предметна область предиката), n-місцевий предикат - довільне відображення Приклад 1. Предикат A (x) = «x ≤ 2» на безлічі X = R - одномісний. Предикат B (x. Y) = «xy> 0» на безлічі X = - двомісний. Якщо X =, то n-місний предикат є n-місні булевої функцією. Нульместний предикат є висловлювання. Оскільки безліч значень будь-якого предиката лежить в безлічі, то з предикатами можна робити всі операції алгебри логіки, і всі відомі властивості логічних операцій узагальнюються для предикатів. Розглянемо ці властивості (для зручності у властивостях записуються одномісні предикати): 6. Закон виключення третього: P (x) P (x) = 1. 8. Закони де Моргана: 9. Властивості операцій з логічними константами: Для предикатів визначені операції спеціального виду, які називаються кванторами. Нехай дано n-місний предикат на множині X. означає, що для набору виконано властивість A. і нехай - одна з змінних. Тоді запис означає, що для всіх значень змінної властивість A виконано. Символ називається квантором загальності (спільності). Предикат є (n- 1) -місцевим. Він залежить від змінних. Якщо дан одномісний предикат P (x), то твердження xP (x) являє собою нульместний предикат, тобто істинне або помилкове висловлювання. Для n- місцевого предиката на безлічі X і змінної запис означає, що існує значення змінної. для которойсвойство A виконано. Символ називається квантором існування. Предикат є (n- 1) -місцевим, залежить від змінних. для одномісного предиката P (x) твердження xP (x) являє собою нульместний предикат, тобто істинне або помилкове висловлювання. Приклад 2. На множині X = R дан предикат A (x) = «x ≤2». Висловлення x (x ≤ 2) - помилково, x (x ≤ 2) - істинно. Запис xA (xA) не має на увазі, що у формулі A є змінна x. Мінлива x називається змінної в Квантори. а A - областю дії квантора. Мають місце еквівалентності: Предикат тотожне істинний (тотожне помилковий). якщо при всіх можливих значеннях змінних він приймає значення 1 (0). Пропозиція - одномісний предикат, визначений на множині N. - «існує х. для якого вірно »- справжнє висловлювання; - «для всіх x вірно» - хибне висловлювання. Пропозиція - двомісний предикат, визначений на множині А. Предикат називається здійсненним. якщо при деяких значеннях змінних він приймає значення істина. Приклад 4.Найті значення висловлювання. Тримісний предикат визначено на безлічі N. Рішення: Нехай = 1. Еквівалентність має місце тоді і тільки тоді, коли для деякого. і предикат є тотожно істинним щодо y. тобто оригінал висловлювання істинно. Нехай A - формула, - змінна, яка входить в формулу A (один або кілька разів). Входження в формулу A називається пов'язаним. якщо або - змінна в Квантор, або знаходиться в області дії квантора. Якщо входження в A не пов'язане, то воно називається вільним. У формулі входження обох змінних вільні, у формулі входження змінної x пов'язано, а входження змінної у вільно. Для кожного предиката A областю істинності називається безліч Y = x X. A (x) = 1>, на якому предикат приймає значення 1. Безліч істинності предиката, Для предиката A (x) = «x ≤ 2» на безлічі X = областю істинності є безліч Y = x R, x ≤ 2>. Для області істинності перетину і об'єднання предикатів вірні співвідношення: Наступні пропозиції означають: - «для всіх m вірно: m ділиться на n» або «будь-яке натуральне нульове число ділиться на n» - одномісний предикат, залежить від n. здійсненний предикат, область його істинності - n = 1>, так як всі числа діляться на 1; - «існує m, для якого вірно: m ділиться на n» або «знайдеться натуральне нульове число, яке ділиться на інше натуральне нульове число» - одномісний предикат, залежить від n. тотожно істинний предикат, область його істинності - А; - «для всіх n вірно: m ділиться на n» або «натуральне нульове число ділиться на будь-яке натуральне нульове число» - одномісний предикат, залежить від m. тотожно помилковий предикат, область його істинності -Нехай безліч; - «існує n. для якого вірно: m ділиться на n »або« натуральне нульове число ділиться на деяке натуральне нульове число »- одномісний предикат, залежить від m. тотожно істинний предикат, область його істинності - А. 1.Виделіть предикати, для кожного предиката встановити місцевість і область істинності, якщо X = R. Для двомісних предикатів зобразити область істинності графічно. 2) При x = 0 виконується рівність x - 2 = 0; 5) однозначне число x є простим.Схожі статті