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

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

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

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

Таблиця 4.1

З таблиці 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

З таблиці 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.

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