АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Тема 2. Вступ до математичної логіки

Читайте также:
  1. I. Вступительное слово учителя.
  2. I. ВСТУПНА ЧАСТИНА
  3. III. ЦЕЛИ ВСТУПИТЕЛЬНОЙ ЧАСТИ БЕСЕДЫ
  4. III.1.6. Акты Президента Российской Федерации, порядок их подготовки и вступление в силу.
  5. III.4.6. Акты федеральных органов исполнительной власти, их регистрация, опубликование и вступление в силу
  6. VІІ.Участь у конкурсі за результатами вступних екзаменів на основі повної загальної середньої освіти
  7. Анкета кандидата на вступ до ВМГО Демократичний Альянс
  8. Баланс (вступительный)
  9. Блок 1. Вступ до анатомії. Скелет людини: хребет, скелет грудної клітки, верхньої та нижньої кінцівок.
  10. БУДУЩЕЕ – НЕ ПЕРЕПУТАЙТЕ УТВЕРДИТЕЛЬНОЕ «ДА» С ВАРИАТИВНЫМ «РАЗРЕШИТСЯ». СИТУАЦИЯ СКОРО ВСТУПИТ В СВОЮ ЗАКЛЮЧИТЕЛЬНУЮ ФАЗУ.
  11. В наш час дискретна математика є необхідною компонентою математичної освіти студента-фізика.
  12. Визначення похибок обробки методом математичної статистики

Логіка Буля

Операції булевої логіки також зручно ввести через поняття множини. Отже, розглянемо дві множини: та . І перша, і друга множини – підмножини множини .

Об’єднання множин та :

Іншими словами, елемент належить або/і , можна виразити формулою:

,

де - символ логічної зв’язки або, яка називається диз’юнкцією.

З точки зору логіки, замість однієї предметної змінної зручно ввести дві логічні змінні x1 та x2. Областю визначення x1 та x2 будуть вже не числа натурального ряду, а тільки два логічних значення: 1 для істинного значення та 0 для хибного.

Допустимо, що . Оскільки це число не належить ні множині , ні множині , то логічні значення змінних будуть: x1=0, x2=0. Тепер передбачимо, що вибране число 4. Це число входить як в множину , так і множину . Отже, x1=1, . Існують ще два варіанта. Наприклад, для числа маємо x1=1, x2=0, та для - значення x1=0, x2=1.

Змінні x1 та x2 визначають деяку логічну функцію , яку у випадку диз’юнкції можна записати як пропозиційну зв’язку .

Ми бачимо, що число 7 не входить до об’єднаної множини , тому при x1=0, x2=0 значення логічної функції дорівнює нулю. Все це зручно оформити таблицею, яку називають таблицею істинності:

     
     
     
     

табл.1

Між таблицею істинності та колами Ейлера існує взаємно однозначна відповідність. Тому число одиниць для завжди буде дорівнювати числу заштрихованих областей на діаграмі Ейлера. Чотири комбінації аргументів x1 та x2 будуть відповідати чотирьом областям. Крім того, неважко підрахувати, що число комбінацій нулей та одиниць для функції дорівнює 16 (7 елементів та варіант, коли елемент не належить ні однієї із множин). Отже, загальне число можливих операцій на двох множинах теж дорівнює цьому числу.

Пересічення множин та : де - символ логічної зв’язки „і”, яка називається кон’юнкцією. Для нашого числового випадку будемо мати: .

Таблицю істинності для кон’юнкції можна представити слідуючим чином:

табл.2
       
       
       
       

Якщо у таблиці істинності для диз’юнкції усі нулі поміняти на одиниці, а всі одиниці – на нулі, то у підсумку отримуємо таблицю істинності для кон’юнкції. Цей факт визначає взаємну двоїстість кон’юнкції та диз’юнкції. Для будь-якої логічної операції можна знайти двоїсту.

Множина доповнює множину до універсуму (або 1). Доповнення до логічної змінної , тобто (не- ), називають у логіці частіше за все запереченням .

Розглянемо дві нові операції: стрілка Пірса та штрих Шеффера. Діаграми цих операцій доповнюють об’єднання та пересічення до фундаментальної множини (універсуму U).

 
 

 


Стрілка Пірса

 

 

Штрих Шеффера

Мовою логічних формул цей факт виражається слідуючим чином: для стрілки Пірса:

Таблиця істинності для даної операції має вигляд:

     
     
     
     

З цієї таблиці бачимо, що

Для штриха Шеффера:

.

Таблиця істинності для операції штрих Шеффера має вигляд:

     
     
     
     

З цієї таблиці маємо:

.

З теорії множин знаємо, що різниця між множинами та містить сукупність тих елементів множини , що не входять до множини . Для нашого числового прикладу маємо: .

Доповненням до різниці служить імплікація.

Таблиці істинності для цих операцій мають вигляд:


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)