Все решту

sasha19970808
9 дек. 2015 г.
40 мин. чтения

Висловлення й операції над ними. Логічні операції. Пропозиційні формули
Класифікація формул логіки висловлень. Основні тавтології
Логічна рівносильність
Логічне слідування. Ознаки логічного наслідку
Нормальні форми. Подання формул алгебри висловлювань у вигляді досконалої нормальної диз'юнктивної або кон'юнктивної форм
Висловлення й операції над ними. Логічні операції. Пропозиційні формули

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

Під істиннісним значенням розуміється абстрактний об'єкт («істина» або «хибність»), що ставиться у відповідність висловленню залежно від того, є це висловлення істинним або хибним. Можна сказати, що «істина» («неправда») - це те загальне, що властиве всім істинним (відповідно, хибним) висловленням. У математичній логіці для позначення істинісних значень «істина» й «хибність» найчастіше використаються числа 1 й 0 або букви /іX, Ті Рвідповідно.

Надалі будемо вважати, що є первісна сукупність деяких найпростіших висловлень, які називаються елементарними або вихідними, про кожне з яких точно відомо, істинно воно чи хибне. Причому в цій сукупності є як істині висловлення, так і хибні. Домовимося позначати конкретні висловлення початковими заголовними буквами латинського алфавіту А. В, С, О ... або тими ж буквами з індексами внизу А/, А2, ... В/, В: , ... (пропозиційні імена). З одних висловлень різними способами можна будувати нові, більше складні висловлення.

Логічні операції

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

Означення. Запереченням висловлення Р називається нове висловлення, що позначається -'Р, або

Р (читається: «не Р» або «не вірно, що Р»), що істинне, якщо висловлення Р хибне, і хибне, якщо висловлення Р істинне. Інакше кажучи, логічне значення висловлення --Р пов'язане з логічним значенням висловлення Р, як зазначено в наступній таблиці, що називається таблицею істинності операції заперечення:

-нР

