WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаЛогіка → Логічний вивід і проблема розв'язання - Реферат

Логічний вивід і проблема розв'язання - Реферат

логічне слідування справді має місце в тому чи іншому виводі. Так, щоб довести, що проголошена нами формула В (теза) є справді істинною, треба підібрати такі фор-мули-аргументи А1лА2л...лАп, з яких за відповідною процедурою можна вивести формулу, що збігається з проголошеною (з тезою), проте на відміну від останньої є достовірною.
Для позначення логічного слідування в логіці застосовують знак "І- " (або" f="). Вираз "А-В" читається так: "з А логічно випливає В".
Із формули А випливає формула В тоді, коли імплікація "А-їВ" є законом логіки ("завжди істинною" формулою). Ось чому (і не тільки тому) знаходження процедури, що дає змогу визначити, до якого класу формул логіки висловлювань ("завжди істинних", "завжди хибних" чи виконуваних) належить будь-яка формула, є винятково важливою проблемою логіки висловлювань.
Побудова відповідних таблиць істинності є ефективною лише за умови, коли до розглядуваних формул входить невелике число змінних. В іншому разі вона буде громіздкою, оскільки кількість рядків у таблиці стрімко зростає із збільшенням числа змінних, які входять до формули. Так, якщо формула містить три пропозиційні змінні, то рядків у таблиці буде 8, чотири - 16, п'ять - 32, десять - 1024. До того ж існують інші, менш громіздкі, зручніші процедури, з допомогою яких розв'язуються ці задачі. Йдеться про зведення формул до нормальної форми.
Нормальні форми формул логіки висловлювань
Формула логіки висловлювань має нормальну форму, якщо вона, по-перше, не містить у собі знаків -", , у, а по-друге, знаки заперечення стоять у ній лише при змінних.
Будь-яку формулу, що не має нормальної форми, можна скінченним числом застосувань правил заміни перетворити у формулу, яка має нормальну форму. Ця процедура називається процесом зведення формули до нормальної форми.
Щоб звести формулу до нормальної форми, необхідно зробити в ній такі рівносильні заміни:
1) кожну підформулу типу (А->В) замінити згідно з рівносильністю 13 формулою (AvB);
2) кожну підформулу типу (АВ) замінити згідно з рівносильністю 16 формулою (AVB)A(BVA);
3) кожну підформулу типу (AvB) замінити згідно з рівносильністю 17 формулою (АУВ)Л(АУВ);
4) кожну підформулу типу (АлВ) замінити згідно з рівносильністю 10 формулою (AvB);
5) кожну підформулу типу (AvB) замінити згідно з рівносильністю 11 формулою (АлВ);
6) кожну підформулу типуіГ замінити згідно з рівносильністю 1 формулою А.
Якщо ж перелічені процедури не можна застосувати до формули, то вона вже має нормальну форму.
Наприклад, дано формулу (pq), яку треба звести до нормальної форми. Згідно з рівносильністю 16 одержимо формулу(p~vq)л(qvp). 3 цієї формули згідно з рівносильністю 10 одержимо формулу(pvq)v(qvp), де підформулі (pvq) відповідає підформула рівносильності А , виражена засобами метамови, а підформулі (FVQ) - В. Вдавшись до рівносильності 11 і застосувавши її до кожного з диз'юнктів одержаної формули, дістанемо формулу (pAq~)v(c[Ap). І нарешті згідно з рівносильністю 1 одержимо формулу (pAq)v(q~Xp).
До нормальних форм формул логіки висловлювань належать передусім кон'юнктивна нормальна форма (КНФ) і диз'юнктивна нормальна форма (ДНФ). Причому кожна з них має свій специфічний спосіб утворення (зведення) і дає змогу розв'язувати відповідні задачі.
Проблема розв'язання
Є три класи формул логіки висловлювань ("завжди істинні", "завжди хибні" і невизначені, або виконувані). Завдання, що полягає у відшуканні процедури, котра дає змогу визначити, до якого з перелічених класів належить будь-яка формула, називається семантичною проблемою розв'язання для формул логіки висловлювань. А процедура, що дає змогу скінченним числом простих дій вирішувати проблему розв'язання, називається розв'язуючою процедурою.
Для того щоб одержати розв'язуючу процедуру, достатньо знайти спосіб відрізняти "завжди істинні" Формули від усіх інших. Якщо в результаті застосування такої процедури до формули А виявиться, що вона "завжди істинна", то проблема розв'язання вирішена. Коли ж ця формула виявиться не "завжди істинною", то цю процедуру треба застосувати до фор-мулиА Якщо буде встановлено, що ця формула є "завжди істинною", то звідси випливає висновок: формула А є "завжди хибною". Коли ж буде встановлено, що і формула А не є "завжди істинною", то це свідчить, що формула А є виконуваною, тобто при одних логічних значеннях змінних вона є істинною, а при інших - хибною.
Існує формальна процедура, з допомогою якої, не вдаючись до побудови відповідних таблиць істинності, можна визначати, до якого класу належить будь-яка формула логіки висловлювань - до "завжди істинних", "завжди хибних" чи виконуваних.
Пропозиційна змінна входить до складу формули, зведеної до нормальної форми, регулярно, якщо вона (змінна) входить до складу цієї форми одночасно як із запереченням, так і без заперечення. Якщо ж змінна входить до складу формули, зведеної до нормальної форми, тільки із запереченням або тільки без заперечення, то вона входить до складу формули нерегулярно.
Розв'язуюча процедура передбачає такі дії:
1) зведення формули до нормальної форми;
2) у зведеній до нормальної форми формулі виділення змінних, які входять до неї нерегулярно;
3) замість усіх змінних і заперечень змінних, які входять до формули нерегулярно, слід підставити на всіх місцях, де вони трапляються в нормальній формі, букву х (тобто логічне значення "хиба");
4) застосування правил заміни згідно з рівносиль-ностями 48, 48', 50 і 50' до всіх підформул одержуваної формули, доки є приводи для його застосування. В результаті такої процедури довжина формули буде скорочуватись, і можутьз'явитися нові змінні, що нерегулярно входять до формули. З ними чинять аналогічно, тобто згідно з пунктами 3 і 4. Передбачувані в пунктах 2-4 перетворення слід повторювати, доки не одержимо формулу, яка не містить у собі змінних, що входять до неї нерегулярно;
5) розгляд наступних двох формул, одержаних з формули, яка не містить змінних, що входять до неї нерегулярно, якщо:
а) замість однієї змінної, яка регулярно входить до формули, в усіх місцях слід підставити і (логічне значення ?- "істина") і застосовувати правило рівносильної заміни згідно з рівносильностями 43, 47-50;
б) замість тієї ж змінної на всіх місцях підставити букву х (логічне значення - "хиба") і застосовувати правило рівносильної заміни згідно з рівносильностями 44, 47-50.
До формул а і б, якщо це можливо, знову застосовують пункти 2-4, а потім, згідно з пунктом 5, з формул а і б одержують відповідно формули аа, аб, ба і бб тощо, доки не вичерпані можливості застосування пунктів 2-5.
Якщо в результаті застосування цієї процедури до будь-якої формули А всі заключні формули набудуть значення і ("істина"), то формула А є "завжди істинною", а якщо хоча б одна заключна формула набуде значення х ("хиба"), то формула А не є "завжди істинною"
Кон'юнктивна нормальна форма
Кон'юнктивна нормальна форма формул логіки висловлювань є кон'юнкцією елементарних диз'юнкцій.
Елементарною диз'юнкцією є формула, що має такий вигляд: A1vA2v...vAn, де п>1, а кожна з формул Ар А2, ..А є змінною або запереченням змінної. Так, формула (pvqvrvs) є елементарною диз'юнкцією, чого не можна сказати про формулу (pvqv(pAr)vs), оскільки третій її диз'юнкт (рлг) не є ні змінною, ні запереченням
Loading...

 
 

Цікаве