На головну

Теорема дедукції. Предикати, квантори.

Дедукція ТЕОРЕМА

- Загальна назва ряду теорем, що дозволяють встановлювати доказовою імплікації  в разі, коли даний логічний висновок формули Віз формули А. У найпростішому випадку класичного, інтуїционістського і т. п. числень висловлювань Д. т. стверджує: якщо Г,  (З припущень Г, Авиводімо В), то

Теорема дедукції-одне з найважливіших змістовних тверджень математичної логіки, що визначає зв'язок між логічно правильними (аподиктической) міркуваннями (іліумозаключеніямі, або висновками) і законами (доказовими формулами) логіки, що лежать в їх основі. Прообраз Т. о д. Було відомо в вигляді загального принципу зв'язку між виводимістю і импликацией. Т. о д. Була сформульована незалежно франц. математиком Ж. Ербраном (1928) і А. Тарським (1930) і доведена Ербраном (1930) для обчислень, що включають позитивне импликативного числення висловів Гільберта. Формулювання Т. о д. Залежать ,, від того як в тому чи іншому обчисленні визначаються поняття "виводимість" і "імплікація", тому завжди слід мати на увазі той чи інший в а р і а н т Т. о д.

предикат (nмісний, або n-арної) - це функція з безліччю значень  (Або {брехня, істина}), певна на безлічі  . Таким чином, кожен набір елементів безлічі M характеризується або як «істинний», або як «помилковий». предикат називають тотожно-істинним і пишуть:

якщо на будь-якому наборі аргументів він приймає значення 1.

предикат називають тотожно-хибним і пишуть:

якщо на будь-якому наборі аргументів він приймає значення 0.

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

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

Квантор - Загальна назва для логічних операцій, що обмежують область істинності будь-якого предиката і створюють висловлювання. Найчастіше згадують:

· Квантор загальності (Позначення:  , Читається: «для будь-якого ...», «для кожного ...», «для всіх ...» або «кожен ...», «будь-який ...», «все ...»).

· Квантор існування (Позначення:  , Читається: «існує ...» або «знайдеться ...»).

· Правило заперечення кванторів - Застосовується для побудови заперечень висловлювань, що містять квантори, і має вигляд:

·



 Аксіоматичні теорії. Виводимість формул в обчисленні висловлювань. |  Формули логіки предикатів, їх еквівалентність, здійсненність і общезначімость.

 Формули логіки висловлювань |  Равносильность формул. |  Нормальні форми формул, приведення до ДНФ, КНФ. |  Використовуючи закон дистрибутивности, перетворимо формулу так, щоб все диз'юнкції виконувалися раніше, ніж кон'юнкції. |  Алгоритм отримання СДНФ по таблиці істинності. |  Алгоритм отримання СКНФ по таблиці істинності. |  Суперпозиції функцій. Повні системи логічних функцій. |  Мінімізація в класі діз'юнктівних нормальних форм. |  Обчислення висловлювань і числення предикатів. |  обчислення предикатів |

© um.co.ua - учбові матеріали та реферати