[endif]-- Означення. Кон ’юкцією двох висловлень Р і (9 називається нове висловлення, яке позначається Рл <2 або Р & (9 (читається: «Р і (9»), Щ° істинне лише в єдиному випадку, коли істинні вихідних висловлення Р і (9, та хибне у всіх інших випадках. Інакше кажучи, логічне значення висловлення Рл{2 пов’язане з логічними значеннями висловлень Р та (9, як зазначено в наступній таблиці, що називається таблицею істинності операції кон ’юнкція:

РаО

Р лО = 0 Рлі =Р

Рл.Р = Р

Р д -'Р = 0[endif]-- Практика повністю підтвердила, що саме такий розподіл значень істинності найбільше відповідає тому змісту, що надається в процесі розумової діяльності сполучнику «і».

Означення. Диз'юнкцією двох висловлень Р і (9 називається нове висловлення, яке позначається Ру(9 (читається «Р або (9)= що істинно в тих випадках, коли хоча б одне з висловлень Р або О істинно, і хибне в єдиному випадку, коли обоє висловлення Р і 2 помилкові. Інакше кажучи, Р\/{9 - таке

Ру0

Ру0 = Р Ру 1 = 1

значенн

РуР = Р Ру-'Р = 1[endif]-- висловлення, логічне значення якого пов'язане з логічними значеннями вихідних висловлень Р і ^ так, як зазначено в наступній таблиці, що називається таблицею істинності операції диз'юнкція:

я. Імплікацією двох висловлень Р і <2 називається нове висловлення, що позначається Р=> (З (читається: «якщо Р, то (2», або «з Р треба 0», або «Р тягне 2», або «Р достатньо для ()», або «<2 необхідно для Р»), яке хибне в єдиному випадку, коли висловлення Р істинне, а () - хибне, а у всіх інших випадках - істинне. Інакше кажучи, логічне значення висловлення Р=><2 пов'язане з логічними значеннями висловлень Р та 2, як зазначено в наступній таблиці, що називається таблицею істинності операції імплікація:

Р=>Р = 1 Р => -Р = -Р[endif]--Р = 1 Р => -Р = -Р">

Р^о.

[endif]--Р=?0 = ~'Р Р=>1 = 1< >=>Р=1 =>р=р cellspacing="0" width="100%"

р»0

Р су 0 = ^Р Рсуі = Р

Р оР = 1 Ра^Р = 0[endif]-- Означення. Еквівалентністю двох висловлень Я та О називається нове висловлення, що позначається Р <=> <2 (читається: «Р еквівалентно <2», або «Р необхідно й достатньо для О», або «Р тоді й тільки тоді, коли <2», або «Р, якщо й тільки якщо 0»), що істинне тоді і тільки в тоді, коли одночасно обоє висловлювань Р та (З або істинні, або хибні, а у всіх інших випадках - хибне. Інакше кажучи, логічне значення висловлення Яо2 пов'язане з логічними значеннями висловлень /’ і О. як зазначено в наступній таблиці, що називається таблицею істинності операції еквівалентності:

Пропозицій!!! формули

Алфавіт мови логіки висловлень складається із символів логічних зв'язків (логічних операцій) і пропозиційних змінних А, В, С,....

Означення. Алфавіт логіки висловлювань - це множина пропозиційних змінних Р та логічних операцій л, V, =>, о}.

Символи ■>, д, V, =>, о називаються логічними символами, логічними операціями або логічними зв'язуваннями.

Означення. Поняття пропозиційної формули (або формули логіки висловлень) визначається індуктивно в такий спосіб: < >будь-яка пропозиційна змінна є формулою (така формула називається атомарною формулою): якщо А і В - формули, то -•А, (АлВ), (А\/В), (А => В), (Ачз> В)- формули. кожна атомарна формула має властивість V; /

< >якщо формула А має властивість V, те формула (-•А) має властивість V; якщо формули А і В мають властивість V, як - одна з операцій л, V, =>, <=> то формула (АІВ) має властивість V. кожній атомарній формулі А поставлений у відповідність деякий об'єкт Р'(А); задане правило, що визначає, який об’єкт Р(-'А) ставиться у відповідність формулі (~'А), якщо формулі А поставлений у відповідність об'єкт Р(А); задане правило, що визначає, який об'єкт Р(АкВ) ставиться у відповідність формулі (АІВ), де І - одна з операцій л, V, =>, о якщо формулам А, В вже поставлені у відповідність об'єкти Р(А), Р(В), тоді для кожної формули А однозначно визначений об'єкт Р(А).- 2. Класифікація формул алгебри висловлень

Формули алгебри висловлень поділяються на наступні типи: виконувані, тавтології й суперечності.

Означення. Формула Р(хі,х2,...,хп) називається виконуваною, якщо існує такий набір значень А/ А2, .... А„ при підстановці яких у формулу замість Хі, х2, .... х„ наша формула перетворюється в тотожне висловлення.

Приклад: Р(хІ) = х1 а хі - не є виконуваною.

А Х1

*х

\/Хх

[endif]-- Означення. Формула Р(хі,х2,...,хп) називається тавтологією або тотожноістинною, якщо при будь-яких наборах А/ Л2,.... А„ формула перетворюється у істинне висловлення. Позначається |=. Приклад. Р(х{) = хІ Vx^ - тавтологія.

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

Основні тавтології: < >закон виключення третього: Р\/Р закон заперечення протиріччя: Р'-у Р закон подвійного заперечення: Р <=> Р закон тотожності: Р => Р закон контрапозиції: (Р => 0 <=> (О => Р)З

в < >закон силогізму: ((Р => б)Л (б => Я)) => (Р => Я)Властивості диз'юнкції й кон'юнкції< >закон ідемпотентносп:РуР Р

. Рлб<=>бл^ < >закон комутативності:РV^<Ї>^VР Р V (2 V К) О (Р V О) V К< >закон асоціативності:Ял(Єлй)«(Рл0лй

Рл(^\/К)о(Рл^)V(РлК) < >закон дистрибутивності:ру(блР)сї>(руб)л(Ру/г)

5. закон спрощення:[endif]--

6. закон поглинання[endif]--(Рл0=>Р

Я=>(Ру6)

Р А (Р V 0 О Р Р V (Р Л 0 Р

Рлб О Р Vб < >закон де Моргана: _ _Рм£) Р /\^

Властивості імплікації й еквівалентності < >(Р^.0с»(Ру0 (Р=>0«(Рл0 0л0»(Ру0 (Ру0»(Р^0 РоР (Ро0«(2о Р) (Р=>0у(Є^Р) (б л (Р 0) => Р (Рл(Ру6))=>6 (Р => б) => ((Р V Я) => (б V Р)) Логічна рівносильність симетричність: якщо Р1 = Рг, то Р2 = Я, рефлективність: Я е Я транзитивність: якщо Р] = Я2, Я2 = Я3, тоР, = Я3. style="margin-left:1.0pt;"Основні рівносильності:< >Р=Р (Р^б) = (б=>?) (Роб)М?о0 Р=*(2=^Л)£(РлЄ)^>Л {Р=>Д)л(Є=>Я) = О^0=>Л РлР = Р Р,мР = Р Рлб = ЄлР Рч <2 = <2\/ р Рл(Ру0гР Р V (Р Л 2) = Р Рл0=Р р^є=рл2 (Р=>0г(Р^) (Ро0 = (б«?) (Р^05(РлЄ) (РлЄ) = (^=>Є) (/^0 = (Р=>2) РоЄ2(р=>0л(д^>р) Р V Р н 1 РлР = 0 РуО = Р РлО = 0 Логічне слідування. Ознаки логічного наслідку Поняття логічного наслідку. Коли говорять, що з одного або декількох висловлювань Аі, А і, .... А„ випливає висловлення В, то мають на увазі наступне: завжди, коли виявляться істинними всіОзнаки логічного наслідку

Теорема (ознака логічного наслідку). Формула Н є логічним наслідком формули Р тоді і тільки тоді, коли формула Р => Я є тавтологією. Схематично Я|=Я <-> Р Я Доведення.

Необхідність: Нехай Н логічно слідує з Р (Р\= Н ), тоді за означенням якщо Л(Р(х1,х2,..,ха)) = 1 то Л(Н (х„х2,..,хп)) = 1. Дане твердження можна записати в такому вигляді:

Л(Р(х1,х2,..,хп)) ->Л(Н(хІ,х2,..,хя)). Скористаємось формулою Л(А)* Л(В) з Л(А* В) і наш вираз набуде вигляду Л(Р(х1,х2,..,хп) —> Н(х,,х1,..,хп)) = 1

Достатність: Оскільки Р => Я є тавтологією, то для будь-якого набору аі, а„ виконується рівність Л(Р(х„х2,..,х„) Н(х1,х2,..,х„)) = 1. Скориставшись Л(А* В) = Л(А)* Л(В) маємо

Л(Р(хІ,х2,..,хпУ) -> Л(Н(х1,х2,..,хпУ) = 1. Згідно даної формули і означення ми можемо стверджувати, що якщо Л(Р(хх,х2,..,хп)) = 1 то Л(Н(х1,х2,..,хп)) = 1. За означенням логічного слідування Н є наслідком Р. Доведено.

Теорема. Для будь-яких формул РІ,Р2,..., Рп, Н наступні запису є рівносильними:

а) Р2,Р2,...,Р„\=Н

б) РілР2л...лРп\=Н

в) |= РілР2л...лРп -+Н Доведення.

а) =>б): ___ ______ ________

Нехай існує набір значень а/, а2, а„, таких що Л{Р1(аі,ап)лР2{аі,агі)л...лРт(а2,ап)) = 1. З

означення кон’юнкції випливає, що кожен елемент рівний 1. Л(Р,) = 1,Л(Р2) = 1 ,...,Л(Рт) = 1 Якщо кожен елемент Р, істинний, те згідно пункту а) Л(Н) = 1, тобто з формули Р1(а1,ап)лР2(аІ,а[І)л...лРІп(аиа„) випливає істинність формули Н.

б) => а):

Якщо Л(Д лД2л...лДі) = 1, теЛ(#) = 1, Л(РІ)лЯ(Р2)л...лЛ(Рп) = \. За означенням кон’юнкції кожен елемент винний дорівнювати 1, тобто з того, що Л(РІ) = 1, (/ = 1..я) випливає, що Л(Н) = 1, тобто Н є логічним наслідком даної формули.

Рівносильність пунктів б), в) випливає з умови попередньої теореми. Доведено.

Теорема. Відношення логічного слідування між формулами алгебри висловлень має наступні властивості: < >і^Кьр,, дХнд, Д,М2 ^ Р^Рт\ = в2 Д,Дт|=Д => ВиРт,Р\= В, Р- довільна формула алгебри висловлювань. РІ,Р2,...,РІ_„РІ,Р^ ,Рт | =В=>Р„Р2 Д_„Д+1,...,Рт,\=В,Рі-тавтологія. cellspacing="0" width="100%"

Приклад.[endif]--р,с р-+с,с РлС

В РлС Р Р

Зауваження! Якщо формули, що знаходяться в чисельнику схеми логічного слідування є тавтологіями, то формула, що знаходиться в знаменнику є теж тавтологією.

Прилад:

Р,Р^С

с[endif]--Правило (тойия ропет)

Це правило означає, що від твердження про істинність посилки Р за допомогою іншої посилки Р—>С переходять до твердження про істинність наслідку С. Дане правило називають також правилом висновку або відділення (від посилки Р —>С за допомогою посилки Р відділяється висновок С).

Правило {тойт Іоііет):

>0,0[endif]--0,0">Воно називається правилом тосіиз Іоііепа: від заперечення істинності посилки О за допомогою посилки Р —*0 переходять до заперечення істинності Р.

Правило (введення кон’юнкції) Правило (видалення кон’юнкції)[endif]--р,о

РлО

РлС[endif]--РлО

Р О РуО’ РуО[endif]--Правило (введення диз'юнкції):

Правило (контрапозиції):

Способи доведення схем логічного слідування < >Утворити формулу Р, л Рг л... л Рт -+ Н і показати, що вона є тавтологією. Доводити методом від супротивного. Припустити, що існують такі а, ат, які при Нормальні форми. Подання формул алгебри висловлювань у вигляді досконалої нормальної диз'юнктивної або кон'юнктивної формОзначення. Атомарні формули та їхні заперечення називаються літерами.

Означення. Якщо (? - змінна, то літери <2 й називаються контрарними.

Означення. Поняття диз ’юнкта (елементарна диз ’юнкція) визначається в такий спосіб:

1) будь-яка літера вважається диз’юнктом;

* 2) якщо О - диз’юнкт, Ь - літера, то формула йуЬ є диз’юнктом.

Таким чином, користуючись домовленістю про опускання дужок, кожен диз’юнкт можна записати у ВИГЛЯДІ І; V Ь2 У ... V і„, де Ьі, . літери, п > 1. Очевидно, що такий диз’юнкт приймає

при даній оцінці значення 0 тоді й тільки тоді, коли всі літери І/, . ,.,Ь„ приймають значення 0. Звідси, зокрема, треба, що дизьюнкт £/ у ... V £„ є тавтологією тоді й тільки тоді, коли серед літер Ьі, ... Ь„ є контрарні.

Означення. Поняття кон ’юнкта (елементарна кон ’юкнція) визначається в такий спосіб: < >будь-яка літера вважається кон’юнкгом; якщо К- кон’юнкт, Ь - літера, то формула К діє кон’юнктом.Означення. Кількість змінних, що входить у диз’юнкт (кон’юнкт) називається його рангом.

Означення. Кон ’юнктивна нормальна форма (КНФ) визначається так: < >будь-який диз’юнкт є КНФ; якщо А є КНФ, £> - диз’юнкт, то формула А л О є КНФ.Означення. Диз’юнктивна нормальна форма (ДРІФ) визначається так:< >будь-який кон’юнкт є ДНФ якщо А є ДНФ, К— кон’юнкт, то формула А у К є ДДФ. /

с,

Означення. Якщо функцію задано формулою у вигляді кон’юнкції елементарних диз’юнкцій, то її задано кон’юнктивною нормальною формою (КНФ).

Означення. Конституентою одиниці (мінтермом) називають формулу, що подана у вигляді елементарної кон’юнкції, яка набуває значення 1 тільки на одному з наборів своїх змінних. Кількість різних конституент одиниці для функцій п аргументів дорівнює числу різних наборів, тобто Т.

Означення. Конституентою нуля (макстермом) називають формулу, що подана у вигляді елементарної диз’юнкції, яка набуває значення 0 тільки на одному з наборів своїх змінних. Кількість різних конституент нуля для функцій п аргументів дорівнює числу різних наборів, тобто Т.

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

Означення. Кон’юнкт (диз’юнкт) від літер X] X], ..., Х„ називається досконалим, якщо серед літер немає контрарних.

Означення. Нормальна форма (диз'юнктивна або кон’юнктивна) від літер X] X}, ..., Х„ називається досконалою від цих літер, якщо в неї входять лише досконалі кон’юнктори або диз’юнктори від X/, Х2,

.... Х„.

Подання формул алгебри висловлювань у вигляді досконалої нормальної диз'юнктивної або

кон'юнктивної форм

Введемо позначення:

„ їх, якщо а = 1 . Г=1 1° = 0 . Xа =1 коли х = а

X = < _ звідси тобто

[х, якщо а = 0 0і =0 0°=0 х“=0 колих*а

Наступне позначення: х1 V хг V... V х„ = \у"І=)хі

У Н(хІ,х2,...,хл,а1,а2,...,а„)- це є диз’юнкція всі можливих наборів формули

аІУа2,.,а„

Н(х[,х2,..,,хп,аІ,а2,...,ап), де формула Н залежить від змінних хі, Х2, ..., х„у щ- пробігають всі можливі набори значень 0 та 1.

Приклад:

У Н(Х, У, а, Р) = У (Xа, ¥р) = (Х° л Г0) V (Х° л Ґ) V (Xі л ¥°) V (Xі л 7і) =

а.Р а.Р

(X л К) V (X л К) V (X л К) V (X л 7)

Лема: Кожну формулу алгебри висловлювань можна податі в наступному вигляді:

Р(х],х2,.,.,хп)= У {Р{аиаг,...,ап)/\х“' лх2“2 л.„лх„“”)

Теорема: Кожна формула алгебри висловлювань, яка не є тотожньохибною, має єдину (з точністю до перестановок кон'юнктів) досконалу диз'юнктивну нормальну форму.

Доведення.

Існування: За попередньою лемою нашу формулу можна податі в наступному вигляді: К(хІ,х2,...,хп)= У (Р(ах,а2,...,ап)/\х“' лг2“’ л...лх°‘) оскільки формула не є тотожньохибною, те

СГ| ,&2......... а„

існує набір аі, 02, ..., а„, що Л(Р{ах,а2,...,ап)) = 1. В другій частині формули в нас є диз’юнкція кон'юнктивних елементів аі, а.2, .... а„ пробігають набори будь-яких значень 0 та 1. Відкинемо всі ті елементи, у яких Р(ах,а2,...,ап) = 0, оскільки при виконанні кон’юнкції ми отримаємо 0, а ті кон’юнктори, що приймають значення 0 при виконанні диз’юнкції можна відкинути. Тому наша формула набуде вигляду

Р(хх,х2,...,хп) = У (Р(а],а2,...,а„)лх“‘ лх2“2 л...лхла")~ У х“' лх2“г л...лх/",

«! ,аг2 «і ,а2 ,а„

Бо значення одиниці можна з диз’юкцїї відкинути ” 1

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

Єдиність: Нехай формулу Д(х„х2,...,х„) можна податі у вигляді двох досконалих диз'юнктивних нормальних форм.

Р(х1,х2,...,х„) = к1 \/к2 у...у^=УА,. і Б(х1,х2,...,хп) = к" чк’ ч...чкт' =0і/

<=І 7-І

де кі,к] - кон’юнкти.

Прирівняємо праві частини двох формул: кх мк2\/...\/кч = к' Vк2' V ...\/ кт'.

Візьмемо один елемент диз’юнкції і запишемо його вигляд: Аг, = х,“[1] лх/! а...лх“‘.

Надамо змінним х, значення а,. Кожен елемент тепер дорівнює 1.

Кон’юнкція цих елементів дорівнює 1. Тоді диз’юнкція дорівнює 1, оскільки один з її елементів дорівнює 1. Якщо ліва частина дорівнює 1, то і права частина повинна Дорівнювати 1. Це означає що хоча б один елемент правої частини повинен дорівнювати 1. Нехай це буде елемент кр‘. Розпишемо загальний вигляд к’ = х/1' ах/‘[2] л...лх/'\ Підставимо в наш елемент а і, а2, а„, тоді

к’ = ахА а а/2 л...ла/л. Для того, щоб наш елемент дорівнював 1 кожен член кон’юнкції дорівнювати 1, тобто а/ = 1, а/2 = 1, .... а/" = 1 звідси ах = Д, а2 = ап = Д, тобто

к’ = х"‘ ах/' а...лх„“- = кг Аналогічно доводити рівність всіх інших елементів у формах розкладу. Тобто дані розкладу будуть співпадати, що доводити єдність розкладу. Доведено.

Для доведення єдиності розкладу в досконалу кон'юнктивну нормальну форму використовуються наступні позначення:

Гх, ЯКІЦО Р = 1 „

X, ЛХ, Л...ЛХ = Л. ,х,

X, якщо Р = о 1 2 /Х,=1 '

ґ(х„х2,...,х„)= р Г(хх,х2,...,хп,р,р2,...,рп)

А.А...... А

Лема: Будь які формулу алгебри висловлювань можна подати у вигляді;

Р'(х1,х2,...,хп)= Рі Д)V^Д VД:2/?2

АЛ....... А

Теорема: Кожна формула алгебри висловлювань, яка не є тавтологією, має єдину (включно до перестановок диз’юнктів) досконалу кон'юнктивну нормальну форму.

Доведення аналогічне попередньому.

БУЛЕВІ ФУНКЦІЇ < >Булеві функції від п аргументів Двоїстість. Принцип двоїстості Вираження булевих функцій через кон'юнкцію, диз'юнкцію й заперечення Поліном Жегалкіна Спеціальні класи булевих функцій Системи булевих функцій. Повнота системи Застосування булевих функцій до аналізу й синтезу дискретних пристроїв /

Означення. Булевою функцією від двох аргументів називається функція, яка задана на множині {0,і}х{0,і}, і приймає значення на множині {0,1}.

Інакше кажучи, булева функція від двох аргументів ставить у відповідність будь-якій упорядкованій парі, складеної з елементів 0 й 1 (а таких упорядкованих пар буде чотири), або 0, або 1.

Означення. Булевою функцією від п аргументів називається функція, яка задана на множині

{0,1}” і приймає значення на множині {0,1}.

Інакше кажучи, булева функція від п аргументів зіставляє кожному впорядкованому набору довжини п, складеному з елементів 0 й 1, або 0, або 1.

Булева функція/від п аргументів хі,хг, ...,х„ позначається так:/(хі Х2.... х^.

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

Наприклад, для булевої функції /(х, у, г) сукупність значень х=1, у=0, 2=1 записується як набір

101.

Існує три способи задання булевої функції: вербальний (або словесний), аналітичний і табличний. Аналітичне задання функції - опис її аналітичним виразом (формулою).

Хі

Х„-1

х„

Р(хі. ..., Хп_! , х„)

Р(0,...,0,0)

Р(0,...,0,1)

Р(0,...,1,0)

РО.... 1,1)

[endif]--Номера функцій та інтерпретацій. Кожній функції надається порядковий номер у вигляді натурального числа, двійковий код якого є стовпцем значень функції в таблиці істинності. Молодшим розрядом вважається самий нижній рядок (значення функції на інтерпретації (1, 1, ..., 1), а старшим - самий верхній (значення функції на інтерпретації (0, 0, .. ., 0).

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

Кожній інтерпретації булевої функції надається номер - значення двійкового коду, який являє . собою інтерпретацію.

Приклад. Найти порядковий номер функції /(х, у), яка приймає наступні значення /(0, 0)=1,/(0, 1)=1,/(1. 0)=0,/(1, 1)=1.

Я*, у)

[endif]--Побудуємо таблицю істинності для цієї функції.

Двійковий код, який відповідає цій функції 110І2 = 1 -23-+-1 •2^+1=13ю Таким чином, номер даної функції дорівнює 13.

Означення. Булеві функції /(хих„) і ^(х,, хп) називаються рівними, якщо при будь-якому наборі які підставляються замість х,,хп функції отримують однакові значення, тобто /(аі,ап) = §(а],ап)

Означенняя. Суперпозицією булевих функцій В,ІУі ,у2,--,УІ"'), 8і(Уг> Уі,—,У“2 .

8„(.Ун’У*2’—>уГ") У булеву функцію /(х,,хп) називається така функція, яка отримана в процесі підстановки у функцію/замість змінних хихП функції відповідно, тобто отримується функція

/(£,(У?,У2,~,УіЩ),82(Уі >Уі2>-’У2т*)>•••>£„Ь>.',У*.~,У""))-

Отримана функція залежить від т] +т2 +... + т:і аргументів.

[endif]--![endif]--[endif]--

Доведення. Дійсно, множина всіх наборів булевої функції від п змінних утворена декартовим добутком {0,1}", потужність якого дорівнює 2". Множина всіх булевих функцій від п змінних є множина

відображень {0,1}"->{0,1}, потужність якого дорівнює 22 .Доведено.

Таким чином, булева функція від двох змінних повністю визначена, якщо задано її значення в кожному із чотирьох можливих наборів (22 = 4); булева функція трьох аргументів - в кожному з восьми наборів (23 = 8). Кількість різних можливих булевих функцій від двох аргументів дорівнює 16, від трьох -256.

Функції двох змінних відіграють важливу роль, тому що з них може бути побудована будь-яка булева функція.

/і

Із

І*

[endif]--Загальна таблиця істинності для булевих функцій однієї змінної має вигляд:

Змінних

Змінна у

/і-0

Константа нуль

{2=ХАу=Х&у-Х-у

Кон’юнкція

/з^Х=3>у

Заперечення (інверсія) імплікації

й=х

Повторення X

/з=х<=у

Заперечення оберненої імплікації

/б=У

Повторення у

/7=хФу

Сумування за модулем 2

/в=хуу=х+.у

Диз’юнкція

І9=хіу

Стрілка Пірса-Вебба

/ю=Х<^>У~Х'^у

Еквівалентність

1 Рч

<5,

Заперечення (інверсія у)

/Ь=Х<=У

Обернена іпмлікація

ТіЗ~ X ~—іХ

Заперечення (інверсія х)

(і4=Х^>У

Імплікація

І15=х\у

Штрих Шеффера

ЇЇ <1-1

Константа одиниця

Усього є чотири різних булевих функції від одного аргументу:

/о(х) = 0=ху х- функція, тотожно рівна 0 (тотожний нуль);

/і(х) = х —х-тотожна функція; приймає значення зміннох;

/2(х) = х - функція-заперечення;

/з(х) = 1=хлх - функція, що тотожно рівна 1 (тотожна одиниця).

Перелічимо всі можливі булеві функції від двох аргументів у формі наступної таблиці:[endif]-- Як вже зазначалось, булевих функцій від двох змінних 16, з яких шість є константами або функціями одного аргументу: /\ = 0,Д = х,/в —у,/п ~ У ,/із = х ,/ц = 1. Інші 10 функцій залежать від двох змінних і мають свої загальноприйняті позначення та назви.

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

Приклад. Запис / (хі, Х2, хз) = \/ Р(1,4,7) означає, що функція набуває одиничних значень на

2Г;

Хз

ЯХі. х2, ХЗ)

[endif]--наборах 1,4 і 7. Таку форму запису називають числовою

Означення. Булевим простором називається множина всіх наборів булевих векторів: М= {X}.

Поставимо у взаємно однозначну відповідність елементам хі,Х2,... ,х„ множини X двійкові змінні, що позначаються тими самим літерами хі,Х2,...,х„, але набувають значень із множини {0,1}, а у відповідність елементам булевого простору М поставимо набори змінних, вважаючи, що змінна х, набуває значення 1 в деякому наборі, якщо елемент х, множини X належить відповідному простору М і набуває значення 0 в іншому випадку.

Таким чином, упорядковану сукупність двійкових змінних хі,Х2,... ,х„ можна розглядати як деякий змінний вектор Х= (хі,Х2,... ,х„), що набуває значення з множини М усіх сталих и-компонентних булевих векторів. Сукупність значень вектора X, на яких булева функція набуває значення 1, позначимо через Мі, а сукупність значень, на яких функція перетворюється на 0, - через Мо. Очевидно, МіиМо = М (для повністю визначеної булевої функції). Безпосередній перелік цих векторів можна здійснити за допомогою булевої матриці, кожний рядок якої задає один з елементів множини М\. Наприклад,

функція/(х/, Х2, хз, х4)= \/ Р(3,6,10) набуває значення 1 на трьох наборах. Булева матриця має вигляд < > cellspacing="0" width="100%"

ІМ1 є х\[endif]--0 10 0 110. 10 10

Властивості функцій алгебри логіки

Означення. Функція /(хі,х%... ,х„) суттєво залежить від змінної х„ якщо існує такий набір значень а\, ..., ащ, Яі+і, ..., а„, щоДаї,..., ви, 0, ві+і, Дві,..., ви, 1, ві+і, ...,ап). В цьому випадку

Хз

х2

Ши х2)

М.Х 1, х2)

[endif]--змінна*, називається суттєвою змінною, інакше х, називають несуттєвою (фіктивною) змінною. Приклад. Нехай булеві функції /ї(*і, хі) таД(*і, *;) задані таблицею істинності:

Для цих функцій змінна х\ - суттєва, а *2 - несуттєва.

Означення. Функції /і та (г називаються рівними, якщо функцію /2 можна одержати з /і додаванням і/або вилученням фіктивних аргументів.

Можна вважати, що коли задано функцію /і, то задано також функцію Д.

Існують два типи функцій, які не мають суттєвих змінних: функція, тотожна 0 (константа 0); функція, тотожна 1 (константа 1).

Константи 1 і 0 можна розглядати як функції порожньої множини змінних.

Властивості диз'юнкції, кон’юнкції й заперечення < >Закон подвійного заперечення х = х. Ідемпотентність X V X V ... VX = X, хх---х = х. Комутативність X V у = у V X, ху = ух. Асоціативність х V (у V г) = (* V у) VI, х(уг) = (х у) 2. Дистрибутивність х(у V г) = ху V Х2, X V у 2 = (х V у)(х V і) . Закони де Моргана ху =х \/у, XV у = ху.1. Закон виключення третього * V * = 1.< >Закон протиріччя XX = 0. Формулисконстантами, 0Vх = х, 1Vх = 1, 0х=0, 1х= х.Додаткові рівносильності:

Х->У = Х V У,

х~у = ху\^ху, х~у=(х=>у)(у=> х), х® у = ху\/ху, х®1=х,

X V у = х®у®ху,

X і у = X V у , х\у = ху,

ху V ху = х, (IV у)(х \/у) = х (закони склеювання),

XV ху = х (закон поглинання).

xуVX2 = xуVX2Vу2 (закон узагальненого склеювання).

Властивості еквівалентності й імплікації такі ж як й в алгебрі висловлювань.

3. Двоїстість. Принцип двоїстості

Означення. Нехай /(х,,х2,...,хп) - булева функція. Тоді функція

/\хі,х2,...,хп) = /(х1,х2,...,х„)

називається двоїстою функцією до/

Якщо в таблиці істинності булевої функції/ інвертувати всі значення, то отримана таблиця буде таблицею істинності двоїстої функції/ .

Таким чином можна визначити двоїсту функцію до будь-якої булевої функції.

Наведемо приклади інших двоїстих функцій: < >функція 0' двоїста 1; функція 1 двоїста 0; функція кон’юнкції двоїста диз’юнкції; cellspacing="0" width="100%"

/\хих2,...,х„) = /(хих2,...,хп) = р{/,(х

І,х2,...,х„),...,/т(х1,х2,...,х„)]

р\

|/1(х1,х2,...,х„),...,/ш(х1,х2,...,х„)]

[/7(х|,х2,...,х„),...,/т*(х1,х2,..

[endif]-- = Р’\/і(.хх,х2,...,х„),...,/„‘(х,,х2,...,х„)) . Доведено.

Принцип двоїстості встановлює зв’язок між структурами формул, які реалізують пару двоїстих функцій.

Теорема (принцип двоїстості). Нехай Ь={/і, ...,/ш} і £*={/і /т"}. Тоді якщо формула і7 над

базисом Ь реалізує функцію^ то формула р" над базисом Ь*, яка отримана з формули Р заміною функцій /і на двоїсті функції / , реалізує функцію/*.

Доведення. За індукцією по структурі формули Р. Початковий крок: якщо формула Р має вигляд Р=ф{хі,...л), де /еЬ, то формула Р =/(хі;... х„) реалізує функцію / за визначенням. Крок індукції доводиться на основі попередньої теореми.

Наслідок. Якщо формули Рі та Р2 рівносильні, юбто Рі=р2, то також рівносильні формули Р/* та Р]*, тобто Р*=Р2 .

Якщо формула Р містигь лише логічні зв’язки кон’юнкції та диз’юнкції, то для того, щоб отримати двоїсту формулу Р достатньо у формулі Р всюди замінити 0 на 1, 1 - на 0, кон’юнкцію - на диз’юнкцію, диз’юнкцію - на кон’юнкцію.

3. Вираження булевих функцій через кон'юнкцію, диз'юнкцію й заперечення

Лема: Для будь-якої булевої функції /(х,,лл) справедливі наступні формули, які ще називають формулами розкладу по змінній х.

/(*!,*„) = (*, л/(0,Х;, :<■„))

/(*!,*„) = О, V/(0,д:2,x„))л(x1 V/(1,X2,X„))

Теорема: Будь-яку булеву функцію від п аргументів можна податі у вигляді суперпозиції кон’юнкції, диз’юнкції і заперечення, при чому заперечення стоїть біля змінної, а не біля внутрішніх дужок.

Доведення. Доводити методом математичної індукції. Запишемо дану властивість для булевої функції від однієї змінної.

/о=0 = хлх, /}-х, /2=х, /,=1 = хчх.

У даних записах ми використовували тільки операцію кон'юнкції, диз'юнкції й заперечення, тобто для п = 1 наша теорема вірна. Припустимо, що вона вірна й для п = к, тобто кожна булева функція від к змінних виражається у вигляді суперпозиції кон'юнкції, диз'юнкції й заперечення. Доведемо, що дана умова виконується для п = к+ 1.

За умовою попередньої леми ми можемо нашу булеву функцію від к + 1 змінних податі в наступному вигляді: /(хх,хп) = (х^л/{\,хг,хм))у(хх/\/{(),хг,хк+1)). Згідно даного розкладу ми

отримали функції /(1,х2,х4+1),/(0,х2,хі+,), які залежати від к аргументів, і умова теореми для них виконується. Над даними булевими функціями виконуються тільки операції кон’юнкції і диз’юнкції, а заперечення СТОЇТЬ ТІЛЬКИ біля ЗМІННОЇ Хі, тобто умова теореми виконується для булевих функцій при п = к+ І, що і доводить теорему. Доведено.

4. Поліном Жегалкіна

Означення. Кон’юнкт називають монотонним, якщо він не містить заперечення своїх змінних.

Приклад, хлулк.

Означення. Вираз виду кх Фкг ®...®к1, де к„ і = 1,х - монотонні кон’юнкти, який заданий на фіксованій множині значень називається поліномом Жегалкіна. 8 називається довжиною полінома.

Означення. Довільна формула алгебри Жегалкіна, яка має вигляд суми (за модулем 2) кон’юнкцій булевих змінних, називається поліномом Жегалкіна. Якщо у кожний член поліному Жегалкіна кожна - змінна входить один раз та поліном не містить однакових членів, то такий поліном Жегалкіна називається канонічним.

Приклад. ху(Ву®х.

Справедливі наступні рівності:

Г0, якщо к - парне,

" Краз ' Iа’ якщо к- непарне.

(1)

а=1©а

(2)

а(Ь © с) = аЬ® ас

(3)

ачЬ = а®Ь®аЬ

(4)

аVЬ = а®Ь , если аЬ = 0

(5)

сд V а2 V... V ак - а1 ® а2 ©... © ак,

(6)

якщо а, а, = 0 для і = \,к, ] = 1,к, і Ф і.

[endif]-- Методи побудови полінома Жегалкіна

Теорема. Довільна булева функція єдиним чином представляється у вигляді канонічного поліному Жегалкіна. < >Метод исвизначених коефіцієнтів. /{Х,у) = XV у = XV у = Х Лу = (х®ї)(уф\)®\ = х(у®\)®\(у®\)®\ = ху®х®у®\®\ = ху®х®у< >Спеціальні класи булевих функцій /

Означення. Клас називається замкнутім, якщо він разом з усіма своїми формулами містить і будь-яку свою суперпозицію.

Теорема. Класи Ро, Рі, 8, М,Ь є власними, замкнутими. < >Системи булевих функцій. Повнота системи {^л,-,};2) {+л-};3) Ь-,};4){л,-,};5) <=>,-.}; 6) { | } ;7) {4} Повноту даної системи {у,л,-і} доведено в попередній теоремі про вираження булевих функцій, як суперпозиції кон’юнкції, диз’юнкції і заперечення. Виразимо дію V через кон’юнкцію і Ф (сумування за модулем два): хуу=хфуфхлу Попередня Оскільки система {у,л,-і} є повного, виразимо а через V і-1: хлу = х/\у = хму, тобто система {V,-.} є повного. Виразимо V через а XV у = х\/у= тлу, тобто система {а,-і} є повного. Оскільки система {V, є повного, виразимо V через =>: х V у = (х => у) => у. Це доводить, що система {=>, -.} є повного. У повній системі {V,-!} виразимо кожну цю операцію через | : х = х\х, У повній системі {а,-і} виразимо кожну через 4-: х = х-1х, х л у = х І у = (х і х)1 (у І у). Що і доводити повноту системи . Доведено. Застосування булевих функцій до аналізу й синтезу дискретних пристроїв Комбінаційні схеми. У комбінаційних схемах логічний стан виходів елементів залежить тільки від комбінації вхідних сигналів у даний момент часу. До функціональних вузлів комбінаційного типу відносяться суматори, дешифратори, шифратори, мультиплексори і демультиплексори, схеми порівняння (компаратори) і контролю за парністю, кодоперетворювачі. Послідовні схеми. У послідовнісних схемах логічне значення виходів визначають як комбінацією вихідних сигналів, так і станом пам'яті схеми в даний момент часу. До функціональних вузлів послідовнісного типу відносяться регістри, лічильники, генератори чисел і керуючі автомати. На основі типових функціональних вузлів будують різноманітні пристрої комп'ютерів.Аналіз та синтез електронних схем

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

Аналіз електронної схеми проводиться в три етапи: < >) з принципової схеми видаляються всі несуттєві допоміжні елементи, які не впливають на логіку роботи схеми; ) через логічні оператори виражають всі електронні елементи, отримуючи логічне рівняння, яке є моделлю функції, що виконується заданою схемою ; ) будь-яким способом отримують мінімізовану ДНФ і мінімізовану КНФ цього рівняння і тим самим виявляють зайві частини аналізованої схеми, якщо звичайно вони в ній є.Логічні елементи

Розглянемо логічні елементи, що реалізують основні логічні операції.

Назва

Позначення

Булевий

вираз

Найпростішим логічним елементом є інвертор, що виконує функцію заперечення (інверсію).

—

Логічний елемент, що виконує логічне додавання, називається диз'юнктор.

хуу

Логічний елемент, що виконує логічне множення, називається кон'юнктор.

хлу

Інші логічні елементи побудовані з трьох н більш складні логічні пег

зйпростіших базових елементів і виконують )Єтворення інформації.

Логічний елемент І-НЕ виконує логічну функцію штрих Шеффера,

х\у

Логічний елемент АБО-НЕ виконує логічну функцію стрілка Пірса

X Ф у

Логічшій елемент виключне АБО, або сумування за модулем 2

=і

X® у

[endif]-- Сигнал, що вироблений одним логічним елементом, можна подавати на вхід іншого елемента, це дає можливість утворювати ланцюги з окремих логічних елементів - функціональні схеми.

Означення. Функціональна (логічна) схема - це схема, що складається з логічних елементів, яка виконує певну функцію.

Двійковий суматор

Всі числа в ЕОМ зберігаються у двійковій системі числення у пам’яті порозрядно. Додавання у двійковій системі числення здійснюється за правилами: 0+0=0, 0+1=1,1+0=1, 1+1=10.

Згідно даних правил додавання здійснюється методом додавання відповідних розрядів. Коли відбувається переповнення розряду (1+1) елемент переноситься у наступний розряд, тобто процес додавання характеризується двома функціями: 8(х,у), Р(х,у).

8(х,у) - являє собою додавання елементів в одному розряді і запис результату в тому ж розряді.

Р(х,у) - це перенос елементу з одного розряду в інший.

8(х,у)

Р(х,у)

[endif]--Для даних функцій побудуємо таблицю істинності:

За даними з таблиці істинності побудуємо досконалу диз’юнктивну нормальну форму:

8(х,у) = ху\/ ху Р(х,у) = ху

Подамо другу формулу наступним чином.

8(А,В) = А&В\/А&.В=А&В\'А&.В\/А&А\/В8сВ=(А&АуА&В)ч(А&.В\/В&.В)=ТІоЬутм°

функціональну схему.

Однорозрядний двійковий суматор

Хк

м___

\рк-,

рк

[endif]-- При додаванні двох елементів у першому розряді ми додаємо елементи порозрядно, і тільки в деяких випадках здійснюється перенос в інший розряд. Але якщо здійснюється додавання в другому розряді і вище, крім елементів даного розряду, ще може бути елемент, який перенісся при додаванні з попереднього розряду. Тобто наша сума 8к залежить не тільки від елементів хі< і уь які додаються, а і від функції Рі_,(хк_і,ук_і), тобто 8к{хк,ук,Рк_,). Аналогічно Рк{хк,ук,РкА). Для даних функцій будуємо таблицю істинності.

Для даних функцій будуємо досконалі ДНФ.

8(х,у,р) = х' у' рм х' ур'м ху' р'у хур = р{х'у'у ху) V р\х'у Уху*)

8 = (Лч ВчР0)&Р0ч(Л&В&Р0) Функціональна схема

[endif]-- Р(х,у, р) = х' урч ху' Р'У хур V хур V Хур V Хур = ур{х V X) V Хр(у V у') V Ху(р'\/ р)

Побудувавши схему для кожного розряду і здійснивши належне їх з’єднання можна отримати багаторозрядний двійковий суматор.

МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ < >Індекс простоти Скорочена форма Тупикові нормальні форми Карти Карно. Діаграми Вейча Індекс простоти І 1(А) - число символів змінних, які зустрічаються в запису ДНФ. Якщо проаналізувати формули А та В, то можна встановити, що Ь\(А) = 15, а Ь\(В) = 3, тобто функція В є простішою; Ь2(А) - число елементарних кон’юнкцій, що входять у функцію А. Для ДНФ А та В очевидно, що Ь2(А) = 5, а І2(В) = 2, тобто функція В теж є простішою за цим критерієм; ЬЗ(А) - число символів інверсій, які зустрічаються в запису ДНФ. Для ДНФ А та В ІЗ (А) = 7, а ІЗ(В) = 2, тобто функція В за цим критерієм є також простішою. Скорочена форма диз’юнкція будь-якого числа імплікант булевої функції /також є імплікантою цієї функції; будь-яка булева функція / еквівалентна диз’юнкції всіх своїх імплікант; така форма подання булевої функції називається скороченою ДНФ. Тупикові нормальні форми Операції! вилучення елементарних кон’юнкцій. Перехід від А до А' - перетворення, яке здійснюється виключенням елементарних кон’юнкцій АГ, що можливо при А=А'. Операції! вилучення множника, тобто перехід від А до ДНФ вигляду (А'чК') вилученням множника. Це перетворення можливо тільки при А = А' \гК'. Функціїо подають у ДДНФ. Упорядковують ДДНФ (записують співмножники так, щоб було зручно здійснювати перетворення). До ДДНФ застосовують операціїо вилучення елементарних кон’юнкцій, а потім операціїо вилучення співмножників. /

Карти Карно для функцій трьох змінних Р(х,, х2, х3).

000

001

011

010

100

101

пі

110

її

X, Х2 Х3

X, Х2 X,

х, х2 х3

Хх х2 Х3

X, х2 х3

X, Х2 Х3

х1 х2 х3

[endif]-- є

Означення. Диз’юнкція простих імплікант, жодну з яких вилучити не можна, є тупиковою ДНФ заданої булевої функції. Деякі функції мають кілька тупикових форм.

Тупикові форми, що містять найменшу кількість символів, будуть мінімальними.

Теорема. Будь-яка мінімальна ДНФ булевої функції є тупиковою.

Для утворення мінімальної ДНФ досить знайти всі тупикові форми заданої функції і вибрати з них мінімальні. Існує кілька методів пошуку тупикових форм.

4. Карти Карио. Діаграми Вейча

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

Мінімізація забезпечує побудову економічних схем цифрових автоматів. Для мінімізації функцій із числом букв п<, 6 застосовують карти Карно. їх будують у вигляді таблиць з 2" кліток з розміткою рядків і стовпчиків змінними.

Для мінімізації булевих функцій використовують також діаграми Вейча, які аналогічні картам Карно і відрізняються від них способом розмітки замість символів 0 і 1 використовують булеві аргументи - х,, х,, х2 та інші.

Х2

хї

\^3*4

0000

0001

0011

0010

0100

0101

0111

0110

1100

1101

1111

1110

1000

1001

1011

1010

Х4 Х4 Х4

Приклад. Спростити логічний вираз з використанням діаграм Вейча. у = х: А х2 А Х3 V X] А х2 А Х3 V X! Л Х2 А Х3 V X) А Х2 А х3 V Х} А х2 А Х3 Діаграма Вейча згідно заданого виразу буде мати вигляд:[endif]-- Діаграма Вейча для 2- х змінних.

Діаграма Вейча для 3- х змінних.

Х2

по

111

100

010

011

000

хз

хз хз

Діаграма Вейча для 4- х змінних.

Х2 Х2

1100

1101

1001

1000

1110

1111

1011

1010

0110

0111

Ооп

0010

0100

0101

0001

0000

< ■-.... •>

<----------------------- >

4;--------

Спрощений вираз мас вигляд:

У = Х[ А Х2 V X, А Х3 V Х1 А Х3 .

АКСІОМАТИЧНИЙ ПІДХІД < >Формальні системи Фундаментальні властивості формальних теорій Числення висловлень Автоматичне доведення теорем. Метод резолюцій Формальні системиКожне числення Ф (або формальну систему) будемо будувати з використанням наступних понять:

алфавіт, мова, формули, схеми формул, секвенції, аксіоми, схеми аксіом, правила виведення, вивідність, виведення з гіпотез, множина виведених формул.

Нехай а - деяка множина символів, яку називатимемо алфавітом. Найбільш типовими частинами алфавіту а будуть:

а! = {а,Ь,с,...} - пропозиційні змінні (або просто змінні);

аг = {х,у... х],у2,г,,...} - предметні змінні (або просто змінні);

«з = {/*' } - логічні зв’язки;

«4 = {<з0,а|;...} - константні символи;

а5 = {?рР"'} - предикатні символи;

а6 = } - функціональні символи;

а, - {=} - символи рівності;

«8 = - допоміжні символи (дужки).

Означення. Словами в алфавіті о: називаються скінченні впорядковані послідовності символів алфавіту. Кількість символів, що входить в слово, називається довжиною даного слова.

Означення. Добутком слів А і В називається слово АВ, яке отримане дописуванням справа до слова А слова В.

Означення. Слово В називається підсловом слова А, якщо А=СВО, де С і £> - деякі слово, можливо пусті. Якщо І - деякий символ з а і А=СЮ, то говорять про входження символу і в слово А.

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

Виділимо серед всіх слів Ьа деяку множину, елементи якої назвемо формулами. Для опису формул будуть вказуватись правила їх побудови, що носять індукційний характер. А саме, спочатку будуть вказані короткі та прості формули, що називаються атомарними формулами.

Множину формул мови Ьа, що побудовані з допомогою правил Р, позначають РВа .

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

Введемо в користування метасимвол |- , який дозволить формулювати метатвердження про виведення фомул в численні Ф. Якщо Г - деяка скінченна множина формул РЬа, А - деяка формула з РЬа, то вираз виду Г|-ф А будемо в подальшому називати секвенцією. Формули з множини Г називаються гіпотезами або посилками, а формула А - наслідком даної секвенції.

Кожне числення буде визначатись своїми аксіомами і правилами виведення. Для задання числення Ф виділимо деяку множину формул II, яку будемо в подальшому називати аксіомами для числення Ф, з єдиною вимогою, щоб існував ефективний спосіб визначення для будь-якої формули чи є вона аксіомою для Ф чи ні.

Дуже часто задають не самі аксіоми, а схеми аксіом. Схеми аксіом - деякі схеми формул. Конкретна аксіома може бути отримана як варіант відповідної схеми аксіом заміною метасимволів, що позначають формули, конкретними формулами. Схеми аксіом будемо також називати просто аксіомами.

Зазвичай аксіоми поділяються на два види: логічні аксіоми (загальні для цілого класу формальних теорій або систем) та нелогічні (або власні) аксіоми (які визначають специфіку га зміст конкретної теорії або системи).

Основним логічним засобом отримання нових формул у численні є правша виведення.

Правилами виведення називаються вирази виду

Я:

(умови),

де Аи...,Ап і А - деякі формули. Метасимвол Я служить для назви або позначення даного правила. Формули А,,..., Ап називаються посилками правила Я, а формула А - безпосереднім наслідком посилок згідно даного правила Я. В дужках записуються умови при яких можна застосовувати правило Я до формул А,,..., А„. Ця частина правила може бути відсутньою, якщо жодних умов не накладається.

Для задання конкретного числення Ф виділимо деяке множину правил Я, яку будемо надалі називати правилами виведення для числення Ф.

Введемо поняття вивідності з гіпотез Г в числення Ф, де Г - деяка скінченна множина формул. Означення. Вивідністю з гіпотез Г в численні Ф, що задана аксіомами І] і правилами виведення Я, називається скінченна послідовність формул АІ,А2,...,АІІ така, що для кожного ї = 1,2,...,и формула А, є аксіомою з II або отримана з попередніх формул даної послідовності згідно з правил виведення Я (тобто є безпосереднім наслідком попередніх формул).

Означення. Говорять, що формула А вивідна з гіпотез Г в даному численні Ф і позначається через Г|-ф А, якщо існує вивідають з гіпотез Г в Ф, що закінчується даною формулою А.

Деякі загальні властивості виведення в численнях Лема (вивідність гіпотези). Г,А\-ФА Лема (перестановка гіпотез). Наступне правило

Г„А,В,Г2\-ФС

Г|,В,Д,Г2|-ФС

(Справедливе для довільного числення Ф.

Лема (скорочення гіпотез). Наступне правило

Г„Л,Л,Г2|-ФС

г„д,г2|-фс

справедливе для довільного числення Ф.

Лема (розширення гіпотез). Наступне правило

Г|-ФД Г,в|\-фА

справедливе для довільного числення Ф.

Саме числення (формальну систему) Ф(ІІ; Я), яка задана схемами аксіомам і/ і правилами виведення Я, ототожнюється з множиною всіх вивідних формул в Ф. Тобто:

А є Ф(і/ ;Я) тоді і тільки тоді, коли \-фА . < >Фундаментальні властивості формальних теорій множина А символів, які утворюють алфавіт; множина Я слів алфавіту А, які називаються формулами; гіідмножина І! формул, ІІаР, які називаються аксіомами; множина Я відношень Я на множині формул, ЯсР, ЯсЯп+ї, які називаються правилами /

висловлення відносно об’єктів множини М. Це висловлення може бути істинним або хибним (або не мати значення істинності). Якщо відповідне висловлення є істинним, то кажуть, що формула виконується в даній інтерпретації.

Означення. Інтерпретація 1 називається моделлю множини формул ІУ, якщо всі формули цієї множини виконуються в інтерпретації І. Інтерпретація І називається моделлю формальної теорії З, якщо всі теореми цієї теорії виконуються в інтерпретації І (тобто всі формули що виводяться є істинними в даній інтерпретації).

Тепер наведемо означення фундаментальних властивостей формальних теорій (не суперечність, повнота, розв ’язність, незалежність). Наявність або відсутність даних властивостей в певній формальній теорії надає можливість вирішувати, чи є дана теорія практично корисною.

Означення. Формальна теорія 5 називається семантично несуперечливою, якщо жодна її теорема не є суперечністю.

Таким чином, формальна теорія підходить для опису тих множин, які є її моделями. Модель для формальної теорії 5 існує тоді й тільки тоді, коли 5 семантично несуперечлива.

Означення. Формальна теорія 5 називається формально несуперечливою, якщо в ній не виводяться одночасно формули А та А. Теорія 5і формально несуперечлива тоді й тільки тоді, коли вона семантично несуперечлива.

Означення. Нехай множина М є моделлю формальної теорії 5. Формальна теорія 5 називається поєною (або адекватною), якщо кожному істинному висловленню М відповідає теорема теорії 8.

Також розрізнюють повноту у широкому та вузькому сенсі. Теорія є повною у широкому сенсі, якщо довільній формулі А теорії відповідає таке висловлення моделі, яке є або істинне, або хибне. Тоді або А, або А є істинним і має виводитись у формальній теорії, тобто довільна формула А теорії або її заперечення А є теоремою формальної теорії. Теорія, яка одночасно несуперечлива та повна, є максимальною в тому сенсі, що додавання до неї в якості аксіоми довільної формули, яка не є її теоремою, призводить до суперечності теорії. Ця властивість формальних теорій має назву повноти у вузькому сенсі.

Означення. Якщо для множини М існує формальна повна несуперечлива теорія 8, то М називається такою, що формалізується.

Означення. Система аксіом формально несуперечливої теорії 5 називається незалежною, якщо жодна з аксіом не виводиться з решти за правилами виведення теорії 5.

Властивість незалежності системи аксіом не є обов’язковою для формальних теорій, - це питання лаконічності та компактності засобів формальної теорії.

Означення. Формальна теорія 5 називається розв ’язною, якщо існує алгоритм, який для будь-якої формули теорії визначає, чи є ця формула теоремою теорії. Формальна теорія 5 називається напіврозв'явною, якщо існує алгоритм, який для довільної формули А теорії може дати відповідь “так”, якщо А є теоремою теорії, і, можливо, не дати жодної відповіді, якщо Я не є теоремою (тобто алгоритм застосовується не до всіх формул).

Розрізняють: < >формальні теорії нульового порядку (числення висловлень ЧВ і числення секвенцій) формальні теорії першого порядку (числення предикатів ЧП і їх розширення) формальні теорії другого та вищих порядків. Числення висловлень кожна пропозиційне змінна є ПФ; такі ПФ назвемо атомарними; якщо Я та В є ПФ, то Я та Я=>В є ПФ. Я=>(Л=>Я) (Л=>(В=> С)) => ((А => В) => (А => С)) ЯлВ=>Я Ал В.=> В А=>(В=> АлВ) А => А V В (А => С) => ((В => С) => (А V В => С)) (Я=>В)=>((Я=>В)=>Я)І, Я => (Л => Я)

Г2 (Я => (Л => С)) => ((Я => 5) => (Я => С))

ІІ:ЯлЛ=>Я ІІ2ЯлЛ=>Л ІД (Я => В) => ((Я => С) => (Я => В л С))

' III 1Я=>ЯVЛ ІІІ2В=>Я^В ІІІз (Я С) => ((В => С) => (Я V Л => С))

IV: (Я => В) => (В => Я) ІУ2Я=>Я ІУ3Я=>Я.

Єдиним правилом виведення класичного числення висловлень є модус поненс (тобиз ропепз; скорочено МР) - правило, яке дозволяє з формул Я і А => В отримати формулу В. Формула В є безпосереднім наслідком формул Я і Я => В.

У відповідності з загальним визначенням, формальним доведенням в численні висловлень вважається така скінченна послідовність формул Я,,Я2,...,Я„, в якій кожна формула є аксіомою, або безпосереднім наслідком довільних двох попередніх формул. Формула Я називається теоремою в численні висловлень, якщо існує формальне доведення, що закінчується формулою Я; в даному випадку будемо писати |-А. Очевидно, що довільна аксіома доводиться в численні висловлень.

Приклад. Формально довести формулу II -> II. < >Запишемо аксіому Є2, заміна СІ, =11, =11, II2 = II -» V Запишемо аксіому Д з аналогічною заміною Застосуємо правило МР для 1,2 Запишемо аксіому Ь] із заміною II, = Д = Vп->(п->і/) (ьь о,=их=о)< >Застосуємо правішо МР для 3,4 /

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

існує скінченна послідовність формул А,,А2 А„, кожний член якої є або одним з припущень, або

теоремою числення висловлень, або випливає з попередніх членів послідовності за правилом МР.

Теорема (теорема про дедукцію). Для довільних формул А, В і множини формул Г, якщо Ги {А} |-В, то Г |-А=>В.

Метатсореми дедукції (МТГ)). Якщо Г - множина формул, V, В - формули і якщо Г|- V =» В, то

г,и\-в.

Приклад. Довести правило силогізму І], -> II2, (/2 -»• (731 £/3

Доведення. Припущення

1. (7, ->П2

г.и2-*и, < >и, ІІ2 (МР,1,3) г7,->(и2->-н3) і/, П2 ->(73 (МР.1,3) Пі (МР,2,4) cellspacing="0" width="100%"

г|-я-

Теорема про дедукції та принцип приведення до абсурду дозволяють довести вивідність деяких формул без побудови доведення. Ці теореми можна сформулювати у вигляді так званих допустимих

Г,Я|-7?[endif]--

. Дане правило називається[endif]--

Г|-Л => В[endif]-- В">правил доведення. А саме, теорема про дедукцію виглядає так:

“введенням імплікації” Його зміст такий: якщо вірне твердження в посилці правила (чисельнику), то вірне і твердження в його висновку (знаменнику). Принцип приведення до абсурду формується у

Г,Л|-В г, А\-В ,

вигляді такого допустимого правила: 1 г-=—1— (введення заперечення).

гМ

Правило виключення вивідної гіпотези. Правило

Г, а\- В; Г| -А Г|-В

справедливе в ЧВ.

Правила транзитивності. Правила

г|- (А => В); Г|-(В=>С) . Г,Л|-В; Г,В|-С Г|-(Л => С) 1 Г,А\-С

справедливі в ЧВ.

Правила контрапозиції. Правила

Т,А\-В . Т,в\-А

г,в|-л 1 т,а\-в

справедливі в ЧВ.

Розглянемо логічні символи, що служать для скорочення записів формул: (А а В) позначає формулу (А => В);

(А VВ) позначає формулу (А=> В).

Символи кон’юнкції і диз’юнкції використовуються як метасимволи. Теорема. В численні висловлень допустимі наступні правила виведення:

Назва правила

Запис правила дробом

Запис правила

Позначення

Правило введення диз’юнкції

Г | -А Г |-В Г|-Я V В ’ Г|-Л V В

а |-ауЬ Ь |-ачЬ

вд

Правило вилучення диз’юнкції

Г,А\-С Г,В|-С Т,А\/В\-С

а |-с

Ь \-с

то а V Ь |-с

влд

Правило введення кон’юнкції

Г - А Г -В Т\-А л В

а,Ь |-алЬ

вк

Правило вилучення кон’юнкції

Г|- А лВ Г|- А а В Г| -А ’ Г|-В

алЬ |-а алЬ |-Ь

влк

Правило силогізму

г|-А=>В Г|-В=>С Г|-Я=>С

а=>Ь Ь=> с то а => с

ПС

Правило перестановки посилок

Г|- А =>(В => С) Г|-В => (А => С)

а=>(Ь=> с) \- Ь^(а=> с)

ппе

Правило об’єднання посилок

Г|- А =>(В => С) Г|-Я а В => С

а=>(Ь=> с) |- аЬ => с

оп

Правило роз’єднання посилок

Г|-ЯлВ=>С г|-^ => (в С)

аЬ=>с\-

а=>(Ь=>с)

РП

Правило композиції

г|-л=>в г|-л=>с Г|-Я => В а с

а=>Ь а=> с І- а => Ьс

гас

Вилучення заперечення

т,а\-в г,а\-в

Т\-А

а \-Ь а (-Ь

то |-а

вз

Теорема тавтології (ТТ). Множина теорем числення висловлень співпадає з множиною тавтологій.

На практиці найчастіше використовується такий наслідок:

Наслідок. Якщо {Аі,..., А„} ^ А та |-Аі,..., |-А„, то |-А.

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

Із теореми тавтологій безпосередньо випливає: < >розв'язність числення висловлень: множина теорем числення висловлень алгоритмічно розв ’язна відносно множини всіх пропозиційних формул. несуперечливість: не існує про позиційної формули А такої, що \-А та |- А. Автоматичне доведення теорем. Метод резолюційА], Аг, ...,А„ |-В.

Даний вираз можна прочитати наступним чином: якщо посилки Я і, Аг, ...,А„ істинні, то істинний і висновок В.

Проблема виведення в логіці полягає в тому, щоб встановити чи істинна формула В, якщо формули істинні А\, Аг, ..., А„. В загальному випадку такий алгоритм неможливо побудувати, але в деяких випадках такі алгоритми існують. Доведення теореми рівносильно доведенню загальнозначущості деякої формули. Найбільш ефективне доведення загальнозначущості формул здійснюється методом резолюцій. Процедура пошуку доведення методом резолюцій фактично є процедурою пошуку спростування, тобто замість доведення загальнозначущості формули доводять, що заперечення формули суперечливе: А = 1 о А = 0.

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

Означення. Літерами будемо називати вирази А або А .

Означення. Літери А і А називають контрарними, а множину {А, А) - контрарною парою.

Диз ’юнкт - це диз’юнкція літер.

Означення. Диз’юнкт називається порожнім (позначається #), якщо він не містить літер. Порожній диз’юнкт завжди хибний, оскільки в ньому нема літер, які могли б бути істинними при будь-яких наборах змінних.

Правилом резолюцій називається наступне правило виведення:

А у В, АуС ВуС

Дане правило[endif]-- Розглянемо застосування методу резолюцій до числення висловлень.

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

АуВ, АуС |- ВуС.

Приклад. Довести правило резолюцій, використавши рівносильності логіки:[endif]-- (АуВ)/\ (АуС) => (ВуС) = (АуВ)л(АуС) у(ВуС) = (А у В) у. (АуС)у (В у С) = АлВ у АлС у (В у С) = (Ау А) л (АуС)а (Ву А) л (ВуС) у (В у С) = (АуС)л (Ву А) л (ВуС) у (В у С)

-(А у С у В у С) л (В у А у В у С) л (В уС у В у С) = 1.

Отже, при істинних посилках істинний висновок. Доведено.

Означення. Диз’юнкт ВуС називається резольвентою для диз’юнктів А у В і АуС за літерою А:

ВуС= гєза(Ау В і АуС).

Якщо диз’юнкт не містить контрарних літер,-то резольвенти для них не існує. Для диз’юнктів А і А резольвентою є порожній диз’юнкт: гезЛ( А, А )= #.

Приклад. Нехай Р = А у В у С, О = А у В у О.

Тоді резольвентою

гезДР, С) = Ву Су В у О. гевц(Р, <Д)= Ау Су А у й.

ГЄ8с{Р, О) не існує.

Метод резолюцій відповідає методу доведення від супротивного. Дійсно, умова Ап (- В

рівносильна умові А1,Л2,...,Ап, В (-#.

Алгоритм побудови виведення методом резолюцій.

Крок 1. Побудувати кон’юкцію множини гіпотез А1,А2,...,Ап і заперечення висновку В; звести формулу А1 лЛ^ л...лЛп лВ доКНФ.

Крок 2. Побудувати множину 5 диз’юнктів з отриманої КНФ.

Крок 3. Замість пари диз’юнктів, що містить контрарні літери записати їх резольвенту за правилом резолюцій.

Крок 4. Продовжувати процес. Якщо він закінчується порожній диз’юнктом, то висновок обґрунтований.

Викладений алгоритм називається резолютивним висновком з 5.

Можливі три випадки: < >Серед множини диз’юнктів нема тих, що містять контрарні літери. Це означає, що формула В не виводиться з множини формул АІ,А2,..., Лп. В результаті наступного застосування правила резолюцій отриманий порожній диз’юнкт. Це означає, що формула В виводиться з множини А1,А2,...,Ап. Процес зациклюється, тобто отримуються все нові і нові резольвенти, серед яких нема порожніх. Це нічого не означає. А_ ' АуВ. В. В. (1,2) #.(3,4) /

ЛОГІКА ПРЕДИКАТІВ < >Поняття предиката. Формули логіки предикатів. Загальнозначущі формули логіки предикатів Випереджена нормальна форма1. Поняття предиката Формули логіки предикатів. Загальнозначущі формули логіки

предикатів

Внутрішню структуру висловлень можна розділити на суб’єкт та предикат, де суб’єктом є підмет, а предикат визначає властивість суб’єкта. Наприклад, у висловленні «Соркат - це людина» Сократ - це суб’єкт, який має властивість бути людиною. Ця властивість представляє собою одномісний предикат, визначений на множині людей: “бути людиною”. Позначимо його Р(х), де х - змінна. Підставляючи на місце змінної х об’єкти з області визначення предиката, отримуємо висловлення. Таким чином, одномісний предикат, визначений на деякій множині об’єктів, задає властивість, якою ці об’єкти можуть володіти чи не володіти. Отже, предикат розбиває цю множину на дві області: область істинності та хибності.

Означення. Одномісним предикатом Р(х'), визначеним на множині М, називається вираз, який після підстановки в нього замість х об’єкта з області визначення М, перетворюється у висловлення. Область визначення предиката називається предметною областю. Елементи з області визначення називаються предметними константами. Змінна, від якої залежить предикат, називається предметною змінною.

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

Означення. И-місним предикатом, визначеним на множинах Мі,...,Мл, називається вираз, який перетворюється у висловлення після заміни кожної предметної змінної на елемент з її області визначення. Якщо всі змінні визначені на одній та й самій множині, то предикат називається однорідним.

Отже предикат можна розглядати як функцію, що відображає множину (або декартовий добуток множин) об’єктів на множину {Т, Р}. Таким чином, над предикатами визначено всі булеві операції, а також дві нові операції - квантори: V- квантор загальності та 3- квантор існування.

Якщо Р(х) означає деяку властивість на множині М, то формула УхР(х) означає висловлення: “для будь-якого предмету шєМ виконується властивість Р(х)” або “всі х мають властивість Р(х)". Формула \/хР(х) набуває значення “істина”, коли властивість Р виконується для всіх об’єктів з А/, та набуває значення “хибність” у протилежному випадку, тобто коли існує хоча б один об’єкт з множини М, для якого ця властивість не виконується.

Формула 3хР(х) означає: “існує принаймні один предмет х, який має властивість Р» або «деякі х мають властивість Р». Значення формули ЗхР(х) є істинним, коли властивість Р виконується хоча б дам одного об’єкту з множини М, та хибним, коли не існує жодного об’єкта, для якого ця властивість виконувалась би.

Означення. Формула, на яку розповсюджується дія квантора, називається областю дії квантора. Змінна, за якою “навішується” квантор та яка попадає в його область дії, називається зв'язаною змінною. Змінна, яка лежить за межами області дії квантора, називається вільною змінною.

Означення. Формула, що не містить вільних змінних, називається замкненою.

Замкнуті формули є висловленнями.

Означення. Предикат Р(х), визначений на множині М, називається тотожньо-істинним, якщо його множина істинності збігається з областю визначення.

Означення. Предикат Р(х), визначений на множині М, називається тотожньо-хибним, якщо його множина істинності є порожньою множиною.

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

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

Означення формули логіки предикатів: < >нуль-міский предикат е формулою логіки предикатів. якщо Р" - п-місний предикат, то Р"(х,хп) є формулою логіки предикатів, в якій ЗМІННІ X,... ,Х„ € вільними. якщо Р є формулою логіки предикатів, то Р € теж формулою логіки предикатів, при чому вільні змінні формули Р будуть вільними у формулі Р і зв’язані змінні формули Р будуть зв’язаними у формулі Р . якщо Ці і 0 формули логіки предикатів, то 0 А0, 0У0, £/,<->0, теж є якщо II - формула логіки предикатів, х - вільна змінна даної формули, то наступні вирази Ух II(х) і Зх II(х) теж будуть формулами логіки предикатів, причому х буде зв’язаною змінною. Якщо формула II містила крім х інші змінні, то вони залишаться вільними або зв’язаними в залежності від того, які вони е у даній формулі. інших формул, крім перелічених вище, не існує.Загальнозначущі формули логіки предикатів< >якщо в тавтології алгебри висловлень замість змінних поставити предикат, то ми отримаємо формулу логіки предикатів, яка буде загальнозначущою. закони де МорганаУхР(х) <-> 3хй{х)

ЗхР(х)*+УхО(х) < >закони вираження одного квантора через інший УхО{х)<^Зхй{х)ЗхІІ{х) <-► УхО(х)< >закони перенесення кванторів через д і V Ух(Р(х) А £(*)) <-* (УхР(*)) А (^хд(.т))Ух{Р(х) V 0 (УхР(х)) V (2

3*(Р(х)м0<->(3*/Ч*))^ < >закон перенесення кванторів через імплікацію Ух(Р(х) -> 0 <-> (ЗхДх)) -> 0Зх{Р{х) ->0^ (УхР(х)) -х 0 Ух(0 -> Р(х)) <-» О -»(УхР(х))

3х(0 -> Р(х)) о• £> -> (3хР(х)) < >закони знищення квантора узагальнення і введення квантора існування /

(УхР(х)) -> Р(у)

Р(у)^(ЗхР(х)) < >закони комутативності Ух\/уР(х, у) <г+ УуУлР(дг, у)ЗхЗуР(х, у) <-» ЗуЗхР(х, у)

Зх'іуР{х,у) Зу\/хР(х,у)

Означення. Множина предметних змінних 7} = {х,у,г,...} , предметних сталих Г2 = {а,В,с,...}, функціональних символів Г3 = і предикатів Г4 = |р1',р2у,р34,...|, Г = {7],7’2,7’3,7’4} разом з

множиною логічних операцій р = {-і, л, V, <->, V, 3} утворюють алгебру предикатів.

Деякі правила запису складних формул алгебри предикатів. < >логічні зв’язки л і V після розстановки дужок зв’язують ті елементи формули предикатів, які стоять безпосередньо біля логічного зв’язку. пріоритет операцій ->,л,у,-»,<-» за квантором V частіше всього іде оператор =>, за квантором 3 - л. якщо формула містить підформулу, то внутрішня формула не повинна містити квантора, що зв’язує змінну, яка вже є зв’язаною квантором загальної формули. всі предметні змінні і сталі повинні бути визначені на одній множині. якщо у формулі задані загальні квантори 3 і V, то квантор 3 записується лівіше квантора V.Основні закони алгебри предикатів< >закон комутативності закон дистрибутивності закон ідемпотентностіКх Р(х,у)\/ Кх Р(х,у) = Кх Р(х,у)

Кх Р(х,у)лКх Р(х,у)= Кх Р(х,у), Вє{3,\/} < >закон виключеного третього Кх Р{х,у) V Кх Р(х,у) = 1 закон протиріччяЯх Р(х, у)лКх Р(х, у) = 0< >закони де Моргана закон доповнення Кх Р{х,у) = Кх Р{х,у) властивості константи Кх Р(х, у) л 1 = Кх Р(х,у)Кх Р(х,у)л 0 = 0 КхР{х,у)у 1 = 1

Кх Р(х, у)\/0-Кх Р(х, у)

2. Випереджена нормальна форма

Означення. Формула логіки предикатів називається зведеною, якщо вона містить тільки наступні логічні операції алгебри висловлювань: -і,л,у.

Приклад. Ут (Р(х) V (Дх)) є зведеною.

Означення. Формула логіки предикатів називається відкритою, якщо вона не містить кванторів. Зведена формула логіки предикатів знаходиться у випередженій нормальній формі, якщо вона має вигляд

де В - відкрита формула логіки предикатів, £3 - квантор є {У,3}

Теорема. Будь-яку формулу логіки предикатів можна подати у випередженій нормальній формі. Доведення.

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

При т = 0 ми отримуємо нуль-місний предикат або предикатну формулу без операцій. Для даного предиката можна сказати, що він знаходиться у випередженій нормальній формі.

Припустимо, що дана теорема виконується при т-п-1. Доведемо, що вона справедлива для т-п. Нехай и, Vі,1}2 - формули логіки предикатів, які подані у випередженій нормальній формі з кількістю логічних операцій п-1. Додамо ще по одній операції, щоб отримати кількість п. Ми отримаємо вирази: О, 1/,лї/2, П, уП2, <2(17).

а) Р = 1]. Так як 17 - можна подати у випередженій нормальній формі, то

17 = 2г12<2"-0с,('®Х Р = У = С?*і6*2-йотС®) ■ Отримана формула Р подана у випередженій нормальній формі.

б) 17, л 17 2 = Р. В даному випадку виконується спрощення отриманого виразу за допомогою основних законів логіки предикатів (закони перенесення кванторів через л, V, закони комутативності). При необхідності здійснюється заміна змінних, оскільки у даних формулах можуть бути і зв’язані і незв’язані змінні. Виконавши наступну послідовність рівносильних дій ми прийдемо до випередженої нормальної форми.

в) 17, V17 2 = Р. Даний випадок аналогічний до попереднього.

г) £?(£/) = Р. Введення ще одного квантора не порушує випередженості нормальної форми. Згідно методу математичної індукції теорема доведена. Доведено.

Означення. Формула <У* називається двоїстою до формули 17, якщо її можна отримати з формули V заміною л,у,У,3 на V,л,3,V відповідно. З означення випливає (V ) =11.

іуПерший закон двоїстості.

Якщо'(/(*,,х„) = В(х,,хп), то І7'(х„хг) = В'(х1гхг). < >Другий закон двоїстості. Третій закон двоїстості.ЛОГІКИ ПЕРШОГО ПОРЯДКУ< >Мова першого порядку Числення предикатів1. Мова першого порядку

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

Алфавіт класичної мови першого порядку складається з таких символів: < >предметні імена (змінні)х,у, 2, ... функціональні символи/0,/;,/2, ... предикатні символиро, рі, Р2, ■■■ символи логічних операцій -і, => та Ух. кожне предметна змінна та кожна константа є термом; такі терми назвемо атомарними; якщо її,..., Іп - терми, /- н-арний функціональний символ, то/і\ ..Іп - терм. кожна атомарна формула є формулою; якщо Р та О - формули, то Р та Р=РЗ - формули; якщо Р - формула, х - предметна змінна, то МхР - формула. варіанти мови одної сигнатури, що відрізняються наборами символів логічних операцій та способами запису термів і формул; істотно різні мови, що відрізняються сигнатурами.Приклади мов 1-го порядку

Наведемо кілька прикладів мов 1-го порядку.

Приклад. Мова арифметики Ьаг визначається сигнатурою £2ОГ={0, 1, +, х, =}, де 0 та 1 - константні символи, + та х - бінарні функціональні символи, = - бінарний предикатний символ.

Терм мови арифметики назвемо арифметичним термом.

Формулу мови арифметики назвемо арифметичною формулою.

Наприклад, 1+1 - замкнений арифметичний терм; хх(у+г) - арифметичний терм; Зг(х+г=у) - арифметична формула.

Приклад. Мова теорії множин Ь!е, визначається сигнатурою П5(.,={є, =), де є та = - бінарні предикатні символи.

Наприклад, гєх - атомарна формула, Уг(2єл:->2єу) - формула, ЗхЗу(у є х) - замкнена формула мови Ь!е,. Зауважимо, що останні дві формули відповідно означають "хсу" та "існує 0".

2. Числення предикатів

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

Означення. Числення предикатів (теорія першого порядку) - це аксіоматична теорія, символами якої є: < >пропозиційні зв’язки , =>; квантор загальності V; допоміжні символи: кома та дужки “(“, предметні змінніх,у,...; предметні константи а, функціональні СИМВОЛИ предикатні символи ро, рирі,...Власні аксіоми формулюються окремо для кожної конкретної предметної області. В ЧП два правила виведення:

юр:[endif]--А,(А => В)

ОЕ№ введення V:[endif]--В => А(х)

------ (х не входить вільно в В).

В=>МхА(х)

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

Моделлю теорії першого порядку називається довільна інтерпретація, в якій істинні всі аксіоми даної теорії. Якщо правила виведення МР та Оеп застосовуються до істинних в даній інтерпретації формул, то результатом є формули, які також істинні в тій самій інтерпретації. Множина формул, які виводяться за правилами виведення з аксіом теорії, є теоремами даної теорії.

Г,А\-В Г|-<А=>В)[endif]--В) ">

справедливе для ЧП.[endif]--Теорема про дедукцію: Правило

Вільні входження предметних змінних в формулу або терм можна замінювати термами. Позначимо Р х [1\,..., і„\ формулу, отриману із формули Р заміною всіх вільних входжень змінних хі, хп на терми її,..., Іп відповідно. Аналогічно визначаємо терм А,, [<і {п]

При заміні вільних входжень предметних змінних термами можливі колізії, коли вільна змінна стає зв’язаною. Наприклад, нехай Р - це формула Зг(х+г=у). Тоді Рх[и\ - це формула Зг(и+г=уУ, Рх[г\ - це формула 3г(г+г=у); отже, маємо колізію.

Звідси терм І допустимий для заміни вільної змінної х в формулі Р, якщо І не лежить в області дії ніякого квантора по деякій змінній, яке входить до складу І.

Мови першого порядку використовуються для запису математичних тверджень, при цьому для кожної конкретної області математики (математичної теорії) вибирають мову з необхідною сигнатурою.

[1] Булеві функції від п аргументів

Булеві функції належать до класу двозначних однорідних функцій. Це найпростіший і водночас найважливіший клас однорідних функцій, що використовуються для опису скінченних автоматів та ЕОМ. Останні, у свою чергу, призначаються для опрацювання дискретної інформації. Як модель засобів опрацювання застосовується поняття автомата.

І хоча символи 0 та 1, елементи булевої алгебри, є абстрактними, зручніше розглядати булеву алгебру як таку, що оперує висловлюваннями.

Означення. Булевою функцією від одного аргументу називається функція, яка задана на множині двох елементів і приймає значення в цій же множині двох елементів. Елементи двохелементної множини будемо позначати 0 й 1. У такий спосіб /{0, 1}.

![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--![endif]--