Головна

досконала ДНФ

  1. W - сумарна робота, здійснена системою.
  2. Питання 4. Досконала конкуренція
  3. Вставка 5.2. «Інтернет-економіка»: досконала конкуренція - реальність?
  4. Глава V Ринкові структури: досконала конкуренція та монополія
  5. Диз'юнктивна нормальна форма і досконала діз'юнктівная нормальна форма
  6. Кон'юнктивна нормальна форма і досконала кон'юнктивна нормальна форма
  7. недосконала конкуренція

Опр. ДНФ називається досконалою отн-но дан. мн-ва пере-х, якщо кожна пере-я входить в кожну елементарну кон'юнкцію (з запереченням або без заперечення), причому рівно один раз. елементарні кон'юнкції, вхід. в СДНФ д. б. різними. н-р:

1) xyz xyz- СДНФ від x, y, z.

2) xy- СДНФ від x, y, але не є СДНФ від x, y, z.

Зауваження 1. const.?0 - СДНФ;

2. ДНФ, знайдена табличним способом, є СДНФ.

3. F = - СДНФ від змінної x, але не є СДНФ від x, y, z, яка може бути з неї отримано: F = = = - СДНФ від x, y, z.

Теорема. Будь-ф-ла ал-ри вис-й має рівносильну їй СДНФ, кіт. опр-ся з точ-ю до порядку запису елемент-х кон'юнкція.

2. Поняття булевої функції. Таблиця істинності формулиПідставляючи в ф-лу замість пропозіціональних пер-x, y, z, ... значення 0,1, і виконуючи дії, ми б. пол-ть знач-я ф-ли. опр. Булевой ф-цією наз-ся ф-ція, зад. на мн-ве {0,1} і прийнятий. знач-я з цього ж мн-ва. кожної ф-ле алгебри в-й відповідає булева ф-ція і притому єдина. Таблиця знач-й цієї ф-ції наз-ся таблицею істинності. лема. Сущ. 2n наборів, елементами кіт-х явл-ся нулі і одиниці, довжини n. (Довжина набору - число символів, що входять в набір). док-під методом математичної індукції:

1. Нехай n = 1: Маємо 2 набору {0}, {1}.

2. Припустимо, що твердження леми справедливо для n = k. існує 2k наборів довжини k, елементами кіт-х явл-ся нулі і одиниці.

 I {0,1}

Застосуємо до набору (1) слід. перетворення: спочатку допишемо в кінці набору 0, а потім 1. У рез-ті, з одного набору довжини k отримаємо два набору довжини (k + 1).

Таким же чином зробимо з кожним з 2k наборів. Всього наборів вийде: 2 ? 2k= 2k+1. за принципом мат. індукції твердження леми справ-під для люб. нат. числа n. теорема. існує 22n булевих функцій від n змінних. р! Булеві ф-ції від 2 пер-х:

x y f0 f1 f2 f3
f4 f5 f6 f7 f8 f9
f10 f11 f12 f13 f14 f15

f0?0 - константа, f1= X & y - кон'юнкція

f2=, F3= X - повторення аргументу x, f4=, F5= Y - повторення аргументу y, f6=, F7= XUy - диз'юнкція. f8= - Стрілка Пірса, f9= X «y - еквівалентність, f10= - Інверсія y, f11= Y®x - імплікація, f12= - Інверсія x, f13= X®y - імплікація, f14= - Штрих Шеффера, f15?1 - константа. Серед перерахованих 16-ти ф-ций дві ф-ції - константи, 4 ф-ції залежать від однієї пров-й і 10 - від 2-х. особливу роль грають булеві ф-ції тотожне рав.1 при люб. наборах знач-й пров-х.

Опр. Формула (АВ) наз-ся тотожно істинною (тавтологією), якщо вона приймає значення «істина» при люб. знач-х пере-х, що входять в ф-лу.

Приклад: F (x, y) = (x®y) U (y®x)

