НОУ ІНТУІТ, Лекція, Висловлювання та предикати
Інформатика, як було розглянуто вище, вивчає знакові (алфавітні) системи. Алгебра - найбільш адекватний математичний апарат опису дій у них, тому алгебраїчний апарат найкраще підходить для опису інформаційних систем загальної природи, абстрактно від їх предметної спрямованості. Інформаційні процеси добре формалізуються за допомогою різних структур алгебри.
Алгеброю A називається деяка сукупність певних елементів X , із заданими з них певними операціями f (часто обумовлені схожістю з операціями складання і множення чисел), які задовольняють певним властивостям – аксіомам алгебри.
Операція f називаєтьсяn-місцевої, якщо вона пов'язує n операндів (об'єктів – учасників цієї операції).
Сукупність операцій алгебри A називається її сигнатурою, а сукупність елементів алгебри – носієм алгебри.
Твердження (висловлювальна форма) – основна одиниця, неподільна з погляду відображення сенсу інформації (семантики).
Висловлювання - деяке оповідальне твердження, про яке можна однозначно сказати ("відразу подивившись на нього"), істинно воно чи хибно. Ці два значення всіляких висловлювань позначаються "істина" та "брехня", "true" і "fаlse" або "1" та "0".
Змінна , значеннями якої можуть бути лише значення "1" або "0", називаєтьсялогічною змінноюабобулевою змінною.
Приклад. Розглянемо словосполучення:
- Москва – столиця США.
- Мешканець міста Москва.
- 5 - 7 + 8 .
- 5 - 9 + 28 = 4 .
- П'ятого тижня зими було дуже холодно.
- В Антарктиді мешкають тигри.
Висловлювання має бути однозначно істинним абооднозначно хибним, тому висловлюваннями є лише твердження 1), 4), 6).
Приклад. Не є висловлюванням і "парадокс брехуна" (Евбулід, вчитель Демосфена, близько 350 років до н.е.):"Те, що я зараз стверджую, - хибно", бо якщо воно істинно - то воно хибне а якщо припустити, що воно хибне, то воно істинне. Це невизначена висловлювальна форма. Аналогічний приклад належить відомому математику, логіку Гёделю (1931 р.):" Те, що стверджується у цій пропозиції, може бути доведено ". Якщо його можна спростувати, його не можна довести, і якщо його не можна спростувати, його можна довести. Пропозиції такого роду не можуть бути доведені або спростовані в межах тієї мови (той теорії, алгебри), за допомогою якої вони сформульовані. Відомі багато подібних парадокси.
Розглядаючи висловлювання, ми не звертаємо уваги на їхню внутрішню структуру і можемо розкладати їх на структурні частини, так само як і об'єднувати їх.
Приклад. Побудуємо з нижче заданих простих висловлювань складові, складні висловлювання, що приймають значення "істина", "брехня":
- "Зима – холодна пора року".
- "Пальто – теплий одяг".
- "Камін – джерело тепла".
Предикат – висловлювальна форма з логічними змінними (безліч значень цих змінних цілком визначено), що має сенс за будь-яких допустимих значень цих змінних. Кількість змінних запису предикату називається йогоместностью.
Прості висловлювання чи предикати не залежить від інших висловлювань чи предикатів ( " не розбиваються більш прості " ), а складні – залежать хоча від двох простих.
Приклад. Вираз "х = у" - предикат, "х" 5" - предикат, а "7 & 5; - висловлювання. Твердження "Добре"не є висловлюванням, твердження "Оцінка студента А з інформатики – хороша" – простий вислів, твердження "Вчора була ясна погода, я був учора на рибалці" – складний вислів, що складається з двох простих.
Логічною (бульовою) функцією f(х) називається деяка функціональна залежність, в якій аргумент х – логічна змінна із заданим безліччю змін аргументу, а значення функції f(x) беруться з двоелементної множини R(f) = .
Приклад. Задані предикати виду р = "число х ділиться націло на 3" і q = "у – день тижня". Знайдемо безліч істинності предикатів р і q, якщо . Отримуємо, що , .
Безліч логічних змінних з визначеними над ним операціями : -запереченняабоінверсії, -логічного складанняабо диз'юнкції, -логічного множенняабо кон'юнкції називається алгеброю предикатів (і висловлювань), якщо ці операції задовольняють наступним аксіомам:
Аксіома подвійного заперечення:
Аксіоми переміщування операндів (щодо операцій диз'юнкції та кон'юнкції):
Аксіоми переміщування операцій диз'юнкції та кон'юнкції (щодо операндів):
Аксіоми однакових операндів:
Аксіоми поглинання (множником - множника-суми або доданком - доданку-твору):
Аксіоми розподілу операції (диз'юнкції щодо кон'юнкції та навпаки):
Аксіоми де Моргана (перенесення бінарної операції на операнди):
Аксіоми нейтральності (взаємноінверсних множників або доданків):
Аксіома існування одиниці ( істина , true, 1) і нуля ( брехня , false, 0), причому,
З цих аксіом випливає ряд корисних співвідношень, наприклад,