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

Способи доведення логічних тверджень

Читайте также:
  1. А) Концентрация, вызывающая изменения, выходящие за пределы физиологических приспособительных реакций или, скрытую (временно компенсированную) патологию.
  2. Аварії в свердловинах, причини виникнення й способи ліквідації
  3. Аналіз геоморфологічних умов господарювання
  4. Аномалії характеру і акцентуації індивідуально-психологічних властивостей особистість.
  5. Біологічних ритмів людини
  6. Взяття крові із вени для імунологічних та біохімічних досліджень
  7. Види (типи) виробництва і характеристика їх технологічних процесів. Організаційні форми роботи.
  8. Види і способи спостереження.
  9. Види психологічних тестів.
  10. Визначення конфлікту, зміст, типи і способи протікання
  11. Вимоги безпеки до галузевих технологічних процесів та обладнання.
  12. Вимоги до індивідуально – психологічних особливостей

 

Означення 4.1. Еквівалентні (тотожні, рівносильні) формули – це формули f та g, значення істинності яких збігаються у всіх їхніх інтерпретаціях.

Перший спосіб перевірки еквівалентності формул – використання таблиць істинності.

Приклад 4.1. Нехай необхідно перевірити еквівалентність формул (Ø(p ® q)) та (p Ù(Ø q)). Для цього необхідно в таблиці істинності показати тотожність формули (Ø(p ® q))~(p Ù(Ø q))). Результат наведено в таблиці 4.1.

Таблиця 4.1

P Q p ® q Ø(p ® q) Ø q p Ù(Ø q) Ø(p ® q)~(p Ù(Ø q))
T T T F F F T
T F F T T T T
F T T F F F T
F F T F T F T

 

 

З таблиці 4.1 видно, що формула (Ø(p ® q))~(p Ù(Ø q))) є тавтологією, а, отже, формули (Ø(p ® q)) та (p Ù(Ø q)) еквівалентні.

Очевидно, що для перевірки тотожності (Ø(p ® q)) та (p Ù(Ø q)) можна не обчислювати (Ø(p ® q))~(p Ù(Ø q))), а порівняти їхні значення у кожній з інтерпретації. Як видно з таблиці істинності стовбчики значень (Ø(p ® q)) та (p Ù(Ø q)) співпадають, а отже ці формули еквівалентні. p

Приклад 4.2. За допомогою таблиць істинності довести, що (p ® q) (q ® p).

Складемо таблицю істинності для формули (p ® q)~(q ® p):

Таблиця 4.2

p q p ® q q ® p (p ® q)~(q ® p)
T T T T T
T F F T F
F T T F F
F F T T T

 

 

З таблиці 4.2 видно, що формула (p ® q)~(q ® p) не є тавтологією, а, отже, формули (p ® q) та (q ® p) не є еквівалентними.p

Другий спосіб визначення еквівалентності формул – використання законів логіки висловлювань. Алгоритм доведення:

1) Вилучити імплікації, еквівалентності та альтернативне або.

Правило вилучення еквівалентності: . Правило вилучення імплікації: .

Правило вилучення альтернативного або: .

2) Позбутись знаків заперечень над великими виразами за допомогою законів де Моргана та закону подвійного заперечення.

3) Використання решти законів для спрощенння формул.

 

Дані закони наведені в таблиці 4.3. Їхню істинність можна перевірити таблицями істинності.

 

Приклад 4.3. Довести, що формула є еквівалентною формулі , використовуючи закони та правила логіки висловлювань.

1. Вилучення імплікації у формулі:

.

2. Використання законів де Моргана:

.

3. Використання закону подвійного заперечення:

.

4. Застосування закону асоціативності та комутативності:

.

5. Використання закону поглинання

.

6. Застосування правила вилучення імплікації:

.

Отже, формули та є еквівалентними. ▲

 

Приклад 4.4. Використовуючи закони логіки, показати, що формула є тавтологією.

1. Вилучаємо імплікацію:

.

2. Використовуємо закони де Моргана:

.

.

3. Використання закону подвійного заперечення:

.

4. Застосування закону асоціативності:

.

5. Застосування закону виключеного третього:

= = T.

Отже, задана формула є тавтологією. ▲

 

Третім способом доведення логічних рівностей є комбінований спосіб, що використовує як таблиці істинності, так і закони логіки висловлювань.

Приклад 4.5. З використанням комбінованого способу довести, що формула є тавтологією.

Позбудемось імплікації:

= .

Складемо таблицю істинності для формули , беручи до уваги лише можливе значення змінної p:

Таблиця 4.4

p Підстановка p та спрощення за допомогою законів логіки Результат
T = = T
F = = T

 

Отже, формула є тавтологією.p

 

Логіка предикатів

Логіка предикатів – розвиток логіки висловлювань. За допомогою формул логіки висловлювань можна описати структуру складних висловлювань, встановити їхню істинність чи хибність в залежності від істинності простих висловлювань, що входять у нього. Для опису внутрішньої логічної структури простих висловлювань використовується поняття «предиката».

Означення 5.1. Предикатом називається логічна функція, аргументами якої можуть бути довільні об'єкти з деякої множини, а сама функція може приймати значення істинності або хибності.

Предикати відображають властивості та відношення між предметами деякої множини.

Означення 5.2. Предметні символи – імена аргументів предикату, що позначаються малими буквами.

Означення 5.3. Предикатні символи – імена, якими позначають предикати та записують великими буквами.

Означення 5.4. Предметна область – це область значень аргументів предикату.

Приклад 5.1. Нехай маємо речення «x – просте число».

Предикат: P (x) «x – просте число».

Предметний символ: х.

Предикатний символ: Р – «просте число».

Предметна область: D – (-∞,∞).

Означення 5.5. n-місний предикат – предикат, що містить n змінних

Приклад 5.2. Нехай речення « ≥4» задано предикатом P (). Тоді Р (1,2) – хибне висловлювання, а Р (3,5) – істинне. Тобто Р (1,2)=Т, а Р (3,5)=F. ▲

 

Правильно побудована формула логіки предикатів визначається так:

1. Атомарна формула є формулою.

2. Якщо Р та Q формули, то і (Ø Р), (Р Ú Q), (P Ù Q), (P ~ Q), (P ® Q), (P Å Q) теж формули.

3. Якщо Р формула, а х – змінна у формулі, то " хР та $ хР теж формули (квантори розглянуті в наступному розділі).

4. Формули отримуються лише скінченною кількістю застосувань правил 1-3.

 


1 | 2 | 3 | 4 | 5 |

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



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