1. висловлювання. алгебра висловлювань. висловлювання і операції над нимиВис-е-основне, невизначені поняття. будь-які твердження, про іст-ти або лож-ти кіт-х має сенс говорити, ми б. наз-ть висловлюваннями, При цьому ми можемо не знати, чи істинне дане вис-е чи ні. Вис-ми, наприклад, б. слід. твердження: - «Кама є однією з найбільших річок Росії»; - «8 - є просте число»; - «9000 -я цифра в десяткового запису числа ? є 7». Перше з цих утвержд-й істинно, другий-брехливо; іст-ть або лож-ть третього утверж-я нам невідома. вис-я б. обоз-ть лат. буквами (великими та малими, з індексами і без них): A, B, C, ..., A1, A2, C3, ..., p, q, r, ..., q2, q3 ... отже, нехай p, q, r -вис-я або пропозіціональние (висказивательную) змінні, кіт. м. приймати два значення істинності: Л (0; F - false) і І (1; Т - true). Разл. чином поєднуючи вис.-я м \ д собою, ми м. пол-ть нові вис-я. Н-р, з двох вис-й: «Перм - столиця Пермського краю» та «8 - є просте число» м. Пол-ть слід. вис-я: - «Перм-столиця Перм. краю і 8 - є пр. число », -« Перм - столиця Пермського краю або 8 - є просте число », -« Якщо Перм - столиця Пермського краю, то 8 - є просте число », -« Перм - столиця Пермського краю тоді і тільки тоді, коли 8 - є просте число ». з перв. вис-я м. отримати нове вис-е - «невірно, що Перм є столицею Пермського краю», т. е. вис-я, явл. запереченням першого. наведені поєднання вис-й утворюються за допомогою слів «І»; «АБО», «ЯКЩО ..., ТО», «ТОДІ І ТІЛЬКИ ТОДІ, КОЛИ ...», «НЕ». У математичній логіці для позначення цих основних типів поєднань, що мають назву, використовуються спец. символи: p q (p & q, pq, p • q) - читається «пе і ку») - позначає складне вис-е, справжнє тільки в тому випадку, коли p і q обидва істинні. Таке вис-е називають кон'юнкція (від лат. Conjunctio - союз, зв'язок) висловлювань p та q. p q (читається «пе чи ку») позначає складне вис-е, справжнє тоді лише, коли принаймні одне з вис-й істинно (м. бути істинними обидва вис-я). Таке вис-е зв-т диз'юнкція (від лат. Disjunctio - розрізнення, роз'єднання) висловлювань p та qp q (pq, pq) - читається «якщо пе, то ку», «пе досить для ку», «ку необхідно для пе »,« ку з необхідністю випливає з пе »,« з пе слід ку »,« пе тягне ку ») позначає складне вис-е, кіт. помилково тільки в тому випадку, коли p істинно, а q помилково і істинно у всіх інших випадках. Таке вис-е називають импликацией (від лат. Implico - тісно пов'язую) вис-й p і q. У импликативного висловлюванні pq розрізняють антецедент (підстава) - висловлювання p і консеквент (наслідок) -вис-е qp q (pq, pq, pq) - читається «пе тоді і тільки тоді, коли ку», «пе якщо і тільки якщо ку »,« пе в тому і тільки тому випадку, коли ку ») обоз-т складне вис-е, справжнє, коли вис-я p і q одночасно обидва істинні або обидва хибні. Таке вис-е зв-т еквівалентність вис-p і q. - Читається «Не пе», «невірно, що пе») - є протилежність p. Позначає вис-е, справжнє, якщо p помилково і помилкове, якщо p істинно. Таке вис-е зв-т запереченням висловлювання p. зауваження 1. Символи &,,, відповідають бінарним операціями: нове висловлювання зіставляють ці два вислови p і q, а символ висловлює певну на тому ж мн-ве унарна операцію: зіставляє нове висловлювання одному висловом p. зауваження 2. Слова «і»; «Або», «якщо ..., то», «тоді і тільки тоді, коли ...», є зв'язками в нашому звичайному мові, в мат. логіці отримують дещо інший сенс. в звичайній мові союз «і» исп-ся, як правило, для об'єднання двох пропозицій, відповідних один одному за змістом в некіт. зв'язковому оповіданні як це буває при описі послідовності подій (Олена добре підготувалася до іспиту Однак в логіці «І» м. з'єднувати люб. пропоз-а, зовсім неза-мо від наявності смислового відповідності м \ д ними. аналог. союз АБО в звичайній мові вживається в двох значеннях - у сенсі виключає від лат. aut ( «p або q, але не обидва») і в сенсі невиключає від лат. vel ( «p або q, або обидва). Саме в останньому сенсі ми б. ісп- ть союз АБО частіше. і тут знову несуттєва сенс. зав-ть з'єднуються вис-й. не ім-на смислова зв'язок в логіці між вис-ми і при побудові імплікації, хоча в звичайній мові складне предл-е «якщо p, то q »припускає-т м \ д p і q отн-е посилки і слідства, або ж причини і обумовленого нею дей-я. (Якщо б. дощ, то ми не підемо на прогулянку). в логіці для ис-ти імплікації дост- але, щоб p було помилково або q - істинно. т. о., вис-я типу: - Якщо 7 - просте число, то 2'2 = 4; - Якщо 8 - просте число, то 2'2 = 4; - якщо 8 - просте число, то 2'2 = 5 д. вважатися істинним. Затвердження «p тоді і тільки тоді, коли q» не означає в логіці, що складові предл-я p і q мають один і той же знач-е або один і той же сенс, воно означає лише Виска-е, кіт. істинно, коли обидва вис-я істинними чи хибні. все, що говорилося про лог. сенсі кон'юнкції, диз'юнкції, імплікації, еквівалентності і заперечення м. просто і наочно проілюструвати з пом-ю Т. н. таб-ц істинності. в таблицях випіс-ся всілякі комбінації іст-х і лож-х зн-й і Про. вис-й, а в результуючої колонці указ-ся іст-ть або лож-ть складного вис-я для кожн. такої комбінації. Б. зіставляти іст-му вис-ю символ 1, а хибним - символ 0. ось як виглядають т-ці істинності для &,,, і:

p q  P & q  p q  P q  p q
 
 

Поняття формули алгебри вис-й.Опр. Алфавітом наз-ся произв. мн-во символів. Введемо алфавіт, сост. з слід. груп символів: x, y, z, p, ... а, В, ... - пропозіціональние пере-е; &,,, і: - лог. зв'язки; (,) - 2 технічних символу. опр. (Ф-ли алгебри Виска-й): Кожна окремо взята пропозіціон-я перем-я є ф-ла алгебри вис-й. Ф-ли такого виду наз-ся найпростішими (атомами). якщо x - формула ал-ри вис-й (АВ), то (Ox) - ф-ла (АВ). якщо x і y - ф-ли ал-ри вис-й, то (x & y), (xUy), (x®y), (x «y) - теж ф-ли (АВ). ніяких ін. ф-л (АВ), крім виходять СОГ-сно п. п.1-3 немає. опр-я такого типу наз-ся індуктивними. У них є прямі пункти (1,2,3), де задаються об'єкти, к. Надалі іменуються визначеним терміном і непрямий пункт (4), в к. Говориться, що такі об'єкти вичерпуються зад. в прямих пунктах. Серед прямих пунктів їм-ться базисні (1), де указ-ся недо. конкретні об'єкти, іменовані в дав. визначеним терміном, і індуктивні пункти (2,3), де даються правила отримання визначених об'єктів з уже наявних об'єктів, зокрема з об'єктів, перечисл-х в базисних пунктах. зам-е: «Про силу зв'язок». для спрощення запису формул (зменшення числа дужок в них) будемо вважати, що: Порядок виконання лог. операцій над вис-ми д. б. слід.: O, &, U, ®, «зовнішні дужки, що укладають в собі всі інші символи, переклад У.. ф-лу, м. опускати. враховуючи цю угоду, а також опустивши знак кон'юнкції, ф-лу м. зап-ть у вигляді. при читанні ф-ла м. б. названа за «останньої» операції. Запис. ф-ла П. с. Импли-цію.



штрих Шеффера | Предмет вивчення географії

Поняття про елементарні теоріях. | Побудова числення предикатів: алфавіт, формула, аксіоми. Правила виведення, опр. Виведення формули та виведення з гіпотез в ВП. Теорема ЛП. Несуперечливість ВП. | Попереджання нормальна форма (ПНФ), її знаходження. | Метод Генцен для вирішення проблеми виконуваності формул логіки предикатів. | протиріччя | Проблеми здійсненності, общезначимости в тотожною хибності формул логіки предикатів. Зв'язок між цими проблемами. Т. Черча (без док-ва). | Поняття моделі даної сигнатури і істинності формули на моделі. | Приклади запису математичних пропозицій формулами логіки предикатів | Способи завдання предикатів | квантори |

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