МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ІІ. Алгебра висловлень
2. Означення логічних операцій
Основними об’єктами алгебри висловлень є елементарні висловлення. Кожне елементарне висловлення обов’язково повинно бути або істинним, або хибним. Будемо позначати елементарні висловлення малими латинськими буквами a, b, c, …, x, y, z,… Значення істинності позначають буквою І або цифрою 1, значення хибності – Х або 0. Приклади елементарних висловлень: 2 > 3, 2 × 2 = 4, „ сніг білий ”, „ парта чорна ”. Елементарним висловленням відповідають прості речення української мови, в яких щось стверджується. Складні речення містять сполучники і є прикладами складних висловлень. Сполучникам „і”, „або”, „якщо..., то...”, слову „еквівалентно” та частці „не” в алгебрі висловлень відповідають логічні операції „кон’юнкція”, „диз’юнкція”, „імплікація”, „еквівалентність” та „заперечення”. Позначають ці операції символами: Ù , Ú , ", 1 , ¯ . Дамо означення логічних операцій:
Відмітимо ще: - „кон’юнкція”, „логічне множення”, читають: „x і y”. - „диз’юнкція”, „логічне додавання”, читають: „x або y”, “або” в нероздільному розумінні. - „імплікація”, „логічне слідування”, читають: „якщо x, то y”, „з х слідує (випливає) у”. - „еквівалентність”, читають: „x еквівалентно y”. ¯ - заперечення, читають: „не x”
3.Формули алгебри висловлень
Кожна буква, що виражає елементарне висловлення, є формулою. З букв за допомогою логічних операцій можна будувати нові формули. Зв’язуючи побудовані формули знаками логічних операцій, одержуватимемо нові, більш складні формули. Формули з двох або більшої кількості букв виражають складні висловлення. При цих побудовах формули з двох або більшої кількості букв потрібно брати в дужки. Приклади: ab, bc, ab, …, , , … , ,… Можна обчислити значення істинності висловлення для деякого набору значень елементарних висловлень. Наприклад: |010 ===, . Визначимо порядок старшинства операцій: ¯ , , , , . Домовимось, що =. Будемо використовувати це для спрощення запису формул. Наприклад: = =. Побудуємо таблицю істинності висловлення, що виражається формулою .
Побудована таблиця дає нам значення істинності складного висловлення, що виражається формулою для всіх можливих наборів значень елементарних висловлень , , . З іншого боку, формула і таблиця виражають деяку функцію від трьох змінних , , . Особливість цієї функції полягає в тому, що значення функції та Ії аргументів належать множині {0,1}. Такі функції називають бульовими.
4. Бульові функціхї та їх властивості
Означення. Функцію f(x1,x2,…xn), для якої f,x1,x2,…xn{0;1} називають n-місною бульовою функцією. Властивість 1. n-місна Бульова функція визначена на 2n наборах. Доведення. Побудуємо таблицю наборів для довільної n-місної бульової функції. Набори значень аргументів розташовуємо в порядку зростання двійкового числа. У першому рядку
записано число 0, в другому – число 1, в третьому – число 2 і т.д. В останньому рядку записано двійкове число, що виражає кількість наборів, починаючи з другого. Додаючи число 1 до двійкового числа, що записано в останньому наборі, одержуємо кількість всіх наборів, записану двійковим числом. Залишається перевести число з двійкової системи числення в десяткову. Позначаючи кількість всіх наборів буквою m, маємо: m = 11…112 + 1 = 100…002 = 1×2n+ 0×2n-1 + 0×2n-2 + … + 0×21 + 0×2 0 = 2n Запишемо одержаний результат у формі властивості двійкових чисел: Різних двійкових чисел, розмірність яких не перевищує n, Існує точно 2n. Властивість 2. Різних n-місних бульових функцій існує точно . Доведення. Побудуємо таблицю значень всіх можливих n - місних бульових функцій від f1 до f k.
Стовпчики значень функцій розташовуємо в порядку зростання двійкового числа. В першому стовпчику записано число 0, в другому – число 1, в третьому – число 2 і т.д. В останньому стовпчику записано двійкове число, що виражає кількість стовпчиків, починаючи з другого. За відміченою вище властивістю двійкових чисел одержуємо, що кількість стовпчиків k = 2m, де m – кількість наборів. Вище доведено, що m = 2n, тому k = .
5. Рівносильні та тотожно істинні формули алгебри висловлень Означення. Дві формули алгебри висловлень, що виражають одну і ту ж бульову функцію, називаються рівносильними. Бульова функція визначається таблицею однозначно, тому для перевірки рівносильності двох формул достатньо побудувати для них таблиці істинності і порівняти. Приклад: Перевірити на рівносильність формули та .
Значення в таблицях істинності співпадають, тому =b. Означення. Формула алгебри висловлень, для якої відповідна бульова функція приймає значення 1 на всіх наборах, називається тотожно істинною. Приклад. Перевірити, чи тотожно істинною є формула .
Відповідна бульова функція приймає значення 1 на всіх наборах, тому .
6. Огляд всіх можливих 2- місних бульових функцій
Підрахуємо кількість всіх можливих двомісних бульових функцій. |n=2= Побудуємо таблицю істинності для всіх цих функцій.
Запишемо формулою кожну з побудованих функцій.
Висновок. Введених нами п’яти логічних операцій ¯ , , , , достатньо для того, щоб записати формулою довільну двомісну бульову функцію. Функції і визначають операції кон’юнкцію і диз’юнкцію. За допомогою функцій та можна ввести ще дві логічні операції /,: = = x/ y, == xy. Ці операції використовують в техніці. Першу з них називають штрих Шеффера, а другу називають стрілка Пірса.
7. Функціонально повний набір логічних операцій
Означення. Набір логічніх операцій, за допомогою якого можна представити формулою довільну n-місну бульову функцію, називають функціонально повним. Теорема. Набір логічних операцій ¯ , , , , є функціонально повним . Для двомісних бульових функцій теорема виконується, бо ми тільки-що записали за допомогою цих логічних операцій всі двомісні бульові функції. Використовуючи метод математичної індукції, можна довести теорему і для n-місних бульових функцій. Покажемо, що функціонально повний набір (ФПН) логічних операцій може містити меншу кількість операцій.
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|