![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ІІ. Алгебра висловлень
2. Означення логічних операцій
Основними об’єктами алгебри висловлень є елементарні висловлення. Кожне елементарне висловлення обов’язково повинно бути або істинним, або хибним. Будемо позначати елементарні висловлення малими латинськими буквами a, b, c, …, x, y, z,… Значення істинності позначають буквою І або цифрою 1, значення хибності – Х або 0. Приклади елементарних висловлень: 2 > 3, 2 × 2 = 4, „ сніг білий ”, „ парта чорна ”. Елементарним висловленням відповідають прості речення української мови, в яких щось стверджується. Складні речення містять сполучники і є прикладами складних висловлень. Сполучникам „і”, „або”, „якщо..., то...”, слову „еквівалентно” та частці „не” в алгебрі висловлень відповідають логічні операції „кон’юнкція”, „диз’юнкція”, „імплікація”, „еквівалентність” та „заперечення”. Позначають ці операції символами: Ù , Ú , ", 1 , ¯ . Дамо означення логічних операцій:
Відмітимо ще:
¯ - заперечення, читають: „не x”
3.Формули алгебри висловлень
Кожна буква, що виражає елементарне висловлення, є формулою. З букв за допомогою логічних операцій можна будувати нові формули. Зв’язуючи побудовані формули знаками логічних операцій, одержуватимемо нові, більш складні формули. Формули з двох або більшої кількості букв виражають складні висловлення. При цих побудовах формули з двох або більшої кількості букв потрібно брати в дужки. Приклади: a
Можна обчислити значення істинності висловлення для деякого набору значень елементарних висловлень. Наприклад:
Визначимо порядок старшинства операцій: ¯ ,
Побудуємо таблицю істинності висловлення, що виражається формулою
Побудована таблиця дає нам значення істинності складного висловлення, що виражається формулою
4. Бульові функціхї та їх властивості
Означення. Функцію f(x1,x2,…xn), для якої f,x1,x2,…xn Властивість 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. Рівносильні та тотожно істинні формули алгебри висловлень Означення. Дві формули алгебри висловлень, що виражають одну і ту ж бульову функцію, називаються рівносильними. Бульова функція визначається таблицею однозначно, тому для перевірки рівносильності двох формул достатньо побудувати для них таблиці істинності і порівняти. Приклад: Перевірити на рівносильність формули
Значення в таблицях істинності співпадають, тому Означення. Формула алгебри висловлень, для якої відповідна бульова функція приймає значення 1 на всіх наборах, називається тотожно істинною. Приклад. Перевірити, чи тотожно істинною є формула
Відповідна бульова функція приймає значення 1 на всіх наборах, тому
6. Огляд всіх можливих 2- місних бульових функцій
Підрахуємо кількість всіх можливих двомісних бульових функцій.
Побудуємо таблицю істинності для всіх цих функцій.
Запишемо формулою кожну з побудованих функцій.
Висновок. Введених нами п’яти логічних операцій ¯ , Функції
7. Функціонально повний набір логічних операцій
Означення. Набір логічніх операцій, за допомогою якого можна представити формулою довільну n-місну бульову функцію, називають функціонально повним. Теорема. Набір логічних операцій ¯ , Для двомісних бульових функцій теорема виконується, бо ми тільки-що записали за допомогою цих логічних операцій всі двомісні бульові функції. Використовуючи метод математичної індукції, можна довести теорему і для n-місних бульових функцій. Покажемо, що функціонально повний набір (ФПН) логічних операцій може містити меншу кількість операцій.
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|